CodeExtractor.cpp revision 65826bf435620824763af926270cf0efdc82ea5a
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> 290e06674287b15696f66a65f20f2ba99137b29213Chris Lattner#include <set> 30e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanusing namespace llvm; 31e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 32e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmannamespace { 33e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 34e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman /// getFunctionArg - Return a pointer to F's ARGNOth argument. 35e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman /// 36e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Argument *getFunctionArg(Function *F, unsigned argno) { 3765826bf435620824763af926270cf0efdc82ea5aChris Lattner Function::aiterator I = F->abegin(); 3865826bf435620824763af926270cf0efdc82ea5aChris Lattner std::advance(I, argno); 3965826bf435620824763af926270cf0efdc82ea5aChris Lattner return I; 40e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 41e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 42e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman struct CodeExtractor { 43e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman typedef std::vector<Value*> Values; 44e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman typedef std::vector<std::pair<unsigned, unsigned> > PhiValChangesTy; 45e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman typedef std::map<PHINode*, PhiValChangesTy> PhiVal2ArgTy; 46e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiVal2ArgTy PhiVal2Arg; 470e06674287b15696f66a65f20f2ba99137b29213Chris Lattner std::set<BasicBlock*> BlocksToExtract; 48e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman public: 49e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *ExtractCodeRegion(const std::vector<BasicBlock*> &code); 50e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 51e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman private: 520e06674287b15696f66a65f20f2ba99137b29213Chris Lattner void findInputsOutputs(Values &inputs, Values &outputs, 53e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 54e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode); 55e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 56e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void processPhiNodeInputs(PHINode *Phi, 57e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 58e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 59e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode); 60e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 61e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void rewritePhiNodes(Function *F, BasicBlock *newFuncRoot); 62e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 63e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *constructFunction(const Values &inputs, 64e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Values &outputs, 65e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, BasicBlock *newHeader, 66e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction, Module *M); 67e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 680e06674287b15696f66a65f20f2ba99137b29213Chris Lattner void moveCodeToFunction(Function *newFunction); 69e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 70e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void emitCallAndSwitchStatement(Function *newFunction, 71e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 72e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 73e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &outputs); 74e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 75e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman }; 76e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 77e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 78e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanvoid CodeExtractor::processPhiNodeInputs(PHINode *Phi, 79e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 80e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *codeReplacer, 81e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newFuncRoot) 82e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman{ 83e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Separate incoming values and BasicBlocks as internal/external. We ignore 84e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // the case where both the value and BasicBlock are internal, because we don't 85e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // need to do a thing. 86e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<unsigned> EValEBB; 87e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<unsigned> EValIBB; 88e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<unsigned> IValEBB; 89e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 90e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (unsigned i = 0, e = Phi->getNumIncomingValues(); i != e; ++i) { 91e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Value *phiVal = Phi->getIncomingValue(i); 92e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (Instruction *Inst = dyn_cast<Instruction>(phiVal)) { 930e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (BlocksToExtract.count(Inst->getParent())) { 940e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (!BlocksToExtract.count(Phi->getIncomingBlock(i))) 95e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman IValEBB.push_back(i); 96e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 970e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (BlocksToExtract.count(Phi->getIncomingBlock(i))) 98e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman EValIBB.push_back(i); 99e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman else 100e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman EValEBB.push_back(i); 101e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 102e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else if (Constant *Const = dyn_cast<Constant>(phiVal)) { 103e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Constants are internal, but considered `external' if they are coming 104e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // from an external block. 1050e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (!BlocksToExtract.count(Phi->getIncomingBlock(i))) 106e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman EValEBB.push_back(i); 107e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else if (Argument *Arg = dyn_cast<Argument>(phiVal)) { 108e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // arguments are external 1090e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (BlocksToExtract.count(Phi->getIncomingBlock(i))) 110e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman EValIBB.push_back(i); 111e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman else 112e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman EValEBB.push_back(i); 113e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 114e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman phiVal->dump(); 115e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman assert(0 && "Unhandled input in a Phi node"); 116e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 117e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 118e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 119e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Both value and block are external. Need to group all of 120e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // these, have an external phi, pass the result as an 121e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // argument, and have THIS phi use that result. 122e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (EValEBB.size() > 0) { 123e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (EValEBB.size() == 1) { 124e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Now if it's coming from the newFuncRoot, it's that funky input 125e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman unsigned phiIdx = EValEBB[0]; 126e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (!dyn_cast<Constant>(Phi->getIncomingValue(phiIdx))) 127e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 128e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiVal2Arg[Phi].push_back(std::make_pair(phiIdx, inputs.size())); 129e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // We can just pass this value in as argument 130e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inputs.push_back(Phi->getIncomingValue(phiIdx)); 131e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 132e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Phi->setIncomingBlock(phiIdx, newFuncRoot); 133e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 134e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PHINode *externalPhi = new PHINode(Phi->getType(), "extPhi"); 135e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman codeReplacer->getInstList().insert(codeReplacer->begin(), externalPhi); 136e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<unsigned>::iterator i = EValEBB.begin(), 137e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = EValEBB.end(); i != e; ++i) 138e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 139e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman externalPhi->addIncoming(Phi->getIncomingValue(*i), 140e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Phi->getIncomingBlock(*i)); 141e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 142e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // We make these values invalid instead of deleting them because that 143e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // would shift the indices of other values... The fixPhiNodes should 144e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // clean these phi nodes up later. 145e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Phi->setIncomingValue(*i, 0); 146e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Phi->setIncomingBlock(*i, 0); 147e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 148e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiVal2Arg[Phi].push_back(std::make_pair(Phi->getNumIncomingValues(), 149e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inputs.size())); 150e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // We can just pass this value in as argument 151e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inputs.push_back(externalPhi); 152e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 153e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 154e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 155e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // When the value is external, but block internal... 156e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // just pass it in as argument, no change to phi node 157e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<unsigned>::iterator i = EValIBB.begin(), 158e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = EValIBB.end(); i != e; ++i) 159e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 160e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // rewrite the phi input node to be an argument 161e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiVal2Arg[Phi].push_back(std::make_pair(*i, inputs.size())); 162e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inputs.push_back(Phi->getIncomingValue(*i)); 163e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 164e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 165e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Value internal, block external 166e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // this can happen if we are extracting a part of a loop 167e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<unsigned>::iterator i = IValEBB.begin(), 168e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = IValEBB.end(); i != e; ++i) 169e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 170e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman assert(0 && "Cannot (YET) handle internal values via external blocks"); 171e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 172e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 173e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 174e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 1750e06674287b15696f66a65f20f2ba99137b29213Chris Lattnervoid CodeExtractor::findInputsOutputs(Values &inputs, 176e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &outputs, 177e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 178e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode) 179e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman{ 1800e06674287b15696f66a65f20f2ba99137b29213Chris Lattner for (std::set<BasicBlock*>::const_iterator ci = BlocksToExtract.begin(), 1810e06674287b15696f66a65f20f2ba99137b29213Chris Lattner ce = BlocksToExtract.end(); ci != ce; ++ci) { 182e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *BB = *ci; 183e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (BasicBlock::iterator BBi = BB->begin(), BBe = BB->end(); 184e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BBi != BBe; ++BBi) { 185e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // If a use is defined outside the region, it's an input. 186e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // If a def is used outside the region, it's an output. 187e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (Instruction *I = dyn_cast<Instruction>(&*BBi)) { 188e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // If it's a phi node 189e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (PHINode *Phi = dyn_cast<PHINode>(I)) { 1900e06674287b15696f66a65f20f2ba99137b29213Chris Lattner processPhiNodeInputs(Phi, inputs, newHeader, newRootNode); 191e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 192e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // All other instructions go through the generic input finder 193e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Loop over the operands of each instruction (inputs) 194e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (User::op_iterator op = I->op_begin(), opE = I->op_end(); 195e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman op != opE; ++op) { 196e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (Instruction *opI = dyn_cast<Instruction>(op->get())) { 197e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Check if definition of this operand is within the loop 1980e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (!BlocksToExtract.count(opI->getParent())) { 199e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // add this operand to the inputs 200e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inputs.push_back(opI); 201e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 202e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 203e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 204e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 205e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 206e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Consider uses of this instruction (outputs) 207e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Value::use_iterator use = I->use_begin(), useE = I->use_end(); 208e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman use != useE; ++use) { 209e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (Instruction* inst = dyn_cast<Instruction>(*use)) { 2100e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (!BlocksToExtract.count(inst->getParent())) { 211e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // add this op to the outputs 212e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman outputs.push_back(I); 213e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 214e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 215e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 216e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } /* if */ 217e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } /* for: insts */ 218e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } /* for: basic blocks */ 219e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 220e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 221e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanvoid CodeExtractor::rewritePhiNodes(Function *F, 222e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newFuncRoot) { 223e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Write any changes that were saved before: use function arguments as inputs 224e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (PhiVal2ArgTy::iterator i = PhiVal2Arg.begin(), e = PhiVal2Arg.end(); 225e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman i != e; ++i) 226e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 227e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PHINode *phi = (*i).first; 228e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiValChangesTy &values = (*i).second; 229e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (unsigned cIdx = 0, ce = values.size(); cIdx != ce; ++cIdx) 230e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 231e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman unsigned phiValueIdx = values[cIdx].first, argNum = values[cIdx].second; 232e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (phiValueIdx < phi->getNumIncomingValues()) 233e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman phi->setIncomingValue(phiValueIdx, getFunctionArg(F, argNum)); 234e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman else 235e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman phi->addIncoming(getFunctionArg(F, argNum), newFuncRoot); 236e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 237e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 238e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 239e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Delete any invalid Phi node inputs that were marked as NULL previously 240e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (PhiVal2ArgTy::iterator i = PhiVal2Arg.begin(), e = PhiVal2Arg.end(); 241e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman i != e; ++i) 242e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 243e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PHINode *phi = (*i).first; 244e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (unsigned idx = 0, end = phi->getNumIncomingValues(); idx != end; ++idx) 245e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman { 246e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (phi->getIncomingValue(idx) == 0 && phi->getIncomingBlock(idx) == 0) { 247e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman phi->removeIncomingValue(idx); 248e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman --idx; 249e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman --end; 250e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 251e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 252e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 253e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 254e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // We are done with the saved values 255e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman PhiVal2Arg.clear(); 256e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 257e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 258e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 259e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// constructFunction - make a function based on inputs and outputs, as follows: 260e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// f(in0, ..., inN, out0, ..., outN) 261e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 262e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanFunction *CodeExtractor::constructFunction(const Values &inputs, 263e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Values &outputs, 264e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, 265e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 266e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction, Module *M) { 267e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "inputs: " << inputs.size() << "\n"); 268e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "outputs: " << outputs.size() << "\n"); 2690e06674287b15696f66a65f20f2ba99137b29213Chris Lattner BasicBlock *header = *BlocksToExtract.begin(); 270e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 271e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This function returns unsigned, outputs will go back by reference. 272e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Type *retTy = Type::UShortTy; 273e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<const Type*> paramTy; 274e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 275e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Add the types of the input values to the function's argument list 276e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Values::const_iterator i = inputs.begin(), 277e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = inputs.end(); i != e; ++i) { 278e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Value *value = *i; 279e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "value used in func: " << value << "\n"); 280e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman paramTy.push_back(value->getType()); 281e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 282e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 283e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Add the types of the output values to the function's argument list, but 284e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // make them pointer types for scalars 285e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Values::const_iterator i = outputs.begin(), 286e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = outputs.end(); i != e; ++i) { 287e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Value *value = *i; 288e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "instr used in func: " << value << "\n"); 289e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Type *valueType = value->getType(); 290e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Convert scalar types into a pointer of that type 291e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (valueType->isPrimitiveType()) { 292e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman valueType = PointerType::get(valueType); 293e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 294e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman paramTy.push_back(valueType); 295e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 296e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 297e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "Function type: " << retTy << " f("); 298e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<const Type*>::iterator i = paramTy.begin(), 299e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = paramTy.end(); i != e; ++i) 300e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << (*i) << ", "); 301e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << ")\n"); 302e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 303e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const FunctionType *funcType = FunctionType::get(retTy, paramTy, false); 304e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 305e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Create the new function 306e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *newFunction = new Function(funcType, 307e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman GlobalValue::InternalLinkage, 308e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman oldFunction->getName() + "_code", M); 309e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newFunction->getBasicBlockList().push_back(newRootNode); 310e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 311e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 312e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(inputs[i]->use_begin(), inputs[i]->use_end()); 313e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<User*>::iterator use = Users.begin(), useE = Users.end(); 314ffada9327301094411146627cf6bc16cd517585dChris Lattner use != useE; ++use) 315ffada9327301094411146627cf6bc16cd517585dChris Lattner if (Instruction* inst = dyn_cast<Instruction>(*use)) 3160e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (BlocksToExtract.count(inst->getParent())) 317e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inst->replaceUsesOfWith(inputs[i], getFunctionArg(newFunction, i)); 318e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 319e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 320e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Rewrite branches to basic blocks outside of the loop to new dummy blocks 321e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // within the new function. This must be done before we lose track of which 322e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // blocks were originally in the code region. 323e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(header->use_begin(), header->use_end()); 324e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<User*>::iterator i = Users.begin(), e = Users.end(); 325e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman i != e; ++i) { 326e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (BranchInst *inst = dyn_cast<BranchInst>(*i)) { 327e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *BB = inst->getParent(); 3280e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (!BlocksToExtract.count(BB) && BB->getParent() == oldFunction) { 329e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // The BasicBlock which contains the branch is not in the region 330e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // modify the branch target to a new block 331e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inst->replaceUsesOfWith(header, newHeader); 332e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 333e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 334e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 335e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 336e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 337e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 338e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 33912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattnervoid CodeExtractor::moveCodeToFunction(Function *newFunction) { 3400e06674287b15696f66a65f20f2ba99137b29213Chris Lattner Function *oldFunc = (*BlocksToExtract.begin())->getParent(); 341bb41156c0ce9cc8d0af35f6eb928a42cfe93a799Chris Lattner Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); 34212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); 343bb41156c0ce9cc8d0af35f6eb928a42cfe93a799Chris Lattner 3440e06674287b15696f66a65f20f2ba99137b29213Chris Lattner for (std::set<BasicBlock*>::const_iterator i = BlocksToExtract.begin(), 3450e06674287b15696f66a65f20f2ba99137b29213Chris Lattner e = BlocksToExtract.end(); i != e; ++i) { 346e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Delete the basic block from the old function, and the list of blocks 3470e06674287b15696f66a65f20f2ba99137b29213Chris Lattner oldBlocks.remove(*i); 348e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 349e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Insert this basic block into the new function 3500e06674287b15696f66a65f20f2ba99137b29213Chris Lattner newBlocks.push_back(*i); 351e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 352e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 353e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 354e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanvoid 355e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanCodeExtractor::emitCallAndSwitchStatement(Function *newFunction, 356e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *codeReplacer, 357e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 358e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &outputs) 359e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman{ 360e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Emit a call to the new function, passing allocated memory for outputs and 361e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // just plain inputs for non-scalars 36265826bf435620824763af926270cf0efdc82ea5aChris Lattner std::vector<Value*> params(inputs); 36365826bf435620824763af926270cf0efdc82ea5aChris Lattner 36465826bf435620824763af926270cf0efdc82ea5aChris Lattner for (Values::const_iterator i = outputs.begin(), e = outputs.end(); i != e; 36565826bf435620824763af926270cf0efdc82ea5aChris Lattner ++i) { 36665826bf435620824763af926270cf0efdc82ea5aChris Lattner Value *Output = *i; 367e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Create allocas for scalar outputs 36865826bf435620824763af926270cf0efdc82ea5aChris Lattner if (Output->getType()->isPrimitiveType()) { 36965826bf435620824763af926270cf0efdc82ea5aChris Lattner AllocaInst *alloca = 37065826bf435620824763af926270cf0efdc82ea5aChris Lattner new AllocaInst((*i)->getType(), 0, Output->getName()+".loc", 37165826bf435620824763af926270cf0efdc82ea5aChris Lattner codeReplacer->getParent()->begin()->begin()); 372e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman params.push_back(alloca); 373e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 37465826bf435620824763af926270cf0efdc82ea5aChris Lattner LoadInst *load = new LoadInst(alloca, Output->getName()+".reload"); 37565826bf435620824763af926270cf0efdc82ea5aChris Lattner codeReplacer->getInstList().push_back(load); 376e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users((*i)->use_begin(), (*i)->use_end()); 377e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<User*>::iterator use = Users.begin(), useE =Users.end(); 378e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman use != useE; ++use) { 379e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman if (Instruction* inst = dyn_cast<Instruction>(*use)) { 38065826bf435620824763af926270cf0efdc82ea5aChris Lattner if (!BlocksToExtract.count(inst->getParent())) 381e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman inst->replaceUsesOfWith(*i, load); 382e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 383e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 384e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } else { 385e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman params.push_back(*i); 386e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 387e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 38812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 389e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman CallInst *call = new CallInst(newFunction, params, "targetBlock"); 39065826bf435620824763af926270cf0efdc82ea5aChris Lattner codeReplacer->getInstList().push_front(call); 391e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 392e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Now we can emit a switch statement using the call as a value. 39365826bf435620824763af926270cf0efdc82ea5aChris Lattner SwitchInst *TheSwitch = new SwitchInst(call, codeReplacer, codeReplacer); 394e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 395e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Since there may be multiple exits from the original region, make the new 39612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // function return an unsigned, switch on that number. This loop iterates 39712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // over all of the blocks in the extracted region, updating any terminator 39812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // instructions in the to-be-extracted region that branch to blocks that are 39912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // not in the region to be extracted. 40012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner std::map<BasicBlock*, BasicBlock*> ExitBlockMap; 40112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 402e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman unsigned switchVal = 0; 4030e06674287b15696f66a65f20f2ba99137b29213Chris Lattner for (std::set<BasicBlock*>::const_iterator i = BlocksToExtract.begin(), 4040e06674287b15696f66a65f20f2ba99137b29213Chris Lattner e = BlocksToExtract.end(); i != e; ++i) { 40512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner TerminatorInst *TI = (*i)->getTerminator(); 40612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 40712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner if (!BlocksToExtract.count(TI->getSuccessor(i))) { 40812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner BasicBlock *OldTarget = TI->getSuccessor(i); 40912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // add a new basic block which returns the appropriate value 41012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; 41112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner if (!NewTarget) { 41212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // If we don't already have an exit stub for this non-extracted 41312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // destination, create one now! 41412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner NewTarget = new BasicBlock(OldTarget->getName() + ".exitStub", 41512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner newFunction); 41612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 41712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner ConstantUInt *brVal = ConstantUInt::get(Type::UShortTy, switchVal++); 41812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner ReturnInst *NTRet = new ReturnInst(brVal, NewTarget); 41912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 42012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // Update the switch instruction. 42165826bf435620824763af926270cf0efdc82ea5aChris Lattner TheSwitch->addCase(brVal, OldTarget); 42212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 42312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // Restore values just before we exit 42412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // FIXME: Use a GetElementPtr to bunch the outputs in a struct 42512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner for (unsigned out = 0, e = outputs.size(); out != e; ++out) 42612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner new StoreInst(outputs[out], getFunctionArg(newFunction, out),NTRet); 427e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 4280e06674287b15696f66a65f20f2ba99137b29213Chris Lattner 42912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // rewrite the original branch instruction with this new target 43012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner TI->setSuccessor(i, NewTarget); 43112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner } 432e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 43365826bf435620824763af926270cf0efdc82ea5aChris Lattner 43465826bf435620824763af926270cf0efdc82ea5aChris Lattner // Now that we've done the deed, make the default destination of the switch 43565826bf435620824763af926270cf0efdc82ea5aChris Lattner // instruction be one of the exit blocks of the region. 43665826bf435620824763af926270cf0efdc82ea5aChris Lattner if (TheSwitch->getNumSuccessors() > 1) { 43765826bf435620824763af926270cf0efdc82ea5aChris Lattner // FIXME: this is broken w.r.t. PHI nodes, but the old code was more broken. 43865826bf435620824763af926270cf0efdc82ea5aChris Lattner // This edge is not traversable. 43965826bf435620824763af926270cf0efdc82ea5aChris Lattner TheSwitch->setSuccessor(0, TheSwitch->getSuccessor(1)); 44065826bf435620824763af926270cf0efdc82ea5aChris Lattner } 441e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 442e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 443e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 444e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// ExtractRegion - Removes a loop from a function, replaces it with a call to 445e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// new function. Returns pointer to the new function. 446e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 447e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// algorithm: 448e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 449e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// find inputs and outputs for the region 450e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 451e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// for inputs: add to function as args, map input instr* to arg# 452e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// for outputs: add allocas for scalars, 453e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// add to func as args, map output instr* to arg# 454e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 455e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// rewrite func to use argument #s instead of instr* 456e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 457e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// for each scalar output in the function: at every exit, store intermediate 458e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// computed result back into memory. 459e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 460e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanFunction *CodeExtractor::ExtractCodeRegion(const std::vector<BasicBlock*> &code) 461e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman{ 462e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 1) Find inputs, outputs 463e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 2) Construct new function 464e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * Add allocas for defs, pass as args by reference 465e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * Pass in uses as args 466e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 3) Move code region, add call instr to func 4670e06674287b15696f66a65f20f2ba99137b29213Chris Lattner // 4680e06674287b15696f66a65f20f2ba99137b29213Chris Lattner BlocksToExtract.insert(code.begin(), code.end()); 469e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 470e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values inputs, outputs; 471e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 472e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Assumption: this is a single-entry code region, and the header is the first 473e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // block in the region. FIXME: is this true for a list of blocks from a 474e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // natural function? 475e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *header = code[0]; 476e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction = header->getParent(); 477e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Module *module = oldFunction->getParent(); 478e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 479e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This takes place of the original loop 480e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *codeReplacer = new BasicBlock("codeRepl", oldFunction); 481e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 482e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // The new function needs a root node because other nodes can branch to the 483e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // head of the loop, and the root cannot have predecessors 484e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newFuncRoot = new BasicBlock("newFuncRoot"); 485e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newFuncRoot->getInstList().push_back(new BranchInst(header)); 486e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 487e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Find inputs to, outputs from the code region 488e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 489e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // If one of the inputs is coming from a different basic block and it's in a 490e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // phi node, we need to rewrite the phi node: 491e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 492e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * All the inputs which involve basic blocks OUTSIDE of this region go into 493e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // a NEW phi node that takes care of finding which value really came in. 494e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // The result of this phi is passed to the function as an argument. 495e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 496e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * All the other phi values stay. 497e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 498e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // FIXME: PHI nodes' incoming blocks aren't being rewritten to accomodate for 499e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // blocks moving to a new function. 500e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // SOLUTION: move Phi nodes out of the loop header into the codeReplacer, pass 501e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // the values as parameters to the function 5020e06674287b15696f66a65f20f2ba99137b29213Chris Lattner findInputsOutputs(inputs, outputs, codeReplacer, newFuncRoot); 503e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 504e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Step 2: Construct new function based on inputs/outputs, 505e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Add allocas for all defs 506e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *newFunction = constructFunction(inputs, outputs, newFuncRoot, 5070e06674287b15696f66a65f20f2ba99137b29213Chris Lattner codeReplacer, oldFunction, module); 508e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 509e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman rewritePhiNodes(newFunction, newFuncRoot); 510e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 5110e06674287b15696f66a65f20f2ba99137b29213Chris Lattner emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); 512e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 5130e06674287b15696f66a65f20f2ba99137b29213Chris Lattner moveCodeToFunction(newFunction); 514e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 515ffada9327301094411146627cf6bc16cd517585dChris Lattner DEBUG(if (verifyFunction(*newFunction)) abort()); 516e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 517e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 518e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 5190256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// ExtractCodeRegion - slurp a sequence of basic blocks into a brand new 5200256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// function 5210256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// 5220256e4bbf9d8108912d3015634bc1a6f78366d16Misha BrukmanFunction* llvm::ExtractCodeRegion(const std::vector<BasicBlock*> &code) { 523bb41156c0ce9cc8d0af35f6eb928a42cfe93a799Chris Lattner return CodeExtractor().ExtractCodeRegion(code); 5240256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman} 5250256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman 526b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// ExtractBasicBlock - slurp a natural loop into a brand new function 527b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// 528e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanFunction* llvm::ExtractLoop(Loop *L) { 529bb41156c0ce9cc8d0af35f6eb928a42cfe93a799Chris Lattner return CodeExtractor().ExtractCodeRegion(L->getBlocks()); 530e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 531e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 532b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// ExtractBasicBlock - slurp a basic block into a brand new function 533b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// 534b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha BrukmanFunction* llvm::ExtractBasicBlock(BasicBlock *BB) { 535b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman std::vector<BasicBlock*> Blocks; 536b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman Blocks.push_back(BB); 537bb41156c0ce9cc8d0af35f6eb928a42cfe93a799Chris Lattner return CodeExtractor().ExtractCodeRegion(Blocks); 538b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman} 539