LLVM API Documentation

Inliner.cpp

Go to the documentation of this file.
00001 //===- Inliner.cpp - Code common to all inliners --------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the mechanics required to implement inlining without
00011 // missing any calls and updating the call graph.  The decisions of which calls
00012 // are profitable to inline are implemented elsewhere.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "Inliner.h"
00017 #include "llvm/Module.h"
00018 #include "llvm/Instructions.h"
00019 #include "llvm/Analysis/CallGraph.h"
00020 #include "llvm/Support/CallSite.h"
00021 #include "llvm/Transforms/Utils/Cloning.h"
00022 #include "llvm/Support/CommandLine.h"
00023 #include "llvm/Support/Debug.h"
00024 #include "llvm/ADT/Statistic.h"
00025 #include <iostream>
00026 #include <set>
00027 using namespace llvm;
00028 
00029 namespace {
00030   Statistic<> NumInlined("inline", "Number of functions inlined");
00031   Statistic<> NumDeleted("inline",
00032                        "Number of functions deleted because all callers found");
00033   cl::opt<unsigned>             // FIXME: 200 is VERY conservative
00034   InlineLimit("inline-threshold", cl::Hidden, cl::init(200),
00035         cl::desc("Control the amount of inlining to perform (default = 200)"));
00036 }
00037 
00038 Inliner::Inliner() : InlineThreshold(InlineLimit) {}
00039 
00040 // InlineCallIfPossible - If it is possible to inline the specified call site,
00041 // do so and update the CallGraph for this operation.
00042 static bool InlineCallIfPossible(CallSite CS, CallGraph &CG,
00043                                  const std::set<Function*> &SCCFunctions) {
00044   Function *Caller = CS.getInstruction()->getParent()->getParent();
00045   Function *Callee = CS.getCalledFunction();
00046   if (!InlineFunction(CS, &CG)) return false;
00047 
00048   // If we inlined the last possible call site to the function, delete the
00049   // function body now.
00050   if (Callee->use_empty() && Callee->hasInternalLinkage() &&
00051       !SCCFunctions.count(Callee)) {
00052     DEBUG(std::cerr << "    -> Deleting dead function: "
00053                     << Callee->getName() << "\n");
00054 
00055     // Remove any call graph edges from the callee to its callees.
00056     CallGraphNode *CalleeNode = CG[Callee];
00057     while (CalleeNode->begin() != CalleeNode->end())
00058       CalleeNode->removeCallEdgeTo(*(CalleeNode->end()-1));
00059 
00060     // Removing the node for callee from the call graph and delete it.
00061     delete CG.removeFunctionFromModule(CalleeNode);
00062     ++NumDeleted;
00063   }
00064   return true;
00065 }
00066 
00067 bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) {
00068   CallGraph &CG = getAnalysis<CallGraph>();
00069 
00070   std::set<Function*> SCCFunctions;
00071   DEBUG(std::cerr << "Inliner visiting SCC:");
00072   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00073     Function *F = SCC[i]->getFunction();
00074     if (F) SCCFunctions.insert(F);
00075     DEBUG(std::cerr << " " << (F ? F->getName() : "INDIRECTNODE"));
00076   }
00077 
00078   // Scan through and identify all call sites ahead of time so that we only
00079   // inline call sites in the original functions, not call sites that result
00080   // from inlining other functions.
00081   std::vector<CallSite> CallSites;
00082 
00083   for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00084     if (Function *F = SCC[i]->getFunction())
00085       for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
00086         for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
00087           CallSite CS = CallSite::get(I);
00088           if (CS.getInstruction() && (!CS.getCalledFunction() ||
00089                                       !CS.getCalledFunction()->isExternal()))
00090             CallSites.push_back(CS);
00091         }
00092 
00093   DEBUG(std::cerr << ": " << CallSites.size() << " call sites.\n");
00094 
00095   // Now that we have all of the call sites, move the ones to functions in the
00096   // current SCC to the end of the list.
00097   unsigned FirstCallInSCC = CallSites.size();
00098   for (unsigned i = 0; i < FirstCallInSCC; ++i)
00099     if (Function *F = CallSites[i].getCalledFunction())
00100       if (SCCFunctions.count(F))
00101         std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
00102 
00103   // Now that we have all of the call sites, loop over them and inline them if
00104   // it looks profitable to do so.
00105   bool Changed = false;
00106   bool LocalChange;
00107   do {
00108     LocalChange = false;
00109     // Iterate over the outer loop because inlining functions can cause indirect
00110     // calls to become direct calls.
00111     for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi)
00112       if (Function *Callee = CallSites[CSi].getCalledFunction()) {
00113         // Calls to external functions are never inlinable.
00114         if (Callee->isExternal() ||
00115             CallSites[CSi].getInstruction()->getParent()->getParent() ==Callee){
00116           std::swap(CallSites[CSi], CallSites.back());
00117           CallSites.pop_back();
00118           --CSi;
00119           continue;
00120         }
00121 
00122         // If the policy determines that we should inline this function,
00123         // try to do so.
00124         CallSite CS = CallSites[CSi];
00125         int InlineCost = getInlineCost(CS);
00126         if (InlineCost >= (int)InlineThreshold) {
00127           DEBUG(std::cerr << "    NOT Inlining: cost=" << InlineCost
00128                 << ", Call: " << *CS.getInstruction());
00129         } else {
00130           DEBUG(std::cerr << "    Inlining: cost=" << InlineCost
00131                 << ", Call: " << *CS.getInstruction());
00132 
00133           Function *Caller = CS.getInstruction()->getParent()->getParent();
00134 
00135           // Attempt to inline the function...
00136           if (InlineCallIfPossible(CS, CG, SCCFunctions)) {
00137             // Remove this call site from the list.
00138             std::swap(CallSites[CSi], CallSites.back());
00139             CallSites.pop_back();
00140             --CSi;
00141 
00142             ++NumInlined;
00143             Changed = true;
00144             LocalChange = true;
00145           }
00146         }
00147       }
00148   } while (LocalChange);
00149 
00150   return Changed;
00151 }
00152 
00153 // doFinalization - Remove now-dead linkonce functions at the end of
00154 // processing to avoid breaking the SCC traversal.
00155 bool Inliner::doFinalization(CallGraph &CG) {
00156   std::set<CallGraphNode*> FunctionsToRemove;
00157 
00158   // Scan for all of the functions, looking for ones that should now be removed
00159   // from the program.  Insert the dead ones in the FunctionsToRemove set.
00160   for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) {
00161     CallGraphNode *CGN = I->second;
00162     if (Function *F = CGN ? CGN->getFunction() : 0) {
00163       // If the only remaining users of the function are dead constants, remove
00164       // them.
00165       F->removeDeadConstantUsers();
00166 
00167       if ((F->hasLinkOnceLinkage() || F->hasInternalLinkage()) &&
00168           F->use_empty()) {
00169 
00170         // Remove any call graph edges from the function to its callees.
00171         while (CGN->begin() != CGN->end())
00172           CGN->removeCallEdgeTo(*(CGN->end()-1));
00173 
00174         // Remove any edges from the external node to the function's call graph
00175         // node.  These edges might have been made irrelegant due to
00176         // optimization of the program.
00177         CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN);
00178 
00179         // Removing the node for callee from the call graph and delete it.
00180         FunctionsToRemove.insert(CGN);
00181       }
00182     }
00183   }
00184 
00185   // Now that we know which functions to delete, do so.  We didn't want to do
00186   // this inline, because that would invalidate our CallGraph::iterator
00187   // objects. :(
00188   bool Changed = false;
00189   for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(),
00190          E = FunctionsToRemove.end(); I != E; ++I) {
00191     delete CG.removeFunctionFromModule(*I);
00192     ++NumDeleted;
00193     Changed = true;
00194   }
00195 
00196   return Changed;
00197 }