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