1 | //===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===// |
2 | // |
3 | // The LLVM Compiler Infrastructure |
4 | // |
5 | // This file is distributed under the University of Illinois Open Source |
6 | // License. See LICENSE.TXT for details. |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | // |
10 | // This file implements heuristics for inlining decisions. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_ANALYSIS_INLINECOST_H |
15 | #define LLVM_ANALYSIS_INLINECOST_H |
16 | |
17 | #include "llvm/Analysis/AssumptionCache.h" |
18 | #include "llvm/Analysis/CallGraphSCCPass.h" |
19 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
20 | #include <cassert> |
21 | #include <climits> |
22 | |
23 | namespace llvm { |
24 | class AssumptionCacheTracker; |
25 | class BlockFrequencyInfo; |
26 | class CallSite; |
27 | class DataLayout; |
28 | class Function; |
29 | class ProfileSummaryInfo; |
30 | class TargetTransformInfo; |
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 | } |
53 | |
54 | /// Represents the cost of inlining a function. |
55 | /// |
56 | /// This supports special values for functions which should "always" or |
57 | /// "never" be inlined. Otherwise, the cost represents a unitless amount; |
58 | /// smaller values increase the likelihood of the function being inlined. |
59 | /// |
60 | /// Objects of this type also provide the adjusted threshold for inlining |
61 | /// based on the information available for a particular callsite. They can be |
62 | /// directly tested to determine if inlining should occur given the cost and |
63 | /// threshold for this cost metric. |
64 | class InlineCost { |
65 | enum SentinelValues { |
66 | AlwaysInlineCost = INT_MIN, |
67 | NeverInlineCost = INT_MAX |
68 | }; |
69 | |
70 | /// The estimated cost of inlining this callsite. |
71 | const int Cost; |
72 | |
73 | /// The adjusted threshold against which this cost was computed. |
74 | const int Threshold; |
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 { |
101 | return Cost < Threshold; |
102 | } |
103 | |
104 | bool isAlways() const { return Cost == AlwaysInlineCost; } |
105 | bool isNever() const { return Cost == NeverInlineCost; } |
106 | bool isVariable() const { return !isAlways() && !isNever(); } |
107 | |
108 | /// Get the inline cost estimate. |
109 | /// It is an error to call this on an "always" or "never" InlineCost. |
110 | int getCost() const { |
111 | assert(isVariable() && "Invalid access of InlineCost" ); |
112 | return Cost; |
113 | } |
114 | |
115 | /// Get the threshold against which the cost was computed |
116 | int getThreshold() const { |
117 | assert(isVariable() && "Invalid access of InlineCost" ); |
118 | return Threshold; |
119 | } |
120 | |
121 | /// Get the reason of Always or Never. |
122 | const char *getReason() const { |
123 | assert((Reason || isVariable()) && |
124 | "InlineCost reason must be set for Always or Never" ); |
125 | return Reason; |
126 | } |
127 | |
128 | /// Get the cost delta from the threshold for inlining. |
129 | /// Only valid if the cost is of the variable kind. Returns a negative |
130 | /// value if the cost is too high to inline. |
131 | int getCostDelta() const { return Threshold - getCost(); } |
132 | }; |
133 | |
134 | /// InlineResult is basically true or false. For false results the message |
135 | /// describes a reason why it is decided not to inline. |
136 | struct InlineResult { |
137 | const char *message = nullptr; |
138 | InlineResult(bool result, const char *message = nullptr) |
139 | : message(result ? nullptr : (message ? message : "cost > threshold" )) {} |
140 | InlineResult(const char *message = nullptr) : message(message) {} |
141 | operator bool() const { return !message; } |
142 | operator const char *() const { return message; } |
143 | }; |
144 | |
145 | /// Thresholds to tune inline cost analysis. The inline cost analysis decides |
146 | /// the condition to apply a threshold and applies it. Otherwise, |
147 | /// DefaultThreshold is used. If a threshold is Optional, it is applied only |
148 | /// when it has a valid value. Typically, users of inline cost analysis |
149 | /// obtain an InlineParams object through one of the \c getInlineParams methods |
150 | /// and pass it to \c getInlineCost. Some specialized versions of inliner |
151 | /// (such as the pre-inliner) might have custom logic to compute \c InlineParams |
152 | /// object. |
153 | |
154 | struct InlineParams { |
155 | /// The default threshold to start with for a callee. |
156 | int DefaultThreshold; |
157 | |
158 | /// Threshold to use for callees with inline hint. |
159 | Optional<int> HintThreshold; |
160 | |
161 | /// Threshold to use for cold callees. |
162 | Optional<int> ColdThreshold; |
163 | |
164 | /// Threshold to use when the caller is optimized for size. |
165 | Optional<int> OptSizeThreshold; |
166 | |
167 | /// Threshold to use when the caller is optimized for minsize. |
168 | Optional<int> OptMinSizeThreshold; |
169 | |
170 | /// Threshold to use when the callsite is considered hot. |
171 | Optional<int> HotCallSiteThreshold; |
172 | |
173 | /// Threshold to use when the callsite is considered hot relative to function |
174 | /// entry. |
175 | Optional<int> LocallyHotCallSiteThreshold; |
176 | |
177 | /// Threshold to use when the callsite is considered cold. |
178 | Optional<int> ColdCallSiteThreshold; |
179 | |
180 | /// Compute inline cost even when the cost has exceeded the threshold. |
181 | Optional<bool> ComputeFullInlineCost; |
182 | }; |
183 | |
184 | /// Generate the parameters to tune the inline cost analysis based only on the |
185 | /// commandline options. |
186 | InlineParams getInlineParams(); |
187 | |
188 | /// Generate the parameters to tune the inline cost analysis based on command |
189 | /// line options. If -inline-threshold option is not explicitly passed, |
190 | /// \p Threshold is used as the default threshold. |
191 | InlineParams getInlineParams(int Threshold); |
192 | |
193 | /// Generate the parameters to tune the inline cost analysis based on command |
194 | /// line options. If -inline-threshold option is not explicitly passed, |
195 | /// the default threshold is computed from \p OptLevel and \p SizeOptLevel. |
196 | /// An \p OptLevel value above 3 is considered an aggressive optimization mode. |
197 | /// \p SizeOptLevel of 1 corresponds to the -Os flag and 2 corresponds to |
198 | /// the -Oz flag. |
199 | InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel); |
200 | |
201 | /// Return the cost associated with a callsite, including parameter passing |
202 | /// and the call/return instruction. |
203 | int getCallsiteCost(CallSite CS, const DataLayout &DL); |
204 | |
205 | /// Get an InlineCost object representing the cost of inlining this |
206 | /// callsite. |
207 | /// |
208 | /// Note that a default threshold is passed into this function. This threshold |
209 | /// could be modified based on callsite's properties and only costs below this |
210 | /// new threshold are computed with any accuracy. The new threshold can be |
211 | /// used to bound the computation necessary to determine whether the cost is |
212 | /// sufficiently low to warrant inlining. |
213 | /// |
214 | /// Also note that calling this function *dynamically* computes the cost of |
215 | /// inlining the callsite. It is an expensive, heavyweight call. |
216 | InlineCost getInlineCost( |
217 | CallSite CS, const InlineParams &Params, TargetTransformInfo &CalleeTTI, |
218 | std::function<AssumptionCache &(Function &)> &GetAssumptionCache, |
219 | Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI, |
220 | ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE = nullptr); |
221 | |
222 | /// Get an InlineCost with the callee explicitly specified. |
223 | /// This allows you to calculate the cost of inlining a function via a |
224 | /// pointer. This behaves exactly as the version with no explicit callee |
225 | /// parameter in all other respects. |
226 | // |
227 | InlineCost |
228 | getInlineCost(CallSite CS, Function *Callee, const InlineParams &Params, |
229 | TargetTransformInfo &CalleeTTI, |
230 | std::function<AssumptionCache &(Function &)> &GetAssumptionCache, |
231 | Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI, |
232 | ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE); |
233 | |
234 | /// Minimal filter to detect invalid constructs for inlining. |
235 | bool isInlineViable(Function &Callee); |
236 | } |
237 | |
238 | #endif |
239 | |