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" |
17 | #include "llvm/ADT/STLFunctionalExtras.h" |
18 | #include "llvm/Analysis/InlineModelFeatureMaps.h" |
19 | #include "llvm/IR/PassManager.h" |
20 | #include <cassert> |
21 | #include <climits> |
22 | #include <optional> |
23 | |
24 | namespace llvm { |
25 | class AssumptionCache; |
26 | class ; |
27 | class BlockFrequencyInfo; |
28 | class CallBase; |
29 | class DataLayout; |
30 | class Function; |
31 | class ProfileSummaryInfo; |
32 | class TargetTransformInfo; |
33 | class TargetLibraryInfo; |
34 | |
35 | namespace InlineConstants { |
36 | // Various thresholds used by inline cost analysis. |
37 | /// Use when optsize (-Os) is specified. |
38 | const int OptSizeThreshold = 50; |
39 | |
40 | /// Use when minsize (-Oz) is specified. |
41 | const int OptMinSizeThreshold = 5; |
42 | |
43 | /// Use when -O3 is specified. |
44 | const int OptAggressiveThreshold = 250; |
45 | |
46 | // Various magic constants used to adjust heuristics. |
47 | int getInstrCost(); |
48 | const int IndirectCallThreshold = 100; |
49 | const int LoopPenalty = 25; |
50 | const int LastCallToStaticBonus = 15000; |
51 | const int ColdccPenalty = 2000; |
52 | /// Do not inline functions which allocate this many bytes on the stack |
53 | /// when the caller is recursive. |
54 | const unsigned TotalAllocaSizeRecursiveCaller = 1024; |
55 | /// Do not inline dynamic allocas that have been constant propagated to be |
56 | /// static allocas above this amount in bytes. |
57 | const uint64_t MaxSimplifiedDynamicAllocaToInline = 65536; |
58 | |
59 | const char FunctionInlineCostMultiplierAttributeName[] = |
60 | "function-inline-cost-multiplier" ; |
61 | |
62 | const char MaxInlineStackSizeAttributeName[] = "inline-max-stacksize" ; |
63 | } // namespace InlineConstants |
64 | |
65 | // The cost-benefit pair computed by cost-benefit analysis. |
66 | class CostBenefitPair { |
67 | public: |
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 | |
74 | private: |
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. |
89 | class InlineCost { |
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), |
113 | CostBenefit(CostBenefit) { |
114 | assert((isVariable() || Reason) && |
115 | "Reason must be provided for Never or Always" ); |
116 | } |
117 | |
118 | public: |
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. |
156 | int getStaticBonusApplied() const { |
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. |
179 | class InlineResult { |
180 | const char *Message = nullptr; |
181 | InlineResult(const char *Message = nullptr) : Message(Message) {} |
182 | |
183 | public: |
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 | |
205 | struct InlineParams { |
206 | /// The default threshold to start with for a callee. |
207 | int DefaultThreshold = -1; |
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 | |
241 | std::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. |
245 | InlineParams getInlineParams(); |
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. |
250 | InlineParams 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. |
258 | InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel); |
259 | |
260 | /// Return the cost associated with a callsite, including parameter passing |
261 | /// and the call/return instruction. |
262 | int 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. |
276 | InlineCost |
277 | getInlineCost(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 | // |
290 | InlineCost |
291 | getInlineCost(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). |
305 | std::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. |
317 | std::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. |
326 | std::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. |
334 | InlineResult isInlineViable(Function &Callee); |
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. |
339 | struct InlineCostAnnotationPrinterPass |
340 | : PassInfoMixin<InlineCostAnnotationPrinterPass> { |
341 | raw_ostream &OS; |
342 | |
343 | public: |
344 | explicit InlineCostAnnotationPrinterPass(raw_ostream &OS) : OS(OS) {} |
345 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); |
346 | static bool isRequired() { return true; } |
347 | }; |
348 | } // namespace llvm |
349 | |
350 | #endif |
351 | |