LLVM  12.0.0git
InlineCost.h
Go to the documentation of this file.
1 //===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements heuristics for inlining decisions.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ANALYSIS_INLINECOST_H
14 #define LLVM_ANALYSIS_INLINECOST_H
15 
19 #include <cassert>
20 #include <climits>
21 
22 namespace llvm {
23 class AssumptionCacheTracker;
24 class BlockFrequencyInfo;
25 class CallBase;
26 class DataLayout;
27 class Function;
28 class ProfileSummaryInfo;
29 class TargetTransformInfo;
30 class TargetLibraryInfo;
31 
32 namespace InlineConstants {
33 // Various thresholds used by inline cost analysis.
34 /// Use when optsize (-Os) is specified.
35 const int OptSizeThreshold = 50;
36 
37 /// Use when minsize (-Oz) is specified.
38 const int OptMinSizeThreshold = 5;
39 
40 /// Use when -O3 is specified.
41 const int OptAggressiveThreshold = 250;
42 
43 // Various magic constants used to adjust heuristics.
44 const int InstrCost = 5;
45 const int IndirectCallThreshold = 100;
46 const int CallPenalty = 25;
47 const int LastCallToStaticBonus = 15000;
48 const int ColdccPenalty = 2000;
49 /// Do not inline functions which allocate this many bytes on the stack
50 /// when the caller is recursive.
51 const unsigned TotalAllocaSizeRecursiveCaller = 1024;
52 /// Do not inline dynamic allocas that have been constant propagated to be
53 /// static allocas above this amount in bytes.
54 const uint64_t MaxSimplifiedDynamicAllocaToInline = 65536;
55 } // namespace InlineConstants
56 
57 /// Represents the cost of inlining a function.
58 ///
59 /// This supports special values for functions which should "always" or
60 /// "never" be inlined. Otherwise, the cost represents a unitless amount;
61 /// smaller values increase the likelihood of the function being inlined.
62 ///
63 /// Objects of this type also provide the adjusted threshold for inlining
64 /// based on the information available for a particular callsite. They can be
65 /// directly tested to determine if inlining should occur given the cost and
66 /// threshold for this cost metric.
67 class InlineCost {
68  enum SentinelValues { AlwaysInlineCost = INT_MIN, NeverInlineCost = INT_MAX };
69 
70  /// The estimated cost of inlining this callsite.
71  int Cost = 0;
72 
73  /// The adjusted threshold against which this cost was computed.
74  int Threshold = 0;
75 
76  /// Must be set for Always and Never instances.
77  const char *Reason = nullptr;
78 
79  // Trivial constructor, interesting logic in the factory functions below.
80  InlineCost(int Cost, int Threshold, const char *Reason = nullptr)
81  : Cost(Cost), Threshold(Threshold), Reason(Reason) {
82  assert((isVariable() || Reason) &&
83  "Reason must be provided for Never or Always");
84  }
85 
86 public:
87  static InlineCost get(int Cost, int Threshold) {
88  assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value");
89  assert(Cost < NeverInlineCost && "Cost crosses sentinel value");
90  return InlineCost(Cost, Threshold);
91  }
92  static InlineCost getAlways(const char *Reason) {
93  return InlineCost(AlwaysInlineCost, 0, Reason);
94  }
95  static InlineCost getNever(const char *Reason) {
96  return InlineCost(NeverInlineCost, 0, Reason);
97  }
98 
99  /// Test whether the inline cost is low enough for inlining.
100  explicit operator bool() const { return Cost < Threshold; }
101 
102  bool isAlways() const { return Cost == AlwaysInlineCost; }
103  bool isNever() const { return Cost == NeverInlineCost; }
104  bool isVariable() const { return !isAlways() && !isNever(); }
105 
106  /// Get the inline cost estimate.
107  /// It is an error to call this on an "always" or "never" InlineCost.
108  int getCost() const {
109  assert(isVariable() && "Invalid access of InlineCost");
110  return Cost;
111  }
112 
113  /// Get the threshold against which the cost was computed
114  int getThreshold() const {
115  assert(isVariable() && "Invalid access of InlineCost");
116  return Threshold;
117  }
118 
119  /// Get the reason of Always or Never.
120  const char *getReason() const {
121  assert((Reason || isVariable()) &&
122  "InlineCost reason must be set for Always or Never");
123  return Reason;
124  }
125 
126  /// Get the cost delta from the threshold for inlining.
127  /// Only valid if the cost is of the variable kind. Returns a negative
128  /// value if the cost is too high to inline.
129  int getCostDelta() const { return Threshold - getCost(); }
130 };
131 
132 /// InlineResult is basically true or false. For false results the message
133 /// describes a reason.
135  const char *Message = nullptr;
136  InlineResult(const char *Message = nullptr) : Message(Message) {}
137 
138 public:
139  static InlineResult success() { return {}; }
140  static InlineResult failure(const char *Reason) {
141  return InlineResult(Reason);
142  }
143  bool isSuccess() const { return Message == nullptr; }
144  const char *getFailureReason() const {
145  assert(!isSuccess() &&
146  "getFailureReason should only be called in failure cases");
147  return Message;
148  }
149 };
150 
151 /// Thresholds to tune inline cost analysis. The inline cost analysis decides
152 /// the condition to apply a threshold and applies it. Otherwise,
153 /// DefaultThreshold is used. If a threshold is Optional, it is applied only
154 /// when it has a valid value. Typically, users of inline cost analysis
155 /// obtain an InlineParams object through one of the \c getInlineParams methods
156 /// and pass it to \c getInlineCost. Some specialized versions of inliner
157 /// (such as the pre-inliner) might have custom logic to compute \c InlineParams
158 /// object.
159 
160 struct InlineParams {
161  /// The default threshold to start with for a callee.
163 
164  /// Threshold to use for callees with inline hint.
166 
167  /// Threshold to use for cold callees.
169 
170  /// Threshold to use when the caller is optimized for size.
172 
173  /// Threshold to use when the caller is optimized for minsize.
175 
176  /// Threshold to use when the callsite is considered hot.
178 
179  /// Threshold to use when the callsite is considered hot relative to function
180  /// entry.
182 
183  /// Threshold to use when the callsite is considered cold.
185 
186  /// Compute inline cost even when the cost has exceeded the threshold.
188 
189  /// Indicate whether we should allow inline deferral.
190  Optional<bool> EnableDeferral = true;
191 };
192 
193 /// Generate the parameters to tune the inline cost analysis based only on the
194 /// commandline options.
196 
197 /// Generate the parameters to tune the inline cost analysis based on command
198 /// line options. If -inline-threshold option is not explicitly passed,
199 /// \p Threshold is used as the default threshold.
201 
202 /// Generate the parameters to tune the inline cost analysis based on command
203 /// line options. If -inline-threshold option is not explicitly passed,
204 /// the default threshold is computed from \p OptLevel and \p SizeOptLevel.
205 /// An \p OptLevel value above 3 is considered an aggressive optimization mode.
206 /// \p SizeOptLevel of 1 corresponds to the -Os flag and 2 corresponds to
207 /// the -Oz flag.
208 InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel);
209 
210 /// Return the cost associated with a callsite, including parameter passing
211 /// and the call/return instruction.
212 int getCallsiteCost(CallBase &Call, const DataLayout &DL);
213 
214 /// Get an InlineCost object representing the cost of inlining this
215 /// callsite.
216 ///
217 /// Note that a default threshold is passed into this function. This threshold
218 /// could be modified based on callsite's properties and only costs below this
219 /// new threshold are computed with any accuracy. The new threshold can be
220 /// used to bound the computation necessary to determine whether the cost is
221 /// sufficiently low to warrant inlining.
222 ///
223 /// Also note that calling this function *dynamically* computes the cost of
224 /// inlining the callsite. It is an expensive, heavyweight call.
226 getInlineCost(CallBase &Call, const InlineParams &Params,
227  TargetTransformInfo &CalleeTTI,
228  function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
229  function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
230  function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
231  ProfileSummaryInfo *PSI = nullptr,
232  OptimizationRemarkEmitter *ORE = nullptr);
233 
234 /// Get an InlineCost with the callee explicitly specified.
235 /// This allows you to calculate the cost of inlining a function via a
236 /// pointer. This behaves exactly as the version with no explicit callee
237 /// parameter in all other respects.
238 //
240 getInlineCost(CallBase &Call, Function *Callee, const InlineParams &Params,
241  TargetTransformInfo &CalleeTTI,
242  function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
243  function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
244  function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
245  ProfileSummaryInfo *PSI = nullptr,
246  OptimizationRemarkEmitter *ORE = nullptr);
247 
248 /// Returns InlineResult::success() if the call site should be always inlined
249 /// because of user directives, and the inlining is viable. Returns
250 /// InlineResult::failure() if the inlining may never happen because of user
251 /// directives or incompatibilities detectable without needing callee traversal.
252 /// Otherwise returns None, meaning that inlining should be decided based on
253 /// other criteria (e.g. cost modeling).
255  CallBase &Call, Function *Callee, TargetTransformInfo &CalleeTTI,
256  function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
257 
258 /// Get the cost estimate ignoring thresholds. This is similar to getInlineCost
259 /// when passed InlineParams::ComputeFullInlineCost, or a non-null ORE. It
260 /// uses default InlineParams otherwise.
261 /// Contrary to getInlineCost, which makes a threshold-based final evaluation of
262 /// should/shouldn't inline, captured in InlineResult, getInliningCostEstimate
263 /// returns:
264 /// - None, if the inlining cannot happen (is illegal)
265 /// - an integer, representing the cost.
267  CallBase &Call, TargetTransformInfo &CalleeTTI,
268  function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
269  function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
270  ProfileSummaryInfo *PSI = nullptr,
271  OptimizationRemarkEmitter *ORE = nullptr);
272 
273 /// Minimal filter to detect invalid constructs for inlining.
275 
276 // This pass is used to annotate instructions during the inline process for
277 // debugging and analysis. The main purpose of the pass is to see and test
278 // inliner's decisions when creating new optimizations to InlineCost.
280  : PassInfoMixin<InlineCostAnnotationPrinterPass> {
282 
283 public:
286 };
287 } // namespace llvm
288 
289 #endif
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
Thresholds to tune inline cost analysis.
Definition: InlineCost.h:160
bool isNever() const
Definition: InlineCost.h:103
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Optional< int > OptSizeThreshold
Threshold to use when the caller is optimized for size.
Definition: InlineCost.h:171
bool isVariable() const
Definition: InlineCost.h:104
InlineCostAnnotationPrinterPass(raw_ostream &OS)
Definition: InlineCost.h:284
Analysis providing profile information.
const int OptMinSizeThreshold
Use when minsize (-Oz) is specified.
Definition: InlineCost.h:38
const int ColdccPenalty
Definition: InlineCost.h:48
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:176
A cache of @llvm.assume calls within a function.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
InlineCost getInlineCost(CallBase &Call, const InlineParams &Params, TargetTransformInfo &CalleeTTI, function_ref< AssumptionCache &(Function &)> GetAssumptionCache, function_ref< const TargetLibraryInfo &(Function &)> GetTLI, function_ref< BlockFrequencyInfo &(Function &)> GetBFI=nullptr, ProfileSummaryInfo *PSI=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
Get an InlineCost object representing the cost of inlining this callsite.
Represents the cost of inlining a function.
Definition: InlineCost.h:67
bool isSuccess() const
Definition: InlineCost.h:143
Optional< int > HintThreshold
Threshold to use for callees with inline hint.
Definition: InlineCost.h:165
Optional< int > getInliningCostEstimate(CallBase &Call, TargetTransformInfo &CalleeTTI, function_ref< AssumptionCache &(Function &)> GetAssumptionCache, function_ref< BlockFrequencyInfo &(Function &)> GetBFI=nullptr, ProfileSummaryInfo *PSI=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
Get the cost estimate ignoring thresholds.
InlineResult is basically true or false.
Definition: InlineCost.h:134
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:373
const int LastCallToStaticBonus
Definition: InlineCost.h:47
static InlineCost getAlways(const char *Reason)
Definition: InlineCost.h:92
const int CallPenalty
Definition: InlineCost.h:46
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
bool isAlways() const
Definition: InlineCost.h:102
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
const int IndirectCallThreshold
Definition: InlineCost.h:45
const int OptAggressiveThreshold
Use when -O3 is specified.
Definition: InlineCost.h:41
Optional< int > OptMinSizeThreshold
Threshold to use when the caller is optimized for minsize.
Definition: InlineCost.h:174
InlineResult isInlineViable(Function &Callee)
Minimal filter to detect invalid constructs for inlining.
static InlineResult success()
Definition: InlineCost.h:139
Optional< int > LocallyHotCallSiteThreshold
Threshold to use when the callsite is considered hot relative to function entry.
Definition: InlineCost.h:181
int getThreshold() const
Get the threshold against which the cost was computed.
Definition: InlineCost.h:114
const char * getReason() const
Get the reason of Always or Never.
Definition: InlineCost.h:120
Optional< bool > ComputeFullInlineCost
Compute inline cost even when the cost has exceeded the threshold.
Definition: InlineCost.h:187
static InlineResult failure(const char *Reason)
Definition: InlineCost.h:140
const uint64_t MaxSimplifiedDynamicAllocaToInline
Do not inline dynamic allocas that have been constant propagated to be static allocas above this amou...
Definition: InlineCost.h:54
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
InlineParams getInlineParams()
Generate the parameters to tune the inline cost analysis based only on the commandline options...
Provides information about what library functions are available for the current target.
Optional< int > ColdThreshold
Threshold to use for cold callees.
Definition: InlineCost.h:168
int getCallsiteCost(CallBase &Call, const DataLayout &DL)
Return the cost associated with a callsite, including parameter passing and the call/return instructi...
int getCost() const
Get the inline cost estimate.
Definition: InlineCost.h:108
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
int getCostDelta() const
Get the cost delta from the threshold for inlining.
Definition: InlineCost.h:129
static InlineCost getNever(const char *Reason)
Definition: InlineCost.h:95
static cl::opt< int > DefaultThreshold("inlinedefault-threshold", cl::Hidden, cl::init(225), cl::ZeroOrMore, cl::desc("Default amount of inlining to perform"))
const unsigned TotalAllocaSizeRecursiveCaller
Do not inline functions which allocate this many bytes on the stack when the caller is recursive...
Definition: InlineCost.h:51
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Optional< InlineResult > getAttributeBasedInliningDecision(CallBase &Call, Function *Callee, TargetTransformInfo &CalleeTTI, function_ref< const TargetLibraryInfo &(Function &)> GetTLI)
Returns InlineResult::success() if the call site should be always inlined because of user directives...
Optional< int > ColdCallSiteThreshold
Threshold to use when the callsite is considered cold.
Definition: InlineCost.h:184
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
const char * getFailureReason() const
Definition: InlineCost.h:144
A container for analyses that lazily runs them and caches their results.
const int OptSizeThreshold
Use when optsize (-Os) is specified.
Definition: InlineCost.h:35
The optimization diagnostic interface.
Optional< int > HotCallSiteThreshold
Threshold to use when the callsite is considered hot.
Definition: InlineCost.h:177
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL