lib/Transforms/IPO/Inliner.cpp

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