lib/Transforms/IPO/Inliner.cpp

   1 //===- InlineCommon.cpp - Code common to all inliners ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the code shared between the LLVM inliners.  This
  11 // implements all of the boring mechanics of the bottom-up inlining.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "Inliner.h"
  16 #include "llvm/Constants.h"   // ConstantPointerRef should die
  17 #include "llvm/Module.h"
  18 #include "llvm/iOther.h"
  19 #include "llvm/iTerminators.h"
  20 #include "llvm/Analysis/CallGraph.h"
  21 #include "llvm/Support/CallSite.h"
  22 #include "llvm/Transforms/Utils/Cloning.h"
  23 #include "Support/CommandLine.h"
  24 #include "Support/Debug.h"
  25 #include "Support/Statistic.h"
  26
  27 namespace {
  28   Statistic<> NumInlined("inline", "Number of functions inlined");
  29   Statistic<> NumDeleted("inline", "Number of functions deleted because all callers found");
  30   cl::opt<unsigned>             // FIXME: 200 is VERY conservative
  31   InlineLimit("inline-threshold", cl::Hidden, cl::init(200),
  32               cl::desc("Control the amount of inlining to perform (default = 200)"));
  33 }
  34
  35 Inliner::Inliner() : InlineThreshold(InlineLimit) {}
  36
  37 int Inliner::getRecursiveInlineCost(CallSite CS) {
  38   return getInlineCost(CS);
  39 }
  40
  41 bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) {
  42   CallGraph &CG = getAnalysis<CallGraph>();
  43
  44   std::set<Function*> SCCFunctions;
  45   DEBUG(std::cerr << "Inliner visiting SCC:");
  46   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
  47     SCCFunctions.insert(SCC[i]->getFunction());
  48     DEBUG(std::cerr << " " << (SCC[i]->getFunction() ?
  49               SCC[i]->getFunction()->getName() : "INDIRECTNODE"));
  50   }
  51   DEBUG(std::cerr << "\n");
  52
  53   bool Changed = false;
  54   for (std::set<Function*>::iterator SCCI = SCCFunctions.begin(),
  55          E = SCCFunctions.end(); SCCI != E; ++SCCI) {
  56     Function *F = *SCCI;
  57     if (F == 0 || F->isExternal()) continue;
  58     DEBUG(std::cerr << "  Inspecting function: " << F->getName() << "\n");
  59
  60     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
  61       for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
  62         bool ShouldInc = true;
  63         // Found a call or invoke instruction?
  64         if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
  65           CallSite CS = CallSite::get(I);
  66           if (Function *Callee = CS.getCalledFunction())
  67             if (!Callee->isExternal() && !IsRecursiveFunction.count(Callee)) {
  68               // Determine whether this is a function IN the SCC...
  69               bool inSCC = SCCFunctions.count(Callee);
  70
  71               // Keep track of whether this is a directly recursive function.
  72               if (Callee == F) IsRecursiveFunction.insert(F);
  73
  74               // If the policy determines that we should inline this function,
  75               // try to do so...
  76               int InlineCost = inSCC ? getRecursiveInlineCost(CS) :
  77                                        getInlineCost(CS);
  78               if (InlineCost < (int)InlineThreshold) {
  79                 DEBUG(std::cerr << "    Inlining: cost=" << InlineCost
  80                                 << ", Call: " << *CS.getInstruction());
  81
  82                 // Save an iterator to the instruction before the call if it
  83                 // exists, otherwise get an iterator at the end of the
  84                 // block... because the call will be destroyed.
  85                 //
  86                 BasicBlock::iterator SI;
  87                 if (I != BB->begin()) {
  88                   SI = I; --SI;           // Instruction before the call...
  89                 } else {
  90                   SI = BB->end();
  91                 }
  92
  93                 if (performInlining(CS, SCCFunctions)) {
  94                   // Move to instruction before the call...
  95                   I = (SI == BB->end()) ? BB->begin() : SI;
  96                   ShouldInc = false; // Don't increment iterator until next time
  97                   Changed = true;
  98                 }
  99               }
 100             }
 101         }
 102         if (ShouldInc) ++I;
 103       }
 104   }
 105   return Changed;
 106 }
 107
 108 bool Inliner::performInlining(CallSite CS, std::set<Function*> &SCC) {
 109   Function *Callee = CS.getCalledFunction();
 110   Function *Caller = CS.getInstruction()->getParent()->getParent();
 111
 112   // Attempt to inline the function...
 113   if (!InlineFunction(CS)) return false;
 114   ++NumInlined;
 115
 116   if (Callee->hasOneUse())
 117     if (ConstantPointerRef *CPR =
 118         dyn_cast<ConstantPointerRef>(Callee->use_back()))
 119       if (CPR->use_empty())
 120         CPR->destroyConstant();
 121
 122   // If we inlined the last possible call site to the function,
 123   // delete the function body now.
 124   if (Callee->use_empty() && Callee != Caller &&
 125       (Callee->hasInternalLinkage() || Callee->hasLinkOnceLinkage())) {
 126     DEBUG(std::cerr << "    -> Deleting dead function: " << (void*)Callee
 127                     << Callee->getName() << "\n");
 128     std::set<Function*>::iterator I = SCC.find(Callee);
 129     if (I != SCC.end())       // Remove function from this SCC...
 130       SCC.erase(I);
 131
 132     Callee->getParent()->getFunctionList().erase(Callee);
 133     ++NumDeleted;
 134   }
 135   return true;
 136 }