contrib/llvm/lib/Transforms/IPO/PartialInlining.cpp

   1 //===- PartialInlining.cpp - Inline parts of functions --------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass performs partial inlining, typically by inlining an if statement
  11 // that surrounds the body of the function.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/IPO/PartialInlining.h"
  16 #include "llvm/ADT/Statistic.h"
  17 #include "llvm/Analysis/BlockFrequencyInfo.h"
  18 #include "llvm/Analysis/BranchProbabilityInfo.h"
  19 #include "llvm/Analysis/LoopInfo.h"
  20 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
  21 #include "llvm/IR/CFG.h"
  22 #include "llvm/IR/DiagnosticInfo.h"
  23 #include "llvm/IR/Dominators.h"
  24 #include "llvm/IR/Instructions.h"
  25 #include "llvm/IR/Module.h"
  26 #include "llvm/Pass.h"
  27 #include "llvm/Transforms/IPO.h"
  28 #include "llvm/Transforms/Utils/Cloning.h"
  29 #include "llvm/Transforms/Utils/CodeExtractor.h"
  30 using namespace llvm;
  31
  32 #define DEBUG_TYPE "partial-inlining"
  33
  34 STATISTIC(NumPartialInlined, "Number of functions partially inlined");
  35
  36 // Command line option to disable partial-inlining. The default is false:
  37 static cl::opt<bool>
  38     DisablePartialInlining("disable-partial-inlining", cl::init(false),
  39                            cl::Hidden, cl::desc("Disable partial ininling"));
  40
  41 // Command line option to set the maximum number of partial inlining allowed
  42 // for the module. The default value of -1 means no limit.
  43 static cl::opt<int> MaxNumPartialInlining(
  44     "max-partial-inlining", cl::init(-1), cl::Hidden, cl::ZeroOrMore,
  45     cl::desc("Max number of partial inlining. The default is unlimited"));
  46
  47 namespace {
  48 struct PartialInlinerImpl {
  49   PartialInlinerImpl(InlineFunctionInfo IFI) : IFI(std::move(IFI)) {}
  50   bool run(Module &M);
  51   Function *unswitchFunction(Function *F);
  52
  53 private:
  54   InlineFunctionInfo IFI;
  55   int NumPartialInlining = 0;
  56
  57   bool IsLimitReached() {
  58     return (MaxNumPartialInlining != -1 &&
  59             NumPartialInlining >= MaxNumPartialInlining);
  60   }
  61 };
  62 struct PartialInlinerLegacyPass : public ModulePass {
  63   static char ID; // Pass identification, replacement for typeid
  64   PartialInlinerLegacyPass() : ModulePass(ID) {
  65     initializePartialInlinerLegacyPassPass(*PassRegistry::getPassRegistry());
  66   }
  67
  68   void getAnalysisUsage(AnalysisUsage &AU) const override {
  69     AU.addRequired<AssumptionCacheTracker>();
  70   }
  71   bool runOnModule(Module &M) override {
  72     if (skipModule(M))
  73       return false;
  74
  75     AssumptionCacheTracker *ACT = &getAnalysis<AssumptionCacheTracker>();
  76     std::function<AssumptionCache &(Function &)> GetAssumptionCache =
  77         [&ACT](Function &F) -> AssumptionCache & {
  78       return ACT->getAssumptionCache(F);
  79     };
  80     InlineFunctionInfo IFI(nullptr, &GetAssumptionCache);
  81     return PartialInlinerImpl(IFI).run(M);
  82   }
  83 };
  84 }
  85
  86 Function *PartialInlinerImpl::unswitchFunction(Function *F) {
  87   // First, verify that this function is an unswitching candidate...
  88   if (F->hasAddressTaken())
  89     return nullptr;
  90
  91   BasicBlock *EntryBlock = &F->front();
  92   BranchInst *BR = dyn_cast<BranchInst>(EntryBlock->getTerminator());
  93   if (!BR || BR->isUnconditional())
  94     return nullptr;
  95
  96   BasicBlock *ReturnBlock = nullptr;
  97   BasicBlock *NonReturnBlock = nullptr;
  98   unsigned ReturnCount = 0;
  99   for (BasicBlock *BB : successors(EntryBlock)) {
 100     if (isa<ReturnInst>(BB->getTerminator())) {
 101       ReturnBlock = BB;
 102       ReturnCount++;
 103     } else
 104       NonReturnBlock = BB;
 105   }
 106
 107   if (ReturnCount != 1)
 108     return nullptr;
 109
 110   // Clone the function, so that we can hack away on it.
 111   ValueToValueMapTy VMap;
 112   Function *DuplicateFunction = CloneFunction(F, VMap);
 113   DuplicateFunction->setLinkage(GlobalValue::InternalLinkage);
 114   BasicBlock *NewEntryBlock = cast<BasicBlock>(VMap[EntryBlock]);
 115   BasicBlock *NewReturnBlock = cast<BasicBlock>(VMap[ReturnBlock]);
 116   BasicBlock *NewNonReturnBlock = cast<BasicBlock>(VMap[NonReturnBlock]);
 117
 118   // Go ahead and update all uses to the duplicate, so that we can just
 119   // use the inliner functionality when we're done hacking.
 120   F->replaceAllUsesWith(DuplicateFunction);
 121
 122   // Special hackery is needed with PHI nodes that have inputs from more than
 123   // one extracted block.  For simplicity, just split the PHIs into a two-level
 124   // sequence of PHIs, some of which will go in the extracted region, and some
 125   // of which will go outside.
 126   BasicBlock *PreReturn = NewReturnBlock;
 127   NewReturnBlock = NewReturnBlock->splitBasicBlock(
 128       NewReturnBlock->getFirstNonPHI()->getIterator());
 129   BasicBlock::iterator I = PreReturn->begin();
 130   Instruction *Ins = &NewReturnBlock->front();
 131   while (I != PreReturn->end()) {
 132     PHINode *OldPhi = dyn_cast<PHINode>(I);
 133     if (!OldPhi)
 134       break;
 135
 136     PHINode *RetPhi = PHINode::Create(OldPhi->getType(), 2, "", Ins);
 137     OldPhi->replaceAllUsesWith(RetPhi);
 138     Ins = NewReturnBlock->getFirstNonPHI();
 139
 140     RetPhi->addIncoming(&*I, PreReturn);
 141     RetPhi->addIncoming(OldPhi->getIncomingValueForBlock(NewEntryBlock),
 142                         NewEntryBlock);
 143     OldPhi->removeIncomingValue(NewEntryBlock);
 144
 145     ++I;
 146   }
 147   NewEntryBlock->getTerminator()->replaceUsesOfWith(PreReturn, NewReturnBlock);
 148
 149   // Gather up the blocks that we're going to extract.
 150   std::vector<BasicBlock *> ToExtract;
 151   ToExtract.push_back(NewNonReturnBlock);
 152   for (BasicBlock &BB : *DuplicateFunction)
 153     if (&BB != NewEntryBlock && &BB != NewReturnBlock &&
 154         &BB != NewNonReturnBlock)
 155       ToExtract.push_back(&BB);
 156
 157   // The CodeExtractor needs a dominator tree.
 158   DominatorTree DT;
 159   DT.recalculate(*DuplicateFunction);
 160
 161   // Manually calculate a BlockFrequencyInfo and BranchProbabilityInfo.
 162   LoopInfo LI(DT);
 163   BranchProbabilityInfo BPI(*DuplicateFunction, LI);
 164   BlockFrequencyInfo BFI(*DuplicateFunction, BPI, LI);
 165
 166   // Extract the body of the if.
 167   Function *ExtractedFunction =
 168       CodeExtractor(ToExtract, &DT, /*AggregateArgs*/ false, &BFI, &BPI)
 169           .extractCodeRegion();
 170
 171   // Inline the top-level if test into all callers.
 172   std::vector<User *> Users(DuplicateFunction->user_begin(),
 173                             DuplicateFunction->user_end());
 174
 175   for (User *User : Users) {
 176     CallSite CS;
 177     if (CallInst *CI = dyn_cast<CallInst>(User))
 178       CS = CallSite(CI);
 179     else if (InvokeInst *II = dyn_cast<InvokeInst>(User))
 180       CS = CallSite(II);
 181     else
 182       llvm_unreachable("All uses must be calls");
 183
 184     if (IsLimitReached())
 185       continue;
 186     NumPartialInlining++;
 187
 188     OptimizationRemarkEmitter ORE(CS.getCaller());
 189     DebugLoc DLoc = CS.getInstruction()->getDebugLoc();
 190     BasicBlock *Block = CS.getParent();
 191     ORE.emit(OptimizationRemark(DEBUG_TYPE, "PartiallyInlined", DLoc, Block)
 192              << ore::NV("Callee", F) << " partially inlined into "
 193              << ore::NV("Caller", CS.getCaller()));
 194
 195     InlineFunction(CS, IFI);
 196   }
 197
 198   // Ditch the duplicate, since we're done with it, and rewrite all remaining
 199   // users (function pointers, etc.) back to the original function.
 200   DuplicateFunction->replaceAllUsesWith(F);
 201   DuplicateFunction->eraseFromParent();
 202
 203   ++NumPartialInlined;
 204
 205   return ExtractedFunction;
 206 }
 207
 208 bool PartialInlinerImpl::run(Module &M) {
 209   if (DisablePartialInlining)
 210     return false;
 211
 212   std::vector<Function *> Worklist;
 213   Worklist.reserve(M.size());
 214   for (Function &F : M)
 215     if (!F.use_empty() && !F.isDeclaration())
 216       Worklist.push_back(&F);
 217
 218   bool Changed = false;
 219   while (!Worklist.empty()) {
 220     Function *CurrFunc = Worklist.back();
 221     Worklist.pop_back();
 222
 223     if (CurrFunc->use_empty())
 224       continue;
 225
 226     bool Recursive = false;
 227     for (User *U : CurrFunc->users())
 228       if (Instruction *I = dyn_cast<Instruction>(U))
 229         if (I->getParent()->getParent() == CurrFunc) {
 230           Recursive = true;
 231           break;
 232         }
 233     if (Recursive)
 234       continue;
 235
 236     if (Function *NewFunc = unswitchFunction(CurrFunc)) {
 237       Worklist.push_back(NewFunc);
 238       Changed = true;
 239     }
 240   }
 241
 242   return Changed;
 243 }
 244
 245 char PartialInlinerLegacyPass::ID = 0;
 246 INITIALIZE_PASS_BEGIN(PartialInlinerLegacyPass, "partial-inliner",
 247                       "Partial Inliner", false, false)
 248 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 249 INITIALIZE_PASS_END(PartialInlinerLegacyPass, "partial-inliner",
 250                     "Partial Inliner", false, false)
 251
 252 ModulePass *llvm::createPartialInliningPass() {
 253   return new PartialInlinerLegacyPass();
 254 }
 255
 256 PreservedAnalyses PartialInlinerPass::run(Module &M,
 257                                           ModuleAnalysisManager &AM) {
 258   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 259   std::function<AssumptionCache &(Function &)> GetAssumptionCache =
 260       [&FAM](Function &F) -> AssumptionCache & {
 261     return FAM.getResult<AssumptionAnalysis>(F);
 262   };
 263   InlineFunctionInfo IFI(nullptr, &GetAssumptionCache);
 264   if (PartialInlinerImpl(IFI).run(M))
 265     return PreservedAnalyses::none();
 266   return PreservedAnalyses::all();
 267 }