CodeExtractor.cpp revision c5dd34209b9936cb500c3d11e732dc094373200d
1e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman//===- CodeExtractor.cpp - Pull code region into a new function -----------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// The LLVM Compiler Infrastructure 4e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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" 210a205a459884ec745df1c529396dd921f029dafdOwen Anderson#include "llvm/LLVMContext.h" 22e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Module.h" 23e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Pass.h" 24b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner#include "llvm/Analysis/Dominators.h" 25e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Analysis/LoopInfo.h" 26ffada9327301094411146627cf6bc16cd517585dChris Lattner#include "llvm/Analysis/Verifier.h" 27e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 28551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 29551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 307d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 31bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 32c5dd34209b9936cb500c3d11e732dc094373200dJulien Lerouge#include "llvm/ADT/SetVector.h" 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/StringExtras.h" 34e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include <algorithm> 350e06674287b15696f66a65f20f2ba99137b29213Chris Lattner#include <set> 36e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanusing namespace llvm; 37e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 3822108fac63eac53d1a23b781a9963fab99700135Misha Brukman// Provide a command-line option to aggregate function arguments into a struct 39a4a83c314c5997ff2b5eadae8e711fec6501121dMisha Brukman// for functions produced by the code extractor. This is useful when converting 4022108fac63eac53d1a23b781a9963fab99700135Misha Brukman// extracted functions to pthread-based code, as only one argument (void*) can 4122108fac63eac53d1a23b781a9963fab99700135Misha Brukman// be passed in to pthread_create(). 4222108fac63eac53d1a23b781a9963fab99700135Misha Brukmanstatic cl::opt<bool> 4322108fac63eac53d1a23b781a9963fab99700135Misha BrukmanAggregateArgsOpt("aggregate-extracted-args", cl::Hidden, 4422108fac63eac53d1a23b781a9963fab99700135Misha Brukman cl::desc("Aggregate arguments to code-extracted functions")); 4522108fac63eac53d1a23b781a9963fab99700135Misha Brukman 46e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmannamespace { 476726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class CodeExtractor { 48e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman typedef std::vector<Value*> Values; 49c5dd34209b9936cb500c3d11e732dc094373200dJulien Lerouge SetVector<BasicBlock*> BlocksToExtract; 50c6fcf29e81f54b68146fb8d375c347d2c689566dOwen Anderson DominatorTree* DT; 5122108fac63eac53d1a23b781a9963fab99700135Misha Brukman bool AggregateArgs; 52346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner unsigned NumExitBlocks; 53346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner const Type *RetTy; 54e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman public: 554b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang Patel CodeExtractor(DominatorTree* dt = 0, bool AggArgs = false) 564b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang Patel : DT(dt), AggregateArgs(AggArgs||AggregateArgsOpt), NumExitBlocks(~0U) {} 57b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 58e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *ExtractCodeRegion(const std::vector<BasicBlock*> &code); 59e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 6022108fac63eac53d1a23b781a9963fab99700135Misha Brukman bool isEligible(const std::vector<BasicBlock*> &code); 6122108fac63eac53d1a23b781a9963fab99700135Misha Brukman 62e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman private: 63bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// definedInRegion - Return true if the specified value is defined in the 64bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// extracted region. 65bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner bool definedInRegion(Value *V) const { 66bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 67bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (BlocksToExtract.count(I->getParent())) 68bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return true; 69bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return false; 70bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 71fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 72bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// definedInCaller - Return true if the specified value is defined in the 73bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// function being code extracted, but not in the region being extracted. 74bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner /// These values must be passed in as live-ins to the function. 75bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner bool definedInCaller(Value *V) const { 76bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (isa<Argument>(V)) return true; 77bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 78bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (!BlocksToExtract.count(I->getParent())) 79bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return true; 80bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return false; 81bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 82bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 83bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner void severSplitPHINodes(BasicBlock *&Header); 84d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner void splitReturnBlocks(); 85bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner void findInputsOutputs(Values &inputs, Values &outputs); 86e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 87e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *constructFunction(const Values &inputs, 88e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Values &outputs, 895cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner BasicBlock *header, 90e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, BasicBlock *newHeader, 91e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction, Module *M); 92e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 930e06674287b15696f66a65f20f2ba99137b29213Chris Lattner void moveCodeToFunction(Function *newFunction); 94e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 95e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman void emitCallAndSwitchStatement(Function *newFunction, 96e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 97e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &inputs, 98e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values &outputs); 99e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 100e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman }; 101e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 102e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 103bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// severSplitPHINodes - If a PHI node has multiple inputs from outside of the 104bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// region, we need to split the entry block of the region so that the PHI node 105bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// is easier to deal with. 106bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::severSplitPHINodes(BasicBlock *&Header) { 107e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner bool HasPredsFromRegion = false; 108e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner unsigned NumPredsOutsideRegion = 0; 109e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 110ecb7a77885b174cf4d001a9b48533b3979e7810dDan Gohman if (Header != &Header->getParent()->getEntryBlock()) { 111e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *PN = dyn_cast<PHINode>(Header->begin()); 112e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (!PN) return; // No PHI nodes. 113e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 114e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // If the header node contains any PHI nodes, check to see if there is more 115e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // than one entry from outside the region. If so, we need to sever the 116e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // header block into two. 117e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 118e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) 119e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner HasPredsFromRegion = true; 120e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner else 121e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner ++NumPredsOutsideRegion; 122e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 123e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // If there is one (or fewer) predecessor from outside the region, we don't 124e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // need to do anything special. 125e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (NumPredsOutsideRegion <= 1) return; 126e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 127bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 128e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Otherwise, we need to split the header block into two pieces: one 129e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // containing PHI nodes merging values from outside of the region, and a 130e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // second that contains all of the code for the block and merges back any 131e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // incoming values from inside of the region. 13202dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator AfterPHIs = Header->getFirstNonPHI(); 133e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BasicBlock *NewBB = Header->splitBasicBlock(AfterPHIs, 134e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Header->getName()+".ce"); 135e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 136e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // We only want to code extract the second block now, and it becomes the new 137e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // header of the region. 138e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BasicBlock *OldPred = Header; 139c5dd34209b9936cb500c3d11e732dc094373200dJulien Lerouge BlocksToExtract.remove(OldPred); 140e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BlocksToExtract.insert(NewBB); 141e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Header = NewBB; 142e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 143e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, update dominator sets. The blocks that dominate the new one are the 144e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // blocks that dominate TIBB plus the new block itself. 1450e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DT) 1460e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT->splitBlock(NewBB); 147bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 148e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, now we need to adjust the PHI nodes and any branches from within the 149e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // region to go to the new header block instead of the old header block. 150e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (HasPredsFromRegion) { 151e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *PN = cast<PHINode>(OldPred->begin()); 152e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the predecessors of OldPred that are in the region, 153e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // changing them to branch to NewBB instead. 154e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 155e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) { 156e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner TerminatorInst *TI = PN->getIncomingBlock(i)->getTerminator(); 157e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner TI->replaceUsesOfWith(OldPred, NewBB); 158e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 159e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 160e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, everthing within the region is now branching to the right block, we 161e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // just have to update the PHI nodes now, inserting PHI nodes into NewBB. 1622da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { 1632da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(AfterPHIs); 164e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Create a new PHI node in the new region, which has an incoming value 165e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // from OldPred of PN. 166051a950000e21935165db56695e35bade668193bGabor Greif PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".ce", 167051a950000e21935165db56695e35bade668193bGabor Greif NewBB->begin()); 168e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner NewPN->addIncoming(PN, OldPred); 169e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 170e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the incoming value in PN, moving them to NewPN if they 171e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // are from the extracted region. 172e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { 173e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (BlocksToExtract.count(PN->getIncomingBlock(i))) { 174e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); 175e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PN->removeIncomingValue(i); 176e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner --i; 177e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 178e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 179e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 180e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 181d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner} 182e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 183d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattnervoid CodeExtractor::splitReturnBlocks() { 184c5dd34209b9936cb500c3d11e732dc094373200dJulien Lerouge for (SetVector<BasicBlock*>::iterator I = BlocksToExtract.begin(), 185d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner E = BlocksToExtract.end(); I != E; ++I) 1869ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson if (ReturnInst *RI = dyn_cast<ReturnInst>((*I)->getTerminator())) { 1879ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson BasicBlock *New = (*I)->splitBasicBlock(RI, (*I)->getName()+".ret"); 1889ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson if (DT) { 1899ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson // Old dominates New. New node domiantes all other nodes dominated 1909ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson //by Old. 1919ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson DomTreeNode *OldNode = DT->getNode(*I); 19255a0f1e41f1b166eb924909eeec94a54417f95ebOwen Anderson SmallVector<DomTreeNode*, 8> Children; 1939ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson for (DomTreeNode::iterator DI = OldNode->begin(), DE = OldNode->end(); 1949ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson DI != DE; ++DI) 1959ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson Children.push_back(*DI); 1969ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson 1979ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson DomTreeNode *NewNode = DT->addNewBlock(New, *I); 1989ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson 19955a0f1e41f1b166eb924909eeec94a54417f95ebOwen Anderson for (SmallVector<DomTreeNode*, 8>::iterator I = Children.begin(), 2009ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson E = Children.end(); I != E; ++I) 2019ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson DT->changeImmediateDominator(*I, NewNode); 2029ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson } 2039ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson } 204bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner} 205bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 206bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner// findInputsOutputs - Find inputs to, outputs from the code region. 207bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner// 208bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::findInputsOutputs(Values &inputs, Values &outputs) { 209346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner std::set<BasicBlock*> ExitBlocks; 210c5dd34209b9936cb500c3d11e732dc094373200dJulien Lerouge for (SetVector<BasicBlock*>::const_iterator ci = BlocksToExtract.begin(), 2110e06674287b15696f66a65f20f2ba99137b29213Chris Lattner ce = BlocksToExtract.end(); ci != ce; ++ci) { 212e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *BB = *ci; 213bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 2140de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 2150de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner // If a used value is defined outside the region, it's an input. If an 2160de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner // instruction is used outside the region, it's an output. 217bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner for (User::op_iterator O = I->op_begin(), E = I->op_end(); O != E; ++O) 218bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (definedInCaller(*O)) 219bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner inputs.push_back(*O); 220fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 221bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Consider uses of this instruction (outputs). 2220de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 2230de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner UI != E; ++UI) 224bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (!definedInRegion(*UI)) { 225b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner outputs.push_back(I); 226b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner break; 227b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner } 2280de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner } // for: insts 229346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 230bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Keep track of the exit blocks from the region. 231346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TerminatorInst *TI = BB->getTerminator(); 232346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 233346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner if (!BlocksToExtract.count(TI->getSuccessor(i))) 234346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner ExitBlocks.insert(TI->getSuccessor(i)); 2350de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner } // for: basic blocks 236346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 237346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner NumExitBlocks = ExitBlocks.size(); 238587992721c3112c94000722941748cf46cd0bce6Chris Lattner 239587992721c3112c94000722941748cf46cd0bce6Chris Lattner // Eliminate duplicates. 240587992721c3112c94000722941748cf46cd0bce6Chris Lattner std::sort(inputs.begin(), inputs.end()); 241587992721c3112c94000722941748cf46cd0bce6Chris Lattner inputs.erase(std::unique(inputs.begin(), inputs.end()), inputs.end()); 242587992721c3112c94000722941748cf46cd0bce6Chris Lattner std::sort(outputs.begin(), outputs.end()); 243587992721c3112c94000722941748cf46cd0bce6Chris Lattner outputs.erase(std::unique(outputs.begin(), outputs.end()), outputs.end()); 244e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 245e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 246e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// constructFunction - make a function based on inputs and outputs, as follows: 247e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// f(in0, ..., inN, out0, ..., outN) 248e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 249e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha BrukmanFunction *CodeExtractor::constructFunction(const Values &inputs, 250e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Values &outputs, 2515cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner BasicBlock *header, 252e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, 253e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 2545cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner Function *oldFunction, 2555cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner Module *M) { 256ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << "inputs: " << inputs.size() << "\n"); 257ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << "outputs: " << outputs.size() << "\n"); 258e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 259e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This function returns unsigned, outputs will go back by reference. 260346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 261346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 2621d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson case 1: RetTy = Type::getVoidTy(header->getContext()); break; 2631d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson case 2: RetTy = Type::getInt1Ty(header->getContext()); break; 2641d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson default: RetTy = Type::getInt16Ty(header->getContext()); break; 265346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner } 266346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 267e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<const Type*> paramTy; 268e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 269e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Add the types of the input values to the function's argument list 270e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (Values::const_iterator i = inputs.begin(), 271e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman e = inputs.end(); i != e; ++i) { 272e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Value *value = *i; 273ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << "value used in func: " << *value << "\n"); 274e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman paramTy.push_back(value->getType()); 275e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 276e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 277b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Add the types of the output values to the function's argument list. 278b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (Values::const_iterator I = outputs.begin(), E = outputs.end(); 279b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner I != E; ++I) { 280ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << "instr used in func: " << **I << "\n"); 28122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) 28222108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.push_back((*I)->getType()); 28322108fac63eac53d1a23b781a9963fab99700135Misha Brukman else 284debcb01b0f0a15f568ca69e8f288fade4bfc7297Owen Anderson paramTy.push_back(PointerType::getUnqual((*I)->getType())); 285e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 286e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 287ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << "Function type: " << *RetTy << " f("); 2880d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling for (std::vector<const Type*>::iterator i = paramTy.begin(), 2890d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling e = paramTy.end(); i != e; ++i) 290ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << **i << ", "); 291ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << ")\n"); 292e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 29322108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 2940a205a459884ec745df1c529396dd921f029dafdOwen Anderson PointerType *StructPtr = 295d7f2a6cb3fbc012763adb42fd967f6fefbb22a37Owen Anderson PointerType::getUnqual(StructType::get(M->getContext(), paramTy)); 29622108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.clear(); 29722108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.push_back(StructPtr); 29822108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 2990a205a459884ec745df1c529396dd921f029dafdOwen Anderson const FunctionType *funcType = 300debcb01b0f0a15f568ca69e8f288fade4bfc7297Owen Anderson FunctionType::get(RetTy, paramTy, false); 301e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 302e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Create the new function 303051a950000e21935165db56695e35bade668193bGabor Greif Function *newFunction = Function::Create(funcType, 304051a950000e21935165db56695e35bade668193bGabor Greif GlobalValue::InternalLinkage, 305051a950000e21935165db56695e35bade668193bGabor Greif oldFunction->getName() + "_" + 306051a950000e21935165db56695e35bade668193bGabor Greif header->getName(), M); 30731535f1f04853974ec53dfc61d90e8dc4a09b456Chris Lattner // If the old function is no-throw, so is the new one. 30831535f1f04853974ec53dfc61d90e8dc4a09b456Chris Lattner if (oldFunction->doesNotThrow()) 30931535f1f04853974ec53dfc61d90e8dc4a09b456Chris Lattner newFunction->setDoesNotThrow(true); 31031535f1f04853974ec53dfc61d90e8dc4a09b456Chris Lattner 311e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newFunction->getBasicBlockList().push_back(newRootNode); 312e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 313b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Create an iterator to name all of the arguments we inserted. 314e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner Function::arg_iterator AI = newFunction->arg_begin(); 315b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 316b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Rewrite all users of the inputs in the extracted region to use the 31722108fac63eac53d1a23b781a9963fab99700135Misha Brukman // arguments (or appropriate addressing into struct) instead. 31822108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 31922108fac63eac53d1a23b781a9963fab99700135Misha Brukman Value *RewriteVal; 32022108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 321b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Value *Idx[2]; 3221d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext())); 3231d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i); 32422108fac63eac53d1a23b781a9963fab99700135Misha Brukman TerminatorInst *TI = newFunction->begin()->getTerminator(); 325f6ccee5a9d2b9573f679bca6266ade3eb8cd3f88Daniel Dunbar GetElementPtrInst *GEP = 326f6ccee5a9d2b9573f679bca6266ade3eb8cd3f88Daniel Dunbar GetElementPtrInst::Create(AI, Idx, Idx+2, 327f6ccee5a9d2b9573f679bca6266ade3eb8cd3f88Daniel Dunbar "gep_" + inputs[i]->getName(), TI); 328f6ccee5a9d2b9573f679bca6266ade3eb8cd3f88Daniel Dunbar RewriteVal = new LoadInst(GEP, "loadgep_" + inputs[i]->getName(), TI); 32922108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else 33022108fac63eac53d1a23b781a9963fab99700135Misha Brukman RewriteVal = AI++; 33122108fac63eac53d1a23b781a9963fab99700135Misha Brukman 332e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(inputs[i]->use_begin(), inputs[i]->use_end()); 333e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<User*>::iterator use = Users.begin(), useE = Users.end(); 334ffada9327301094411146627cf6bc16cd517585dChris Lattner use != useE; ++use) 335ffada9327301094411146627cf6bc16cd517585dChris Lattner if (Instruction* inst = dyn_cast<Instruction>(*use)) 3360e06674287b15696f66a65f20f2ba99137b29213Chris Lattner if (BlocksToExtract.count(inst->getParent())) 33722108fac63eac53d1a23b781a9963fab99700135Misha Brukman inst->replaceUsesOfWith(inputs[i], RewriteVal); 338e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 339e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 34022108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Set names for input and output arguments. 34122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) { 342e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner AI = newFunction->arg_begin(); 34322108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) 3446bc41e8a74d1756da0003641bfebd02a3d6d9586Owen Anderson AI->setName(inputs[i]->getName()); 34522108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) 346fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman AI->setName(outputs[i]->getName()+".out"); 34722108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 348b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 349e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Rewrite branches to basic blocks outside of the loop to new dummy blocks 350e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // within the new function. This must be done before we lose track of which 351e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // blocks were originally in the code region. 352e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(header->use_begin(), header->use_end()); 3535cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner for (unsigned i = 0, e = Users.size(); i != e; ++i) 3545cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // The BasicBlock which contains the branch is not in the region 3555cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // modify the branch target to a new block 3565cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Users[i])) 3575cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner if (!BlocksToExtract.count(TI->getParent()) && 3585cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner TI->getParent()->getParent() == oldFunction) 3595cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner TI->replaceUsesOfWith(header, newHeader); 360e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 361e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 362e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 363e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 364613bf1ef018514e88f64f5e60f126096963248f3Owen Anderson/// FindPhiPredForUseInBlock - Given a value and a basic block, find a PHI 365613bf1ef018514e88f64f5e60f126096963248f3Owen Anderson/// that uses the value within the basic block, and return the predecessor 366613bf1ef018514e88f64f5e60f126096963248f3Owen Anderson/// block associated with that use, or return 0 if none is found. 36760fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Andersonstatic BasicBlock* FindPhiPredForUseInBlock(Value* Used, BasicBlock* BB) { 36860fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson for (Value::use_iterator UI = Used->use_begin(), 36960fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson UE = Used->use_end(); UI != UE; ++UI) { 37060fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson PHINode *P = dyn_cast<PHINode>(*UI); 37160fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson if (P && P->getParent() == BB) 37260fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson return P->getIncomingBlock(UI); 37360fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson } 37460fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson 37560fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson return 0; 37660fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson} 37760fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson 378bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// emitCallAndSwitchStatement - This method sets up the caller side by adding 379bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// the call instruction, splitting any PHI nodes in the header block as 380bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// necessary. 381bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor:: 382bf749367cb2aef7072ee36a9eb681b35aab51921Chris LattneremitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, 383bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Values &inputs, Values &outputs) { 384bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Emit a call to the new function, passing in: *pointer to struct (if 385bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // aggregating parameters), or plan inputs and allocated memory for outputs 3869db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson std::vector<Value*> params, StructValues, ReloadOutputs, Reloads; 3871d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson 3881d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson LLVMContext &Context = newFunction->getContext(); 38922108fac63eac53d1a23b781a9963fab99700135Misha Brukman 39022108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Add inputs as params, or to be filled into the struct 39122108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (Values::iterator i = inputs.begin(), e = inputs.end(); i != e; ++i) 39222108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) 39322108fac63eac53d1a23b781a9963fab99700135Misha Brukman StructValues.push_back(*i); 39422108fac63eac53d1a23b781a9963fab99700135Misha Brukman else 39522108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(*i); 39622108fac63eac53d1a23b781a9963fab99700135Misha Brukman 39722108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Create allocas for the outputs 39822108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (Values::iterator i = outputs.begin(), e = outputs.end(); i != e; ++i) { 39922108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 40022108fac63eac53d1a23b781a9963fab99700135Misha Brukman StructValues.push_back(*i); 40122108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else { 40222108fac63eac53d1a23b781a9963fab99700135Misha Brukman AllocaInst *alloca = 40350dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson new AllocaInst((*i)->getType(), 0, (*i)->getName()+".loc", 40422108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getParent()->begin()->begin()); 40522108fac63eac53d1a23b781a9963fab99700135Misha Brukman ReloadOutputs.push_back(alloca); 40622108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(alloca); 40722108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 40822108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 40922108fac63eac53d1a23b781a9963fab99700135Misha Brukman 41022108fac63eac53d1a23b781a9963fab99700135Misha Brukman AllocaInst *Struct = 0; 41122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 41222108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::vector<const Type*> ArgTypes; 41322108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (Values::iterator v = StructValues.begin(), 41422108fac63eac53d1a23b781a9963fab99700135Misha Brukman ve = StructValues.end(); v != ve; ++v) 41522108fac63eac53d1a23b781a9963fab99700135Misha Brukman ArgTypes.push_back((*v)->getType()); 41622108fac63eac53d1a23b781a9963fab99700135Misha Brukman 41722108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Allocate a struct at the beginning of this function 418d7f2a6cb3fbc012763adb42fd967f6fefbb22a37Owen Anderson Type *StructArgTy = StructType::get(newFunction->getContext(), ArgTypes); 419fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman Struct = 42050dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson new AllocaInst(StructArgTy, 0, "structArg", 42122108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getParent()->begin()->begin()); 42222108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(Struct); 42322108fac63eac53d1a23b781a9963fab99700135Misha Brukman 42422108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 425b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Value *Idx[2]; 4261d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 4271d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i); 42822108fac63eac53d1a23b781a9963fab99700135Misha Brukman GetElementPtrInst *GEP = 429051a950000e21935165db56695e35bade668193bGabor Greif GetElementPtrInst::Create(Struct, Idx, Idx + 2, 430051a950000e21935165db56695e35bade668193bGabor Greif "gep_" + StructValues[i]->getName()); 43122108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(GEP); 43222108fac63eac53d1a23b781a9963fab99700135Misha Brukman StoreInst *SI = new StoreInst(StructValues[i], GEP); 43322108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(SI); 43422108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 435fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman } 43622108fac63eac53d1a23b781a9963fab99700135Misha Brukman 43722108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Emit the call to the function 438051a950000e21935165db56695e35bade668193bGabor Greif CallInst *call = CallInst::Create(newFunction, params.begin(), params.end(), 439051a950000e21935165db56695e35bade668193bGabor Greif NumExitBlocks > 1 ? "targetBlock" : ""); 44022108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(call); 44122108fac63eac53d1a23b781a9963fab99700135Misha Brukman 442e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner Function::arg_iterator OutputArgBegin = newFunction->arg_begin(); 44322108fac63eac53d1a23b781a9963fab99700135Misha Brukman unsigned FirstOut = inputs.size(); 44422108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) 44522108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::advance(OutputArgBegin, inputs.size()); 44604229c192bc153210e8ee8a18eb28d7f1ec21bfeChris Lattner 44722108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Reload the outputs passed in by reference 448b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 44922108fac63eac53d1a23b781a9963fab99700135Misha Brukman Value *Output = 0; 45022108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 451b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Value *Idx[2]; 4521d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 4531d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); 454fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman GetElementPtrInst *GEP 455051a950000e21935165db56695e35bade668193bGabor Greif = GetElementPtrInst::Create(Struct, Idx, Idx + 2, 456051a950000e21935165db56695e35bade668193bGabor Greif "gep_reload_" + outputs[i]->getName()); 45722108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(GEP); 45822108fac63eac53d1a23b781a9963fab99700135Misha Brukman Output = GEP; 45922108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else { 46022108fac63eac53d1a23b781a9963fab99700135Misha Brukman Output = ReloadOutputs[i]; 46122108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 46222108fac63eac53d1a23b781a9963fab99700135Misha Brukman LoadInst *load = new LoadInst(Output, outputs[i]->getName()+".reload"); 4639db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson Reloads.push_back(load); 464b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner codeReplacer->getInstList().push_back(load); 465b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner std::vector<User*> Users(outputs[i]->use_begin(), outputs[i]->use_end()); 466b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (unsigned u = 0, e = Users.size(); u != e; ++u) { 467b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner Instruction *inst = cast<Instruction>(Users[u]); 468b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner if (!BlocksToExtract.count(inst->getParent())) 469b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner inst->replaceUsesOfWith(outputs[i], load); 470e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 471e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 47212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 473e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Now we can emit a switch statement using the call as a value. 474346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner SwitchInst *TheSwitch = 4751d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)), 476051a950000e21935165db56695e35bade668193bGabor Greif codeReplacer, 0, codeReplacer); 477e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 478e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Since there may be multiple exits from the original region, make the new 47912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // function return an unsigned, switch on that number. This loop iterates 48012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // over all of the blocks in the extracted region, updating any terminator 48112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // instructions in the to-be-extracted region that branch to blocks that are 48212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // not in the region to be extracted. 48312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner std::map<BasicBlock*, BasicBlock*> ExitBlockMap; 48412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 485e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman unsigned switchVal = 0; 486c5dd34209b9936cb500c3d11e732dc094373200dJulien Lerouge for (SetVector<BasicBlock*>::const_iterator i = BlocksToExtract.begin(), 4870e06674287b15696f66a65f20f2ba99137b29213Chris Lattner e = BlocksToExtract.end(); i != e; ++i) { 48812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner TerminatorInst *TI = (*i)->getTerminator(); 48912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 49012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner if (!BlocksToExtract.count(TI->getSuccessor(i))) { 49112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner BasicBlock *OldTarget = TI->getSuccessor(i); 49212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // add a new basic block which returns the appropriate value 49312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; 49412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner if (!NewTarget) { 49512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // If we don't already have an exit stub for this non-extracted 49612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // destination, create one now! 4971d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson NewTarget = BasicBlock::Create(Context, 4981d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson OldTarget->getName() + ".exitStub", 499051a950000e21935165db56695e35bade668193bGabor Greif newFunction); 500346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner unsigned SuccNum = switchVal++; 501346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 502346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner Value *brVal = 0; 503346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 504346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 505346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 1: break; // No value needed. 506346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 2: // Conditional branch, return a bool 5071d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum); 508346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 509346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner default: 5101d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum); 511346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 512346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner } 51312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 5141d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst *NTRet = ReturnInst::Create(Context, brVal, NewTarget); 51512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 51612f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // Update the switch instruction. 5171d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context), 5181d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson SuccNum), 519346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner OldTarget); 52012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 52112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // Restore values just before we exit 522e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner Function::arg_iterator OAI = OutputArgBegin; 52322108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned out = 0, e = outputs.size(); out != e; ++out) { 52422108fac63eac53d1a23b781a9963fab99700135Misha Brukman // For an invoke, the normal destination is the only one that is 52522108fac63eac53d1a23b781a9963fab99700135Misha Brukman // dominated by the result of the invocation 52622108fac63eac53d1a23b781a9963fab99700135Misha Brukman BasicBlock *DefBlock = cast<Instruction>(outputs[out])->getParent(); 5279ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 5289ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner bool DominatesDef = true; 5299ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 53068c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner if (InvokeInst *Invoke = dyn_cast<InvokeInst>(outputs[out])) { 53122108fac63eac53d1a23b781a9963fab99700135Misha Brukman DefBlock = Invoke->getNormalDest(); 53268c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner 53368c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner // Make sure we are looking at the original successor block, not 53468c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner // at a newly inserted exit block, which won't be in the dominator 53568c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner // info. 53668c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner for (std::map<BasicBlock*, BasicBlock*>::iterator I = 53768c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner ExitBlockMap.begin(), E = ExitBlockMap.end(); I != E; ++I) 53868c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner if (DefBlock == I->second) { 53968c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner DefBlock = I->first; 54068c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner break; 54168c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner } 5429ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 5439ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner // In the extract block case, if the block we are extracting ends 5449ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner // with an invoke instruction, make sure that we don't emit a 5459ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner // store of the invoke value for the unwind block. 5464b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang Patel if (!DT && DefBlock != OldTarget) 5479ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner DominatesDef = false; 54868c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner } 54968c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner 5509db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson if (DT) { 5514b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang Patel DominatesDef = DT->dominates(DefBlock, OldTarget); 5529db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson 5539db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson // If the output value is used by a phi in the target block, 5549db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson // then we need to test for dominance of the phi's predecessor 5559db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson // instead. Unfortunately, this a little complicated since we 5569db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson // have already rewritten uses of the value to uses of the reload. 55760fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson BasicBlock* pred = FindPhiPredForUseInBlock(Reloads[out], 55860fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson OldTarget); 55960fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson if (pred && DT && DT->dominates(DefBlock, pred)) 56060fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson DominatesDef = true; 5619db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson } 5629ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 5639ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner if (DominatesDef) { 56422108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 565b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Value *Idx[2]; 5661d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 5671d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), 5681d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson FirstOut+out); 56922108fac63eac53d1a23b781a9963fab99700135Misha Brukman GetElementPtrInst *GEP = 570051a950000e21935165db56695e35bade668193bGabor Greif GetElementPtrInst::Create(OAI, Idx, Idx + 2, 571051a950000e21935165db56695e35bade668193bGabor Greif "gep_" + outputs[out]->getName(), 572051a950000e21935165db56695e35bade668193bGabor Greif NTRet); 57322108fac63eac53d1a23b781a9963fab99700135Misha Brukman new StoreInst(outputs[out], GEP, NTRet); 5749ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner } else { 57522108fac63eac53d1a23b781a9963fab99700135Misha Brukman new StoreInst(outputs[out], OAI, NTRet); 5769ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner } 5779ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner } 57822108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Advance output iterator even if we don't emit a store 57922108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) ++OAI; 58022108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 581e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 5820e06674287b15696f66a65f20f2ba99137b29213Chris Lattner 58312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // rewrite the original branch instruction with this new target 58412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner TI->setSuccessor(i, NewTarget); 58512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner } 586e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 58765826bf435620824763af926270cf0efdc82ea5aChris Lattner 5885b01e298ed42d5ce6aaf7634618b5e1769766b21Chris Lattner // Now that we've done the deed, simplify the switch instruction. 589b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner const Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); 590346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 591346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 592b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner // There are no successors (the block containing the switch itself), which 59322108fac63eac53d1a23b781a9963fab99700135Misha Brukman // means that previously this was the last part of the function, and hence 59422108fac63eac53d1a23b781a9963fab99700135Misha Brukman // this should be rewritten as a `ret' 595fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 59622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Check if the function should return a value 597f012705c7e4ca8cf90b6b734ce1d5355daca5ba5Benjamin Kramer if (OldFnRetTy->isVoidTy()) { 5981d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst::Create(Context, 0, TheSwitch); // Return void 599b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { 60022108fac63eac53d1a23b781a9963fab99700135Misha Brukman // return what we have 6011d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch); 602b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner } else { 603b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner // Otherwise we must have code extracted an unwind or something, just 604b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner // return whatever we want. 6051d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst::Create(Context, 6061d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Constant::getNullValue(OldFnRetTy), TheSwitch); 607b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner } 60822108fac63eac53d1a23b781a9963fab99700135Misha Brukman 6091adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman TheSwitch->eraseFromParent(); 610346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 611346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 1: 612346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // Only a single destination, change the switch into an unconditional 613346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // branch. 614051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch); 6151adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman TheSwitch->eraseFromParent(); 616346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 617346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 2: 618051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), 619051a950000e21935165db56695e35bade668193bGabor Greif call, TheSwitch); 6201adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman TheSwitch->eraseFromParent(); 621346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 622346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner default: 623346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // Otherwise, make the default destination of the switch instruction be one 624346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // of the other successors. 625346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->setOperand(0, call); 626346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->setSuccessor(0, TheSwitch->getSuccessor(NumExitBlocks)); 627346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner TheSwitch->removeCase(NumExitBlocks); // Remove redundant case 628346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 62965826bf435620824763af926270cf0efdc82ea5aChris Lattner } 630e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 631e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 632bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::moveCodeToFunction(Function *newFunction) { 633bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function *oldFunc = (*BlocksToExtract.begin())->getParent(); 634bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); 635bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); 636bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 637c5dd34209b9936cb500c3d11e732dc094373200dJulien Lerouge for (SetVector<BasicBlock*>::const_iterator i = BlocksToExtract.begin(), 638bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner e = BlocksToExtract.end(); i != e; ++i) { 639bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Delete the basic block from the old function, and the list of blocks 640bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner oldBlocks.remove(*i); 641bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 642bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Insert this basic block into the new function 643bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner newBlocks.push_back(*i); 644bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 645bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner} 646e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 647e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// ExtractRegion - Removes a loop from a function, replaces it with a call to 648e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// new function. Returns pointer to the new function. 649e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 650e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// algorithm: 651e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 652e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// find inputs and outputs for the region 653e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 654fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// for inputs: add to function as args, map input instr* to arg# 655fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// for outputs: add allocas for scalars, 656e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// add to func as args, map output instr* to arg# 657e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 658e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// rewrite func to use argument #s instead of instr* 659e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 660fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// for each scalar output in the function: at every exit, store intermediate 661e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// computed result back into memory. 662e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 663b519efbafedb356a30a04a32c15a6b406779a997Chris LattnerFunction *CodeExtractor:: 664b519efbafedb356a30a04a32c15a6b406779a997Chris LattnerExtractCodeRegion(const std::vector<BasicBlock*> &code) { 66522108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!isEligible(code)) 66622108fac63eac53d1a23b781a9963fab99700135Misha Brukman return 0; 66722108fac63eac53d1a23b781a9963fab99700135Misha Brukman 668e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 1) Find inputs, outputs 669e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 2) Construct new function 670e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * Add allocas for defs, pass as args by reference 671e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // * Pass in uses as args 672e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // 3) Move code region, add call instr to func 6730e06674287b15696f66a65f20f2ba99137b29213Chris Lattner // 6740e06674287b15696f66a65f20f2ba99137b29213Chris Lattner BlocksToExtract.insert(code.begin(), code.end()); 675e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 676e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Values inputs, outputs; 677e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 678e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Assumption: this is a single-entry code region, and the header is the first 6790de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner // block in the region. 680e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *header = code[0]; 681bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 6820de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (unsigned i = 1, e = code.size(); i != e; ++i) 6830de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner for (pred_iterator PI = pred_begin(code[i]), E = pred_end(code[i]); 6840de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner PI != E; ++PI) 6850de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner assert(BlocksToExtract.count(*PI) && 6860de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner "No blocks in this region may have entries from outside the region" 6870de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner " except for the first block!"); 688fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 689d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner // If we have to split PHI nodes or the entry block, do so now. 690e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner severSplitPHINodes(header); 691e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 692d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner // If we have any return instructions in the region, split those blocks so 693d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner // that the return is not in the region. 694d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner splitReturnBlocks(); 695d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner 696e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction = header->getParent(); 697e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 698e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This takes place of the original loop 6991d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(), 7001d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "codeRepl", oldFunction, 701b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif header); 702e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 703e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // The new function needs a root node because other nodes can branch to the 704bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // head of the region, but the entry node of a function cannot have preds. 7051d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(), 7061d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "newFuncRoot"); 707051a950000e21935165db56695e35bade668193bGabor Greif newFuncRoot->getInstList().push_back(BranchInst::Create(header)); 708e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 709bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Find inputs to, outputs from the code region. 710bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner findInputsOutputs(inputs, outputs); 711bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 712bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Construct new function based on inputs/outputs & add allocas for all defs. 713e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Function *newFunction = constructFunction(inputs, outputs, header, 714fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman newFuncRoot, 7150de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner codeReplacer, oldFunction, 7160de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner oldFunction->getParent()); 717e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 7180e06674287b15696f66a65f20f2ba99137b29213Chris Lattner emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); 719e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 7200e06674287b15696f66a65f20f2ba99137b29213Chris Lattner moveCodeToFunction(newFunction); 721e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 722e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the PHI nodes in the header block, and change any 7235cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // references to the old incoming edge to be the new incoming edge. 7242da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { 7252da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 7265cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 7275cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner if (!BlocksToExtract.count(PN->getIncomingBlock(i))) 7285cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner PN->setIncomingBlock(i, newFuncRoot); 7292da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer } 730fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 731d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // Look at all successors of the codeReplacer block. If any of these blocks 732d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // had PHI nodes in them, we need to update the "from" block to be the code 733d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // replacer, not the original block in the extracted region. 734d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner std::vector<BasicBlock*> Succs(succ_begin(codeReplacer), 735d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner succ_end(codeReplacer)); 736d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner for (unsigned i = 0, e = Succs.size(); i != e; ++i) 7372da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Succs[i]->begin(); isa<PHINode>(I); ++I) { 7382da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 739a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner std::set<BasicBlock*> ProcessedPreds; 740d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 74107e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov if (BlocksToExtract.count(PN->getIncomingBlock(i))) { 742a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner if (ProcessedPreds.insert(PN->getIncomingBlock(i)).second) 743a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner PN->setIncomingBlock(i, codeReplacer); 744a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner else { 745a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner // There were multiple entries in the PHI for this block, now there 746a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner // is only one, so remove the duplicated entries. 747a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner PN->removeIncomingValue(i, false); 748a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner --i; --e; 749a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner } 75007e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov } 751a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner } 752fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 753e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "NEW FUNCTION: " << *newFunction; 754e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // verifyFunction(*newFunction); 755e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 756e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling // cerr << "OLD FUNCTION: " << *oldFunction; 757e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // verifyFunction(*oldFunction); 758d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner 7597d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin DEBUG(if (verifyFunction(*newFunction)) 7607d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin llvm_report_error("verifyFunction failed!")); 761e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 762e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 763e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 76422108fac63eac53d1a23b781a9963fab99700135Misha Brukmanbool CodeExtractor::isEligible(const std::vector<BasicBlock*> &code) { 765bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Deny code region if it contains allocas or vastarts. 76622108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (std::vector<BasicBlock*>::const_iterator BB = code.begin(), e=code.end(); 76722108fac63eac53d1a23b781a9963fab99700135Misha Brukman BB != e; ++BB) 76822108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (BasicBlock::const_iterator I = (*BB)->begin(), Ie = (*BB)->end(); 76922108fac63eac53d1a23b781a9963fab99700135Misha Brukman I != Ie; ++I) 77022108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (isa<AllocaInst>(*I)) 77122108fac63eac53d1a23b781a9963fab99700135Misha Brukman return false; 772bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner else if (const CallInst *CI = dyn_cast<CallInst>(I)) 773bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (const Function *F = CI->getCalledFunction()) 774bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner if (F->getIntrinsicID() == Intrinsic::vastart) 775bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return false; 77622108fac63eac53d1a23b781a9963fab99700135Misha Brukman return true; 77722108fac63eac53d1a23b781a9963fab99700135Misha Brukman} 77822108fac63eac53d1a23b781a9963fab99700135Misha Brukman 77922108fac63eac53d1a23b781a9963fab99700135Misha Brukman 7800256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// ExtractCodeRegion - slurp a sequence of basic blocks into a brand new 7810256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// function 7820256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman/// 7834b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang PatelFunction* llvm::ExtractCodeRegion(DominatorTree &DT, 78422108fac63eac53d1a23b781a9963fab99700135Misha Brukman const std::vector<BasicBlock*> &code, 78522108fac63eac53d1a23b781a9963fab99700135Misha Brukman bool AggregateArgs) { 7864b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang Patel return CodeExtractor(&DT, AggregateArgs).ExtractCodeRegion(code); 7870256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman} 7880256e4bbf9d8108912d3015634bc1a6f78366d16Misha Brukman 789b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// ExtractBasicBlock - slurp a natural loop into a brand new function 790b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// 7914b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang PatelFunction* llvm::ExtractLoop(DominatorTree &DT, Loop *L, bool AggregateArgs) { 7924b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang Patel return CodeExtractor(&DT, AggregateArgs).ExtractCodeRegion(L->getBlocks()); 793e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 794e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 795b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// ExtractBasicBlock - slurp a basic block into a brand new function 796b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman/// 79722108fac63eac53d1a23b781a9963fab99700135Misha BrukmanFunction* llvm::ExtractBasicBlock(BasicBlock *BB, bool AggregateArgs) { 798b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman std::vector<BasicBlock*> Blocks; 799b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman Blocks.push_back(BB); 8004b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang Patel return CodeExtractor(0, AggregateArgs).ExtractCodeRegion(Blocks); 801b97fce52528eb5d9a6e86c3c0e92a73a07341c83Misha Brukman} 802