LLVM API Documentation

PartialInlining.cpp
Go to the documentation of this file.
00001 //===- PartialInlining.cpp - Inline parts of functions --------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass performs partial inlining, typically by inlining an if statement
00011 // that surrounds the body of the function.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "partialinlining"
00016 #include "llvm/Transforms/IPO.h"
00017 #include "llvm/ADT/Statistic.h"
00018 #include "llvm/IR/CFG.h"
00019 #include "llvm/IR/Dominators.h"
00020 #include "llvm/IR/Instructions.h"
00021 #include "llvm/IR/Module.h"
00022 #include "llvm/Pass.h"
00023 #include "llvm/Transforms/Utils/Cloning.h"
00024 #include "llvm/Transforms/Utils/CodeExtractor.h"
00025 using namespace llvm;
00026 
00027 STATISTIC(NumPartialInlined, "Number of functions partially inlined");
00028 
00029 namespace {
00030   struct PartialInliner : public ModulePass {
00031     void getAnalysisUsage(AnalysisUsage &AU) const override { }
00032     static char ID; // Pass identification, replacement for typeid
00033     PartialInliner() : ModulePass(ID) {
00034       initializePartialInlinerPass(*PassRegistry::getPassRegistry());
00035     }
00036 
00037     bool runOnModule(Module& M) override;
00038 
00039   private:
00040     Function* unswitchFunction(Function* F);
00041   };
00042 }
00043 
00044 char PartialInliner::ID = 0;
00045 INITIALIZE_PASS(PartialInliner, "partial-inliner",
00046                 "Partial Inliner", false, false)
00047 
00048 ModulePass* llvm::createPartialInliningPass() { return new PartialInliner(); }
00049 
00050 Function* PartialInliner::unswitchFunction(Function* F) {
00051   // First, verify that this function is an unswitching candidate...
00052   BasicBlock* entryBlock = F->begin();
00053   BranchInst *BR = dyn_cast<BranchInst>(entryBlock->getTerminator());
00054   if (!BR || BR->isUnconditional())
00055     return 0;
00056   
00057   BasicBlock* returnBlock = 0;
00058   BasicBlock* nonReturnBlock = 0;
00059   unsigned returnCount = 0;
00060   for (succ_iterator SI = succ_begin(entryBlock), SE = succ_end(entryBlock);
00061        SI != SE; ++SI)
00062     if (isa<ReturnInst>((*SI)->getTerminator())) {
00063       returnBlock = *SI;
00064       returnCount++;
00065     } else
00066       nonReturnBlock = *SI;
00067   
00068   if (returnCount != 1)
00069     return 0;
00070   
00071   // Clone the function, so that we can hack away on it.
00072   ValueToValueMapTy VMap;
00073   Function* duplicateFunction = CloneFunction(F, VMap,
00074                                               /*ModuleLevelChanges=*/false);
00075   duplicateFunction->setLinkage(GlobalValue::InternalLinkage);
00076   F->getParent()->getFunctionList().push_back(duplicateFunction);
00077   BasicBlock* newEntryBlock = cast<BasicBlock>(VMap[entryBlock]);
00078   BasicBlock* newReturnBlock = cast<BasicBlock>(VMap[returnBlock]);
00079   BasicBlock* newNonReturnBlock = cast<BasicBlock>(VMap[nonReturnBlock]);
00080   
00081   // Go ahead and update all uses to the duplicate, so that we can just
00082   // use the inliner functionality when we're done hacking.
00083   F->replaceAllUsesWith(duplicateFunction);
00084   
00085   // Special hackery is needed with PHI nodes that have inputs from more than
00086   // one extracted block.  For simplicity, just split the PHIs into a two-level
00087   // sequence of PHIs, some of which will go in the extracted region, and some
00088   // of which will go outside.
00089   BasicBlock* preReturn = newReturnBlock;
00090   newReturnBlock = newReturnBlock->splitBasicBlock(
00091                                               newReturnBlock->getFirstNonPHI());
00092   BasicBlock::iterator I = preReturn->begin();
00093   BasicBlock::iterator Ins = newReturnBlock->begin();
00094   while (I != preReturn->end()) {
00095     PHINode* OldPhi = dyn_cast<PHINode>(I);
00096     if (!OldPhi) break;
00097     
00098     PHINode* retPhi = PHINode::Create(OldPhi->getType(), 2, "", Ins);
00099     OldPhi->replaceAllUsesWith(retPhi);
00100     Ins = newReturnBlock->getFirstNonPHI();
00101     
00102     retPhi->addIncoming(I, preReturn);
00103     retPhi->addIncoming(OldPhi->getIncomingValueForBlock(newEntryBlock),
00104                         newEntryBlock);
00105     OldPhi->removeIncomingValue(newEntryBlock);
00106     
00107     ++I;
00108   }
00109   newEntryBlock->getTerminator()->replaceUsesOfWith(preReturn, newReturnBlock);
00110   
00111   // Gather up the blocks that we're going to extract.
00112   std::vector<BasicBlock*> toExtract;
00113   toExtract.push_back(newNonReturnBlock);
00114   for (Function::iterator FI = duplicateFunction->begin(),
00115        FE = duplicateFunction->end(); FI != FE; ++FI)
00116     if (&*FI != newEntryBlock && &*FI != newReturnBlock &&
00117         &*FI != newNonReturnBlock)
00118       toExtract.push_back(FI);
00119       
00120   // The CodeExtractor needs a dominator tree.
00121   DominatorTree DT;
00122   DT.recalculate(*duplicateFunction);
00123 
00124   // Extract the body of the if.
00125   Function* extractedFunction
00126     = CodeExtractor(toExtract, &DT).extractCodeRegion();
00127   
00128   InlineFunctionInfo IFI;
00129   
00130   // Inline the top-level if test into all callers.
00131   std::vector<User *> Users(duplicateFunction->user_begin(),
00132                             duplicateFunction->user_end());
00133   for (std::vector<User*>::iterator UI = Users.begin(), UE = Users.end();
00134        UI != UE; ++UI)
00135     if (CallInst *CI = dyn_cast<CallInst>(*UI))
00136       InlineFunction(CI, IFI);
00137     else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI))
00138       InlineFunction(II, IFI);
00139   
00140   // Ditch the duplicate, since we're done with it, and rewrite all remaining
00141   // users (function pointers, etc.) back to the original function.
00142   duplicateFunction->replaceAllUsesWith(F);
00143   duplicateFunction->eraseFromParent();
00144   
00145   ++NumPartialInlined;
00146   
00147   return extractedFunction;
00148 }
00149 
00150 bool PartialInliner::runOnModule(Module& M) {
00151   std::vector<Function*> worklist;
00152   worklist.reserve(M.size());
00153   for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
00154     if (!FI->use_empty() && !FI->isDeclaration())
00155       worklist.push_back(&*FI);
00156     
00157   bool changed = false;
00158   while (!worklist.empty()) {
00159     Function* currFunc = worklist.back();
00160     worklist.pop_back();
00161   
00162     if (currFunc->use_empty()) continue;
00163     
00164     bool recursive = false;
00165     for (User *U : currFunc->users())
00166       if (Instruction* I = dyn_cast<Instruction>(U))
00167         if (I->getParent()->getParent() == currFunc) {
00168           recursive = true;
00169           break;
00170         }
00171     if (recursive) continue;
00172           
00173     
00174     if (Function* newFunc = unswitchFunction(currFunc)) {
00175       worklist.push_back(newFunc);
00176       changed = true;
00177     }
00178     
00179   }
00180   
00181   return changed;
00182 }