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 <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 }