1ca399021d47d640551eb786620bcd108e1758485Owen Anderson//===- PartialInlining.cpp - Inline parts of functions --------------------===// 2ca399021d47d640551eb786620bcd108e1758485Owen Anderson// 3ca399021d47d640551eb786620bcd108e1758485Owen Anderson// The LLVM Compiler Infrastructure 4ca399021d47d640551eb786620bcd108e1758485Owen Anderson// 5ca399021d47d640551eb786620bcd108e1758485Owen Anderson// This file is distributed under the University of Illinois Open Source 6ca399021d47d640551eb786620bcd108e1758485Owen Anderson// License. See LICENSE.TXT for details. 7ca399021d47d640551eb786620bcd108e1758485Owen Anderson// 8ca399021d47d640551eb786620bcd108e1758485Owen Anderson//===----------------------------------------------------------------------===// 9ca399021d47d640551eb786620bcd108e1758485Owen Anderson// 10ca399021d47d640551eb786620bcd108e1758485Owen Anderson// This pass performs partial inlining, typically by inlining an if statement 11ca399021d47d640551eb786620bcd108e1758485Owen Anderson// that surrounds the body of the function. 12ca399021d47d640551eb786620bcd108e1758485Owen Anderson// 13ca399021d47d640551eb786620bcd108e1758485Owen Anderson//===----------------------------------------------------------------------===// 14ca399021d47d640551eb786620bcd108e1758485Owen Anderson 15ca399021d47d640551eb786620bcd108e1758485Owen Anderson#include "llvm/Transforms/IPO.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 1736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 21ca399021d47d640551eb786620bcd108e1758485Owen Anderson#include "llvm/Pass.h" 22ca399021d47d640551eb786620bcd108e1758485Owen Anderson#include "llvm/Transforms/Utils/Cloning.h" 2399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth#include "llvm/Transforms/Utils/CodeExtractor.h" 24ca399021d47d640551eb786620bcd108e1758485Owen Andersonusing namespace llvm; 25ca399021d47d640551eb786620bcd108e1758485Owen Anderson 26dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "partialinlining" 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 28636768458f9c74b6062f1d9f159b6a0464b208c4Owen AndersonSTATISTIC(NumPartialInlined, "Number of functions partially inlined"); 29636768458f9c74b6062f1d9f159b6a0464b208c4Owen Anderson 30ca399021d47d640551eb786620bcd108e1758485Owen Andersonnamespace { 316726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct PartialInliner : public ModulePass { 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { } 33ca399021d47d640551eb786620bcd108e1758485Owen Anderson static char ID; // Pass identification, replacement for typeid 34081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson PartialInliner() : ModulePass(ID) { 35081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializePartialInlinerPass(*PassRegistry::getPassRegistry()); 36081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnModule(Module& M) override; 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 40ca399021d47d640551eb786620bcd108e1758485Owen Anderson private: 41ca399021d47d640551eb786620bcd108e1758485Owen Anderson Function* unswitchFunction(Function* F); 42ca399021d47d640551eb786620bcd108e1758485Owen Anderson }; 43ca399021d47d640551eb786620bcd108e1758485Owen Anderson} 44ca399021d47d640551eb786620bcd108e1758485Owen Anderson 45ca399021d47d640551eb786620bcd108e1758485Owen Andersonchar PartialInliner::ID = 0; 46d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(PartialInliner, "partial-inliner", 47ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Partial Inliner", false, false) 48ca399021d47d640551eb786620bcd108e1758485Owen Anderson 49ca399021d47d640551eb786620bcd108e1758485Owen AndersonModulePass* llvm::createPartialInliningPass() { return new PartialInliner(); } 50ca399021d47d640551eb786620bcd108e1758485Owen Anderson 51ca399021d47d640551eb786620bcd108e1758485Owen AndersonFunction* PartialInliner::unswitchFunction(Function* F) { 52ca399021d47d640551eb786620bcd108e1758485Owen Anderson // First, verify that this function is an unswitching candidate... 53cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar BasicBlock *entryBlock = &F->front(); 54a0ecbe782177d3ec7c98700434d2d92fb0c0e600Owen Anderson BranchInst *BR = dyn_cast<BranchInst>(entryBlock->getTerminator()); 55a0ecbe782177d3ec7c98700434d2d92fb0c0e600Owen Anderson if (!BR || BR->isUnconditional()) 56dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 57ca399021d47d640551eb786620bcd108e1758485Owen Anderson 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock* returnBlock = nullptr; 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock* nonReturnBlock = nullptr; 60ca399021d47d640551eb786620bcd108e1758485Owen Anderson unsigned returnCount = 0; 61ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (BasicBlock *BB : successors(entryBlock)) { 62ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (isa<ReturnInst>(BB->getTerminator())) { 63ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines returnBlock = BB; 64ca399021d47d640551eb786620bcd108e1758485Owen Anderson returnCount++; 65ca399021d47d640551eb786620bcd108e1758485Owen Anderson } else 66ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines nonReturnBlock = BB; 67ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 68ca399021d47d640551eb786620bcd108e1758485Owen Anderson 69ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (returnCount != 1) 70dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 71ca399021d47d640551eb786620bcd108e1758485Owen Anderson 72ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Clone the function, so that we can hack away on it. 731ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy VMap; 746cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman Function* duplicateFunction = CloneFunction(F, VMap, 756cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman /*ModuleLevelChanges=*/false); 76ca399021d47d640551eb786620bcd108e1758485Owen Anderson duplicateFunction->setLinkage(GlobalValue::InternalLinkage); 77ca399021d47d640551eb786620bcd108e1758485Owen Anderson F->getParent()->getFunctionList().push_back(duplicateFunction); 78e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel BasicBlock* newEntryBlock = cast<BasicBlock>(VMap[entryBlock]); 79e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel BasicBlock* newReturnBlock = cast<BasicBlock>(VMap[returnBlock]); 80e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel BasicBlock* newNonReturnBlock = cast<BasicBlock>(VMap[nonReturnBlock]); 81ca399021d47d640551eb786620bcd108e1758485Owen Anderson 82ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Go ahead and update all uses to the duplicate, so that we can just 83ca399021d47d640551eb786620bcd108e1758485Owen Anderson // use the inliner functionality when we're done hacking. 84ca399021d47d640551eb786620bcd108e1758485Owen Anderson F->replaceAllUsesWith(duplicateFunction); 85ca399021d47d640551eb786620bcd108e1758485Owen Anderson 86ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Special hackery is needed with PHI nodes that have inputs from more than 87ca399021d47d640551eb786620bcd108e1758485Owen Anderson // one extracted block. For simplicity, just split the PHIs into a two-level 88ca399021d47d640551eb786620bcd108e1758485Owen Anderson // sequence of PHIs, some of which will go in the extracted region, and some 89ca399021d47d640551eb786620bcd108e1758485Owen Anderson // of which will go outside. 90ca399021d47d640551eb786620bcd108e1758485Owen Anderson BasicBlock* preReturn = newReturnBlock; 91ca399021d47d640551eb786620bcd108e1758485Owen Anderson newReturnBlock = newReturnBlock->splitBasicBlock( 92cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar newReturnBlock->getFirstNonPHI()->getIterator()); 93ca399021d47d640551eb786620bcd108e1758485Owen Anderson BasicBlock::iterator I = preReturn->begin(); 94cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Instruction *Ins = &newReturnBlock->front(); 95ca399021d47d640551eb786620bcd108e1758485Owen Anderson while (I != preReturn->end()) { 96ca399021d47d640551eb786620bcd108e1758485Owen Anderson PHINode* OldPhi = dyn_cast<PHINode>(I); 97ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (!OldPhi) break; 98cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 99cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar PHINode *retPhi = PHINode::Create(OldPhi->getType(), 2, "", Ins); 100ca399021d47d640551eb786620bcd108e1758485Owen Anderson OldPhi->replaceAllUsesWith(retPhi); 101ca399021d47d640551eb786620bcd108e1758485Owen Anderson Ins = newReturnBlock->getFirstNonPHI(); 102cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 103cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar retPhi->addIncoming(&*I, preReturn); 104ca399021d47d640551eb786620bcd108e1758485Owen Anderson retPhi->addIncoming(OldPhi->getIncomingValueForBlock(newEntryBlock), 105ca399021d47d640551eb786620bcd108e1758485Owen Anderson newEntryBlock); 106ca399021d47d640551eb786620bcd108e1758485Owen Anderson OldPhi->removeIncomingValue(newEntryBlock); 107ca399021d47d640551eb786620bcd108e1758485Owen Anderson 108ca399021d47d640551eb786620bcd108e1758485Owen Anderson ++I; 109ca399021d47d640551eb786620bcd108e1758485Owen Anderson } 110ca399021d47d640551eb786620bcd108e1758485Owen Anderson newEntryBlock->getTerminator()->replaceUsesOfWith(preReturn, newReturnBlock); 111ca399021d47d640551eb786620bcd108e1758485Owen Anderson 112ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Gather up the blocks that we're going to extract. 113ca399021d47d640551eb786620bcd108e1758485Owen Anderson std::vector<BasicBlock*> toExtract; 114ca399021d47d640551eb786620bcd108e1758485Owen Anderson toExtract.push_back(newNonReturnBlock); 115ca399021d47d640551eb786620bcd108e1758485Owen Anderson for (Function::iterator FI = duplicateFunction->begin(), 116ca399021d47d640551eb786620bcd108e1758485Owen Anderson FE = duplicateFunction->end(); FI != FE; ++FI) 117ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (&*FI != newEntryBlock && &*FI != newReturnBlock && 118ca399021d47d640551eb786620bcd108e1758485Owen Anderson &*FI != newNonReturnBlock) 119cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar toExtract.push_back(&*FI); 120cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 121ca399021d47d640551eb786620bcd108e1758485Owen Anderson // The CodeExtractor needs a dominator tree. 122ca399021d47d640551eb786620bcd108e1758485Owen Anderson DominatorTree DT; 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT.recalculate(*duplicateFunction); 12436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 125f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Extract the body of the if. 12699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Function* extractedFunction 12799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth = CodeExtractor(toExtract, &DT).extractCodeRegion(); 128ca399021d47d640551eb786620bcd108e1758485Owen Anderson 12960915146f4d35e12f10dcdaa155596fac79184daChris Lattner InlineFunctionInfo IFI; 13060915146f4d35e12f10dcdaa155596fac79184daChris Lattner 131ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Inline the top-level if test into all callers. 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::vector<User *> Users(duplicateFunction->user_begin(), 13336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines duplicateFunction->user_end()); 134ca399021d47d640551eb786620bcd108e1758485Owen Anderson for (std::vector<User*>::iterator UI = Users.begin(), UE = Users.end(); 135ca399021d47d640551eb786620bcd108e1758485Owen Anderson UI != UE; ++UI) 13660915146f4d35e12f10dcdaa155596fac79184daChris Lattner if (CallInst *CI = dyn_cast<CallInst>(*UI)) 13760915146f4d35e12f10dcdaa155596fac79184daChris Lattner InlineFunction(CI, IFI); 13860915146f4d35e12f10dcdaa155596fac79184daChris Lattner else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) 13960915146f4d35e12f10dcdaa155596fac79184daChris Lattner InlineFunction(II, IFI); 140ca399021d47d640551eb786620bcd108e1758485Owen Anderson 141ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Ditch the duplicate, since we're done with it, and rewrite all remaining 142ca399021d47d640551eb786620bcd108e1758485Owen Anderson // users (function pointers, etc.) back to the original function. 143ca399021d47d640551eb786620bcd108e1758485Owen Anderson duplicateFunction->replaceAllUsesWith(F); 144ca399021d47d640551eb786620bcd108e1758485Owen Anderson duplicateFunction->eraseFromParent(); 145ca399021d47d640551eb786620bcd108e1758485Owen Anderson 146636768458f9c74b6062f1d9f159b6a0464b208c4Owen Anderson ++NumPartialInlined; 147636768458f9c74b6062f1d9f159b6a0464b208c4Owen Anderson 148ca399021d47d640551eb786620bcd108e1758485Owen Anderson return extractedFunction; 149ca399021d47d640551eb786620bcd108e1758485Owen Anderson} 150ca399021d47d640551eb786620bcd108e1758485Owen Anderson 151ca399021d47d640551eb786620bcd108e1758485Owen Andersonbool PartialInliner::runOnModule(Module& M) { 152ca399021d47d640551eb786620bcd108e1758485Owen Anderson std::vector<Function*> worklist; 153ca399021d47d640551eb786620bcd108e1758485Owen Anderson worklist.reserve(M.size()); 154ca399021d47d640551eb786620bcd108e1758485Owen Anderson for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) 155ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (!FI->use_empty() && !FI->isDeclaration()) 156b7a9f2b5042589db89e521a4f86fd2fd70845e0fDan Gohman worklist.push_back(&*FI); 157ca399021d47d640551eb786620bcd108e1758485Owen Anderson 158ca399021d47d640551eb786620bcd108e1758485Owen Anderson bool changed = false; 159ca399021d47d640551eb786620bcd108e1758485Owen Anderson while (!worklist.empty()) { 160ca399021d47d640551eb786620bcd108e1758485Owen Anderson Function* currFunc = worklist.back(); 161ca399021d47d640551eb786620bcd108e1758485Owen Anderson worklist.pop_back(); 162ca399021d47d640551eb786620bcd108e1758485Owen Anderson 163ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (currFunc->use_empty()) continue; 164ca399021d47d640551eb786620bcd108e1758485Owen Anderson 165ca399021d47d640551eb786620bcd108e1758485Owen Anderson bool recursive = false; 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (User *U : currFunc->users()) 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Instruction* I = dyn_cast<Instruction>(U)) 168ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (I->getParent()->getParent() == currFunc) { 169ca399021d47d640551eb786620bcd108e1758485Owen Anderson recursive = true; 170ca399021d47d640551eb786620bcd108e1758485Owen Anderson break; 171ca399021d47d640551eb786620bcd108e1758485Owen Anderson } 172ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (recursive) continue; 173ca399021d47d640551eb786620bcd108e1758485Owen Anderson 174ca399021d47d640551eb786620bcd108e1758485Owen Anderson 175ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (Function* newFunc = unswitchFunction(currFunc)) { 176ca399021d47d640551eb786620bcd108e1758485Owen Anderson worklist.push_back(newFunc); 177ca399021d47d640551eb786620bcd108e1758485Owen Anderson changed = true; 178ca399021d47d640551eb786620bcd108e1758485Owen Anderson } 179ca399021d47d640551eb786620bcd108e1758485Owen Anderson 180ca399021d47d640551eb786620bcd108e1758485Owen Anderson } 181ca399021d47d640551eb786620bcd108e1758485Owen Anderson 182ca399021d47d640551eb786620bcd108e1758485Owen Anderson return changed; 183d5f50da7f06199c03de1294981e35cfd1c4d53ddDuncan Sands} 184