Inliner.cpp revision 008cd3ecea2958540d8d8f5370deffb6103c6758
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 we inlined the last possible call site to the function, delete the 60 // function body now. 61 if (Callee->use_empty() && Callee->hasInternalLinkage() && 62 !SCCFunctions.count(Callee)) { 63 DOUT << " -> Deleting dead function: " << Callee->getName() << "\n"; 64 CallGraphNode *CalleeNode = CG[Callee]; 65 66 // Remove any call graph edges from the callee to its callees. 67 CalleeNode->removeAllCalledFunctions(); 68 69 // Removing the node for callee from the call graph and delete it. 70 delete CG.removeFunctionFromModule(CalleeNode); 71 ++NumDeleted; 72 } 73 return true; 74} 75 76bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) { 77 CallGraph &CG = getAnalysis<CallGraph>(); 78 79 std::set<Function*> SCCFunctions; 80 DOUT << "Inliner visiting SCC:"; 81 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 82 Function *F = SCC[i]->getFunction(); 83 if (F) SCCFunctions.insert(F); 84 DOUT << " " << (F ? F->getName() : "INDIRECTNODE"); 85 } 86 87 // Scan through and identify all call sites ahead of time so that we only 88 // inline call sites in the original functions, not call sites that result 89 // from inlining other functions. 90 std::vector<CallSite> CallSites; 91 92 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 93 if (Function *F = SCC[i]->getFunction()) 94 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 95 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 96 CallSite CS = CallSite::get(I); 97 if (CS.getInstruction() && (!CS.getCalledFunction() || 98 !CS.getCalledFunction()->isDeclaration())) 99 CallSites.push_back(CS); 100 } 101 102 DOUT << ": " << CallSites.size() << " call sites.\n"; 103 104 // Now that we have all of the call sites, move the ones to functions in the 105 // current SCC to the end of the list. 106 unsigned FirstCallInSCC = CallSites.size(); 107 for (unsigned i = 0; i < FirstCallInSCC; ++i) 108 if (Function *F = CallSites[i].getCalledFunction()) 109 if (SCCFunctions.count(F)) 110 std::swap(CallSites[i--], CallSites[--FirstCallInSCC]); 111 112 // Now that we have all of the call sites, loop over them and inline them if 113 // it looks profitable to do so. 114 bool Changed = false; 115 bool LocalChange; 116 do { 117 LocalChange = false; 118 // Iterate over the outer loop because inlining functions can cause indirect 119 // calls to become direct calls. 120 for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) 121 if (Function *Callee = CallSites[CSi].getCalledFunction()) { 122 // Calls to external functions are never inlinable. 123 if (Callee->isDeclaration() || 124 CallSites[CSi].getInstruction()->getParent()->getParent() ==Callee){ 125 if (SCC.size() == 1) { 126 std::swap(CallSites[CSi], CallSites.back()); 127 CallSites.pop_back(); 128 } else { 129 // Keep the 'in SCC / not in SCC' boundary correct. 130 CallSites.erase(CallSites.begin()+CSi); 131 } 132 --CSi; 133 continue; 134 } 135 136 // If the policy determines that we should inline this function, 137 // try to do so. 138 CallSite CS = CallSites[CSi]; 139 int InlineCost = getInlineCost(CS); 140 float FudgeFactor = getInlineFudgeFactor(CS); 141 142 int CurrentThreshold = InlineThreshold; 143 Function *Fn = CS.getCaller(); 144 if (Fn && !Fn->isDeclaration() 145 && Fn->hasFnAttr(Attribute::OptimizeForSize) 146 && InlineThreshold != 50) { 147 CurrentThreshold = 50; 148 } 149 150 if (InlineCost >= (int)(CurrentThreshold * FudgeFactor)) { 151 DOUT << " NOT Inlining: cost=" << InlineCost 152 << ", Call: " << *CS.getInstruction(); 153 } else { 154 DOUT << " Inlining: cost=" << InlineCost 155 << ", Call: " << *CS.getInstruction(); 156 157 // Attempt to inline the function... 158 if (InlineCallIfPossible(CS, CG, SCCFunctions, 159 getAnalysis<TargetData>())) { 160 // Remove this call site from the list. If possible, use 161 // swap/pop_back for efficiency, but do not use it if doing so would 162 // move a call site to a function in this SCC before the 163 // 'FirstCallInSCC' barrier. 164 if (SCC.size() == 1) { 165 std::swap(CallSites[CSi], CallSites.back()); 166 CallSites.pop_back(); 167 } else { 168 CallSites.erase(CallSites.begin()+CSi); 169 } 170 --CSi; 171 172 ++NumInlined; 173 Changed = true; 174 LocalChange = true; 175 } 176 } 177 } 178 } while (LocalChange); 179 180 return Changed; 181} 182 183// doFinalization - Remove now-dead linkonce functions at the end of 184// processing to avoid breaking the SCC traversal. 185bool Inliner::doFinalization(CallGraph &CG) { 186 std::set<CallGraphNode*> FunctionsToRemove; 187 188 // Scan for all of the functions, looking for ones that should now be removed 189 // from the program. Insert the dead ones in the FunctionsToRemove set. 190 for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) { 191 CallGraphNode *CGN = I->second; 192 if (Function *F = CGN ? CGN->getFunction() : 0) { 193 // If the only remaining users of the function are dead constants, remove 194 // them. 195 F->removeDeadConstantUsers(); 196 197 if ((F->hasLinkOnceLinkage() || F->hasInternalLinkage()) && 198 F->use_empty()) { 199 200 // Remove any call graph edges from the function to its callees. 201 CGN->removeAllCalledFunctions(); 202 203 // Remove any edges from the external node to the function's call graph 204 // node. These edges might have been made irrelegant due to 205 // optimization of the program. 206 CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); 207 208 // Removing the node for callee from the call graph and delete it. 209 FunctionsToRemove.insert(CGN); 210 } 211 } 212 } 213 214 // Now that we know which functions to delete, do so. We didn't want to do 215 // this inline, because that would invalidate our CallGraph::iterator 216 // objects. :( 217 bool Changed = false; 218 for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(), 219 E = FunctionsToRemove.end(); I != E; ++I) { 220 delete CG.removeFunctionFromModule(*I); 221 ++NumDeleted; 222 Changed = true; 223 } 224 225 return Changed; 226} 227