Inliner.cpp revision bb46f52027416598a662dc1c58f48d9d56b1a65b 
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  Function *Caller = CS.getCaller();
58
59  if (!InlineFunction(CS, &CG, &TD)) return false;
60
61  // If the inlined function had a higher stack protection level than the
62  // calling function, then bump up the caller's stack protection level.
63  if (Callee->hasFnAttr(Attribute::StackProtectReq))
64    Caller->addFnAttr(Attribute::StackProtectReq);
65  else if (Callee->hasFnAttr(Attribute::StackProtect) &&
66           !Caller->hasFnAttr(Attribute::StackProtectReq))
67    Caller->addFnAttr(Attribute::StackProtect);
68
69  // If we inlined the last possible call site to the function, delete the
70  // function body now.
71  if (Callee->use_empty() && Callee->hasLocalLinkage() &&
72      !SCCFunctions.count(Callee)) {
73    DOUT << "    -> Deleting dead function: " << Callee->getName() << "\n";
74    CallGraphNode *CalleeNode = CG[Callee];
75
76    // Remove any call graph edges from the callee to its callees.
77    CalleeNode->removeAllCalledFunctions();
78
79    // Removing the node for callee from the call graph and delete it.
80    delete CG.removeFunctionFromModule(CalleeNode);
81    ++NumDeleted;
82  }
83  return true;
84}
85
86/// shouldInline - Return true if the inliner should attempt to inline
87/// at the given CallSite.
88bool Inliner::shouldInline(CallSite CS) {
89  InlineCost IC = getInlineCost(CS);
90  float FudgeFactor = getInlineFudgeFactor(CS);
91
92  if (IC.isAlways()) {
93    DOUT << "    Inlining: cost=always"
94         << ", Call: " << *CS.getInstruction();
95    return true;
96  }
97
98  if (IC.isNever()) {
99    DOUT << "    NOT Inlining: cost=never"
100         << ", Call: " << *CS.getInstruction();
101    return false;
102  }
103
104  int Cost = IC.getValue();
105  int CurrentThreshold = InlineThreshold;
106  Function *Fn = CS.getCaller();
107  if (Fn && !Fn->isDeclaration()
108      && Fn->hasFnAttr(Attribute::OptimizeForSize)
109      && InlineThreshold != 50) {
110    CurrentThreshold = 50;
111  }
112
113  if (Cost >= (int)(CurrentThreshold * FudgeFactor)) {
114    DOUT << "    NOT Inlining: cost=" << Cost
115         << ", Call: " << *CS.getInstruction();
116    return false;
117  } else {
118    DOUT << "    Inlining: cost=" << Cost
119         << ", Call: " << *CS.getInstruction();
120    return true;
121  }
122}
123
124bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) {
125  CallGraph &CG = getAnalysis<CallGraph>();
126
127  std::set<Function*> SCCFunctions;
128  DOUT << "Inliner visiting SCC:";
129  for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
130    Function *F = SCC[i]->getFunction();
131    if (F) SCCFunctions.insert(F);
132    DOUT << " " << (F ? F->getName() : "INDIRECTNODE");
133  }
134
135  // Scan through and identify all call sites ahead of time so that we only
136  // inline call sites in the original functions, not call sites that result
137  // from inlining other functions.
138  std::vector<CallSite> CallSites;
139
140  for (unsigned i = 0, e = SCC.size(); i != e; ++i)
141    if (Function *F = SCC[i]->getFunction())
142      for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
143        for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
144          CallSite CS = CallSite::get(I);
145          if (CS.getInstruction() && (!CS.getCalledFunction() ||
146                                      !CS.getCalledFunction()->isDeclaration()))
147            CallSites.push_back(CS);
148        }
149
150  DOUT << ": " << CallSites.size() << " call sites.\n";
151
152  // Now that we have all of the call sites, move the ones to functions in the
153  // current SCC to the end of the list.
154  unsigned FirstCallInSCC = CallSites.size();
155  for (unsigned i = 0; i < FirstCallInSCC; ++i)
156    if (Function *F = CallSites[i].getCalledFunction())
157      if (SCCFunctions.count(F))
158        std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
159
160  // Now that we have all of the call sites, loop over them and inline them if
161  // it looks profitable to do so.
162  bool Changed = false;
163  bool LocalChange;
164  do {
165    LocalChange = false;
166    // Iterate over the outer loop because inlining functions can cause indirect
167    // calls to become direct calls.
168    for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi)
169      if (Function *Callee = CallSites[CSi].getCalledFunction()) {
170        // Calls to external functions are never inlinable.
171        if (Callee->isDeclaration()) {
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          Function *Caller = CS.getCaller();
188          // Attempt to inline the function...
189          if (InlineCallIfPossible(CS, CG, SCCFunctions,
190                                   getAnalysis<TargetData>())) {
191            // Remove any cached cost info for this caller, as inlining the callee
192            // has increased the size of the caller (which may be the same as the
193            // callee).
194            resetCachedCostInfo(Caller);
195
196            // Remove this call site from the list.  If possible, use
197            // swap/pop_back for efficiency, but do not use it if doing so would
198            // move a call site to a function in this SCC before the
199            // 'FirstCallInSCC' barrier.
200            if (SCC.size() == 1) {
201              std::swap(CallSites[CSi], CallSites.back());
202              CallSites.pop_back();
203            } else {
204              CallSites.erase(CallSites.begin()+CSi);
205            }
206            --CSi;
207
208            ++NumInlined;
209            Changed = true;
210            LocalChange = true;
211          }
212        }
213      }
214  } while (LocalChange);
215
216  return Changed;
217}
218
219// doFinalization - Remove now-dead linkonce functions at the end of
220// processing to avoid breaking the SCC traversal.
221bool Inliner::doFinalization(CallGraph &CG) {
222  return removeDeadFunctions(CG);
223}
224
225  /// removeDeadFunctions - Remove dead functions that are not included in
226  /// DNR (Do Not Remove) list.
227bool Inliner::removeDeadFunctions(CallGraph &CG,
228                                 SmallPtrSet<const Function *, 16> *DNR) {
229  std::set<CallGraphNode*> FunctionsToRemove;
230
231  // Scan for all of the functions, looking for ones that should now be removed
232  // from the program.  Insert the dead ones in the FunctionsToRemove set.
233  for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) {
234    CallGraphNode *CGN = I->second;
235    if (Function *F = CGN ? CGN->getFunction() : 0) {
236      // If the only remaining users of the function are dead constants, remove
237      // them.
238      F->removeDeadConstantUsers();
239
240      if (DNR && DNR->count(F))
241        continue;
242
243      if ((F->hasLinkOnceLinkage() || F->hasLocalLinkage()) &&
244          F->use_empty()) {
245
246        // Remove any call graph edges from the function to its callees.
247        CGN->removeAllCalledFunctions();
248
249        // Remove any edges from the external node to the function's call graph
250        // node.  These edges might have been made irrelegant due to
251        // optimization of the program.
252        CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN);
253
254        // Removing the node for callee from the call graph and delete it.
255        FunctionsToRemove.insert(CGN);
256      }
257    }
258  }
259
260  // Now that we know which functions to delete, do so.  We didn't want to do
261  // this inline, because that would invalidate our CallGraph::iterator
262  // objects. :(
263  bool Changed = false;
264  for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(),
265         E = FunctionsToRemove.end(); I != E; ++I) {
266    delete CG.removeFunctionFromModule(*I);
267    ++NumDeleted;
268    Changed = true;
269  }
270
271  return Changed;
272}
273