InlineCost.h revision 453f4f01302f00651aae2fc7658f6e23a2beadb0 
1//===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===//
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 heuristics for inlining decisions.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_INLINECOST_H
15#define LLVM_ANALYSIS_INLINECOST_H
16
17#include "llvm/Analysis/CodeMetrics.h"
18#include "llvm/Analysis/CallGraphSCCPass.h"
19#include <cassert>
20#include <climits>
21
22namespace llvm {
23class CallSite;
24class DataLayout;
25class Function;
26class TargetTransformInfo;
27
28namespace InlineConstants {
29  // Various magic constants used to adjust heuristics.
30  const int InstrCost = 5;
31  const int IndirectCallThreshold = 100;
32  const int CallPenalty = 25;
33  const int LastCallToStaticBonus = -15000;
34  const int ColdccPenalty = 2000;
35  const int NoreturnPenalty = 10000;
36  /// Do not inline functions which allocate this many bytes on the stack
37  /// when the caller is recursive.
38  const unsigned TotalAllocaSizeRecursiveCaller = 1024;
39}
40
41/// \brief Represents the cost of inlining a function.
42///
43/// This supports special values for functions which should "always" or
44/// "never" be inlined. Otherwise, the cost represents a unitless amount;
45/// smaller values increase the likelihood of the function being inlined.
46///
47/// Objects of this type also provide the adjusted threshold for inlining
48/// based on the information available for a particular callsite. They can be
49/// directly tested to determine if inlining should occur given the cost and
50/// threshold for this cost metric.
51class InlineCost {
52  enum SentinelValues {
53    AlwaysInlineCost = INT_MIN,
54    NeverInlineCost = INT_MAX
55  };
56
57  /// \brief The estimated cost of inlining this callsite.
58  const int Cost;
59
60  /// \brief The adjusted threshold against which this cost was computed.
61  const int Threshold;
62
63  // Trivial constructor, interesting logic in the factory functions below.
64  InlineCost(int Cost, int Threshold) : Cost(Cost), Threshold(Threshold) {}
65
66public:
67  static InlineCost get(int Cost, int Threshold) {
68    assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value");
69    assert(Cost < NeverInlineCost && "Cost crosses sentinel value");
70    return InlineCost(Cost, Threshold);
71  }
72  static InlineCost getAlways() {
73    return InlineCost(AlwaysInlineCost, 0);
74  }
75  static InlineCost getNever() {
76    return InlineCost(NeverInlineCost, 0);
77  }
78
79  /// \brief Test whether the inline cost is low enough for inlining.
80  LLVM_EXPLICIT operator bool() const {
81    return Cost < Threshold;
82  }
83
84  bool isAlways() const { return Cost == AlwaysInlineCost; }
85  bool isNever() const { return Cost == NeverInlineCost; }
86  bool isVariable() const { return !isAlways() && !isNever(); }
87
88  /// \brief Get the inline cost estimate.
89  /// It is an error to call this on an "always" or "never" InlineCost.
90  int getCost() const {
91    assert(isVariable() && "Invalid access of InlineCost");
92    return Cost;
93  }
94
95  /// \brief Get the cost delta from the threshold for inlining.
96  /// Only valid if the cost is of the variable kind. Returns a negative
97  /// value if the cost is too high to inline.
98  int getCostDelta() const { return Threshold - getCost(); }
99};
100
101/// \brief Cost analyzer used by inliner.
102class InlineCostAnalysis : public CallGraphSCCPass {
103  const DataLayout *TD;
104  const TargetTransformInfo *TTI;
105
106public:
107  static char ID;
108
109  InlineCostAnalysis();
110  ~InlineCostAnalysis();
111
112  // Pass interface implementation.
113  void getAnalysisUsage(AnalysisUsage &AU) const;
114  bool runOnSCC(CallGraphSCC &SCC);
115
116  /// \brief Get an InlineCost object representing the cost of inlining this
117  /// callsite.
118  ///
119  /// Note that threshold is passed into this function. Only costs below the
120  /// threshold are computed with any accuracy. The threshold can be used to
121  /// bound the computation necessary to determine whether the cost is
122  /// sufficiently low to warrant inlining.
123  ///
124  /// Also note that calling this function *dynamically* computes the cost of
125  /// inlining the callsite. It is an expensive, heavyweight call.
126  InlineCost getInlineCost(CallSite CS, int Threshold);
127
128  /// \brief Get an InlineCost with the callee explicitly specified.
129  /// This allows you to calculate the cost of inlining a function via a
130  /// pointer. This behaves exactly as the version with no explicit callee
131  /// parameter in all other respects.
132  //
133  //  Note: This is used by out-of-tree passes, please do not remove without
134  //  adding a replacement API.
135  InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold);
136
137  /// \brief Minimal filter to detect invalid constructs for inlining.
138  bool isInlineViable(Function &Callee);
139};
140
141}
142
143#endif
144