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