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