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