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#define DEBUG_TYPE "partialinlining" 16ca399021d47d640551eb786620bcd108e1758485Owen Anderson#include "llvm/Transforms/IPO.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Dominators.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 21ca399021d47d640551eb786620bcd108e1758485Owen Anderson#include "llvm/Pass.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/CFG.h" 23ca399021d47d640551eb786620bcd108e1758485Owen Anderson#include "llvm/Transforms/Utils/Cloning.h" 2499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth#include "llvm/Transforms/Utils/CodeExtractor.h" 25ca399021d47d640551eb786620bcd108e1758485Owen Andersonusing namespace llvm; 26ca399021d47d640551eb786620bcd108e1758485Owen Anderson 27636768458f9c74b6062f1d9f159b6a0464b208c4Owen AndersonSTATISTIC(NumPartialInlined, "Number of functions partially inlined"); 28636768458f9c74b6062f1d9f159b6a0464b208c4Owen Anderson 29ca399021d47d640551eb786620bcd108e1758485Owen Andersonnamespace { 306726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct PartialInliner : public ModulePass { 31ca399021d47d640551eb786620bcd108e1758485Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { } 32ca399021d47d640551eb786620bcd108e1758485Owen Anderson static char ID; // Pass identification, replacement for typeid 33081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson PartialInliner() : ModulePass(ID) { 34081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializePartialInlinerPass(*PassRegistry::getPassRegistry()); 35081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 36ca399021d47d640551eb786620bcd108e1758485Owen Anderson 37ca399021d47d640551eb786620bcd108e1758485Owen Anderson bool runOnModule(Module& M); 38ca399021d47d640551eb786620bcd108e1758485Owen Anderson 39ca399021d47d640551eb786620bcd108e1758485Owen Anderson private: 40ca399021d47d640551eb786620bcd108e1758485Owen Anderson Function* unswitchFunction(Function* F); 41ca399021d47d640551eb786620bcd108e1758485Owen Anderson }; 42ca399021d47d640551eb786620bcd108e1758485Owen Anderson} 43ca399021d47d640551eb786620bcd108e1758485Owen Anderson 44ca399021d47d640551eb786620bcd108e1758485Owen Andersonchar PartialInliner::ID = 0; 45d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(PartialInliner, "partial-inliner", 46ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Partial Inliner", false, false) 47ca399021d47d640551eb786620bcd108e1758485Owen Anderson 48ca399021d47d640551eb786620bcd108e1758485Owen AndersonModulePass* llvm::createPartialInliningPass() { return new PartialInliner(); } 49ca399021d47d640551eb786620bcd108e1758485Owen Anderson 50ca399021d47d640551eb786620bcd108e1758485Owen AndersonFunction* PartialInliner::unswitchFunction(Function* F) { 51ca399021d47d640551eb786620bcd108e1758485Owen Anderson // First, verify that this function is an unswitching candidate... 52ca399021d47d640551eb786620bcd108e1758485Owen Anderson BasicBlock* entryBlock = F->begin(); 53a0ecbe782177d3ec7c98700434d2d92fb0c0e600Owen Anderson BranchInst *BR = dyn_cast<BranchInst>(entryBlock->getTerminator()); 54a0ecbe782177d3ec7c98700434d2d92fb0c0e600Owen Anderson if (!BR || BR->isUnconditional()) 55ca399021d47d640551eb786620bcd108e1758485Owen Anderson return 0; 56ca399021d47d640551eb786620bcd108e1758485Owen Anderson 57ca399021d47d640551eb786620bcd108e1758485Owen Anderson BasicBlock* returnBlock = 0; 58ca399021d47d640551eb786620bcd108e1758485Owen Anderson BasicBlock* nonReturnBlock = 0; 59ca399021d47d640551eb786620bcd108e1758485Owen Anderson unsigned returnCount = 0; 60ca399021d47d640551eb786620bcd108e1758485Owen Anderson for (succ_iterator SI = succ_begin(entryBlock), SE = succ_end(entryBlock); 61ca399021d47d640551eb786620bcd108e1758485Owen Anderson SI != SE; ++SI) 62ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (isa<ReturnInst>((*SI)->getTerminator())) { 63ca399021d47d640551eb786620bcd108e1758485Owen Anderson returnBlock = *SI; 64ca399021d47d640551eb786620bcd108e1758485Owen Anderson returnCount++; 65ca399021d47d640551eb786620bcd108e1758485Owen Anderson } else 66ca399021d47d640551eb786620bcd108e1758485Owen Anderson nonReturnBlock = *SI; 67ca399021d47d640551eb786620bcd108e1758485Owen Anderson 68ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (returnCount != 1) 69ca399021d47d640551eb786620bcd108e1758485Owen Anderson return 0; 70ca399021d47d640551eb786620bcd108e1758485Owen Anderson 71ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Clone the function, so that we can hack away on it. 721ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy VMap; 736cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman Function* duplicateFunction = CloneFunction(F, VMap, 746cb8c23db1c3becdce6dfbf1b7f1677faca4251eDan Gohman /*ModuleLevelChanges=*/false); 75ca399021d47d640551eb786620bcd108e1758485Owen Anderson duplicateFunction->setLinkage(GlobalValue::InternalLinkage); 76ca399021d47d640551eb786620bcd108e1758485Owen Anderson F->getParent()->getFunctionList().push_back(duplicateFunction); 77e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel BasicBlock* newEntryBlock = cast<BasicBlock>(VMap[entryBlock]); 78e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel BasicBlock* newReturnBlock = cast<BasicBlock>(VMap[returnBlock]); 79e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel BasicBlock* newNonReturnBlock = cast<BasicBlock>(VMap[nonReturnBlock]); 80ca399021d47d640551eb786620bcd108e1758485Owen Anderson 81ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Go ahead and update all uses to the duplicate, so that we can just 82ca399021d47d640551eb786620bcd108e1758485Owen Anderson // use the inliner functionality when we're done hacking. 83ca399021d47d640551eb786620bcd108e1758485Owen Anderson F->replaceAllUsesWith(duplicateFunction); 84ca399021d47d640551eb786620bcd108e1758485Owen Anderson 85ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Special hackery is needed with PHI nodes that have inputs from more than 86ca399021d47d640551eb786620bcd108e1758485Owen Anderson // one extracted block. For simplicity, just split the PHIs into a two-level 87ca399021d47d640551eb786620bcd108e1758485Owen Anderson // sequence of PHIs, some of which will go in the extracted region, and some 88ca399021d47d640551eb786620bcd108e1758485Owen Anderson // of which will go outside. 89ca399021d47d640551eb786620bcd108e1758485Owen Anderson BasicBlock* preReturn = newReturnBlock; 90ca399021d47d640551eb786620bcd108e1758485Owen Anderson newReturnBlock = newReturnBlock->splitBasicBlock( 91ca399021d47d640551eb786620bcd108e1758485Owen Anderson newReturnBlock->getFirstNonPHI()); 92ca399021d47d640551eb786620bcd108e1758485Owen Anderson BasicBlock::iterator I = preReturn->begin(); 93ca399021d47d640551eb786620bcd108e1758485Owen Anderson BasicBlock::iterator Ins = newReturnBlock->begin(); 94ca399021d47d640551eb786620bcd108e1758485Owen Anderson while (I != preReturn->end()) { 95ca399021d47d640551eb786620bcd108e1758485Owen Anderson PHINode* OldPhi = dyn_cast<PHINode>(I); 96ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (!OldPhi) break; 97ca399021d47d640551eb786620bcd108e1758485Owen Anderson 983ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode* retPhi = PHINode::Create(OldPhi->getType(), 2, "", Ins); 99ca399021d47d640551eb786620bcd108e1758485Owen Anderson OldPhi->replaceAllUsesWith(retPhi); 100ca399021d47d640551eb786620bcd108e1758485Owen Anderson Ins = newReturnBlock->getFirstNonPHI(); 101ca399021d47d640551eb786620bcd108e1758485Owen Anderson 102ca399021d47d640551eb786620bcd108e1758485Owen Anderson retPhi->addIncoming(I, preReturn); 103ca399021d47d640551eb786620bcd108e1758485Owen Anderson retPhi->addIncoming(OldPhi->getIncomingValueForBlock(newEntryBlock), 104ca399021d47d640551eb786620bcd108e1758485Owen Anderson newEntryBlock); 105ca399021d47d640551eb786620bcd108e1758485Owen Anderson OldPhi->removeIncomingValue(newEntryBlock); 106ca399021d47d640551eb786620bcd108e1758485Owen Anderson 107ca399021d47d640551eb786620bcd108e1758485Owen Anderson ++I; 108ca399021d47d640551eb786620bcd108e1758485Owen Anderson } 109ca399021d47d640551eb786620bcd108e1758485Owen Anderson newEntryBlock->getTerminator()->replaceUsesOfWith(preReturn, newReturnBlock); 110ca399021d47d640551eb786620bcd108e1758485Owen Anderson 111ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Gather up the blocks that we're going to extract. 112ca399021d47d640551eb786620bcd108e1758485Owen Anderson std::vector<BasicBlock*> toExtract; 113ca399021d47d640551eb786620bcd108e1758485Owen Anderson toExtract.push_back(newNonReturnBlock); 114ca399021d47d640551eb786620bcd108e1758485Owen Anderson for (Function::iterator FI = duplicateFunction->begin(), 115ca399021d47d640551eb786620bcd108e1758485Owen Anderson FE = duplicateFunction->end(); FI != FE; ++FI) 116ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (&*FI != newEntryBlock && &*FI != newReturnBlock && 117ca399021d47d640551eb786620bcd108e1758485Owen Anderson &*FI != newNonReturnBlock) 118ca399021d47d640551eb786620bcd108e1758485Owen Anderson toExtract.push_back(FI); 119ca399021d47d640551eb786620bcd108e1758485Owen Anderson 120ca399021d47d640551eb786620bcd108e1758485Owen Anderson // The CodeExtractor needs a dominator tree. 121ca399021d47d640551eb786620bcd108e1758485Owen Anderson DominatorTree DT; 122ca399021d47d640551eb786620bcd108e1758485Owen Anderson DT.runOnFunction(*duplicateFunction); 123ca399021d47d640551eb786620bcd108e1758485Owen Anderson 124f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Extract the body of the if. 12599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Function* extractedFunction 12699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth = CodeExtractor(toExtract, &DT).extractCodeRegion(); 127ca399021d47d640551eb786620bcd108e1758485Owen Anderson 12860915146f4d35e12f10dcdaa155596fac79184daChris Lattner InlineFunctionInfo IFI; 12960915146f4d35e12f10dcdaa155596fac79184daChris Lattner 130ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Inline the top-level if test into all callers. 131ca399021d47d640551eb786620bcd108e1758485Owen Anderson std::vector<User*> Users(duplicateFunction->use_begin(), 132ca399021d47d640551eb786620bcd108e1758485Owen Anderson duplicateFunction->use_end()); 133ca399021d47d640551eb786620bcd108e1758485Owen Anderson for (std::vector<User*>::iterator UI = Users.begin(), UE = Users.end(); 134ca399021d47d640551eb786620bcd108e1758485Owen Anderson UI != UE; ++UI) 13560915146f4d35e12f10dcdaa155596fac79184daChris Lattner if (CallInst *CI = dyn_cast<CallInst>(*UI)) 13660915146f4d35e12f10dcdaa155596fac79184daChris Lattner InlineFunction(CI, IFI); 13760915146f4d35e12f10dcdaa155596fac79184daChris Lattner else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) 13860915146f4d35e12f10dcdaa155596fac79184daChris Lattner InlineFunction(II, IFI); 139ca399021d47d640551eb786620bcd108e1758485Owen Anderson 140ca399021d47d640551eb786620bcd108e1758485Owen Anderson // Ditch the duplicate, since we're done with it, and rewrite all remaining 141ca399021d47d640551eb786620bcd108e1758485Owen Anderson // users (function pointers, etc.) back to the original function. 142ca399021d47d640551eb786620bcd108e1758485Owen Anderson duplicateFunction->replaceAllUsesWith(F); 143ca399021d47d640551eb786620bcd108e1758485Owen Anderson duplicateFunction->eraseFromParent(); 144ca399021d47d640551eb786620bcd108e1758485Owen Anderson 145636768458f9c74b6062f1d9f159b6a0464b208c4Owen Anderson ++NumPartialInlined; 146636768458f9c74b6062f1d9f159b6a0464b208c4Owen Anderson 147ca399021d47d640551eb786620bcd108e1758485Owen Anderson return extractedFunction; 148ca399021d47d640551eb786620bcd108e1758485Owen Anderson} 149ca399021d47d640551eb786620bcd108e1758485Owen Anderson 150ca399021d47d640551eb786620bcd108e1758485Owen Andersonbool PartialInliner::runOnModule(Module& M) { 151ca399021d47d640551eb786620bcd108e1758485Owen Anderson std::vector<Function*> worklist; 152ca399021d47d640551eb786620bcd108e1758485Owen Anderson worklist.reserve(M.size()); 153ca399021d47d640551eb786620bcd108e1758485Owen Anderson for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) 154ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (!FI->use_empty() && !FI->isDeclaration()) 155b7a9f2b5042589db89e521a4f86fd2fd70845e0fDan Gohman worklist.push_back(&*FI); 156ca399021d47d640551eb786620bcd108e1758485Owen Anderson 157ca399021d47d640551eb786620bcd108e1758485Owen Anderson bool changed = false; 158ca399021d47d640551eb786620bcd108e1758485Owen Anderson while (!worklist.empty()) { 159ca399021d47d640551eb786620bcd108e1758485Owen Anderson Function* currFunc = worklist.back(); 160ca399021d47d640551eb786620bcd108e1758485Owen Anderson worklist.pop_back(); 161ca399021d47d640551eb786620bcd108e1758485Owen Anderson 162ca399021d47d640551eb786620bcd108e1758485Owen Anderson if (currFunc->use_empty()) continue; 163ca399021d47d640551eb786620bcd108e1758485Owen Anderson 164ca399021d47d640551eb786620bcd108e1758485Owen Anderson bool recursive = false; 165ca399021d47d640551eb786620bcd108e1758485Owen Anderson for (Function::use_iterator UI = currFunc->use_begin(), 166ca399021d47d640551eb786620bcd108e1758485Owen Anderson UE = currFunc->use_end(); UI != UE; ++UI) 16785e01df73d9051ad9468cc835fabbdf40b77e5f6Gabor Greif if (Instruction* I = dyn_cast<Instruction>(*UI)) 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