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 is distributed under the University of Illinois Open Source
00006 // 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 #define DEBUG_TYPE "inline"
00017 #include "llvm/Module.h"
00018 #include "llvm/Instructions.h"
00019 #include "llvm/IntrinsicInst.h"
00020 #include "llvm/Analysis/CallGraph.h"
00021 #include "llvm/Support/CallSite.h"
00022 #include "llvm/Target/TargetData.h"
00023 #include "llvm/Transforms/IPO/InlinerPass.h"
00024 #include "llvm/Transforms/Utils/Cloning.h"
00025 #include "llvm/Support/CommandLine.h"
00026 #include "llvm/Support/Debug.h"
00027 #include "llvm/Support/raw_ostream.h"
00028 #include "llvm/ADT/Statistic.h"
00029 #include <set>
00030 using namespace llvm;
00031 
00032 STATISTIC(NumInlined, "Number of functions inlined");
00033 STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
00034 
00035 static cl::opt<int>
00036 InlineLimit("inline-threshold", cl::Hidden, cl::init(200),
00037         cl::desc("Control the amount of inlining to perform (default = 200)"));
00038 
00039 Inliner::Inliner(void *ID) 
00040   : CallGraphSCCPass(ID), InlineThreshold(InlineLimit) {}
00041 
00042 Inliner::Inliner(void *ID, int Threshold) 
00043   : CallGraphSCCPass(ID), InlineThreshold(Threshold) {}
00044 
00045 /// getAnalysisUsage - For this class, we declare that we require and preserve
00046 /// the call graph.  If the derived class implements this method, it should
00047 /// always explicitly call the implementation here.
00048 void Inliner::getAnalysisUsage(AnalysisUsage &Info) const {
00049   CallGraphSCCPass::getAnalysisUsage(Info);
00050 }
00051 
00052 // InlineCallIfPossible - If it is possible to inline the specified call site,
00053 // do so and update the CallGraph for this operation.
00054 bool Inliner::InlineCallIfPossible(CallSite CS, CallGraph &CG,
00055                                  const SmallPtrSet<Function*, 8> &SCCFunctions,
00056                                  const TargetData *TD) {
00057   Function *Callee = CS.getCalledFunction();
00058   Function *Caller = CS.getCaller();
00059 
00060   if (!InlineFunction(CS, &CG, TD)) return false;
00061 
00062   // If the inlined function had a higher stack protection level than the
00063   // calling function, then bump up the caller's stack protection level.
00064   if (Callee->hasFnAttr(Attribute::StackProtectReq))
00065     Caller->addFnAttr(Attribute::StackProtectReq);
00066   else if (Callee->hasFnAttr(Attribute::StackProtect) &&
00067            !Caller->hasFnAttr(Attribute::StackProtectReq))
00068     Caller->addFnAttr(Attribute::StackProtect);
00069 
00070   // If we inlined the last possible call site to the function, delete the
00071   // function body now.
00072   if (Callee->use_empty() && (Callee->hasLocalLinkage() ||
00073                               Callee->hasAvailableExternallyLinkage()) &&
00074       !SCCFunctions.count(Callee)) {
00075     DEBUG(errs() << "    -> Deleting dead function: " 
00076           << Callee->getName() << "\n");
00077     CallGraphNode *CalleeNode = CG[Callee];
00078 
00079     // Remove any call graph edges from the callee to its callees.
00080     CalleeNode->removeAllCalledFunctions();
00081 
00082     resetCachedCostInfo(CalleeNode->getFunction());
00083 
00084     // Removing the node for callee from the call graph and delete it.
00085     delete CG.removeFunctionFromModule(CalleeNode);
00086     ++NumDeleted;
00087   }
00088   return true;
00089 }
00090         
00091 /// shouldInline - Return true if the inliner should attempt to inline
00092 /// at the given CallSite.
00093 bool Inliner::shouldInline(CallSite CS) {
00094   InlineCost IC = getInlineCost(CS);
00095   float FudgeFactor = getInlineFudgeFactor(CS);
00096   
00097   if (IC.isAlways()) {
00098     DEBUG(errs() << "    Inlining: cost=always"
00099           << ", Call: " << *CS.getInstruction() << "\n");
00100     return true;
00101   }
00102   
00103   if (IC.isNever()) {
00104     DEBUG(errs() << "    NOT Inlining: cost=never"
00105           << ", Call: " << *CS.getInstruction() << "\n");
00106     return false;
00107   }
00108   
00109   int Cost = IC.getValue();
00110   int CurrentThreshold = InlineThreshold;
00111   Function *Fn = CS.getCaller();
00112   if (Fn && !Fn->isDeclaration() &&
00113       Fn->hasFnAttr(Attribute::OptimizeForSize) &&
00114       InlineThreshold != 50)
00115     CurrentThreshold = 50;
00116   
00117   if (Cost >= (int)(CurrentThreshold * FudgeFactor)) {
00118     DEBUG(errs() << "    NOT Inlining: cost=" << Cost
00119           << ", Call: " << *CS.getInstruction() << "\n");
00120     return false;
00121   } else {
00122     DEBUG(errs() << "    Inlining: cost=" << Cost
00123           << ", Call: " << *CS.getInstruction() << "\n");
00124     return true;
00125   }
00126 }
00127 
00128 bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) {
00129   CallGraph &CG = getAnalysis<CallGraph>();
00130   const TargetData *TD = getAnalysisIfAvailable<TargetData>();
00131 
00132   SmallPtrSet<Function*, 8> SCCFunctions;
00133   DEBUG(errs() << "Inliner visiting SCC:");
00134   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00135     Function *F = SCC[i]->getFunction();
00136     if (F) SCCFunctions.insert(F);
00137     DEBUG(errs() << " " << (F ? F->getName() : "INDIRECTNODE"));
00138   }
00139 
00140   // Scan through and identify all call sites ahead of time so that we only
00141   // inline call sites in the original functions, not call sites that result
00142   // from inlining other functions.
00143   std::vector<CallSite> CallSites;
00144 
00145   for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00146     if (Function *F = SCC[i]->getFunction())
00147       for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
00148         for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
00149           CallSite CS = CallSite::get(I);
00150           if (CS.getInstruction() && !isa<DbgInfoIntrinsic>(I) &&
00151                                      (!CS.getCalledFunction() ||
00152                                       !CS.getCalledFunction()->isDeclaration()))
00153             CallSites.push_back(CS);
00154         }
00155 
00156   DEBUG(errs() << ": " << CallSites.size() << " call sites.\n");
00157 
00158   // Now that we have all of the call sites, move the ones to functions in the
00159   // current SCC to the end of the list.
00160   unsigned FirstCallInSCC = CallSites.size();
00161   for (unsigned i = 0; i < FirstCallInSCC; ++i)
00162     if (Function *F = CallSites[i].getCalledFunction())
00163       if (SCCFunctions.count(F))
00164         std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
00165 
00166   // Now that we have all of the call sites, loop over them and inline them if
00167   // it looks profitable to do so.
00168   bool Changed = false;
00169   bool LocalChange;
00170   do {
00171     LocalChange = false;
00172     // Iterate over the outer loop because inlining functions can cause indirect
00173     // calls to become direct calls.
00174     for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi)
00175       if (Function *Callee = CallSites[CSi].getCalledFunction()) {
00176         // Calls to external functions are never inlinable.
00177         if (Callee->isDeclaration()) {
00178           if (SCC.size() == 1) {
00179             std::swap(CallSites[CSi], CallSites.back());
00180             CallSites.pop_back();
00181           } else {
00182             // Keep the 'in SCC / not in SCC' boundary correct.
00183             CallSites.erase(CallSites.begin()+CSi);
00184           }
00185           --CSi;
00186           continue;
00187         }
00188 
00189         // If the policy determines that we should inline this function,
00190         // try to do so.
00191         CallSite CS = CallSites[CSi];
00192         if (shouldInline(CS)) {
00193           Function *Caller = CS.getCaller();
00194           // Attempt to inline the function...
00195           if (InlineCallIfPossible(CS, CG, SCCFunctions, TD)) {
00196             // Remove any cached cost info for this caller, as inlining the
00197             // callee has increased the size of the caller (which may be the
00198             // same as the callee).
00199             resetCachedCostInfo(Caller);
00200 
00201             // Remove this call site from the list.  If possible, use 
00202             // swap/pop_back for efficiency, but do not use it if doing so would
00203             // move a call site to a function in this SCC before the
00204             // 'FirstCallInSCC' barrier.
00205             if (SCC.size() == 1) {
00206               std::swap(CallSites[CSi], CallSites.back());
00207               CallSites.pop_back();
00208             } else {
00209               CallSites.erase(CallSites.begin()+CSi);
00210             }
00211             --CSi;
00212 
00213             ++NumInlined;
00214             Changed = true;
00215             LocalChange = true;
00216           }
00217         }
00218       }
00219   } while (LocalChange);
00220 
00221   return Changed;
00222 }
00223 
00224 // doFinalization - Remove now-dead linkonce functions at the end of
00225 // processing to avoid breaking the SCC traversal.
00226 bool Inliner::doFinalization(CallGraph &CG) {
00227   return removeDeadFunctions(CG);
00228 }
00229 
00230   /// removeDeadFunctions - Remove dead functions that are not included in
00231   /// DNR (Do Not Remove) list.
00232 bool Inliner::removeDeadFunctions(CallGraph &CG, 
00233                                  SmallPtrSet<const Function *, 16> *DNR) {
00234   std::set<CallGraphNode*> FunctionsToRemove;
00235 
00236   // Scan for all of the functions, looking for ones that should now be removed
00237   // from the program.  Insert the dead ones in the FunctionsToRemove set.
00238   for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) {
00239     CallGraphNode *CGN = I->second;
00240     if (Function *F = CGN ? CGN->getFunction() : 0) {
00241       // If the only remaining users of the function are dead constants, remove
00242       // them.
00243       F->removeDeadConstantUsers();
00244 
00245       if (DNR && DNR->count(F))
00246         continue;
00247 
00248       if ((F->hasLinkOnceLinkage() || F->hasLocalLinkage()) &&
00249           F->use_empty()) {
00250 
00251         // Remove any call graph edges from the function to its callees.
00252         CGN->removeAllCalledFunctions();
00253 
00254         // Remove any edges from the external node to the function's call graph
00255         // node.  These edges might have been made irrelegant due to
00256         // optimization of the program.
00257         CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN);
00258 
00259         // Removing the node for callee from the call graph and delete it.
00260         FunctionsToRemove.insert(CGN);
00261       }
00262     }
00263   }
00264 
00265   // Now that we know which functions to delete, do so.  We didn't want to do
00266   // this inline, because that would invalidate our CallGraph::iterator
00267   // objects. :(
00268   bool Changed = false;
00269   for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(),
00270          E = FunctionsToRemove.end(); I != E; ++I) {
00271     resetCachedCostInfo((*I)->getFunction());
00272     delete CG.removeFunctionFromModule(*I);
00273     ++NumDeleted;
00274     Changed = true;
00275   }
00276 
00277   return Changed;
00278 }