CodeExtractor.cpp revision e746ad512efc447f352f9580a82c808c2d32ab26
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 1633e197b7778c92acc732c3255dc8fbb99923e8ccChris Lattner#include "llvm/Transforms/Utils/FunctionUtils.h" 17e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Constants.h" 18e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/DerivedTypes.h" 19e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Instructions.h" 20bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner#include "llvm/Intrinsics.h" 21e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Module.h" 22e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Pass.h" 23b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner#include "llvm/Analysis/Dominators.h" 24e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Analysis/LoopInfo.h" 25ffada9327301094411146627cf6bc16cd517585dChris Lattner#include "llvm/Analysis/Verifier.h" 26e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 2722108fac63eac53d1a23b781a9963fab99700135Misha Brukman#include "Support/CommandLine.h" 28e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "Support/Debug.h" 29e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "Support/StringExtras.h" 30e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include <algorithm> 310e06674287b15696f66a65f20f2ba99137b29213Chris Lattner#include <set> 32e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanusing namespace llvm; 33e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 3422108fac63eac53d1a23b781a9963fab99700135Misha Brukman// Provide a command-line option to aggregate function arguments into a struct 3522108fac63eac53d1a23b781a9963fab99700135Misha Brukman// for functions produced by the code extrator. This is useful when converting 3622108fac63eac53d1a23b781a9963fab99700135Misha Brukman// extracted functions to pthread-based code, as only one argument (void*) can 3722108fac63eac53d1a23b781a9963fab99700135Misha Brukman// be passed in to pthread_create(). 3822108fac63eac53d1a23b781a9963fab99700135Misha Brukmanstatic cl::opt<bool> 3922108fac63eac53d1a23b781a9963fab99700135Misha BrukmanAggregateArgsOpt("aggregate-extracted-args", cl::Hidden, 4022108fac63eac53d1a23b781a9963fab99700135Misha Brukman cl::desc("Aggregate arguments to code-extracted functions")); 4122108fac63eac53d1a23b781a9963fab99700135Misha Brukman 42e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmannamespace { 43b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner class CodeExtractor { 44e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman typedef std::vector<Value*> Values; 450e06674287b15696f66a65f20f2ba99137b29213Chris Lattner std::set<BasicBlock*> BlocksToExtract; 46b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner DominatorSet *DS; 4722108fac63eac53d1a23b781a9963fab99700135Misha Brukman bool AggregateArgs; 48346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner unsigned NumExitBlocks; 49346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner const Type *RetTy; 50e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman public: 5122108fac63eac53d1a23b781a9963fab99700135Misha Brukman CodeExtractor(DominatorSet *ds = 0, bool AggArgs = false) 52346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner : DS(ds), AggregateArgs(AggregateArgsOpt), NumExitBlocks(~0U) {} 53b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 54e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *ExtractCodeRegion(const std::vector<BasicBlock*> &code); 55e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 5622108fac63eac53d1a23b781a9963fab99700135Misha Brukman bool isEligible(const std::vector<BasicBlock*> &code); 5722108fac63eac53d1a23b781a9963fab99700135Misha Brukman 58e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman private: 59bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// definedInRegion - Return true if the specified value is defined in the 60bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// extracted region. 61bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner bool definedInRegion(Value *V) const { 62bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 63bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (BlocksToExtract.count(I->getParent())) 64bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return true; 65bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return false; 66bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 67bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 68bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// definedInCaller - Return true if the specified value is defined in the 69bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// function being code extracted, but not in the region being extracted. 70bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// These values must be passed in as live-ins to the function. 71bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner bool definedInCaller(Value *V) const { 72bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (isa<Argument>(V)) return true; 73bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 74bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (!BlocksToExtract.count(I->getParent())) 75bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return true; 76bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return false; 77bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 78bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 79bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner void severSplitPHINodes(BasicBlock *&Header); 80bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner void findInputsOutputs(Values &inputs, Values &outputs); 81e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 82e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *constructFunction(const Values &inputs, 83e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Values &outputs, 845cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner BasicBlock *header, 85e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, BasicBlock *newHeader, 86e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction, Module *M); 87e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 880e06674287b15696f66a65f20f2ba99137b29213Chris Lattner void moveCodeToFunction(Function *newFunction); 89e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 90e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void emitCallAndSwitchStatement(Function *newFunction, 91e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 92e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 93e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &outputs); 94e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 95e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman }; 96e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 97e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 98bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// severSplitPHINodes - If a PHI node has multiple inputs from outside of the 99bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// region, we need to split the entry block of the region so that the PHI node 100bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// is easier to deal with. 101bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::severSplitPHINodes(BasicBlock *&Header) { 102e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner bool HasPredsFromRegion = false; 103e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner unsigned NumPredsOutsideRegion = 0; 104e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 105e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (Header != &Header->getParent()->front()) { 106e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *PN = dyn_cast<PHINode>(Header->begin()); 107e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (!PN) return; // No PHI nodes. 108e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 109e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // If the header node contains any PHI nodes, check to see if there is more 110e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // than one entry from outside the region. If so, we need to sever the 111e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // header block into two. 112e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 113e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) 114e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner HasPredsFromRegion = true; 115e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner else 116e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner ++NumPredsOutsideRegion; 117e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 118e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // If there is one (or fewer) predecessor from outside the region, we don't 119e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // need to do anything special. 120e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (NumPredsOutsideRegion <= 1) return; 121e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 122bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 123e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Otherwise, we need to split the header block into two pieces: one 124e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // containing PHI nodes merging values from outside of the region, and a 125e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // second that contains all of the code for the block and merges back any 126e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // incoming values from inside of the region. 127e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BasicBlock::iterator AfterPHIs = Header->begin(); 128e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner while (isa<PHINode>(AfterPHIs)) ++AfterPHIs; 129e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BasicBlock *NewBB = Header->splitBasicBlock(AfterPHIs, 130e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Header->getName()+".ce"); 131e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 132e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // We only want to code extract the second block now, and it becomes the new 133e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // header of the region. 134e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BasicBlock *OldPred = Header; 135e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BlocksToExtract.erase(OldPred); 136e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BlocksToExtract.insert(NewBB); 137e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Header = NewBB; 138e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 139e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, update dominator sets. The blocks that dominate the new one are the 140e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // blocks that dominate TIBB plus the new block itself. 141e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (DS) { 142e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner DominatorSet::DomSetType DomSet = DS->getDominators(OldPred); 143e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner DomSet.insert(NewBB); // A block always dominates itself. 144e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner DS->addBasicBlock(NewBB, DomSet); 145e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 146e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Additionally, NewBB dominates all blocks in the function that are 147e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // dominated by OldPred. 148e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Function *F = Header->getParent(); 149e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 150e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (DS->properlyDominates(OldPred, I)) 151e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner DS->addDominator(I, NewBB); 152e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 153bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 154e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, now we need to adjust the PHI nodes and any branches from within the 155e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // region to go to the new header block instead of the old header block. 156e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (HasPredsFromRegion) { 157e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *PN = cast<PHINode>(OldPred->begin()); 158e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the predecessors of OldPred that are in the region, 159e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // changing them to branch to NewBB instead. 160e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 161e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) { 162e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner TerminatorInst *TI = PN->getIncomingBlock(i)->getTerminator(); 163e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner TI->replaceUsesOfWith(OldPred, NewBB); 164e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 165e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 166e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, everthing within the region is now branching to the right block, we 167e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // just have to update the PHI nodes now, inserting PHI nodes into NewBB. 168e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (AfterPHIs = OldPred->begin(); 169e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *PN = dyn_cast<PHINode>(AfterPHIs); ++AfterPHIs) { 170e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Create a new PHI node in the new region, which has an incoming value 171e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // from OldPred of PN. 172e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".ce", 173e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner NewBB->begin()); 174e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner NewPN->addIncoming(PN, OldPred); 175e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 176e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the incoming value in PN, moving them to NewPN if they 177e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // are from the extracted region. 178e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { 179e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) { 180e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); 181e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PN->removeIncomingValue(i); 182e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner --i; 183e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 184e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 185e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 186e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 187e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 188e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner verifyFunction(*NewBB->getParent()); 189bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner} 190bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 191bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner// findInputsOutputs - Find inputs to, outputs from the code region. 192bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner// 193bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::findInputsOutputs(Values &inputs, Values &outputs) { 194346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner std::set<BasicBlock*> ExitBlocks; 1950e06674287b15696f66a65f20f2ba99137b29213Chris Lattner for (std::set<BasicBlock*>::const_iterator ci = BlocksToExtract.begin(), 1960e06674287b15696f66a65f20f2ba99137b29213Chris Lattner ce = BlocksToExtract.end(); ci != ce; ++ci) { 197e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *BB = *ci; 198bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 1990de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 2000de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner // If a used value is defined outside the region, it's an input. If an 2010de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner // instruction is used outside the region, it's an output. 202bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner for (User::op_iterator O = I->op_begin(), E = I->op_end(); O != E; ++O) 203bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (definedInCaller(*O)) 204bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner inputs.push_back(*O); 2050de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner 206bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Consider uses of this instruction (outputs). 2070de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 2080de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner UI != E; ++UI) 209bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (!definedInRegion(*UI)) { 210b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner outputs.push_back(I); 211b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner break; 212b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner } 2130de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner } // for: insts 214346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 215bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Keep track of the exit blocks from the region. 216346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TerminatorInst *TI = BB->getTerminator(); 217346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 218346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner if (!BlocksToExtract.count(TI->getSuccessor(i))) 219346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner ExitBlocks.insert(TI->getSuccessor(i)); 2200de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner } // for: basic blocks 221346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 222346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner NumExitBlocks = ExitBlocks.size(); 223e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 224e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 225e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// constructFunction - make a function based on inputs and outputs, as follows: 226e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// f(in0, ..., inN, out0, ..., outN) 227e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 228e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanFunction *CodeExtractor::constructFunction(const Values &inputs, 229e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Values &outputs, 2305cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner BasicBlock *header, 231e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, 232e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 2335cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner Function *oldFunction, 2345cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner Module *M) { 235e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "inputs: " << inputs.size() << "\n"); 236e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "outputs: " << outputs.size() << "\n"); 237e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 238e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This function returns unsigned, outputs will go back by reference. 239346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 240346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 241346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 1: RetTy = Type::VoidTy; break; 242346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 2: RetTy = Type::BoolTy; break; 243346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner default: RetTy = Type::UShortTy; break; 244346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner } 245346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 246e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<const Type*> paramTy; 247e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 248e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Add the types of the input values to the function's argument list 249e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Values::const_iterator i = inputs.begin(), 250e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = inputs.end(); i != e; ++i) { 251e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Value *value = *i; 252e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << "value used in func: " << value << "\n"); 253e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman paramTy.push_back(value->getType()); 254e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 255e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 256b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Add the types of the output values to the function's argument list. 257b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (Values::const_iterator I = outputs.begin(), E = outputs.end(); 258b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner I != E; ++I) { 259b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner DEBUG(std::cerr << "instr used in func: " << *I << "\n"); 26022108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) 26122108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.push_back((*I)->getType()); 26222108fac63eac53d1a23b781a9963fab99700135Misha Brukman else 26322108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.push_back(PointerType::get((*I)->getType())); 264e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 265e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 266346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner DEBUG(std::cerr << "Function type: " << RetTy << " f("); 26722108fac63eac53d1a23b781a9963fab99700135Misha Brukman DEBUG(for (std::vector<const Type*>::iterator i = paramTy.begin(), 26822108fac63eac53d1a23b781a9963fab99700135Misha Brukman e = paramTy.end(); i != e; ++i) std::cerr << *i << ", "); 269e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman DEBUG(std::cerr << ")\n"); 270e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 27122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 27222108fac63eac53d1a23b781a9963fab99700135Misha Brukman PointerType *StructPtr = PointerType::get(StructType::get(paramTy)); 27322108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.clear(); 27422108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.push_back(StructPtr); 27522108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 276346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner const FunctionType *funcType = FunctionType::get(RetTy, paramTy, false); 277e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 278e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Create the new function 279e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *newFunction = new Function(funcType, 280e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman GlobalValue::InternalLinkage, 281e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman oldFunction->getName() + "_code", M); 282e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newFunction->getBasicBlockList().push_back(newRootNode); 283e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 284b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Create an iterator to name all of the arguments we inserted. 285b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner Function::aiterator AI = newFunction->abegin(); 286b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 287b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Rewrite all users of the inputs in the extracted region to use the 28822108fac63eac53d1a23b781a9963fab99700135Misha Brukman // arguments (or appropriate addressing into struct) instead. 28922108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 29022108fac63eac53d1a23b781a9963fab99700135Misha Brukman Value *RewriteVal; 29122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 29222108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::vector<Value*> Indices; 29322108fac63eac53d1a23b781a9963fab99700135Misha Brukman Indices.push_back(Constant::getNullValue(Type::UIntTy)); 29422108fac63eac53d1a23b781a9963fab99700135Misha Brukman Indices.push_back(ConstantUInt::get(Type::UIntTy, i)); 29522108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::string GEPname = "gep_" + inputs[i]->getName(); 29622108fac63eac53d1a23b781a9963fab99700135Misha Brukman TerminatorInst *TI = newFunction->begin()->getTerminator(); 29722108fac63eac53d1a23b781a9963fab99700135Misha Brukman GetElementPtrInst *GEP = new GetElementPtrInst(AI, Indices, GEPname, TI); 29822108fac63eac53d1a23b781a9963fab99700135Misha Brukman RewriteVal = new LoadInst(GEP, "load" + GEPname, TI); 29922108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else 30022108fac63eac53d1a23b781a9963fab99700135Misha Brukman RewriteVal = AI++; 30122108fac63eac53d1a23b781a9963fab99700135Misha Brukman 302e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(inputs[i]->use_begin(), inputs[i]->use_end()); 303e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<User*>::iterator use = Users.begin(), useE = Users.end(); 304ffada9327301094411146627cf6bc16cd517585dChris Lattner use != useE; ++use) 305ffada9327301094411146627cf6bc16cd517585dChris Lattner if (Instruction* inst = dyn_cast<Instruction>(*use)) 3060e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (BlocksToExtract.count(inst->getParent())) 30722108fac63eac53d1a23b781a9963fab99700135Misha Brukman inst->replaceUsesOfWith(inputs[i], RewriteVal); 308e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 309e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 31022108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Set names for input and output arguments. 31122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) { 31222108fac63eac53d1a23b781a9963fab99700135Misha Brukman AI = newFunction->abegin(); 31322108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) 31422108fac63eac53d1a23b781a9963fab99700135Misha Brukman AI->setName(inputs[i]->getName()); 31522108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) 31622108fac63eac53d1a23b781a9963fab99700135Misha Brukman AI->setName(outputs[i]->getName()+".out"); 31722108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 318b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 319e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Rewrite branches to basic blocks outside of the loop to new dummy blocks 320e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // within the new function. This must be done before we lose track of which 321e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // blocks were originally in the code region. 322e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(header->use_begin(), header->use_end()); 3235cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner for (unsigned i = 0, e = Users.size(); i != e; ++i) 3245cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // The BasicBlock which contains the branch is not in the region 3255cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // modify the branch target to a new block 3265cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Users[i])) 3275cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner if (!BlocksToExtract.count(TI->getParent()) && 3285cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner TI->getParent()->getParent() == oldFunction) 3295cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner TI->replaceUsesOfWith(header, newHeader); 330e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 331e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 332e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 333e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 334bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// emitCallAndSwitchStatement - This method sets up the caller side by adding 335bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// the call instruction, splitting any PHI nodes in the header block as 336bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// necessary. 337bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor:: 338bf749367cb2aef7072ee36a9eb681b35aab51921Chris LattneremitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, 339bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Values &inputs, Values &outputs) { 340bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Emit a call to the new function, passing in: *pointer to struct (if 341bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // aggregating parameters), or plan inputs and allocated memory for outputs 34222108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::vector<Value*> params, StructValues, ReloadOutputs; 34322108fac63eac53d1a23b781a9963fab99700135Misha Brukman 34422108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Add inputs as params, or to be filled into the struct 34522108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (Values::iterator i = inputs.begin(), e = inputs.end(); i != e; ++i) 34622108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) 34722108fac63eac53d1a23b781a9963fab99700135Misha Brukman StructValues.push_back(*i); 34822108fac63eac53d1a23b781a9963fab99700135Misha Brukman else 34922108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(*i); 35022108fac63eac53d1a23b781a9963fab99700135Misha Brukman 35122108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Create allocas for the outputs 35222108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (Values::iterator i = outputs.begin(), e = outputs.end(); i != e; ++i) { 35322108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 35422108fac63eac53d1a23b781a9963fab99700135Misha Brukman StructValues.push_back(*i); 35522108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else { 35622108fac63eac53d1a23b781a9963fab99700135Misha Brukman AllocaInst *alloca = 35722108fac63eac53d1a23b781a9963fab99700135Misha Brukman new AllocaInst((*i)->getType(), 0, (*i)->getName()+".loc", 35822108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getParent()->begin()->begin()); 35922108fac63eac53d1a23b781a9963fab99700135Misha Brukman ReloadOutputs.push_back(alloca); 36022108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(alloca); 36122108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 36222108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 36322108fac63eac53d1a23b781a9963fab99700135Misha Brukman 36422108fac63eac53d1a23b781a9963fab99700135Misha Brukman AllocaInst *Struct = 0; 36522108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 36622108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::vector<const Type*> ArgTypes; 36722108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (Values::iterator v = StructValues.begin(), 36822108fac63eac53d1a23b781a9963fab99700135Misha Brukman ve = StructValues.end(); v != ve; ++v) 36922108fac63eac53d1a23b781a9963fab99700135Misha Brukman ArgTypes.push_back((*v)->getType()); 37022108fac63eac53d1a23b781a9963fab99700135Misha Brukman 37122108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Allocate a struct at the beginning of this function 37222108fac63eac53d1a23b781a9963fab99700135Misha Brukman Type *StructArgTy = StructType::get(ArgTypes); 37322108fac63eac53d1a23b781a9963fab99700135Misha Brukman Struct = 37422108fac63eac53d1a23b781a9963fab99700135Misha Brukman new AllocaInst(StructArgTy, 0, "structArg", 37522108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getParent()->begin()->begin()); 37622108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(Struct); 37722108fac63eac53d1a23b781a9963fab99700135Misha Brukman 37822108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 37922108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::vector<Value*> Indices; 38022108fac63eac53d1a23b781a9963fab99700135Misha Brukman Indices.push_back(Constant::getNullValue(Type::UIntTy)); 38122108fac63eac53d1a23b781a9963fab99700135Misha Brukman Indices.push_back(ConstantUInt::get(Type::UIntTy, i)); 38222108fac63eac53d1a23b781a9963fab99700135Misha Brukman GetElementPtrInst *GEP = 38322108fac63eac53d1a23b781a9963fab99700135Misha Brukman new GetElementPtrInst(Struct, Indices, 38422108fac63eac53d1a23b781a9963fab99700135Misha Brukman "gep_" + StructValues[i]->getName(), 0); 38522108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(GEP); 38622108fac63eac53d1a23b781a9963fab99700135Misha Brukman StoreInst *SI = new StoreInst(StructValues[i], GEP); 38722108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(SI); 38822108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 38922108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 39022108fac63eac53d1a23b781a9963fab99700135Misha Brukman 39122108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Emit the call to the function 392346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner CallInst *call = new CallInst(newFunction, params, 393346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner NumExitBlocks > 1 ? "targetBlock": ""); 39422108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(call); 39522108fac63eac53d1a23b781a9963fab99700135Misha Brukman 39604229c192bc153210e8ee8a18eb28d7f1ec21bfeChris Lattner Function::aiterator OutputArgBegin = newFunction->abegin(); 39722108fac63eac53d1a23b781a9963fab99700135Misha Brukman unsigned FirstOut = inputs.size(); 39822108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) 39922108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::advance(OutputArgBegin, inputs.size()); 40004229c192bc153210e8ee8a18eb28d7f1ec21bfeChris Lattner 40122108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Reload the outputs passed in by reference 402b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 40322108fac63eac53d1a23b781a9963fab99700135Misha Brukman Value *Output = 0; 40422108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 40522108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::vector<Value*> Indices; 40622108fac63eac53d1a23b781a9963fab99700135Misha Brukman Indices.push_back(Constant::getNullValue(Type::UIntTy)); 40722108fac63eac53d1a23b781a9963fab99700135Misha Brukman Indices.push_back(ConstantUInt::get(Type::UIntTy, FirstOut + i)); 40822108fac63eac53d1a23b781a9963fab99700135Misha Brukman GetElementPtrInst *GEP 40922108fac63eac53d1a23b781a9963fab99700135Misha Brukman = new GetElementPtrInst(Struct, Indices, 41022108fac63eac53d1a23b781a9963fab99700135Misha Brukman "gep_reload_" + outputs[i]->getName(), 0); 41122108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(GEP); 41222108fac63eac53d1a23b781a9963fab99700135Misha Brukman Output = GEP; 41322108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else { 41422108fac63eac53d1a23b781a9963fab99700135Misha Brukman Output = ReloadOutputs[i]; 41522108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 41622108fac63eac53d1a23b781a9963fab99700135Misha Brukman LoadInst *load = new LoadInst(Output, outputs[i]->getName()+".reload"); 417b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner codeReplacer->getInstList().push_back(load); 418b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner std::vector<User*> Users(outputs[i]->use_begin(), outputs[i]->use_end()); 419b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (unsigned u = 0, e = Users.size(); u != e; ++u) { 420b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner Instruction *inst = cast<Instruction>(Users[u]); 421b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner if (!BlocksToExtract.count(inst->getParent())) 422b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner inst->replaceUsesOfWith(outputs[i], load); 423e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 424e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 42512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 426e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Now we can emit a switch statement using the call as a value. 427346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner SwitchInst *TheSwitch = 428346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner new SwitchInst(ConstantUInt::getNullValue(Type::UShortTy), 429346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner codeReplacer, codeReplacer); 430e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 431e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Since there may be multiple exits from the original region, make the new 43212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // function return an unsigned, switch on that number. This loop iterates 43312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // over all of the blocks in the extracted region, updating any terminator 43412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // instructions in the to-be-extracted region that branch to blocks that are 43512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // not in the region to be extracted. 43612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner std::map<BasicBlock*, BasicBlock*> ExitBlockMap; 43712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 438e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman unsigned switchVal = 0; 4390e06674287b15696f66a65f20f2ba99137b29213Chris Lattner for (std::set<BasicBlock*>::const_iterator i = BlocksToExtract.begin(), 4400e06674287b15696f66a65f20f2ba99137b29213Chris Lattner e = BlocksToExtract.end(); i != e; ++i) { 44112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner TerminatorInst *TI = (*i)->getTerminator(); 44212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 44312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner if (!BlocksToExtract.count(TI->getSuccessor(i))) { 44412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner BasicBlock *OldTarget = TI->getSuccessor(i); 44512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // add a new basic block which returns the appropriate value 44612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; 44712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner if (!NewTarget) { 44812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // If we don't already have an exit stub for this non-extracted 44912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // destination, create one now! 45012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner NewTarget = new BasicBlock(OldTarget->getName() + ".exitStub", 45112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner newFunction); 452346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner unsigned SuccNum = switchVal++; 453346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 454346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner Value *brVal = 0; 455346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 456346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 457346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 1: break; // No value needed. 458346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 2: // Conditional branch, return a bool 459346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner brVal = SuccNum ? ConstantBool::False : ConstantBool::True; 460346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 461346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner default: 462346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner brVal = ConstantUInt::get(Type::UShortTy, SuccNum); 463346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 464346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner } 46512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 46612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner ReturnInst *NTRet = new ReturnInst(brVal, NewTarget); 46712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 46812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // Update the switch instruction. 469346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->addCase(ConstantUInt::get(Type::UShortTy, SuccNum), 470346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner OldTarget); 47112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 47212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // Restore values just before we exit 47304229c192bc153210e8ee8a18eb28d7f1ec21bfeChris Lattner Function::aiterator OAI = OutputArgBegin; 47422108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned out = 0, e = outputs.size(); out != e; ++out) { 47522108fac63eac53d1a23b781a9963fab99700135Misha Brukman // For an invoke, the normal destination is the only one that is 47622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // dominated by the result of the invocation 47722108fac63eac53d1a23b781a9963fab99700135Misha Brukman BasicBlock *DefBlock = cast<Instruction>(outputs[out])->getParent(); 47822108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (InvokeInst *Invoke = dyn_cast<InvokeInst>(outputs[out])) 47922108fac63eac53d1a23b781a9963fab99700135Misha Brukman DefBlock = Invoke->getNormalDest(); 48022108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!DS || DS->dominates(DefBlock, TI->getParent())) 48122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 48222108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::vector<Value*> Indices; 48322108fac63eac53d1a23b781a9963fab99700135Misha Brukman Indices.push_back(Constant::getNullValue(Type::UIntTy)); 48422108fac63eac53d1a23b781a9963fab99700135Misha Brukman Indices.push_back(ConstantUInt::get(Type::UIntTy,FirstOut+out)); 48522108fac63eac53d1a23b781a9963fab99700135Misha Brukman GetElementPtrInst *GEP = 48622108fac63eac53d1a23b781a9963fab99700135Misha Brukman new GetElementPtrInst(OAI, Indices, 48722108fac63eac53d1a23b781a9963fab99700135Misha Brukman "gep_" + outputs[out]->getName(), 48822108fac63eac53d1a23b781a9963fab99700135Misha Brukman NTRet); 48922108fac63eac53d1a23b781a9963fab99700135Misha Brukman new StoreInst(outputs[out], GEP, NTRet); 49022108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else 49122108fac63eac53d1a23b781a9963fab99700135Misha Brukman new StoreInst(outputs[out], OAI, NTRet); 49222108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Advance output iterator even if we don't emit a store 49322108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) ++OAI; 49422108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 495e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 4960e06674287b15696f66a65f20f2ba99137b29213Chris Lattner 49712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // rewrite the original branch instruction with this new target 49812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner TI->setSuccessor(i, NewTarget); 49912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner } 500e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 50165826bf435620824763af926270cf0efdc82ea5aChris Lattner 5025b01e298ed42d5ce6aaf7634618b5e1769766b21Chris Lattner // Now that we've done the deed, simplify the switch instruction. 503346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 504346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 50522108fac63eac53d1a23b781a9963fab99700135Misha Brukman // There is only 1 successor (the block containing the switch itself), which 50622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // means that previously this was the last part of the function, and hence 50722108fac63eac53d1a23b781a9963fab99700135Misha Brukman // this should be rewritten as a `ret' 50822108fac63eac53d1a23b781a9963fab99700135Misha Brukman 50922108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Check if the function should return a value 51022108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (TheSwitch->getParent()->getParent()->getReturnType() != Type::VoidTy && 51122108fac63eac53d1a23b781a9963fab99700135Misha Brukman TheSwitch->getParent()->getParent()->getReturnType() == 51222108fac63eac53d1a23b781a9963fab99700135Misha Brukman TheSwitch->getCondition()->getType()) 51322108fac63eac53d1a23b781a9963fab99700135Misha Brukman // return what we have 51422108fac63eac53d1a23b781a9963fab99700135Misha Brukman new ReturnInst(TheSwitch->getCondition(), TheSwitch); 51522108fac63eac53d1a23b781a9963fab99700135Misha Brukman else 51622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // just return 51722108fac63eac53d1a23b781a9963fab99700135Misha Brukman new ReturnInst(0, TheSwitch); 51822108fac63eac53d1a23b781a9963fab99700135Misha Brukman 51922108fac63eac53d1a23b781a9963fab99700135Misha Brukman TheSwitch->getParent()->getInstList().erase(TheSwitch); 520346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 521346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 1: 522346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // Only a single destination, change the switch into an unconditional 523346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // branch. 524346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner new BranchInst(TheSwitch->getSuccessor(1), TheSwitch); 525346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->getParent()->getInstList().erase(TheSwitch); 526346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 527346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 2: 528346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner new BranchInst(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), 529346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner call, TheSwitch); 530346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->getParent()->getInstList().erase(TheSwitch); 531346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 532346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner default: 533346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // Otherwise, make the default destination of the switch instruction be one 534346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // of the other successors. 535346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->setOperand(0, call); 536346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->setSuccessor(0, TheSwitch->getSuccessor(NumExitBlocks)); 537346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->removeCase(NumExitBlocks); // Remove redundant case 538346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 53965826bf435620824763af926270cf0efdc82ea5aChris Lattner } 540e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 541e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 542bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::moveCodeToFunction(Function *newFunction) { 543bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function *oldFunc = (*BlocksToExtract.begin())->getParent(); 544bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); 545bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); 546bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 547bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner for (std::set<BasicBlock*>::const_iterator i = BlocksToExtract.begin(), 548bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner e = BlocksToExtract.end(); i != e; ++i) { 549bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Delete the basic block from the old function, and the list of blocks 550bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner oldBlocks.remove(*i); 551bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 552bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Insert this basic block into the new function 553bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner newBlocks.push_back(*i); 554bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 555bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner} 556e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 557e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// ExtractRegion - Removes a loop from a function, replaces it with a call to 558e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// new function. Returns pointer to the new function. 559e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 560e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// algorithm: 561e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 562e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// find inputs and outputs for the region 563e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 564e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// for inputs: add to function as args, map input instr* to arg# 565e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// for outputs: add allocas for scalars, 566e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// add to func as args, map output instr* to arg# 567e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 568e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// rewrite func to use argument #s instead of instr* 569e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 570e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// for each scalar output in the function: at every exit, store intermediate 571e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// computed result back into memory. 572e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 573e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanFunction *CodeExtractor::ExtractCodeRegion(const std::vector<BasicBlock*> &code) 574e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman{ 57522108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!isEligible(code)) 57622108fac63eac53d1a23b781a9963fab99700135Misha Brukman return 0; 57722108fac63eac53d1a23b781a9963fab99700135Misha Brukman 578e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 1) Find inputs, outputs 579e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 2) Construct new function 580e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * Add allocas for defs, pass as args by reference 581e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * Pass in uses as args 582e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 3) Move code region, add call instr to func 5830e06674287b15696f66a65f20f2ba99137b29213Chris Lattner // 5840e06674287b15696f66a65f20f2ba99137b29213Chris Lattner BlocksToExtract.insert(code.begin(), code.end()); 585e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 586e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values inputs, outputs; 587e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 588e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Assumption: this is a single-entry code region, and the header is the first 5890de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner // block in the region. 590e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *header = code[0]; 591bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 5920de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (unsigned i = 1, e = code.size(); i != e; ++i) 5930de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (pred_iterator PI = pred_begin(code[i]), E = pred_end(code[i]); 5940de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner PI != E; ++PI) 5950de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner assert(BlocksToExtract.count(*PI) && 5960de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner "No blocks in this region may have entries from outside the region" 5970de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner " except for the first block!"); 5980de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner 599e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // If we have to split PHI nodes, do so now. 600e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner severSplitPHINodes(header); 601e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 602e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction = header->getParent(); 603e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 604e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This takes place of the original loop 605e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *codeReplacer = new BasicBlock("codeRepl", oldFunction); 606e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 607e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // The new function needs a root node because other nodes can branch to the 608bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // head of the region, but the entry node of a function cannot have preds. 609e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newFuncRoot = new BasicBlock("newFuncRoot"); 610e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newFuncRoot->getInstList().push_back(new BranchInst(header)); 611e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 612bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Find inputs to, outputs from the code region. 613bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner findInputsOutputs(inputs, outputs); 614bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 615bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Construct new function based on inputs/outputs & add allocas for all defs. 616e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Function *newFunction = constructFunction(inputs, outputs, header, 6175cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner newFuncRoot, 6180de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner codeReplacer, oldFunction, 6190de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner oldFunction->getParent()); 620e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 6210e06674287b15696f66a65f20f2ba99137b29213Chris Lattner emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); 622e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 6230e06674287b15696f66a65f20f2ba99137b29213Chris Lattner moveCodeToFunction(newFunction); 624e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 625e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the PHI nodes in the header block, and change any 6265cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // references to the old incoming edge to be the new incoming edge. 627e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (BasicBlock::iterator I = header->begin(); 6285cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) 6295cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 6305cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner if (!BlocksToExtract.count(PN->getIncomingBlock(i))) 6315cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner PN->setIncomingBlock(i, newFuncRoot); 6325cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner 633d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // Look at all successors of the codeReplacer block. If any of these blocks 634d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // had PHI nodes in them, we need to update the "from" block to be the code 635d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // replacer, not the original block in the extracted region. 636d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner std::vector<BasicBlock*> Succs(succ_begin(codeReplacer), 637d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner succ_end(codeReplacer)); 638d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner for (unsigned i = 0, e = Succs.size(); i != e; ++i) 639d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner for (BasicBlock::iterator I = Succs[i]->begin(); 640d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) 641d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 642d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) 643d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner PN->setIncomingBlock(i, codeReplacer); 644d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner 645e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner //std::cerr << "NEW FUNCTION: " << *newFunction; 646e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // verifyFunction(*newFunction); 647e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 648e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // std::cerr << "OLD FUNCTION: " << *oldFunction; 649e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // verifyFunction(*oldFunction); 650d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner 651ffada9327301094411146627cf6bc16cd517585dChris Lattner DEBUG(if (verifyFunction(*newFunction)) abort()); 652e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 653e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 654e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 65522108fac63eac53d1a23b781a9963fab99700135Misha Brukmanbool CodeExtractor::isEligible(const std::vector<BasicBlock*> &code) { 656bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Deny code region if it contains allocas or vastarts. 65722108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (std::vector<BasicBlock*>::const_iterator BB = code.begin(), e=code.end(); 65822108fac63eac53d1a23b781a9963fab99700135Misha Brukman BB != e; ++BB) 65922108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (BasicBlock::const_iterator I = (*BB)->begin(), Ie = (*BB)->end(); 66022108fac63eac53d1a23b781a9963fab99700135Misha Brukman I != Ie; ++I) 66122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (isa<AllocaInst>(*I)) 66222108fac63eac53d1a23b781a9963fab99700135Misha Brukman return false; 663bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner else if (const CallInst *CI = dyn_cast<CallInst>(I)) 664bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (const Function *F = CI->getCalledFunction()) 665bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (F->getIntrinsicID() == Intrinsic::vastart) 666bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return false; 66722108fac63eac53d1a23b781a9963fab99700135Misha Brukman return true; 66822108fac63eac53d1a23b781a9963fab99700135Misha Brukman} 66922108fac63eac53d1a23b781a9963fab99700135Misha Brukman 67022108fac63eac53d1a23b781a9963fab99700135Misha Brukman 6710256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// ExtractCodeRegion - slurp a sequence of basic blocks into a brand new 6720256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// function 6730256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// 674b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris LattnerFunction* llvm::ExtractCodeRegion(DominatorSet &DS, 67522108fac63eac53d1a23b781a9963fab99700135Misha Brukman const std::vector<BasicBlock*> &code, 67622108fac63eac53d1a23b781a9963fab99700135Misha Brukman bool AggregateArgs) { 67722108fac63eac53d1a23b781a9963fab99700135Misha Brukman return CodeExtractor(&DS, AggregateArgs).ExtractCodeRegion(code); 6780256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman} 6790256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman 680b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// ExtractBasicBlock - slurp a natural loop into a brand new function 681b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// 68222108fac63eac53d1a23b781a9963fab99700135Misha BrukmanFunction* llvm::ExtractLoop(DominatorSet &DS, Loop *L, bool AggregateArgs) { 68322108fac63eac53d1a23b781a9963fab99700135Misha Brukman return CodeExtractor(&DS, AggregateArgs).ExtractCodeRegion(L->getBlocks()); 684e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 685e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 686b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// ExtractBasicBlock - slurp a basic block into a brand new function 687b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// 68822108fac63eac53d1a23b781a9963fab99700135Misha BrukmanFunction* llvm::ExtractBasicBlock(BasicBlock *BB, bool AggregateArgs) { 689b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman std::vector<BasicBlock*> Blocks; 690b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman Blocks.push_back(BB); 69122108fac63eac53d1a23b781a9963fab99700135Misha Brukman return CodeExtractor(0, AggregateArgs).ExtractCodeRegion(Blocks); 692b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman} 693