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 using namespace llvm;
  27
  28 namespace {
  29   Statistic<> NumInlined("inline", "Number of functions inlined");
  30   Statistic<> NumDeleted("inline", "Number of functions deleted because all callers found");
  31   cl::opt<unsigned>             // FIXME: 200 is VERY conservative
  32   InlineLimit("inline-threshold", cl::Hidden, cl::init(200),
  33               cl::desc("Control the amount of inlining to perform (default = 200)"));
  34 }
  35
  36 Inliner::Inliner() : InlineThreshold(InlineLimit) {}
  37
  38 int Inliner::getRecursiveInlineCost(CallSite CS) {
  39   return getInlineCost(CS);
  40 }
  41
  42 bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) {
  43   CallGraph &CG = getAnalysis<CallGraph>();
  44
  45   std::set<Function*> SCCFunctions;
  46   DEBUG(std::cerr << "Inliner visiting SCC:");
  47   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
  48     SCCFunctions.insert(SCC[i]->getFunction());
  49     DEBUG(std::cerr << " " << (SCC[i]->getFunction() ?
  50               SCC[i]->getFunction()->getName() : "INDIRECTNODE"));
  51   }
  52   DEBUG(std::cerr << "\n");
  53
  54   bool Changed = false;
  55   for (std::set<Function*>::iterator SCCI = SCCFunctions.begin(),
  56          E = SCCFunctions.end(); SCCI != E; ++SCCI) {
  57     Function *F = *SCCI;
  58     if (F == 0 || F->isExternal()) continue;
  59     DEBUG(std::cerr << "  Inspecting function: " << F->getName() << "\n");
  60
  61     // Scan through and identify all call sites ahead of time so that we only
  62     // inline call sites in the original functions, not call sites that result
  63     // in inlining other functions.
  64     std::vector<CallSite> CallSites;
  65     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
  66       for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
  67         CallSite CS = CallSite::get(I);
  68         if (CS.getInstruction() && CS.getCalledFunction() &&
  69             !CS.getCalledFunction()->isExternal())
  70           CallSites.push_back(CS);
  71       }
  72
  73     // Now that we have all of the call sites, loop over them and inline them if
  74     // it looks profitable to do so.
  75     for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
  76       CallSite CS = CallSites[i];
  77       Function *Callee = CS.getCalledFunction();
  78       // Determine whether this is a function IN the SCC...
  79       bool inSCC = SCCFunctions.count(Callee);
  80
  81       // If the policy determines that we should inline this function,
  82       // try to do so...
  83       int InlineCost = inSCC ? getRecursiveInlineCost(CS) : getInlineCost(CS);
  84       if (InlineCost >= (int)InlineThreshold) {
  85         DEBUG(std::cerr << "    NOT Inlining: cost=" << InlineCost
  86               << ", Call: " << *CS.getInstruction());
  87       } else {
  88         DEBUG(std::cerr << "    Inlining: cost=" << InlineCost
  89               << ", Call: " << *CS.getInstruction());
  90
  91         Function *Caller = CS.getInstruction()->getParent()->getParent();
  92
  93         // Attempt to inline the function...
  94         if (InlineFunction(CS)) {
  95           ++NumInlined;
  96
  97           // Update the call graph by deleting the edge from Callee to Caller
  98           CallGraphNode *CalleeNode = CG[Callee];
  99           CallGraphNode *CallerNode = CG[Caller];
 100           CallerNode->removeCallEdgeTo(CalleeNode);
 101
 102           // Since we inlined all uninlinable call sites in the callee into the
 103           // caller, add edges from the caller to all of the callees of the
 104           // callee.
 105           for (CallGraphNode::iterator I = CalleeNode->begin(),
 106                  E = CalleeNode->end(); I != E; ++I)
 107             CallerNode->addCalledFunction(*I);
 108
 109           // If we inlined the last possible call site to the function,
 110           // delete the function body now.
 111           if (Callee->use_empty() && Callee != Caller &&
 112               Callee->hasInternalLinkage()) {
 113             DEBUG(std::cerr << "    -> Deleting dead function: "
 114                             << Callee->getName() << "\n");
 115             SCCFunctions.erase(Callee);    // Remove function from this SCC.
 116
 117             // Remove any call graph edges from the callee to its callees.
 118             while (CalleeNode->begin() != CalleeNode->end())
 119               CalleeNode->removeCallEdgeTo(*(CalleeNode->end()-1));
 120
 121             // Removing the node for callee from the call graph and delete it.
 122             delete CG.removeFunctionFromModule(CalleeNode);
 123             ++NumDeleted;
 124           }
 125           Changed = true;
 126         }
 127       }
 128     }
 129   }
 130
 131   return Changed;
 132 }
 133
 134 // doFinalization - Remove now-dead linkonce functions at the end of
 135 // processing to avoid breaking the SCC traversal.
 136 bool Inliner::doFinalization(CallGraph &CG) {
 137   std::set<CallGraphNode*> FunctionsToRemove;
 138
 139   // Scan for all of the functions, looking for ones that should now be removed
 140   // from the program.  Insert the dead ones in the FunctionsToRemove set.
 141   for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) {
 142     CallGraphNode *CGN = I->second;
 143     Function *F = CGN ? CGN->getFunction() : 0;
 144
 145     // If the only remaining use of the function is a dead constant
 146     // pointer ref, remove it.
 147     if (F && F->hasOneUse())
 148       if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(F->use_back()))
 149         if (CPR->use_empty()) {
 150           CPR->destroyConstant();
 151           if (F->hasInternalLinkage()) {
 152             // There *MAY* be an edge from the external call node to this
 153             // function.  If so, remove it.
 154             CallGraphNode *EN = CG.getExternalCallingNode();
 155             CallGraphNode::iterator I = std::find(EN->begin(), EN->end(), CGN);
 156             if (I != EN->end()) EN->removeCallEdgeTo(CGN);
 157           }
 158         }
 159
 160     if (F && (F->hasLinkOnceLinkage() || F->hasInternalLinkage()) &&
 161         F->use_empty()) {
 162       // Remove any call graph edges from the function to its callees.
 163       while (CGN->begin() != CGN->end())
 164         CGN->removeCallEdgeTo(*(CGN->end()-1));
 165
 166       // If the function has external linkage (basically if it's a linkonce
 167       // function) remove the edge from the external node to the callee node.
 168       if (!F->hasInternalLinkage())
 169         CG.getExternalCallingNode()->removeCallEdgeTo(CGN);
 170
 171       // Removing the node for callee from the call graph and delete it.
 172       FunctionsToRemove.insert(CGN);
 173     }
 174   }
 175
 176   // Now that we know which functions to delete, do so.  We didn't want to do
 177   // this inline, because that would invalidate our CallGraph::iterator
 178   // objects. :(
 179   bool Changed = false;
 180   for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(),
 181          E = FunctionsToRemove.end(); I != E; ++I) {
 182     delete CG.removeFunctionFromModule(*I);
 183     ++NumDeleted;
 184     Changed = true;
 185   }
 186
 187   return Changed;
 188 }