CodeExtractor.cpp revision ffada9327301094411146627cf6bc16cd517585d
1e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman//===- CodeExtractor.cpp - Pull code region into a new function -----------===// 2e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// 3e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// The LLVM Compiler Infrastructure 4e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// 5e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// This file was developed by the LLVM research group and is distributed under 6e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// the University of Illinois Open Source License. See LICENSE.TXT for details. 7e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// 8e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman//===----------------------------------------------------------------------===// 9e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// 10e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// This file implements the interface to tear out a code region, such as an 11e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// individual loop or a parallel section, into a new function, replacing it with 12e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// a call to the new function. 13e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// 14e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman//===----------------------------------------------------------------------===// 15e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 16e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/BasicBlock.h" 17e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Constants.h" 18e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/DerivedTypes.h" 19e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Instructions.h" 20e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Module.h" 21e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Pass.h" 22e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Analysis/LoopInfo.h" 23ffada9327301094411146627cf6bc16cd517585dChris Lattner#include "llvm/Analysis/Verifier.h" 24e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 25e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Transforms/Utils/FunctionUtils.h" 26e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "Support/Debug.h" 27e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "Support/StringExtras.h" 28e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include <algorithm> 29e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include <map> 30e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include <vector> 31e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanusing namespace llvm; 32e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 33e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmannamespace { 34e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 35e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inline bool contains(const std::vector<BasicBlock*> &V, const BasicBlock *BB){ 36e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return std::find(V.begin(), V.end(), BB) != V.end(); 37e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 38e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 39e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman /// getFunctionArg - Return a pointer to F's ARGNOth argument. 40e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman /// 41e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Argument *getFunctionArg(Function *F, unsigned argno) { 42e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function::aiterator ai = F->abegin(); 43e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman while (argno) { ++ai; --argno; } 44e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return &*ai; 45e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 46e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 47e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman struct CodeExtractor { 48e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman typedef std::vector<Value*> Values; 49e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman typedef std::vector<std::pair<unsigned, unsigned> > PhiValChangesTy; 50e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman typedef std::map<PHINode*, PhiValChangesTy> PhiVal2ArgTy; 51e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiVal2ArgTy PhiVal2Arg; 52e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 53e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman public: 54e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *ExtractCodeRegion(const std::vector<BasicBlock*> &code); 55e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 56e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman private: 57e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void findInputsOutputs(const std::vector<BasicBlock*> &code, 58e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 59e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &outputs, 60e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 61e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode); 62e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 63e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void processPhiNodeInputs(PHINode *Phi, 64e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const std::vector<BasicBlock*> &code, 65e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 66e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 67e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode); 68e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 69e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void rewritePhiNodes(Function *F, BasicBlock *newFuncRoot); 70e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 71e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *constructFunction(const Values &inputs, 72e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Values &outputs, 73e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, BasicBlock *newHeader, 74e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const std::vector<BasicBlock*> &code, 75e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction, Module *M); 76e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 77e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void moveCodeToFunction(const std::vector<BasicBlock*> &code, 78e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *newFunction); 79e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 80e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void emitCallAndSwitchStatement(Function *newFunction, 81e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 82e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const std::vector<BasicBlock*> &code, 83e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 84e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &outputs); 85e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 86e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman }; 87e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 88e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 89e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanvoid CodeExtractor::processPhiNodeInputs(PHINode *Phi, 90e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const std::vector<BasicBlock*> &code, 91e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 92e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *codeReplacer, 93e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newFuncRoot) 94e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman{ 95e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Separate incoming values and BasicBlocks as internal/external. We ignore 96e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // the case where both the value and BasicBlock are internal, because we don't 97e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // need to do a thing. 98e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<unsigned> EValEBB; 99e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<unsigned> EValIBB; 100e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<unsigned> IValEBB; 101e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 102e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 103e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Value *phiVal = Phi->getIncomingValue(i); 104e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (Instruction *Inst = dyn_cast<Instruction>(phiVal)) { 105e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (contains(code, Inst->getParent())) { 106e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (!contains(code, Phi->getIncomingBlock(i))) 107e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman IValEBB.push_back(i); 108e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 109e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (contains(code, Phi->getIncomingBlock(i))) 110e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman EValIBB.push_back(i); 111e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman else 112e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman EValEBB.push_back(i); 113e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 114e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else if (Constant *Const = dyn_cast<Constant>(phiVal)) { 115e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Constants are internal, but considered `external' if they are coming 116e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // from an external block. 117e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (!contains(code, Phi->getIncomingBlock(i))) 118e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman EValEBB.push_back(i); 119e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else if (Argument *Arg = dyn_cast<Argument>(phiVal)) { 120e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // arguments are external 121e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (contains(code, Phi->getIncomingBlock(i))) 122e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman EValIBB.push_back(i); 123e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman else 124e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman EValEBB.push_back(i); 125e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 126e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman phiVal->dump(); 127e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman assert(0 && "Unhandled input in a Phi node"); 128e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 129e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 130e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 131e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Both value and block are external. Need to group all of 132e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // these, have an external phi, pass the result as an 133e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // argument, and have THIS phi use that result. 134e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (EValEBB.size() > 0) { 135e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (EValEBB.size() == 1) { 136e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Now if it's coming from the newFuncRoot, it's that funky input 137e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman unsigned phiIdx = EValEBB[0]; 138e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (!dyn_cast<Constant>(Phi->getIncomingValue(phiIdx))) 139e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 140e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiVal2Arg[Phi].push_back(std::make_pair(phiIdx, inputs.size())); 141e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // We can just pass this value in as argument 142e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inputs.push_back(Phi->getIncomingValue(phiIdx)); 143e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 144e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Phi->setIncomingBlock(phiIdx, newFuncRoot); 145e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 146e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PHINode *externalPhi = new PHINode(Phi->getType(), "extPhi"); 147e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman codeReplacer->getInstList().insert(codeReplacer->begin(), externalPhi); 148e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<unsigned>::iterator i = EValEBB.begin(), 149e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = EValEBB.end(); i != e; ++i) 150e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 151e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman externalPhi->addIncoming(Phi->getIncomingValue(*i), 152e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Phi->getIncomingBlock(*i)); 153e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 154e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // We make these values invalid instead of deleting them because that 155e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // would shift the indices of other values... The fixPhiNodes should 156e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // clean these phi nodes up later. 157e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Phi->setIncomingValue(*i, 0); 158e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Phi->setIncomingBlock(*i, 0); 159e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 160e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiVal2Arg[Phi].push_back(std::make_pair(Phi->getNumIncomingValues(), 161e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inputs.size())); 162e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // We can just pass this value in as argument 163e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inputs.push_back(externalPhi); 164e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 165e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 166e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 167e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // When the value is external, but block internal... 168e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // just pass it in as argument, no change to phi node 169e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<unsigned>::iterator i = EValIBB.begin(), 170e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = EValIBB.end(); i != e; ++i) 171e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 172e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // rewrite the phi input node to be an argument 173e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiVal2Arg[Phi].push_back(std::make_pair(*i, inputs.size())); 174e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inputs.push_back(Phi->getIncomingValue(*i)); 175e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 176e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 177e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Value internal, block external 178e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // this can happen if we are extracting a part of a loop 179e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<unsigned>::iterator i = IValEBB.begin(), 180e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = IValEBB.end(); i != e; ++i) 181e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 182e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman assert(0 && "Cannot (YET) handle internal values via external blocks"); 183e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 184e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 185e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 186e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 187e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanvoid CodeExtractor::findInputsOutputs(const std::vector<BasicBlock*> &code, 188e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 189e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &outputs, 190e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 191e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode) 192e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman{ 193e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<BasicBlock*>::const_iterator ci = code.begin(), 194e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman ce = code.end(); ci != ce; ++ci) { 195e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *BB = *ci; 196e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (BasicBlock::iterator BBi = BB->begin(), BBe = BB->end(); 197e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BBi != BBe; ++BBi) { 198e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // If a use is defined outside the region, it's an input. 199e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // If a def is used outside the region, it's an output. 200e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (Instruction *I = dyn_cast<Instruction>(&*BBi)) { 201e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // If it's a phi node 202e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (PHINode *Phi = dyn_cast<PHINode>(I)) { 203e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman processPhiNodeInputs(Phi, code, inputs, newHeader, newRootNode); 204e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 205e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // All other instructions go through the generic input finder 206e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Loop over the operands of each instruction (inputs) 207e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (User::op_iterator op = I->op_begin(), opE = I->op_end(); 208e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman op != opE; ++op) { 209e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (Instruction *opI = dyn_cast<Instruction>(op->get())) { 210e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Check if definition of this operand is within the loop 211e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (!contains(code, opI->getParent())) { 212e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // add this operand to the inputs 213e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inputs.push_back(opI); 214e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 215e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 216e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 217e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 218e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 219e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Consider uses of this instruction (outputs) 220e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Value::use_iterator use = I->use_begin(), useE = I->use_end(); 221e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman use != useE; ++use) { 222e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (Instruction* inst = dyn_cast<Instruction>(*use)) { 223e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (!contains(code, inst->getParent())) { 224e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // add this op to the outputs 225e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman outputs.push_back(I); 226e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 227e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 228e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 229e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } /* if */ 230e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } /* for: insts */ 231e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } /* for: basic blocks */ 232e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 233e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 234e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanvoid CodeExtractor::rewritePhiNodes(Function *F, 235e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newFuncRoot) { 236e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Write any changes that were saved before: use function arguments as inputs 237e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (PhiVal2ArgTy::iterator i = PhiVal2Arg.begin(), e = PhiVal2Arg.end(); 238e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman i != e; ++i) 239e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 240e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PHINode *phi = (*i).first; 241e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiValChangesTy &values = (*i).second; 242e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (unsigned cIdx = 0, ce = values.size(); cIdx != ce; ++cIdx) 243e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 244e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman unsigned phiValueIdx = values[cIdx].first, argNum = values[cIdx].second; 245e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (phiValueIdx < phi->getNumIncomingValues()) 246e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman phi->setIncomingValue(phiValueIdx, getFunctionArg(F, argNum)); 247e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman else 248e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman phi->addIncoming(getFunctionArg(F, argNum), newFuncRoot); 249e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 250e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 251e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 252e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Delete any invalid Phi node inputs that were marked as NULL previously 253e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (PhiVal2ArgTy::iterator i = PhiVal2Arg.begin(), e = PhiVal2Arg.end(); 254e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman i != e; ++i) 255e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 256e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PHINode *phi = (*i).first; 257e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (unsigned idx = 0, end = phi->getNumIncomingValues(); idx != end; ++idx) 258e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 259e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (phi->getIncomingValue(idx) == 0 && phi->getIncomingBlock(idx) == 0) { 260e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman phi->removeIncomingValue(idx); 261e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman --idx; 262e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman --end; 263e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 264e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 265e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 266e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 267e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // We are done with the saved values 268e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiVal2Arg.clear(); 269e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 270e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 271e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 272e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// constructFunction - make a function based on inputs and outputs, as follows: 273e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// f(in0, ..., inN, out0, ..., outN) 274e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 275e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanFunction *CodeExtractor::constructFunction(const Values &inputs, 276e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Values &outputs, 277e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, 278e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 279e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const std::vector<BasicBlock*> &code, 280e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction, Module *M) { 281e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "inputs: " << inputs.size() << "\n"); 282e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "outputs: " << outputs.size() << "\n"); 283e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *header = code[0]; 284e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 285e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This function returns unsigned, outputs will go back by reference. 286e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Type *retTy = Type::UShortTy; 287e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<const Type*> paramTy; 288e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 289e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Add the types of the input values to the function's argument list 290e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Values::const_iterator i = inputs.begin(), 291e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = inputs.end(); i != e; ++i) { 292e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Value *value = *i; 293e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "value used in func: " << value << "\n"); 294e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman paramTy.push_back(value->getType()); 295e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 296e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 297e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Add the types of the output values to the function's argument list, but 298e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // make them pointer types for scalars 299e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Values::const_iterator i = outputs.begin(), 300e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = outputs.end(); i != e; ++i) { 301e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Value *value = *i; 302e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "instr used in func: " << value << "\n"); 303e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Type *valueType = value->getType(); 304e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Convert scalar types into a pointer of that type 305e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (valueType->isPrimitiveType()) { 306e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman valueType = PointerType::get(valueType); 307e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 308e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman paramTy.push_back(valueType); 309e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 310e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 311e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "Function type: " << retTy << " f("); 312e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<const Type*>::iterator i = paramTy.begin(), 313e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = paramTy.end(); i != e; ++i) 314e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << (*i) << ", "); 315e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << ")\n"); 316e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 317e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const FunctionType *funcType = FunctionType::get(retTy, paramTy, false); 318e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 319e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Create the new function 320e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *newFunction = new Function(funcType, 321e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman GlobalValue::InternalLinkage, 322e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman oldFunction->getName() + "_code", M); 323e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newFunction->getBasicBlockList().push_back(newRootNode); 324e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 325e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 326e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(inputs[i]->use_begin(), inputs[i]->use_end()); 327e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<User*>::iterator use = Users.begin(), useE = Users.end(); 328ffada9327301094411146627cf6bc16cd517585dChris Lattner use != useE; ++use) 329ffada9327301094411146627cf6bc16cd517585dChris Lattner if (Instruction* inst = dyn_cast<Instruction>(*use)) 330ffada9327301094411146627cf6bc16cd517585dChris Lattner if (contains(code, inst->getParent())) 331e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inst->replaceUsesOfWith(inputs[i], getFunctionArg(newFunction, i)); 332e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 333e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 334e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Rewrite branches to basic blocks outside of the loop to new dummy blocks 335e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // within the new function. This must be done before we lose track of which 336e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // blocks were originally in the code region. 337e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(header->use_begin(), header->use_end()); 338e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<User*>::iterator i = Users.begin(), e = Users.end(); 339e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman i != e; ++i) { 340e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (BranchInst *inst = dyn_cast<BranchInst>(*i)) { 341e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *BB = inst->getParent(); 342e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (!contains(code, BB) && BB->getParent() == oldFunction) { 343e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // The BasicBlock which contains the branch is not in the region 344e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // modify the branch target to a new block 345e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inst->replaceUsesOfWith(header, newHeader); 346e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 347e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 348e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 349e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 350e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 351e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 352e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 353e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanvoid CodeExtractor::moveCodeToFunction(const std::vector<BasicBlock*> &code, 354e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *newFunction) 355e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman{ 356e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<BasicBlock*>::const_iterator i = code.begin(), e =code.end(); 357e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman i != e; ++i) { 358e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *BB = *i; 359e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunc = BB->getParent(); 360e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); 361e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 362e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Delete the basic block from the old function, and the list of blocks 363e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman oldBlocks.remove(BB); 364e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 365e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Insert this basic block into the new function 366e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); 367e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newBlocks.push_back(BB); 368e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 369e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 370e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 371e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanvoid 372e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanCodeExtractor::emitCallAndSwitchStatement(Function *newFunction, 373e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *codeReplacer, 374e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const std::vector<BasicBlock*> &code, 375e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 376e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &outputs) 377e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman{ 378e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Emit a call to the new function, passing allocated memory for outputs and 379e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // just plain inputs for non-scalars 380e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<Value*> params; 381e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *codeReplacerTail = new BasicBlock("codeReplTail", 382e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman codeReplacer->getParent()); 383e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Values::const_iterator i = inputs.begin(), 384e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = inputs.end(); i != e; ++i) 385e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman params.push_back(*i); 386e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Values::const_iterator i = outputs.begin(), 387e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = outputs.end(); i != e; ++i) { 388e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Create allocas for scalar outputs 389e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if ((*i)->getType()->isPrimitiveType()) { 390e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Constant *one = ConstantUInt::get(Type::UIntTy, 1); 391e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman AllocaInst *alloca = new AllocaInst((*i)->getType(), one); 392e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman codeReplacer->getInstList().push_back(alloca); 393e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman params.push_back(alloca); 394e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 395e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman LoadInst *load = new LoadInst(alloca, "alloca"); 396e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman codeReplacerTail->getInstList().push_back(load); 397e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users((*i)->use_begin(), (*i)->use_end()); 398e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<User*>::iterator use = Users.begin(), useE =Users.end(); 399e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman use != useE; ++use) { 400e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (Instruction* inst = dyn_cast<Instruction>(*use)) { 401e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (!contains(code, inst->getParent())) { 402e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inst->replaceUsesOfWith(*i, load); 403e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 404e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 405e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 406e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 407e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman params.push_back(*i); 408e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 409e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 410e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman CallInst *call = new CallInst(newFunction, params, "targetBlock"); 411e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman codeReplacer->getInstList().push_back(call); 412e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman codeReplacer->getInstList().push_back(new BranchInst(codeReplacerTail)); 413e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 414e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Now we can emit a switch statement using the call as a value. 415e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // FIXME: perhaps instead of default being self BB, it should be a second 416e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // dummy block which asserts that the value is not within the range...? 417e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman //BasicBlock *defaultBlock = new BasicBlock("defaultBlock", oldF); 418e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman //insert abort() ? 419e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman //defaultBlock->getInstList().push_back(new BranchInst(codeReplacer)); 420e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 421e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman SwitchInst *switchInst = new SwitchInst(call, codeReplacerTail, 422e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman codeReplacerTail); 423e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 424e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Since there may be multiple exits from the original region, make the new 425e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // function return an unsigned, switch on that number 426e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman unsigned switchVal = 0; 427e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<BasicBlock*>::const_iterator i =code.begin(), e = code.end(); 428e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman i != e; ++i) { 429e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *BB = *i; 430e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 431e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // rewrite the terminator of the original BasicBlock 432e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Instruction *term = BB->getTerminator(); 433e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (BranchInst *brInst = dyn_cast<BranchInst>(term)) { 434e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 435e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Restore values just before we exit 436e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // FIXME: Use a GetElementPtr to bunch the outputs in a struct 437e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (unsigned outIdx = 0, outE = outputs.size(); outIdx != outE; ++outIdx) 438e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 439e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman new StoreInst(outputs[outIdx], 440e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman getFunctionArg(newFunction, outIdx), 441e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman brInst); 442e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 443e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 4440256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman // Rewrite branches into exits which return a value based on which 445e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // exit we take from this function 446e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (brInst->isUnconditional()) { 447e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (!contains(code, brInst->getSuccessor(0))) { 448e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman ConstantUInt *brVal = ConstantUInt::get(Type::UShortTy, switchVal); 449e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman ReturnInst *newRet = new ReturnInst(brVal); 450e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // add a new target to the switch 451e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman switchInst->addCase(brVal, brInst->getSuccessor(0)); 452e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman ++switchVal; 453e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // rewrite the branch with a return 454e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock::iterator ii(brInst); 455e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman ReplaceInstWithInst(BB->getInstList(), ii, newRet); 456e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman delete brInst; 457e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 458e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 459e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Replace the conditional branch to branch 460e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // to two new blocks, each of which returns a different code. 461e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (unsigned idx = 0; idx < 2; ++idx) { 462e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *oldTarget = brInst->getSuccessor(idx); 463e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (!contains(code, oldTarget)) { 464e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // add a new basic block which returns the appropriate value 465e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newTarget = new BasicBlock("newTarget", newFunction); 466e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman ConstantUInt *brVal = ConstantUInt::get(Type::UShortTy, switchVal); 467e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman ReturnInst *newRet = new ReturnInst(brVal); 468e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newTarget->getInstList().push_back(newRet); 469e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // rewrite the original branch instruction with this new target 470e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman brInst->setSuccessor(idx, newTarget); 471e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // the switch statement knows what to do with this value 472e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman switchInst->addCase(brVal, oldTarget); 473e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman ++switchVal; 474e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 475e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 476e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 477e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else if (ReturnInst *retTerm = dyn_cast<ReturnInst>(term)) { 478e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman assert(0 && "Cannot handle return instructions just yet."); 479e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // FIXME: what if the terminator is a return!??! 480e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Need to rewrite: add new basic block, move the return there 481e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // treat the original as an unconditional branch to that basicblock 482e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else if (SwitchInst *swTerm = dyn_cast<SwitchInst>(term)) { 483e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman assert(0 && "Cannot handle switch instructions just yet."); 484e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else if (InvokeInst *invInst = dyn_cast<InvokeInst>(term)) { 485e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman assert(0 && "Cannot handle invoke instructions just yet."); 486e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 487e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman assert(0 && "Unrecognized terminator, or badly-formed BasicBlock."); 488e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 489e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 490e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 491e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 492e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 493e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// ExtractRegion - Removes a loop from a function, replaces it with a call to 494e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// new function. Returns pointer to the new function. 495e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 496e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// algorithm: 497e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 498e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// find inputs and outputs for the region 499e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 500e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// for inputs: add to function as args, map input instr* to arg# 501e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// for outputs: add allocas for scalars, 502e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// add to func as args, map output instr* to arg# 503e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 504e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// rewrite func to use argument #s instead of instr* 505e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 506e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// for each scalar output in the function: at every exit, store intermediate 507e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// computed result back into memory. 508e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 509e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanFunction *CodeExtractor::ExtractCodeRegion(const std::vector<BasicBlock*> &code) 510e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman{ 511e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 1) Find inputs, outputs 512e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 2) Construct new function 513e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * Add allocas for defs, pass as args by reference 514e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * Pass in uses as args 515e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 3) Move code region, add call instr to func 516e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 517e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 518e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values inputs, outputs; 519e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 520e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Assumption: this is a single-entry code region, and the header is the first 521e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // block in the region. FIXME: is this true for a list of blocks from a 522e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // natural function? 523e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *header = code[0]; 524e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction = header->getParent(); 525e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Module *module = oldFunction->getParent(); 526e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 527e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This takes place of the original loop 528e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *codeReplacer = new BasicBlock("codeRepl", oldFunction); 529e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 530e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // The new function needs a root node because other nodes can branch to the 531e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // head of the loop, and the root cannot have predecessors 532e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newFuncRoot = new BasicBlock("newFuncRoot"); 533e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newFuncRoot->getInstList().push_back(new BranchInst(header)); 534e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 535e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Find inputs to, outputs from the code region 536e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 537e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // If one of the inputs is coming from a different basic block and it's in a 538e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // phi node, we need to rewrite the phi node: 539e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 540e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * All the inputs which involve basic blocks OUTSIDE of this region go into 541e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // a NEW phi node that takes care of finding which value really came in. 542e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // The result of this phi is passed to the function as an argument. 543e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 544e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * All the other phi values stay. 545e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 546e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // FIXME: PHI nodes' incoming blocks aren't being rewritten to accomodate for 547e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // blocks moving to a new function. 548e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // SOLUTION: move Phi nodes out of the loop header into the codeReplacer, pass 549e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // the values as parameters to the function 550e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman findInputsOutputs(code, inputs, outputs, codeReplacer, newFuncRoot); 551e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 552e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Step 2: Construct new function based on inputs/outputs, 553e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Add allocas for all defs 554e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *newFunction = constructFunction(inputs, outputs, newFuncRoot, 555e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman codeReplacer, code, 556e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman oldFunction, module); 557e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 558e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman rewritePhiNodes(newFunction, newFuncRoot); 559e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 560e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman emitCallAndSwitchStatement(newFunction, codeReplacer, code, inputs, outputs); 561e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 562e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman moveCodeToFunction(code, newFunction); 563e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 564ffada9327301094411146627cf6bc16cd517585dChris Lattner DEBUG(if (verifyFunction(*newFunction)) abort()); 565e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 566e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 567e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 5680256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// ExtractCodeRegion - slurp a sequence of basic blocks into a brand new 5690256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// function 5700256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// 5710256e4bbf9d8108912d3015634bc1a6f78366d16Misha BrukmanFunction* llvm::ExtractCodeRegion(const std::vector<BasicBlock*> &code) { 5720256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman CodeExtractor CE; 5730256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman return CE.ExtractCodeRegion(code); 5740256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman} 5750256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman 576b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// ExtractBasicBlock - slurp a natural loop into a brand new function 577b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// 578e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanFunction* llvm::ExtractLoop(Loop *L) { 579e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman CodeExtractor CE; 580e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return CE.ExtractCodeRegion(L->getBlocks()); 581e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 582e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 583b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// ExtractBasicBlock - slurp a basic block into a brand new function 584b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// 585b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha BrukmanFunction* llvm::ExtractBasicBlock(BasicBlock *BB) { 586b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman CodeExtractor CE; 587b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman std::vector<BasicBlock*> Blocks; 588b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman Blocks.push_back(BB); 589b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman return CE.ExtractCodeRegion(Blocks); 590b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman} 591