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