Inliner.cpp revision ae56c0de911bf5328ffda48e51ce37bcd7aa0d76
1//===- Inliner.cpp - Code common to all inliners --------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the mechanics required to implement inlining without 11// missing any calls and updating the call graph. The decisions of which calls 12// are profitable to inline are implemented elsewhere. 13// 14//===----------------------------------------------------------------------===// 15 16#define DEBUG_TYPE "inline" 17#include "llvm/Module.h" 18#include "llvm/Instructions.h" 19#include "llvm/IntrinsicInst.h" 20#include "llvm/Analysis/CallGraph.h" 21#include "llvm/Support/CallSite.h" 22#include "llvm/Target/TargetData.h" 23#include "llvm/Transforms/IPO/InlinerPass.h" 24#include "llvm/Transforms/Utils/Cloning.h" 25#include "llvm/Support/CommandLine.h" 26#include "llvm/Support/Debug.h" 27#include "llvm/Support/raw_ostream.h" 28#include "llvm/ADT/Statistic.h" 29#include <set> 30using namespace llvm; 31 32STATISTIC(NumInlined, "Number of functions inlined"); 33STATISTIC(NumDeleted, "Number of functions deleted because all callers found"); 34 35static cl::opt<int> 36InlineLimit("inline-threshold", cl::Hidden, cl::init(200), cl::ZeroOrMore, 37 cl::desc("Control the amount of inlining to perform (default = 200)")); 38 39Inliner::Inliner(void *ID) 40 : CallGraphSCCPass(ID), InlineThreshold(InlineLimit) {} 41 42Inliner::Inliner(void *ID, int Threshold) 43 : CallGraphSCCPass(ID), InlineThreshold(Threshold) {} 44 45/// getAnalysisUsage - For this class, we declare that we require and preserve 46/// the call graph. If the derived class implements this method, it should 47/// always explicitly call the implementation here. 48void Inliner::getAnalysisUsage(AnalysisUsage &Info) const { 49 CallGraphSCCPass::getAnalysisUsage(Info); 50} 51 52// InlineCallIfPossible - If it is possible to inline the specified call site, 53// do so and update the CallGraph for this operation. 54bool Inliner::InlineCallIfPossible(CallSite CS, CallGraph &CG, 55 const SmallPtrSet<Function*, 8> &SCCFunctions, 56 const TargetData *TD) { 57 Function *Callee = CS.getCalledFunction(); 58 Function *Caller = CS.getCaller(); 59 60 if (!InlineFunction(CS, &CG, TD)) return false; 61 62 // If the inlined function had a higher stack protection level than the 63 // calling function, then bump up the caller's stack protection level. 64 if (Callee->hasFnAttr(Attribute::StackProtectReq)) 65 Caller->addFnAttr(Attribute::StackProtectReq); 66 else if (Callee->hasFnAttr(Attribute::StackProtect) && 67 !Caller->hasFnAttr(Attribute::StackProtectReq)) 68 Caller->addFnAttr(Attribute::StackProtect); 69 70 // If we inlined the last possible call site to the function, delete the 71 // function body now. 72 if (Callee->use_empty() && 73 (Callee->hasLocalLinkage() || Callee->hasAvailableExternallyLinkage()) && 74 !SCCFunctions.count(Callee)) { 75 DEBUG(errs() << " -> Deleting dead function: " 76 << Callee->getName() << "\n"); 77 CallGraphNode *CalleeNode = CG[Callee]; 78 79 // Remove any call graph edges from the callee to its callees. 80 CalleeNode->removeAllCalledFunctions(); 81 82 resetCachedCostInfo(CalleeNode->getFunction()); 83 84 // Removing the node for callee from the call graph and delete it. 85 delete CG.removeFunctionFromModule(CalleeNode); 86 ++NumDeleted; 87 } 88 return true; 89} 90 91/// shouldInline - Return true if the inliner should attempt to inline 92/// at the given CallSite. 93bool Inliner::shouldInline(CallSite CS) { 94 InlineCost IC = getInlineCost(CS); 95 96 if (IC.isAlways()) { 97 DEBUG(errs() << " Inlining: cost=always" 98 << ", Call: " << *CS.getInstruction() << "\n"); 99 return true; 100 } 101 102 if (IC.isNever()) { 103 DEBUG(errs() << " NOT Inlining: cost=never" 104 << ", Call: " << *CS.getInstruction() << "\n"); 105 return false; 106 } 107 108 int Cost = IC.getValue(); 109 int CurrentThreshold = InlineThreshold; 110 Function *Fn = CS.getCaller(); 111 if (Fn && !Fn->isDeclaration() && 112 Fn->hasFnAttr(Attribute::OptimizeForSize) && 113 InlineThreshold != 50) 114 CurrentThreshold = 50; 115 116 float FudgeFactor = getInlineFudgeFactor(CS); 117 if (Cost >= (int)(CurrentThreshold * FudgeFactor)) { 118 DEBUG(errs() << " NOT Inlining: cost=" << Cost 119 << ", Call: " << *CS.getInstruction() << "\n"); 120 return false; 121 } 122 123 DEBUG(errs() << " Inlining: cost=" << Cost 124 << ", Call: " << *CS.getInstruction() << "\n"); 125 return true; 126} 127 128bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { 129 CallGraph &CG = getAnalysis<CallGraph>(); 130 const TargetData *TD = getAnalysisIfAvailable<TargetData>(); 131 132 SmallPtrSet<Function*, 8> SCCFunctions; 133 DEBUG(errs() << "Inliner visiting SCC:"); 134 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 135 Function *F = SCC[i]->getFunction(); 136 if (F) SCCFunctions.insert(F); 137 DEBUG(errs() << " " << (F ? F->getName() : "INDIRECTNODE")); 138 } 139 140 // Scan through and identify all call sites ahead of time so that we only 141 // inline call sites in the original functions, not call sites that result 142 // from inlining other functions. 143 std::vector<CallSite> CallSites; 144 145 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 146 Function *F = SCC[i]->getFunction(); 147 if (!F) continue; 148 149 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 150 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 151 CallSite CS = CallSite::get(I); 152 if (CS.getInstruction() == 0 || isa<DbgInfoIntrinsic>(I)) 153 continue; 154 155 if (CS.getCalledFunction() == 0 || 156 !CS.getCalledFunction()->isDeclaration()) 157 CallSites.push_back(CS); 158 } 159 } 160 161 DEBUG(errs() << ": " << CallSites.size() << " call sites.\n"); 162 163 // Now that we have all of the call sites, move the ones to functions in the 164 // current SCC to the end of the list. 165 unsigned FirstCallInSCC = CallSites.size(); 166 for (unsigned i = 0; i < FirstCallInSCC; ++i) 167 if (Function *F = CallSites[i].getCalledFunction()) 168 if (SCCFunctions.count(F)) 169 std::swap(CallSites[i--], CallSites[--FirstCallInSCC]); 170 171 // Now that we have all of the call sites, loop over them and inline them if 172 // it looks profitable to do so. 173 bool Changed = false; 174 bool LocalChange; 175 do { 176 LocalChange = false; 177 // Iterate over the outer loop because inlining functions can cause indirect 178 // calls to become direct calls. 179 for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) { 180 // We can only inline direct calls. 181 Function *Callee = CallSites[CSi].getCalledFunction(); 182 if (!Callee) continue; 183 184 // Calls to external functions are never inlinable. 185 if (Callee->isDeclaration()) { 186 if (SCC.size() == 1) { 187 std::swap(CallSites[CSi], CallSites.back()); 188 CallSites.pop_back(); 189 } else { 190 // Keep the 'in SCC / not in SCC' boundary correct. 191 CallSites.erase(CallSites.begin()+CSi); 192 } 193 --CSi; 194 continue; 195 } 196 197 // If the policy determines that we should inline this function, 198 // try to do so. 199 CallSite CS = CallSites[CSi]; 200 if (!shouldInline(CS)) 201 continue; 202 203 Function *Caller = CS.getCaller(); 204 // Attempt to inline the function... 205 if (!InlineCallIfPossible(CS, CG, SCCFunctions, TD)) 206 continue; 207 208 // Remove any cached cost info for this caller, as inlining the 209 // callee has increased the size of the caller (which may be the 210 // same as the callee). 211 resetCachedCostInfo(Caller); 212 213 // Remove this call site from the list. If possible, use 214 // swap/pop_back for efficiency, but do not use it if doing so would 215 // move a call site to a function in this SCC before the 216 // 'FirstCallInSCC' barrier. 217 if (SCC.size() == 1) { 218 std::swap(CallSites[CSi], CallSites.back()); 219 CallSites.pop_back(); 220 } else { 221 CallSites.erase(CallSites.begin()+CSi); 222 } 223 --CSi; 224 225 ++NumInlined; 226 Changed = true; 227 LocalChange = true; 228 } 229 } while (LocalChange); 230 231 return Changed; 232} 233 234// doFinalization - Remove now-dead linkonce functions at the end of 235// processing to avoid breaking the SCC traversal. 236bool Inliner::doFinalization(CallGraph &CG) { 237 return removeDeadFunctions(CG); 238} 239 240/// removeDeadFunctions - Remove dead functions that are not included in 241/// DNR (Do Not Remove) list. 242bool Inliner::removeDeadFunctions(CallGraph &CG, 243 SmallPtrSet<const Function *, 16> *DNR) { 244 SmallPtrSet<CallGraphNode*, 16> FunctionsToRemove; 245 246 // Scan for all of the functions, looking for ones that should now be removed 247 // from the program. Insert the dead ones in the FunctionsToRemove set. 248 for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) { 249 CallGraphNode *CGN = I->second; 250 if (CGN == 0 || CGN->getFunction() == 0) 251 continue; 252 253 Function *F = CGN->getFunction(); 254 255 // If the only remaining users of the function are dead constants, remove 256 // them. 257 F->removeDeadConstantUsers(); 258 259 if (DNR && DNR->count(F)) 260 continue; 261 if (!F->hasLinkOnceLinkage() && !F->hasLocalLinkage()) 262 continue; 263 if (!F->use_empty()) 264 continue; 265 266 // Remove any call graph edges from the function to its callees. 267 CGN->removeAllCalledFunctions(); 268 269 // Remove any edges from the external node to the function's call graph 270 // node. These edges might have been made irrelegant due to 271 // optimization of the program. 272 CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); 273 274 // Removing the node for callee from the call graph and delete it. 275 FunctionsToRemove.insert(CGN); 276 } 277 278 // Now that we know which functions to delete, do so. We didn't want to do 279 // this inline, because that would invalidate our CallGraph::iterator 280 // objects. :( 281 // 282 // Note that it doesn't matter that we are iterating over a non-stable set 283 // here to do this, it doesn't matter which order the functions are deleted 284 // in. 285 bool Changed = false; 286 for (SmallPtrSet<CallGraphNode*, 16>::iterator I = FunctionsToRemove.begin(), 287 E = FunctionsToRemove.end(); I != E; ++I) { 288 resetCachedCostInfo((*I)->getFunction()); 289 delete CG.removeFunctionFromModule(*I); 290 ++NumDeleted; 291 Changed = true; 292 } 293 294 return Changed; 295} 296