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:
69 : Cost(std::move(Cost)), Benefit(std::move(Benefit)) {}
70
71 const APInt &getCost() const { return Cost; }
72
73 const APInt &getBenefit() const { return Benefit; }
74
75private:
76 APInt Cost;
77 APInt Benefit;
78};
79
80/// Represents the cost of inlining a function.
81///
82/// This supports special values for functions which should "always" or
83/// "never" be inlined. Otherwise, the cost represents a unitless amount;
84/// smaller values increase the likelihood of the function being inlined.
85///
86/// Objects of this type also provide the adjusted threshold for inlining
87/// based on the information available for a particular callsite. They can be
88/// directly tested to determine if inlining should occur given the cost and
89/// threshold for this cost metric.
91 enum SentinelValues { AlwaysInlineCost = INT_MIN, NeverInlineCost = INT_MAX };
92
93 /// The estimated cost of inlining this callsite.
94 int Cost = 0;
95
96 /// The adjusted threshold against which this cost was computed.
97 int Threshold = 0;
98
99 /// The amount of StaticBonus that has been applied.
100 int StaticBonusApplied = 0;
101
102 /// Must be set for Always and Never instances.
103 const char *Reason = nullptr;
104
105 /// The cost-benefit pair computed by cost-benefit analysis.
106 std::optional<CostBenefitPair> CostBenefit;
107
108 // Trivial constructor, interesting logic in the factory functions below.
109 InlineCost(int Cost, int Threshold, int StaticBonusApplied,
110 const char *Reason = nullptr,
111 std::optional<CostBenefitPair> CostBenefit = std::nullopt)
112 : Cost(Cost), Threshold(Threshold),
113 StaticBonusApplied(StaticBonusApplied), Reason(Reason),
115 assert((isVariable() || Reason) &&
116 "Reason must be provided for Never or Always");
117 }
118
119public:
120 static InlineCost get(int Cost, int Threshold, int StaticBonus = 0) {
121 assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value");
122 assert(Cost < NeverInlineCost && "Cost crosses sentinel value");
123 return InlineCost(Cost, Threshold, StaticBonus);
124 }
125 static InlineCost
126 getAlways(const char *Reason,
127 std::optional<CostBenefitPair> CostBenefit = std::nullopt) {
128 return InlineCost(AlwaysInlineCost, 0, 0, Reason, CostBenefit);
129 }
130 static InlineCost
131 getNever(const char *Reason,
132 std::optional<CostBenefitPair> CostBenefit = std::nullopt) {
133 return InlineCost(NeverInlineCost, 0, 0, Reason, CostBenefit);
134 }
135
136 /// Test whether the inline cost is low enough for inlining.
137 explicit operator bool() const { return Cost < Threshold; }
138
139 bool isAlways() const { return Cost == AlwaysInlineCost; }
140 bool isNever() const { return Cost == NeverInlineCost; }
141 bool isVariable() const { return !isAlways() && !isNever(); }
142
143 /// Get the inline cost estimate.
144 /// It is an error to call this on an "always" or "never" InlineCost.
145 int getCost() const {
146 assert(isVariable() && "Invalid access of InlineCost");
147 return Cost;
148 }
149
150 /// Get the threshold against which the cost was computed
151 int getThreshold() const {
152 assert(isVariable() && "Invalid access of InlineCost");
153 return Threshold;
154 }
155
156 /// Get the amount of StaticBonus applied.
158 assert(isVariable() && "Invalid access of InlineCost");
159 return StaticBonusApplied;
160 }
161
162 /// Get the cost-benefit pair which was computed by cost-benefit analysis
163 std::optional<CostBenefitPair> getCostBenefit() const { return CostBenefit; }
164
165 /// Get the reason of Always or Never.
166 const char *getReason() const {
167 assert((Reason || isVariable()) &&
168 "InlineCost reason must be set for Always or Never");
169 return Reason;
170 }
171
172 /// Get the cost delta from the threshold for inlining.
173 /// Only valid if the cost is of the variable kind. Returns a negative
174 /// value if the cost is too high to inline.
175 int getCostDelta() const { return Threshold - getCost(); }
176};
177
178/// InlineResult is basically true or false. For false results the message
179/// describes a reason.
181 const char *Message = nullptr;
182 InlineResult(const char *Message = nullptr) : Message(Message) {}
183
184public:
185 static InlineResult success() { return {}; }
186 static InlineResult failure(const char *Reason) {
187 return InlineResult(Reason);
188 }
189 bool isSuccess() const { return Message == nullptr; }
190 const char *getFailureReason() const {
191 assert(!isSuccess() &&
192 "getFailureReason should only be called in failure cases");
193 return Message;
194 }
195};
196
197/// Thresholds to tune inline cost analysis. The inline cost analysis decides
198/// the condition to apply a threshold and applies it. Otherwise,
199/// DefaultThreshold is used. If a threshold is Optional, it is applied only
200/// when it has a valid value. Typically, users of inline cost analysis
201/// obtain an InlineParams object through one of the \c getInlineParams methods
202/// and pass it to \c getInlineCost. Some specialized versions of inliner
203/// (such as the pre-inliner) might have custom logic to compute \c InlineParams
204/// object.
205
207 /// The default threshold to start with for a callee.
209
210 /// Threshold to use for callees with inline hint.
211 std::optional<int> HintThreshold;
212
213 /// Threshold to use for cold callees.
214 std::optional<int> ColdThreshold;
215
216 /// Threshold to use when the caller is optimized for size.
217 std::optional<int> OptSizeThreshold;
218
219 /// Threshold to use when the caller is optimized for minsize.
220 std::optional<int> OptMinSizeThreshold;
221
222 /// Threshold to use when the callsite is considered hot.
223 std::optional<int> HotCallSiteThreshold;
224
225 /// Threshold to use when the callsite is considered hot relative to function
226 /// entry.
227 std::optional<int> LocallyHotCallSiteThreshold;
228
229 /// Threshold to use when the callsite is considered cold.
230 std::optional<int> ColdCallSiteThreshold;
231
232 /// Compute inline cost even when the cost has exceeded the threshold.
233 std::optional<bool> ComputeFullInlineCost;
234
235 /// Indicate whether we should allow inline deferral.
236 std::optional<bool> EnableDeferral;
237
238 /// Indicate whether we allow inlining for recursive call.
239 std::optional<bool> AllowRecursiveCall = false;
240};
241
242std::optional<int> getStringFnAttrAsInt(CallBase &CB, StringRef AttrKind);
243
244/// Generate the parameters to tune the inline cost analysis based only on the
245/// commandline options.
247
248/// Generate the parameters to tune the inline cost analysis based on command
249/// line options. If -inline-threshold option is not explicitly passed,
250/// \p Threshold is used as the default threshold.
251InlineParams getInlineParams(int Threshold);
252
253/// Generate the parameters to tune the inline cost analysis based on command
254/// line options. If -inline-threshold option is not explicitly passed,
255/// the default threshold is computed from \p OptLevel and \p SizeOptLevel.
256/// An \p OptLevel value above 3 is considered an aggressive optimization mode.
257/// \p SizeOptLevel of 1 corresponds to the -Os flag and 2 corresponds to
258/// the -Oz flag.
259InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel);
260
261/// Return the cost associated with a callsite, including parameter passing
262/// and the call/return instruction.
263int getCallsiteCost(const TargetTransformInfo &TTI, const CallBase &Call,
264 const DataLayout &DL);
265
266/// Get an InlineCost object representing the cost of inlining this
267/// callsite.
268///
269/// Note that a default threshold is passed into this function. This threshold
270/// could be modified based on callsite's properties and only costs below this
271/// new threshold are computed with any accuracy. The new threshold can be
272/// used to bound the computation necessary to determine whether the cost is
273/// sufficiently low to warrant inlining.
274///
275/// Also note that calling this function *dynamically* computes the cost of
276/// inlining the callsite. It is an expensive, heavyweight call.
278getInlineCost(CallBase &Call, const InlineParams &Params,
279 TargetTransformInfo &CalleeTTI,
280 function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
281 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
282 function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
283 ProfileSummaryInfo *PSI = nullptr,
284 OptimizationRemarkEmitter *ORE = nullptr);
285
286/// Get an InlineCost with the callee explicitly specified.
287/// This allows you to calculate the cost of inlining a function via a
288/// pointer. This behaves exactly as the version with no explicit callee
289/// parameter in all other respects.
290//
292getInlineCost(CallBase &Call, Function *Callee, const InlineParams &Params,
293 TargetTransformInfo &CalleeTTI,
294 function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
295 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
296 function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
297 ProfileSummaryInfo *PSI = nullptr,
298 OptimizationRemarkEmitter *ORE = nullptr);
299
300/// Returns InlineResult::success() if the call site should be always inlined
301/// because of user directives, and the inlining is viable. Returns
302/// InlineResult::failure() if the inlining may never happen because of user
303/// directives or incompatibilities detectable without needing callee traversal.
304/// Otherwise returns std::nullopt, meaning that inlining should be decided
305/// based on other criteria (e.g. cost modeling).
306std::optional<InlineResult> getAttributeBasedInliningDecision(
307 CallBase &Call, Function *Callee, TargetTransformInfo &CalleeTTI,
308 function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
309
310/// Get the cost estimate ignoring thresholds. This is similar to getInlineCost
311/// when passed InlineParams::ComputeFullInlineCost, or a non-null ORE. It
312/// uses default InlineParams otherwise.
313/// Contrary to getInlineCost, which makes a threshold-based final evaluation of
314/// should/shouldn't inline, captured in InlineResult, getInliningCostEstimate
315/// returns:
316/// - std::nullopt, if the inlining cannot happen (is illegal)
317/// - an integer, representing the cost.
318std::optional<int> getInliningCostEstimate(
319 CallBase &Call, TargetTransformInfo &CalleeTTI,
320 function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
321 function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
322 ProfileSummaryInfo *PSI = nullptr,
323 OptimizationRemarkEmitter *ORE = nullptr);
324
325/// Get the expanded cost features. The features are returned unconditionally,
326/// even if inlining is impossible.
327std::optional<InlineCostFeatures> getInliningCostFeatures(
328 CallBase &Call, TargetTransformInfo &CalleeTTI,
329 function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
330 function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
331 ProfileSummaryInfo *PSI = nullptr,
332 OptimizationRemarkEmitter *ORE = nullptr);
333
334/// Minimal filter to detect invalid constructs for inlining.
336
337// This pass is used to annotate instructions during the inline process for
338// debugging and analysis. The main purpose of the pass is to see and test
339// inliner's decisions when creating new optimizations to InlineCost.
341 : PassInfoMixin<InlineCostAnnotationPrinterPass> {
343
344public:
347 static bool isRequired() { return true; }
348};
349} // namespace llvm
350
351#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:321
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:1467
const APInt & getBenefit() const
Definition: InlineCost.h:73
CostBenefitPair(APInt Cost, APInt Benefit)
Definition: InlineCost.h:68
const APInt & getCost() const
Definition: InlineCost.h:71
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:90
std::optional< CostBenefitPair > getCostBenefit() const
Get the cost-benefit pair which was computed by cost-benefit analysis.
Definition: InlineCost.h:163
int getThreshold() const
Get the threshold against which the cost was computed.
Definition: InlineCost.h:151
const char * getReason() const
Get the reason of Always or Never.
Definition: InlineCost.h:166
int getStaticBonusApplied() const
Get the amount of StaticBonus applied.
Definition: InlineCost.h:157
int getCost() const
Get the inline cost estimate.
Definition: InlineCost.h:145
static InlineCost getNever(const char *Reason, std::optional< CostBenefitPair > CostBenefit=std::nullopt)
Definition: InlineCost.h:131
static InlineCost getAlways(const char *Reason, std::optional< CostBenefitPair > CostBenefit=std::nullopt)
Definition: InlineCost.h:126
static InlineCost get(int Cost, int Threshold, int StaticBonus=0)
Definition: InlineCost.h:120
bool isAlways() const
Definition: InlineCost.h:139
int getCostDelta() const
Get the cost delta from the threshold for inlining.
Definition: InlineCost.h:175
bool isVariable() const
Definition: InlineCost.h:141
bool isNever() const
Definition: InlineCost.h:140
InlineResult is basically true or false.
Definition: InlineCost.h:180
static InlineResult success()
Definition: InlineCost.h:185
static InlineResult failure(const char *Reason)
Definition: InlineCost.h:186
bool isSuccess() const
Definition: InlineCost.h:189
const char * getFailureReason() const
Definition: InlineCost.h:190
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...
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1849
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.
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
InlineCostAnnotationPrinterPass(raw_ostream &OS)
Definition: InlineCost.h:345
Thresholds to tune inline cost analysis.
Definition: InlineCost.h:206
std::optional< int > OptMinSizeThreshold
Threshold to use when the caller is optimized for minsize.
Definition: InlineCost.h:220
std::optional< int > OptSizeThreshold
Threshold to use when the caller is optimized for size.
Definition: InlineCost.h:217
std::optional< int > ColdCallSiteThreshold
Threshold to use when the callsite is considered cold.
Definition: InlineCost.h:230
std::optional< int > ColdThreshold
Threshold to use for cold callees.
Definition: InlineCost.h:214
std::optional< int > HotCallSiteThreshold
Threshold to use when the callsite is considered hot.
Definition: InlineCost.h:223
std::optional< bool > AllowRecursiveCall
Indicate whether we allow inlining for recursive call.
Definition: InlineCost.h:239
int DefaultThreshold
The default threshold to start with for a callee.
Definition: InlineCost.h:208
std::optional< bool > EnableDeferral
Indicate whether we should allow inline deferral.
Definition: InlineCost.h:236
std::optional< int > HintThreshold
Threshold to use for callees with inline hint.
Definition: InlineCost.h:211
std::optional< int > LocallyHotCallSiteThreshold
Threshold to use when the callsite is considered hot relative to function entry.
Definition: InlineCost.h:227
std::optional< bool > ComputeFullInlineCost
Compute inline cost even when the cost has exceeded the threshold.
Definition: InlineCost.h:233
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:74