CodeExtractor.cpp revision ecb7a77885b174cf4d001a9b48533b3979e7810d
1e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman//===- CodeExtractor.cpp - Pull code region into a new function -----------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha 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. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha 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" 27551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 289133fe28954d498fc4de13064c7d65bd811de02cReid Spencer#include "llvm/Support/Compiler.h" 29551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 30551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/StringExtras.h" 31e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include <algorithm> 320e06674287b15696f66a65f20f2ba99137b29213Chris Lattner#include <set> 33e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanusing namespace llvm; 34e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 3522108fac63eac53d1a23b781a9963fab99700135Misha Brukman// Provide a command-line option to aggregate function arguments into a struct 3622108fac63eac53d1a23b781a9963fab99700135Misha Brukman// for functions produced by the code extrator. This is useful when converting 3722108fac63eac53d1a23b781a9963fab99700135Misha Brukman// extracted functions to pthread-based code, as only one argument (void*) can 3822108fac63eac53d1a23b781a9963fab99700135Misha Brukman// be passed in to pthread_create(). 3922108fac63eac53d1a23b781a9963fab99700135Misha Brukmanstatic cl::opt<bool> 4022108fac63eac53d1a23b781a9963fab99700135Misha BrukmanAggregateArgsOpt("aggregate-extracted-args", cl::Hidden, 4122108fac63eac53d1a23b781a9963fab99700135Misha Brukman cl::desc("Aggregate arguments to code-extracted functions")); 4222108fac63eac53d1a23b781a9963fab99700135Misha Brukman 43e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmannamespace { 449133fe28954d498fc4de13064c7d65bd811de02cReid Spencer class VISIBILITY_HIDDEN CodeExtractor { 45e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman typedef std::vector<Value*> Values; 460e06674287b15696f66a65f20f2ba99137b29213Chris Lattner std::set<BasicBlock*> BlocksToExtract; 47b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner DominatorSet *DS; 4822108fac63eac53d1a23b781a9963fab99700135Misha Brukman bool AggregateArgs; 49346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner unsigned NumExitBlocks; 50346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner const Type *RetTy; 51e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman public: 5222108fac63eac53d1a23b781a9963fab99700135Misha Brukman CodeExtractor(DominatorSet *ds = 0, bool AggArgs = false) 53e74c73cf46ce1c158da130c9ab733fdcaadb0df6Misha Brukman : DS(ds), AggregateArgs(AggArgs||AggregateArgsOpt), NumExitBlocks(~0U) {} 54b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 55e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *ExtractCodeRegion(const std::vector<BasicBlock*> &code); 56e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 5722108fac63eac53d1a23b781a9963fab99700135Misha Brukman bool isEligible(const std::vector<BasicBlock*> &code); 5822108fac63eac53d1a23b781a9963fab99700135Misha Brukman 59e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman private: 60bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// definedInRegion - Return true if the specified value is defined in the 61bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// extracted region. 62bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner bool definedInRegion(Value *V) const { 63bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 64bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (BlocksToExtract.count(I->getParent())) 65bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return true; 66bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return false; 67bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 68fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 69bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// definedInCaller - Return true if the specified value is defined in the 70bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// function being code extracted, but not in the region being extracted. 71bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// These values must be passed in as live-ins to the function. 72bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner bool definedInCaller(Value *V) const { 73bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (isa<Argument>(V)) return true; 74bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 75bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (!BlocksToExtract.count(I->getParent())) 76bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return true; 77bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return false; 78bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 79bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 80bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner void severSplitPHINodes(BasicBlock *&Header); 81d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner void splitReturnBlocks(); 82bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner void findInputsOutputs(Values &inputs, Values &outputs); 83e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 84e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *constructFunction(const Values &inputs, 85e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Values &outputs, 865cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner BasicBlock *header, 87e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, BasicBlock *newHeader, 88e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction, Module *M); 89e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 900e06674287b15696f66a65f20f2ba99137b29213Chris Lattner void moveCodeToFunction(Function *newFunction); 91e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 92e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void emitCallAndSwitchStatement(Function *newFunction, 93e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 94e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 95e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &outputs); 96e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 97e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman }; 98e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 99e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 100bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// severSplitPHINodes - If a PHI node has multiple inputs from outside of the 101bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// region, we need to split the entry block of the region so that the PHI node 102bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// is easier to deal with. 103bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::severSplitPHINodes(BasicBlock *&Header) { 104e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner bool HasPredsFromRegion = false; 105e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner unsigned NumPredsOutsideRegion = 0; 106e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 107ecb7a77885b174cf4d001a9b48533b3979e7810dDan Gohman if (Header != &Header->getParent()->getEntryBlock()) { 108e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *PN = dyn_cast<PHINode>(Header->begin()); 109e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (!PN) return; // No PHI nodes. 110e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 111e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // If the header node contains any PHI nodes, check to see if there is more 112e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // than one entry from outside the region. If so, we need to sever the 113e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // header block into two. 114e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 115e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) 116e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner HasPredsFromRegion = true; 117e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner else 118e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner ++NumPredsOutsideRegion; 119e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 120e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // If there is one (or fewer) predecessor from outside the region, we don't 121e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // need to do anything special. 122e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (NumPredsOutsideRegion <= 1) return; 123e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 124bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 125e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Otherwise, we need to split the header block into two pieces: one 126e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // containing PHI nodes merging values from outside of the region, and a 127e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // second that contains all of the code for the block and merges back any 128e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // incoming values from inside of the region. 129e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BasicBlock::iterator AfterPHIs = Header->begin(); 130e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner while (isa<PHINode>(AfterPHIs)) ++AfterPHIs; 131e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BasicBlock *NewBB = Header->splitBasicBlock(AfterPHIs, 132e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Header->getName()+".ce"); 133e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 134e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // We only want to code extract the second block now, and it becomes the new 135e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // header of the region. 136e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BasicBlock *OldPred = Header; 137e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BlocksToExtract.erase(OldPred); 138e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BlocksToExtract.insert(NewBB); 139e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Header = NewBB; 140e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 141e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, update dominator sets. The blocks that dominate the new one are the 142e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // blocks that dominate TIBB plus the new block itself. 143e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (DS) { 144e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner DominatorSet::DomSetType DomSet = DS->getDominators(OldPred); 145e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner DomSet.insert(NewBB); // A block always dominates itself. 146e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner DS->addBasicBlock(NewBB, DomSet); 147e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 148e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Additionally, NewBB dominates all blocks in the function that are 149e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // dominated by OldPred. 150e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Function *F = Header->getParent(); 151e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 152e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (DS->properlyDominates(OldPred, I)) 153e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner DS->addDominator(I, NewBB); 154e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 155bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 156e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, now we need to adjust the PHI nodes and any branches from within the 157e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // region to go to the new header block instead of the old header block. 158e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (HasPredsFromRegion) { 159e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *PN = cast<PHINode>(OldPred->begin()); 160e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the predecessors of OldPred that are in the region, 161e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // changing them to branch to NewBB instead. 162e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 163e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) { 164e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner TerminatorInst *TI = PN->getIncomingBlock(i)->getTerminator(); 165e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner TI->replaceUsesOfWith(OldPred, NewBB); 166e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 167e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 168e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, everthing within the region is now branching to the right block, we 169e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // just have to update the PHI nodes now, inserting PHI nodes into NewBB. 1702da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { 1712da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(AfterPHIs); 172e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Create a new PHI node in the new region, which has an incoming value 173e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // from OldPred of PN. 174e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".ce", 175e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner NewBB->begin()); 176e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner NewPN->addIncoming(PN, OldPred); 177e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 178e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the incoming value in PN, moving them to NewPN if they 179e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // are from the extracted region. 180e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { 181e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) { 182e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); 183e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PN->removeIncomingValue(i); 184e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner --i; 185e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 186e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 187e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 188e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 189d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner} 190e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 191d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattnervoid CodeExtractor::splitReturnBlocks() { 192d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner for (std::set<BasicBlock*>::iterator I = BlocksToExtract.begin(), 193d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner E = BlocksToExtract.end(); I != E; ++I) 194d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>((*I)->getTerminator())) 195d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner (*I)->splitBasicBlock(RI, (*I)->getName()+".ret"); 196bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner} 197bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 198bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner// findInputsOutputs - Find inputs to, outputs from the code region. 199bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner// 200bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::findInputsOutputs(Values &inputs, Values &outputs) { 201346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner std::set<BasicBlock*> ExitBlocks; 202fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman for (std::set<BasicBlock*>::const_iterator ci = BlocksToExtract.begin(), 2030e06674287b15696f66a65f20f2ba99137b29213Chris Lattner ce = BlocksToExtract.end(); ci != ce; ++ci) { 204e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *BB = *ci; 205bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 2060de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 2070de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner // If a used value is defined outside the region, it's an input. If an 2080de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner // instruction is used outside the region, it's an output. 209bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner for (User::op_iterator O = I->op_begin(), E = I->op_end(); O != E; ++O) 210bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (definedInCaller(*O)) 211bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner inputs.push_back(*O); 212fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 213bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Consider uses of this instruction (outputs). 2140de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 2150de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner UI != E; ++UI) 216bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (!definedInRegion(*UI)) { 217b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner outputs.push_back(I); 218b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner break; 219b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner } 2200de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner } // for: insts 221346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 222bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Keep track of the exit blocks from the region. 223346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TerminatorInst *TI = BB->getTerminator(); 224346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 225346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner if (!BlocksToExtract.count(TI->getSuccessor(i))) 226346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner ExitBlocks.insert(TI->getSuccessor(i)); 2270de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner } // for: basic blocks 228346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 229346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner NumExitBlocks = ExitBlocks.size(); 230587992721c3112c94000722941748cf46cd0bce6Chris Lattner 231587992721c3112c94000722941748cf46cd0bce6Chris Lattner // Eliminate duplicates. 232587992721c3112c94000722941748cf46cd0bce6Chris Lattner std::sort(inputs.begin(), inputs.end()); 233587992721c3112c94000722941748cf46cd0bce6Chris Lattner inputs.erase(std::unique(inputs.begin(), inputs.end()), inputs.end()); 234587992721c3112c94000722941748cf46cd0bce6Chris Lattner std::sort(outputs.begin(), outputs.end()); 235587992721c3112c94000722941748cf46cd0bce6Chris Lattner outputs.erase(std::unique(outputs.begin(), outputs.end()), outputs.end()); 236e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 237e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 238e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// constructFunction - make a function based on inputs and outputs, as follows: 239e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// f(in0, ..., inN, out0, ..., outN) 240e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 241e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanFunction *CodeExtractor::constructFunction(const Values &inputs, 242e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Values &outputs, 2435cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner BasicBlock *header, 244e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, 245e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 2465cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner Function *oldFunction, 2475cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner Module *M) { 2480d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "inputs: " << inputs.size() << "\n"; 2490d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "outputs: " << outputs.size() << "\n"; 250e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 251e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This function returns unsigned, outputs will go back by reference. 252346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 253346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 254346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 1: RetTy = Type::VoidTy; break; 2554fe16d607d11e29d742208894909733f5ad01f8fReid Spencer case 2: RetTy = Type::Int1Ty; break; 256c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer default: RetTy = Type::Int16Ty; break; 257346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner } 258346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 259e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<const Type*> paramTy; 260e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 261e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Add the types of the input values to the function's argument list 262e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Values::const_iterator i = inputs.begin(), 263e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = inputs.end(); i != e; ++i) { 264e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Value *value = *i; 2650d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "value used in func: " << *value << "\n"; 266e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman paramTy.push_back(value->getType()); 267e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 268e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 269b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Add the types of the output values to the function's argument list. 270b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (Values::const_iterator I = outputs.begin(), E = outputs.end(); 271b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner I != E; ++I) { 2720d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "instr used in func: " << **I << "\n"; 27322108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) 27422108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.push_back((*I)->getType()); 27522108fac63eac53d1a23b781a9963fab99700135Misha Brukman else 27622108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.push_back(PointerType::get((*I)->getType())); 277e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 278e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 2790d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "Function type: " << *RetTy << " f("; 2800d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling for (std::vector<const Type*>::iterator i = paramTy.begin(), 2810d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling e = paramTy.end(); i != e; ++i) 2820d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << **i << ", "; 2830d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << ")\n"; 284e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 28522108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 28622108fac63eac53d1a23b781a9963fab99700135Misha Brukman PointerType *StructPtr = PointerType::get(StructType::get(paramTy)); 28722108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.clear(); 28822108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.push_back(StructPtr); 28922108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 290346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner const FunctionType *funcType = FunctionType::get(RetTy, paramTy, false); 291e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 292e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Create the new function 293e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *newFunction = new Function(funcType, 294e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman GlobalValue::InternalLinkage, 295587992721c3112c94000722941748cf46cd0bce6Chris Lattner oldFunction->getName() + "_" + 296587992721c3112c94000722941748cf46cd0bce6Chris Lattner header->getName(), M); 297e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newFunction->getBasicBlockList().push_back(newRootNode); 298e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 299b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Create an iterator to name all of the arguments we inserted. 300e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner Function::arg_iterator AI = newFunction->arg_begin(); 301b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 302b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Rewrite all users of the inputs in the extracted region to use the 30322108fac63eac53d1a23b781a9963fab99700135Misha Brukman // arguments (or appropriate addressing into struct) instead. 30422108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 30522108fac63eac53d1a23b781a9963fab99700135Misha Brukman Value *RewriteVal; 30622108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 30720066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner Value *Idx0 = Constant::getNullValue(Type::Int32Ty); 30820066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner Value *Idx1 = ConstantInt::get(Type::Int32Ty, i); 30922108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::string GEPname = "gep_" + inputs[i]->getName(); 31022108fac63eac53d1a23b781a9963fab99700135Misha Brukman TerminatorInst *TI = newFunction->begin()->getTerminator(); 31120066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner GetElementPtrInst *GEP = new GetElementPtrInst(AI, Idx0, Idx1, 31220066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner GEPname, TI); 31322108fac63eac53d1a23b781a9963fab99700135Misha Brukman RewriteVal = new LoadInst(GEP, "load" + GEPname, TI); 31422108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else 31522108fac63eac53d1a23b781a9963fab99700135Misha Brukman RewriteVal = AI++; 31622108fac63eac53d1a23b781a9963fab99700135Misha Brukman 317e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(inputs[i]->use_begin(), inputs[i]->use_end()); 318e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<User*>::iterator use = Users.begin(), useE = Users.end(); 319ffada9327301094411146627cf6bc16cd517585dChris Lattner use != useE; ++use) 320ffada9327301094411146627cf6bc16cd517585dChris Lattner if (Instruction* inst = dyn_cast<Instruction>(*use)) 3210e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (BlocksToExtract.count(inst->getParent())) 32222108fac63eac53d1a23b781a9963fab99700135Misha Brukman inst->replaceUsesOfWith(inputs[i], RewriteVal); 323e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 324e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 32522108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Set names for input and output arguments. 32622108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) { 327e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner AI = newFunction->arg_begin(); 32822108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) 32922108fac63eac53d1a23b781a9963fab99700135Misha Brukman AI->setName(inputs[i]->getName()); 33022108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) 331fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman AI->setName(outputs[i]->getName()+".out"); 33222108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 333b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 334e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Rewrite branches to basic blocks outside of the loop to new dummy blocks 335e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // within the new function. This must be done before we lose track of which 336e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // blocks were originally in the code region. 337e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(header->use_begin(), header->use_end()); 3385cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner for (unsigned i = 0, e = Users.size(); i != e; ++i) 3395cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // The BasicBlock which contains the branch is not in the region 3405cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // modify the branch target to a new block 3415cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Users[i])) 3425cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner if (!BlocksToExtract.count(TI->getParent()) && 3435cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner TI->getParent()->getParent() == oldFunction) 3445cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner TI->replaceUsesOfWith(header, newHeader); 345e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 346e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 347e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 348e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 349bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// emitCallAndSwitchStatement - This method sets up the caller side by adding 350bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// the call instruction, splitting any PHI nodes in the header block as 351bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// necessary. 352bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor:: 353bf749367cb2aef7072ee36a9eb681b35aab51921Chris LattneremitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, 354bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Values &inputs, Values &outputs) { 355bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Emit a call to the new function, passing in: *pointer to struct (if 356bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // aggregating parameters), or plan inputs and allocated memory for outputs 35722108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::vector<Value*> params, StructValues, ReloadOutputs; 35822108fac63eac53d1a23b781a9963fab99700135Misha Brukman 35922108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Add inputs as params, or to be filled into the struct 36022108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (Values::iterator i = inputs.begin(), e = inputs.end(); i != e; ++i) 36122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) 36222108fac63eac53d1a23b781a9963fab99700135Misha Brukman StructValues.push_back(*i); 36322108fac63eac53d1a23b781a9963fab99700135Misha Brukman else 36422108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(*i); 36522108fac63eac53d1a23b781a9963fab99700135Misha Brukman 36622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Create allocas for the outputs 36722108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (Values::iterator i = outputs.begin(), e = outputs.end(); i != e; ++i) { 36822108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 36922108fac63eac53d1a23b781a9963fab99700135Misha Brukman StructValues.push_back(*i); 37022108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else { 37122108fac63eac53d1a23b781a9963fab99700135Misha Brukman AllocaInst *alloca = 37222108fac63eac53d1a23b781a9963fab99700135Misha Brukman new AllocaInst((*i)->getType(), 0, (*i)->getName()+".loc", 37322108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getParent()->begin()->begin()); 37422108fac63eac53d1a23b781a9963fab99700135Misha Brukman ReloadOutputs.push_back(alloca); 37522108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(alloca); 37622108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 37722108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 37822108fac63eac53d1a23b781a9963fab99700135Misha Brukman 37922108fac63eac53d1a23b781a9963fab99700135Misha Brukman AllocaInst *Struct = 0; 38022108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 38122108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::vector<const Type*> ArgTypes; 38222108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (Values::iterator v = StructValues.begin(), 38322108fac63eac53d1a23b781a9963fab99700135Misha Brukman ve = StructValues.end(); v != ve; ++v) 38422108fac63eac53d1a23b781a9963fab99700135Misha Brukman ArgTypes.push_back((*v)->getType()); 38522108fac63eac53d1a23b781a9963fab99700135Misha Brukman 38622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Allocate a struct at the beginning of this function 38722108fac63eac53d1a23b781a9963fab99700135Misha Brukman Type *StructArgTy = StructType::get(ArgTypes); 388fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman Struct = 389fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman new AllocaInst(StructArgTy, 0, "structArg", 39022108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getParent()->begin()->begin()); 39122108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(Struct); 39222108fac63eac53d1a23b781a9963fab99700135Misha Brukman 39322108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 39420066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner Value *Idx0 = Constant::getNullValue(Type::Int32Ty); 39520066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner Value *Idx1 = ConstantInt::get(Type::Int32Ty, i); 39622108fac63eac53d1a23b781a9963fab99700135Misha Brukman GetElementPtrInst *GEP = 39720066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner new GetElementPtrInst(Struct, Idx0, Idx1, 398fe3a093bc61ab11dd2c6c9e1e60f42f0a7ef48f3Alkis Evlogimenos "gep_" + StructValues[i]->getName()); 39922108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(GEP); 40022108fac63eac53d1a23b781a9963fab99700135Misha Brukman StoreInst *SI = new StoreInst(StructValues[i], GEP); 40122108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(SI); 40222108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 403fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman } 40422108fac63eac53d1a23b781a9963fab99700135Misha Brukman 40522108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Emit the call to the function 40693e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner CallInst *call = new CallInst(newFunction, ¶ms[0], params.size(), 407e74c73cf46ce1c158da130c9ab733fdcaadb0df6Misha Brukman NumExitBlocks > 1 ? "targetBlock" : ""); 40822108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(call); 40922108fac63eac53d1a23b781a9963fab99700135Misha Brukman 410e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner Function::arg_iterator OutputArgBegin = newFunction->arg_begin(); 41122108fac63eac53d1a23b781a9963fab99700135Misha Brukman unsigned FirstOut = inputs.size(); 41222108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) 41322108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::advance(OutputArgBegin, inputs.size()); 41404229c192bc153210e8ee8a18eb28d7f1ec21bfeChris Lattner 41522108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Reload the outputs passed in by reference 416b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 41722108fac63eac53d1a23b781a9963fab99700135Misha Brukman Value *Output = 0; 41822108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 41920066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner Value *Idx0 = Constant::getNullValue(Type::Int32Ty); 42020066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner Value *Idx1 = ConstantInt::get(Type::Int32Ty, FirstOut + i); 421fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman GetElementPtrInst *GEP 42220066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner = new GetElementPtrInst(Struct, Idx0, Idx1, 423fe3a093bc61ab11dd2c6c9e1e60f42f0a7ef48f3Alkis Evlogimenos "gep_reload_" + outputs[i]->getName()); 42422108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(GEP); 42522108fac63eac53d1a23b781a9963fab99700135Misha Brukman Output = GEP; 42622108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else { 42722108fac63eac53d1a23b781a9963fab99700135Misha Brukman Output = ReloadOutputs[i]; 42822108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 42922108fac63eac53d1a23b781a9963fab99700135Misha Brukman LoadInst *load = new LoadInst(Output, outputs[i]->getName()+".reload"); 430b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner codeReplacer->getInstList().push_back(load); 431b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner std::vector<User*> Users(outputs[i]->use_begin(), outputs[i]->use_end()); 432b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (unsigned u = 0, e = Users.size(); u != e; ++u) { 433b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner Instruction *inst = cast<Instruction>(Users[u]); 434b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner if (!BlocksToExtract.count(inst->getParent())) 435b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner inst->replaceUsesOfWith(outputs[i], load); 436e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 437e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 43812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 439e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Now we can emit a switch statement using the call as a value. 440346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner SwitchInst *TheSwitch = 441c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer new SwitchInst(ConstantInt::getNullValue(Type::Int16Ty), 442378805969ea928b91aa321746031a8f51667a783Chris Lattner codeReplacer, 0, codeReplacer); 443e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 444e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Since there may be multiple exits from the original region, make the new 44512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // function return an unsigned, switch on that number. This loop iterates 44612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // over all of the blocks in the extracted region, updating any terminator 44712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // instructions in the to-be-extracted region that branch to blocks that are 44812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // not in the region to be extracted. 44912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner std::map<BasicBlock*, BasicBlock*> ExitBlockMap; 45012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 451e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman unsigned switchVal = 0; 4520e06674287b15696f66a65f20f2ba99137b29213Chris Lattner for (std::set<BasicBlock*>::const_iterator i = BlocksToExtract.begin(), 4530e06674287b15696f66a65f20f2ba99137b29213Chris Lattner e = BlocksToExtract.end(); i != e; ++i) { 45412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner TerminatorInst *TI = (*i)->getTerminator(); 45512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 45612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner if (!BlocksToExtract.count(TI->getSuccessor(i))) { 45712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner BasicBlock *OldTarget = TI->getSuccessor(i); 45812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // add a new basic block which returns the appropriate value 45912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; 46012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner if (!NewTarget) { 46112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // If we don't already have an exit stub for this non-extracted 46212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // destination, create one now! 46312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner NewTarget = new BasicBlock(OldTarget->getName() + ".exitStub", 46412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner newFunction); 465346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner unsigned SuccNum = switchVal++; 466346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 467346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner Value *brVal = 0; 468346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 469346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 470346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 1: break; // No value needed. 471346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 2: // Conditional branch, return a bool 472579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer brVal = ConstantInt::get(Type::Int1Ty, !SuccNum); 473346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 474346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner default: 475c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer brVal = ConstantInt::get(Type::Int16Ty, SuccNum); 476346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 477346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner } 47812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 47912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner ReturnInst *NTRet = new ReturnInst(brVal, NewTarget); 48012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 48112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // Update the switch instruction. 482c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer TheSwitch->addCase(ConstantInt::get(Type::Int16Ty, SuccNum), 483346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner OldTarget); 48412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 48512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // Restore values just before we exit 486e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner Function::arg_iterator OAI = OutputArgBegin; 48722108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned out = 0, e = outputs.size(); out != e; ++out) { 48822108fac63eac53d1a23b781a9963fab99700135Misha Brukman // For an invoke, the normal destination is the only one that is 48922108fac63eac53d1a23b781a9963fab99700135Misha Brukman // dominated by the result of the invocation 49022108fac63eac53d1a23b781a9963fab99700135Misha Brukman BasicBlock *DefBlock = cast<Instruction>(outputs[out])->getParent(); 4919ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 4929ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner bool DominatesDef = true; 4939ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 49468c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner if (InvokeInst *Invoke = dyn_cast<InvokeInst>(outputs[out])) { 49522108fac63eac53d1a23b781a9963fab99700135Misha Brukman DefBlock = Invoke->getNormalDest(); 49668c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner 49768c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner // Make sure we are looking at the original successor block, not 49868c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner // at a newly inserted exit block, which won't be in the dominator 49968c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner // info. 50068c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner for (std::map<BasicBlock*, BasicBlock*>::iterator I = 50168c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner ExitBlockMap.begin(), E = ExitBlockMap.end(); I != E; ++I) 50268c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner if (DefBlock == I->second) { 50368c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner DefBlock = I->first; 50468c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner break; 50568c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner } 5069ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 5079ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner // In the extract block case, if the block we are extracting ends 5089ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner // with an invoke instruction, make sure that we don't emit a 5099ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner // store of the invoke value for the unwind block. 5109ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner if (!DS && DefBlock != OldTarget) 5119ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner DominatesDef = false; 51268c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner } 51368c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner 5149ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner if (DS) 5159ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner DominatesDef = DS->dominates(DefBlock, OldTarget); 5169ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 5179ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner if (DominatesDef) { 51822108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 51920066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner Value *Idx0 = Constant::getNullValue(Type::Int32Ty); 52020066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner Value *Idx1 = ConstantInt::get(Type::Int32Ty,FirstOut+out); 52122108fac63eac53d1a23b781a9963fab99700135Misha Brukman GetElementPtrInst *GEP = 52220066f936c56da106bd55de88eb51b7e6fd527cfChris Lattner new GetElementPtrInst(OAI, Idx0, Idx1, 523fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman "gep_" + outputs[out]->getName(), 52422108fac63eac53d1a23b781a9963fab99700135Misha Brukman NTRet); 52522108fac63eac53d1a23b781a9963fab99700135Misha Brukman new StoreInst(outputs[out], GEP, NTRet); 5269ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner } else { 52722108fac63eac53d1a23b781a9963fab99700135Misha Brukman new StoreInst(outputs[out], OAI, NTRet); 5289ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner } 5299ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner } 53022108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Advance output iterator even if we don't emit a store 53122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) ++OAI; 53222108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 533e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 5340e06674287b15696f66a65f20f2ba99137b29213Chris Lattner 53512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // rewrite the original branch instruction with this new target 53612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner TI->setSuccessor(i, NewTarget); 53712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner } 538e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 53965826bf435620824763af926270cf0efdc82ea5aChris Lattner 5405b01e298ed42d5ce6aaf7634618b5e1769766b21Chris Lattner // Now that we've done the deed, simplify the switch instruction. 541b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner const Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); 542346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 543346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 544b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner // There are no successors (the block containing the switch itself), which 54522108fac63eac53d1a23b781a9963fab99700135Misha Brukman // means that previously this was the last part of the function, and hence 54622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // this should be rewritten as a `ret' 547fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 54822108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Check if the function should return a value 549b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner if (OldFnRetTy == Type::VoidTy) { 550b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner new ReturnInst(0, TheSwitch); // Return void 551b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { 55222108fac63eac53d1a23b781a9963fab99700135Misha Brukman // return what we have 55322108fac63eac53d1a23b781a9963fab99700135Misha Brukman new ReturnInst(TheSwitch->getCondition(), TheSwitch); 554b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner } else { 555b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner // Otherwise we must have code extracted an unwind or something, just 556b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner // return whatever we want. 557b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner new ReturnInst(Constant::getNullValue(OldFnRetTy), TheSwitch); 558b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner } 55922108fac63eac53d1a23b781a9963fab99700135Misha Brukman 56022108fac63eac53d1a23b781a9963fab99700135Misha Brukman TheSwitch->getParent()->getInstList().erase(TheSwitch); 561346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 562346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 1: 563346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // Only a single destination, change the switch into an unconditional 564346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // branch. 565346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner new BranchInst(TheSwitch->getSuccessor(1), TheSwitch); 566346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->getParent()->getInstList().erase(TheSwitch); 567346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 568346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 2: 569346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner new BranchInst(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), 570346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner call, TheSwitch); 571346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->getParent()->getInstList().erase(TheSwitch); 572346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 573346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner default: 574346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // Otherwise, make the default destination of the switch instruction be one 575346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // of the other successors. 576346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->setOperand(0, call); 577346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->setSuccessor(0, TheSwitch->getSuccessor(NumExitBlocks)); 578346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->removeCase(NumExitBlocks); // Remove redundant case 579346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 58065826bf435620824763af926270cf0efdc82ea5aChris Lattner } 581e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 582e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 583bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::moveCodeToFunction(Function *newFunction) { 584bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function *oldFunc = (*BlocksToExtract.begin())->getParent(); 585bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); 586bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); 587bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 588bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner for (std::set<BasicBlock*>::const_iterator i = BlocksToExtract.begin(), 589bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner e = BlocksToExtract.end(); i != e; ++i) { 590bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Delete the basic block from the old function, and the list of blocks 591bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner oldBlocks.remove(*i); 592bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 593bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Insert this basic block into the new function 594bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner newBlocks.push_back(*i); 595bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 596bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner} 597e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 598e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// ExtractRegion - Removes a loop from a function, replaces it with a call to 599e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// new function. Returns pointer to the new function. 600e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 601e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// algorithm: 602e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 603e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// find inputs and outputs for the region 604e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 605fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// for inputs: add to function as args, map input instr* to arg# 606fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// for outputs: add allocas for scalars, 607e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// add to func as args, map output instr* to arg# 608e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 609e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// rewrite func to use argument #s instead of instr* 610e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 611fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// for each scalar output in the function: at every exit, store intermediate 612e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// computed result back into memory. 613e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 614b519efbafedb356a30a04a32c15a6b406779a997Chris LattnerFunction *CodeExtractor:: 615b519efbafedb356a30a04a32c15a6b406779a997Chris LattnerExtractCodeRegion(const std::vector<BasicBlock*> &code) { 61622108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!isEligible(code)) 61722108fac63eac53d1a23b781a9963fab99700135Misha Brukman return 0; 61822108fac63eac53d1a23b781a9963fab99700135Misha Brukman 619e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 1) Find inputs, outputs 620e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 2) Construct new function 621e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * Add allocas for defs, pass as args by reference 622e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * Pass in uses as args 623e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 3) Move code region, add call instr to func 6240e06674287b15696f66a65f20f2ba99137b29213Chris Lattner // 6250e06674287b15696f66a65f20f2ba99137b29213Chris Lattner BlocksToExtract.insert(code.begin(), code.end()); 626e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 627e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values inputs, outputs; 628e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 629e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Assumption: this is a single-entry code region, and the header is the first 6300de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner // block in the region. 631e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *header = code[0]; 632bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 6330de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (unsigned i = 1, e = code.size(); i != e; ++i) 6340de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (pred_iterator PI = pred_begin(code[i]), E = pred_end(code[i]); 6350de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner PI != E; ++PI) 6360de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner assert(BlocksToExtract.count(*PI) && 6370de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner "No blocks in this region may have entries from outside the region" 6380de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner " except for the first block!"); 639fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 640d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner // If we have to split PHI nodes or the entry block, do so now. 641e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner severSplitPHINodes(header); 642e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 643d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner // If we have any return instructions in the region, split those blocks so 644d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner // that the return is not in the region. 645d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner splitReturnBlocks(); 646d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner 647e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction = header->getParent(); 648e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 649e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This takes place of the original loop 650337772832bb93ed98ee1e93c584ac3f82d9ea959Chris Lattner BasicBlock *codeReplacer = new BasicBlock("codeRepl", oldFunction, header); 651e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 652e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // The new function needs a root node because other nodes can branch to the 653bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // head of the region, but the entry node of a function cannot have preds. 654e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newFuncRoot = new BasicBlock("newFuncRoot"); 655e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newFuncRoot->getInstList().push_back(new BranchInst(header)); 656e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 657bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Find inputs to, outputs from the code region. 658bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner findInputsOutputs(inputs, outputs); 659bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 660bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Construct new function based on inputs/outputs & add allocas for all defs. 661e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Function *newFunction = constructFunction(inputs, outputs, header, 662fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman newFuncRoot, 6630de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner codeReplacer, oldFunction, 6640de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner oldFunction->getParent()); 665e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 6660e06674287b15696f66a65f20f2ba99137b29213Chris Lattner emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); 667e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 6680e06674287b15696f66a65f20f2ba99137b29213Chris Lattner moveCodeToFunction(newFunction); 669e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 670e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the PHI nodes in the header block, and change any 6715cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // references to the old incoming edge to be the new incoming edge. 6722da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { 6732da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 6745cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 6755cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner if (!BlocksToExtract.count(PN->getIncomingBlock(i))) 6765cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner PN->setIncomingBlock(i, newFuncRoot); 6772da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer } 678fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 679d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // Look at all successors of the codeReplacer block. If any of these blocks 680d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // had PHI nodes in them, we need to update the "from" block to be the code 681d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // replacer, not the original block in the extracted region. 682d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner std::vector<BasicBlock*> Succs(succ_begin(codeReplacer), 683d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner succ_end(codeReplacer)); 684d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner for (unsigned i = 0, e = Succs.size(); i != e; ++i) 6852da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Succs[i]->begin(); isa<PHINode>(I); ++I) { 6862da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 687a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner std::set<BasicBlock*> ProcessedPreds; 688d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 689d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) 690a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner if (ProcessedPreds.insert(PN->getIncomingBlock(i)).second) 691a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner PN->setIncomingBlock(i, codeReplacer); 692a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner else { 693a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner // There were multiple entries in the PHI for this block, now there 694a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner // is only one, so remove the duplicated entries. 695a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner PN->removeIncomingValue(i, false); 696a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner --i; --e; 697a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner } 698a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner } 699fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 700e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "NEW FUNCTION: " << *newFunction; 701e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // verifyFunction(*newFunction); 702e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 703e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling // cerr << "OLD FUNCTION: " << *oldFunction; 704e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // verifyFunction(*oldFunction); 705d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner 706ffada9327301094411146627cf6bc16cd517585dChris Lattner DEBUG(if (verifyFunction(*newFunction)) abort()); 707e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 708e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 709e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 71022108fac63eac53d1a23b781a9963fab99700135Misha Brukmanbool CodeExtractor::isEligible(const std::vector<BasicBlock*> &code) { 711bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Deny code region if it contains allocas or vastarts. 71222108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (std::vector<BasicBlock*>::const_iterator BB = code.begin(), e=code.end(); 71322108fac63eac53d1a23b781a9963fab99700135Misha Brukman BB != e; ++BB) 71422108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (BasicBlock::const_iterator I = (*BB)->begin(), Ie = (*BB)->end(); 71522108fac63eac53d1a23b781a9963fab99700135Misha Brukman I != Ie; ++I) 71622108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (isa<AllocaInst>(*I)) 71722108fac63eac53d1a23b781a9963fab99700135Misha Brukman return false; 718bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner else if (const CallInst *CI = dyn_cast<CallInst>(I)) 719bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (const Function *F = CI->getCalledFunction()) 720bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (F->getIntrinsicID() == Intrinsic::vastart) 721bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return false; 72222108fac63eac53d1a23b781a9963fab99700135Misha Brukman return true; 72322108fac63eac53d1a23b781a9963fab99700135Misha Brukman} 72422108fac63eac53d1a23b781a9963fab99700135Misha Brukman 72522108fac63eac53d1a23b781a9963fab99700135Misha Brukman 7260256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// ExtractCodeRegion - slurp a sequence of basic blocks into a brand new 7270256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// function 7280256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// 729b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris LattnerFunction* llvm::ExtractCodeRegion(DominatorSet &DS, 73022108fac63eac53d1a23b781a9963fab99700135Misha Brukman const std::vector<BasicBlock*> &code, 73122108fac63eac53d1a23b781a9963fab99700135Misha Brukman bool AggregateArgs) { 73222108fac63eac53d1a23b781a9963fab99700135Misha Brukman return CodeExtractor(&DS, AggregateArgs).ExtractCodeRegion(code); 7330256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman} 7340256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman 735b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// ExtractBasicBlock - slurp a natural loop into a brand new function 736b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// 73722108fac63eac53d1a23b781a9963fab99700135Misha BrukmanFunction* llvm::ExtractLoop(DominatorSet &DS, Loop *L, bool AggregateArgs) { 73822108fac63eac53d1a23b781a9963fab99700135Misha Brukman return CodeExtractor(&DS, AggregateArgs).ExtractCodeRegion(L->getBlocks()); 739e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 740e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 741b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// ExtractBasicBlock - slurp a basic block into a brand new function 742b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// 74322108fac63eac53d1a23b781a9963fab99700135Misha BrukmanFunction* llvm::ExtractBasicBlock(BasicBlock *BB, bool AggregateArgs) { 744b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman std::vector<BasicBlock*> Blocks; 745b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman Blocks.push_back(BB); 746fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman return CodeExtractor(0, AggregateArgs).ExtractCodeRegion(Blocks); 747b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman} 748