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