Inliner.cpp revision 0598866c052147c31b808391f58434ce3dbfb838
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() && Fn->hasNote(Attribute::OptimizeForSize) 145 && InlineThreshold != 50) { 146 CurrentThreshold = 50; 147 } 148 149 if (InlineCost >= (int)(CurrentThreshold * FudgeFactor)) { 150 DOUT << " NOT Inlining: cost=" << InlineCost 151 << ", Call: " << *CS.getInstruction(); 152 } else { 153 DOUT << " Inlining: cost=" << InlineCost 154 << ", Call: " << *CS.getInstruction(); 155 156 // Attempt to inline the function... 157 if (InlineCallIfPossible(CS, CG, SCCFunctions, 158 getAnalysis<TargetData>())) { 159 // Remove this call site from the list. If possible, use 160 // swap/pop_back for efficiency, but do not use it if doing so would 161 // move a call site to a function in this SCC before the 162 // 'FirstCallInSCC' barrier. 163 if (SCC.size() == 1) { 164 std::swap(CallSites[CSi], CallSites.back()); 165 CallSites.pop_back(); 166 } else { 167 CallSites.erase(CallSites.begin()+CSi); 168 } 169 --CSi; 170 171 ++NumInlined; 172 Changed = true; 173 LocalChange = true; 174 } 175 } 176 } 177 } while (LocalChange); 178 179 return Changed; 180} 181 182// doFinalization - Remove now-dead linkonce functions at the end of 183// processing to avoid breaking the SCC traversal. 184bool Inliner::doFinalization(CallGraph &CG) { 185 std::set<CallGraphNode*> FunctionsToRemove; 186 187 // Scan for all of the functions, looking for ones that should now be removed 188 // from the program. Insert the dead ones in the FunctionsToRemove set. 189 for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) { 190 CallGraphNode *CGN = I->second; 191 if (Function *F = CGN ? CGN->getFunction() : 0) { 192 // If the only remaining users of the function are dead constants, remove 193 // them. 194 F->removeDeadConstantUsers(); 195 196 if ((F->hasLinkOnceLinkage() || F->hasInternalLinkage()) && 197 F->use_empty()) { 198 199 // Remove any call graph edges from the function to its callees. 200 CGN->removeAllCalledFunctions(); 201 202 // Remove any edges from the external node to the function's call graph 203 // node. These edges might have been made irrelegant due to 204 // optimization of the program. 205 CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); 206 207 // Removing the node for callee from the call graph and delete it. 208 FunctionsToRemove.insert(CGN); 209 } 210 } 211 } 212 213 // Now that we know which functions to delete, do so. We didn't want to do 214 // this inline, because that would invalidate our CallGraph::iterator 215 // objects. :( 216 bool Changed = false; 217 for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(), 218 E = FunctionsToRemove.end(); I != E; ++I) { 219 delete CG.removeFunctionFromModule(*I); 220 ++NumDeleted; 221 Changed = true; 222 } 223 224 return Changed; 225} 226