LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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