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