LLVM API Documentation
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 }