Inliner.cpp revision 16581bf931c0ccf2f8993397acfa4e1d509a68dc 
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/IntrinsicInst.h"
20#include "llvm/Analysis/CallGraph.h"
21#include "llvm/Support/CallSite.h"
22#include "llvm/Target/TargetData.h"
23#include "llvm/Transforms/IPO/InlinerPass.h"
24#include "llvm/Transforms/Utils/Cloning.h"
25#include "llvm/Support/CommandLine.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/ADT/Statistic.h"
28#include <set>
29using namespace llvm;
30
31STATISTIC(NumInlined, "Number of functions inlined");
32STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
33
34static cl::opt<int>
35InlineLimit("inline-threshold", cl::Hidden, cl::init(200),
36        cl::desc("Control the amount of inlining to perform (default = 200)"));
37
38Inliner::Inliner(void *ID)
39  : CallGraphSCCPass(ID), InlineThreshold(InlineLimit) {}
40
41Inliner::Inliner(void *ID, int Threshold)
42  : CallGraphSCCPass(ID), InlineThreshold(Threshold) {}
43
44/// getAnalysisUsage - For this class, we declare that we require and preserve
45/// the call graph.  If the derived class implements this method, it should
46/// always explicitly call the implementation here.
47void Inliner::getAnalysisUsage(AnalysisUsage &Info) const {
48  Info.addRequired<TargetData>();
49  CallGraphSCCPass::getAnalysisUsage(Info);
50}
51
52// InlineCallIfPossible - If it is possible to inline the specified call site,
53// do so and update the CallGraph for this operation.
54bool Inliner::InlineCallIfPossible(CallSite CS, CallGraph &CG,
55                                 const SmallPtrSet<Function*, 8> &SCCFunctions,
56                                 const TargetData &TD) {
57  Function *Callee = CS.getCalledFunction();
58  Function *Caller = CS.getCaller();
59
60  if (!InlineFunction(CS, &CG, &TD)) return false;
61
62  // If the inlined function had a higher stack protection level than the
63  // calling function, then bump up the caller's stack protection level.
64  if (Callee->hasFnAttr(Attribute::StackProtectReq))
65    Caller->addFnAttr(Attribute::StackProtectReq);
66  else if (Callee->hasFnAttr(Attribute::StackProtect) &&
67           !Caller->hasFnAttr(Attribute::StackProtectReq))
68    Caller->addFnAttr(Attribute::StackProtect);
69
70  // If we inlined the last possible call site to the function, delete the
71  // function body now.
72  if (Callee->use_empty() && Callee->hasLocalLinkage() &&
73      !SCCFunctions.count(Callee)) {
74    DOUT << "    -> Deleting dead function: " << Callee->getName() << "\n";
75    CallGraphNode *CalleeNode = CG[Callee];
76
77    // Remove any call graph edges from the callee to its callees.
78    CalleeNode->removeAllCalledFunctions();
79
80    resetCachedCostInfo(CalleeNode->getFunction());
81
82    // Removing the node for callee from the call graph and delete it.
83    delete CG.removeFunctionFromModule(CalleeNode);
84    ++NumDeleted;
85  }
86  return true;
87}
88
89/// shouldInline - Return true if the inliner should attempt to inline
90/// at the given CallSite.
91bool Inliner::shouldInline(CallSite CS) {
92  InlineCost IC = getInlineCost(CS);
93  float FudgeFactor = getInlineFudgeFactor(CS);
94
95  if (IC.isAlways()) {
96    DOUT << "    Inlining: cost=always"
97         << ", Call: " << *CS.getInstruction();
98    return true;
99  }
100
101  if (IC.isNever()) {
102    DOUT << "    NOT Inlining: cost=never"
103         << ", Call: " << *CS.getInstruction();
104    return false;
105  }
106
107  int Cost = IC.getValue();
108  int CurrentThreshold = InlineThreshold;
109  Function *Fn = CS.getCaller();
110  if (Fn && !Fn->isDeclaration()
111      && Fn->hasFnAttr(Attribute::OptimizeForSize)
112      && InlineThreshold != 50) {
113    CurrentThreshold = 50;
114  }
115
116  if (Cost >= (int)(CurrentThreshold * FudgeFactor)) {
117    DOUT << "    NOT Inlining: cost=" << Cost
118         << ", Call: " << *CS.getInstruction();
119    return false;
120  } else {
121    DOUT << "    Inlining: cost=" << Cost
122         << ", Call: " << *CS.getInstruction();
123    return true;
124  }
125}
126
127bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) {
128  CallGraph &CG = getAnalysis<CallGraph>();
129  TargetData &TD = getAnalysis<TargetData>();
130
131  SmallPtrSet<Function*, 8> SCCFunctions;
132  DOUT << "Inliner visiting SCC:";
133  for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
134    Function *F = SCC[i]->getFunction();
135    if (F) SCCFunctions.insert(F);
136    DOUT << " " << (F ? F->getName() : "INDIRECTNODE");
137  }
138
139  // Scan through and identify all call sites ahead of time so that we only
140  // inline call sites in the original functions, not call sites that result
141  // from inlining other functions.
142  std::vector<CallSite> CallSites;
143
144  for (unsigned i = 0, e = SCC.size(); i != e; ++i)
145    if (Function *F = SCC[i]->getFunction())
146      for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
147        for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
148          CallSite CS = CallSite::get(I);
149          if (CS.getInstruction() && !isa<DbgInfoIntrinsic>(I) &&
150                                     (!CS.getCalledFunction() ||
151                                      !CS.getCalledFunction()->isDeclaration()))
152            CallSites.push_back(CS);
153        }
154
155  DOUT << ": " << CallSites.size() << " call sites.\n";
156
157  // Now that we have all of the call sites, move the ones to functions in the
158  // current SCC to the end of the list.
159  unsigned FirstCallInSCC = CallSites.size();
160  for (unsigned i = 0; i < FirstCallInSCC; ++i)
161    if (Function *F = CallSites[i].getCalledFunction())
162      if (SCCFunctions.count(F))
163        std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
164
165  // Now that we have all of the call sites, loop over them and inline them if
166  // it looks profitable to do so.
167  bool Changed = false;
168  bool LocalChange;
169  do {
170    LocalChange = false;
171    // Iterate over the outer loop because inlining functions can cause indirect
172    // calls to become direct calls.
173    for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi)
174      if (Function *Callee = CallSites[CSi].getCalledFunction()) {
175        // Calls to external functions are never inlinable.
176        if (Callee->isDeclaration()) {
177          if (SCC.size() == 1) {
178            std::swap(CallSites[CSi], CallSites.back());
179            CallSites.pop_back();
180          } else {
181            // Keep the 'in SCC / not in SCC' boundary correct.
182            CallSites.erase(CallSites.begin()+CSi);
183          }
184          --CSi;
185          continue;
186        }
187
188        // If the policy determines that we should inline this function,
189        // try to do so.
190        CallSite CS = CallSites[CSi];
191        if (shouldInline(CS)) {
192          Function *Caller = CS.getCaller();
193          // Attempt to inline the function...
194          if (InlineCallIfPossible(CS, CG, SCCFunctions, TD)) {
195            // Remove any cached cost info for this caller, as inlining the
196            // callee has increased the size of the caller (which may be the
197            // same as the callee).
198            resetCachedCostInfo(Caller);
199
200            // Remove this call site from the list.  If possible, use
201            // swap/pop_back for efficiency, but do not use it if doing so would
202            // move a call site to a function in this SCC before the
203            // 'FirstCallInSCC' barrier.
204            if (SCC.size() == 1) {
205              std::swap(CallSites[CSi], CallSites.back());
206              CallSites.pop_back();
207            } else {
208              CallSites.erase(CallSites.begin()+CSi);
209            }
210            --CSi;
211
212            ++NumInlined;
213            Changed = true;
214            LocalChange = true;
215          }
216        }
217      }
218  } while (LocalChange);
219
220  return Changed;
221}
222
223// doFinalization - Remove now-dead linkonce functions at the end of
224// processing to avoid breaking the SCC traversal.
225bool Inliner::doFinalization(CallGraph &CG) {
226  return removeDeadFunctions(CG);
227}
228
229  /// removeDeadFunctions - Remove dead functions that are not included in
230  /// DNR (Do Not Remove) list.
231bool Inliner::removeDeadFunctions(CallGraph &CG,
232                                 SmallPtrSet<const Function *, 16> *DNR) {
233  std::set<CallGraphNode*> FunctionsToRemove;
234
235  // Scan for all of the functions, looking for ones that should now be removed
236  // from the program.  Insert the dead ones in the FunctionsToRemove set.
237  for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) {
238    CallGraphNode *CGN = I->second;
239    if (Function *F = CGN ? CGN->getFunction() : 0) {
240      // If the only remaining users of the function are dead constants, remove
241      // them.
242      F->removeDeadConstantUsers();
243
244      if (DNR && DNR->count(F))
245        continue;
246
247      if ((F->hasLinkOnceLinkage() || F->hasLocalLinkage()) &&
248          F->use_empty()) {
249
250        // Remove any call graph edges from the function to its callees.
251        CGN->removeAllCalledFunctions();
252
253        // Remove any edges from the external node to the function's call graph
254        // node.  These edges might have been made irrelegant due to
255        // optimization of the program.
256        CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN);
257
258        // Removing the node for callee from the call graph and delete it.
259        FunctionsToRemove.insert(CGN);
260      }
261    }
262  }
263
264  // Now that we know which functions to delete, do so.  We didn't want to do
265  // this inline, because that would invalidate our CallGraph::iterator
266  // objects. :(
267  bool Changed = false;
268  for (std::set<CallGraphNode*>::iterator I = FunctionsToRemove.begin(),
269         E = FunctionsToRemove.end(); I != E; ++I) {
270    resetCachedCostInfo((*I)->getFunction());
271    delete CG.removeFunctionFromModule(*I);
272    ++NumDeleted;
273    Changed = true;
274  }
275
276  return Changed;
277}
278