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