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