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