LLVM  13.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 
19 #include <cassert>
20 #include <climits>
21 
22 namespace llvm {
23 class AssumptionCacheTracker;
24 class BlockFrequencyInfo;
25 class CallBase;
26 class DataLayout;
27 class Function;
28 class ProfileSummaryInfo;
29 class TargetTransformInfo;
30 class TargetLibraryInfo;
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 /// Do not inline dynamic allocas that have been constant propagated to be
53 /// static allocas above this amount in bytes.
54 const uint64_t MaxSimplifiedDynamicAllocaToInline = 65536;
55 } // namespace InlineConstants
56 
57 /// Represents the cost of inlining a function.
58 ///
59 /// This supports special values for functions which should "always" or
60 /// "never" be inlined. Otherwise, the cost represents a unitless amount;
61 /// smaller values increase the likelihood of the function being inlined.
62 ///
63 /// Objects of this type also provide the adjusted threshold for inlining
64 /// based on the information available for a particular callsite. They can be
65 /// directly tested to determine if inlining should occur given the cost and
66 /// threshold for this cost metric.
67 class InlineCost {
68  enum SentinelValues { AlwaysInlineCost = INT_MIN, NeverInlineCost = INT_MAX };
69 
70  /// The estimated cost of inlining this callsite.
71  int Cost = 0;
72 
73  /// The adjusted threshold against which this cost was computed.
74  int Threshold = 0;
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 { return Cost < Threshold; }
101 
102  bool isAlways() const { return Cost == AlwaysInlineCost; }
103  bool isNever() const { return Cost == NeverInlineCost; }
104  bool isVariable() const { return !isAlways() && !isNever(); }
105 
106  /// Get the inline cost estimate.
107  /// It is an error to call this on an "always" or "never" InlineCost.
108  int getCost() const {
109  assert(isVariable() && "Invalid access of InlineCost");
110  return Cost;
111  }
112 
113  /// Get the threshold against which the cost was computed
114  int getThreshold() const {
115  assert(isVariable() && "Invalid access of InlineCost");
116  return Threshold;
117  }
118 
119  /// Get the reason of Always or Never.
120  const char *getReason() const {
121  assert((Reason || isVariable()) &&
122  "InlineCost reason must be set for Always or Never");
123  return Reason;
124  }
125 
126  /// Get the cost delta from the threshold for inlining.
127  /// Only valid if the cost is of the variable kind. Returns a negative
128  /// value if the cost is too high to inline.
129  int getCostDelta() const { return Threshold - getCost(); }
130 };
131 
132 /// InlineResult is basically true or false. For false results the message
133 /// describes a reason.
135  const char *Message = nullptr;
136  InlineResult(const char *Message = nullptr) : Message(Message) {}
137 
138 public:
139  static InlineResult success() { return {}; }
140  static InlineResult failure(const char *Reason) {
141  return InlineResult(Reason);
142  }
143  bool isSuccess() const { return Message == nullptr; }
144  const char *getFailureReason() const {
145  assert(!isSuccess() &&
146  "getFailureReason should only be called in failure cases");
147  return Message;
148  }
149 };
150 
151 /// Thresholds to tune inline cost analysis. The inline cost analysis decides
152 /// the condition to apply a threshold and applies it. Otherwise,
153 /// DefaultThreshold is used. If a threshold is Optional, it is applied only
154 /// when it has a valid value. Typically, users of inline cost analysis
155 /// obtain an InlineParams object through one of the \c getInlineParams methods
156 /// and pass it to \c getInlineCost. Some specialized versions of inliner
157 /// (such as the pre-inliner) might have custom logic to compute \c InlineParams
158 /// object.
159 
160 struct InlineParams {
161  /// The default threshold to start with for a callee.
163 
164  /// Threshold to use for callees with inline hint.
166 
167  /// Threshold to use for cold callees.
169 
170  /// Threshold to use when the caller is optimized for size.
172 
173  /// Threshold to use when the caller is optimized for minsize.
175 
176  /// Threshold to use when the callsite is considered hot.
178 
179  /// Threshold to use when the callsite is considered hot relative to function
180  /// entry.
182 
183  /// Threshold to use when the callsite is considered cold.
185 
186  /// Compute inline cost even when the cost has exceeded the threshold.
188 
189  /// Indicate whether we should allow inline deferral.
191 };
192 
193 /// Generate the parameters to tune the inline cost analysis based only on the
194 /// commandline options.
196 
197 /// Generate the parameters to tune the inline cost analysis based on command
198 /// line options. If -inline-threshold option is not explicitly passed,
199 /// \p Threshold is used as the default threshold.
201 
202 /// Generate the parameters to tune the inline cost analysis based on command
203 /// line options. If -inline-threshold option is not explicitly passed,
204 /// the default threshold is computed from \p OptLevel and \p SizeOptLevel.
205 /// An \p OptLevel value above 3 is considered an aggressive optimization mode.
206 /// \p SizeOptLevel of 1 corresponds to the -Os flag and 2 corresponds to
207 /// the -Oz flag.
208 InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel);
209 
210 /// Return the cost associated with a callsite, including parameter passing
211 /// and the call/return instruction.
212 int getCallsiteCost(CallBase &Call, const DataLayout &DL);
213 
214 /// Get an InlineCost object representing the cost of inlining this
215 /// callsite.
216 ///
217 /// Note that a default threshold is passed into this function. This threshold
218 /// could be modified based on callsite's properties and only costs below this
219 /// new threshold are computed with any accuracy. The new threshold can be
220 /// used to bound the computation necessary to determine whether the cost is
221 /// sufficiently low to warrant inlining.
222 ///
223 /// Also note that calling this function *dynamically* computes the cost of
224 /// inlining the callsite. It is an expensive, heavyweight call.
226 getInlineCost(CallBase &Call, const InlineParams &Params,
227  TargetTransformInfo &CalleeTTI,
228  function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
229  function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
230  function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
231  ProfileSummaryInfo *PSI = nullptr,
232  OptimizationRemarkEmitter *ORE = nullptr);
233 
234 /// Get an InlineCost with the callee explicitly specified.
235 /// This allows you to calculate the cost of inlining a function via a
236 /// pointer. This behaves exactly as the version with no explicit callee
237 /// parameter in all other respects.
238 //
240 getInlineCost(CallBase &Call, Function *Callee, const InlineParams &Params,
241  TargetTransformInfo &CalleeTTI,
242  function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
243  function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
244  function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
245  ProfileSummaryInfo *PSI = nullptr,
246  OptimizationRemarkEmitter *ORE = nullptr);
247 
248 /// Returns InlineResult::success() if the call site should be always inlined
249 /// because of user directives, and the inlining is viable. Returns
250 /// InlineResult::failure() if the inlining may never happen because of user
251 /// directives or incompatibilities detectable without needing callee traversal.
252 /// Otherwise returns None, meaning that inlining should be decided based on
253 /// other criteria (e.g. cost modeling).
255  CallBase &Call, Function *Callee, TargetTransformInfo &CalleeTTI,
256  function_ref<const TargetLibraryInfo &(Function &)> GetTLI);
257 
258 /// Get the cost estimate ignoring thresholds. This is similar to getInlineCost
259 /// when passed InlineParams::ComputeFullInlineCost, or a non-null ORE. It
260 /// uses default InlineParams otherwise.
261 /// Contrary to getInlineCost, which makes a threshold-based final evaluation of
262 /// should/shouldn't inline, captured in InlineResult, getInliningCostEstimate
263 /// returns:
264 /// - None, if the inlining cannot happen (is illegal)
265 /// - an integer, representing the cost.
267  CallBase &Call, TargetTransformInfo &CalleeTTI,
268  function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
269  function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
270  ProfileSummaryInfo *PSI = nullptr,
271  OptimizationRemarkEmitter *ORE = nullptr);
272 
273 /// Minimal filter to detect invalid constructs for inlining.
275 
276 // This pass is used to annotate instructions during the inline process for
277 // debugging and analysis. The main purpose of the pass is to see and test
278 // inliner's decisions when creating new optimizations to InlineCost.
280  : PassInfoMixin<InlineCostAnnotationPrinterPass> {
282 
283 public:
286 };
287 } // namespace llvm
288 
289 #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:102
llvm::InlineCost::getCost
int getCost() const
Get the inline cost estimate.
Definition: InlineCost.h:108
AssumptionCache.h
llvm::InlineResult::success
static InlineResult success()
Definition: InlineCost.h:139
llvm::InlineCostAnnotationPrinterPass::InlineCostAnnotationPrinterPass
InlineCostAnnotationPrinterPass(raw_ostream &OS)
Definition: InlineCost.h:284
llvm
Definition: AllocatorList.h:23
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::InlineParams::DefaultThreshold
int DefaultThreshold
The default threshold to start with for a callee.
Definition: InlineCost.h:162
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:61
llvm::InlineParams::LocallyHotCallSiteThreshold
Optional< int > LocallyHotCallSiteThreshold
Threshold to use when the callsite is considered hot relative to function entry.
Definition: InlineCost.h:181
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
OptimizationRemarkEmitter.h
llvm::InlineConstants::OptSizeThreshold
const int OptSizeThreshold
Use when optsize (-Os) is specified.
Definition: InlineCost.h:35
llvm::InlineCost::getNever
static InlineCost getNever(const char *Reason)
Definition: InlineCost.h:95
llvm::Optional< int >
llvm::isInlineViable
InlineResult isInlineViable(Function &Callee)
Minimal filter to detect invalid constructs for inlining.
Definition: InlineCost.cpp:2631
llvm::InlineParams
Thresholds to tune inline cost analysis.
Definition: InlineCost.h:160
llvm::InlineCost::getThreshold
int getThreshold() const
Get the threshold against which the cost was computed.
Definition: InlineCost.h:114
llvm::InlineParams::ColdThreshold
Optional< int > ColdThreshold
Threshold to use for cold callees.
Definition: InlineCost.h:168
llvm::InlineCost::isNever
bool isNever() const
Definition: InlineCost.h:103
llvm::InlineParams::OptMinSizeThreshold
Optional< int > OptMinSizeThreshold
Threshold to use when the caller is optimized for minsize.
Definition: InlineCost.h:174
llvm::InlineConstants::CallPenalty
const int CallPenalty
Definition: InlineCost.h:46
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:187
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:2473
llvm::InlineCost
Represents the cost of inlining a function.
Definition: InlineCost.h:67
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::InlineResult::isSuccess
bool isSuccess() const
Definition: InlineCost.h:143
llvm::InlineCostAnnotationPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: InlineCost.cpp:2772
llvm::InlineCost::get
static InlineCost get(int Cost, int Threshold)
Definition: InlineCost.h:87
llvm::getInlineParams
InlineParams getInlineParams()
Generate the parameters to tune the inline cost analysis based only on the commandline options.
Definition: InlineCost.cpp:2743
llvm::InlineConstants::InstrCost
const int InstrCost
Definition: InlineCost.h:44
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:45
llvm::InlineConstants::OptAggressiveThreshold
const int OptAggressiveThreshold
Use when -O3 is specified.
Definition: InlineCost.h:41
llvm::InlineCost::getCostDelta
int getCostDelta() const
Get the cost delta from the threshold for inlining.
Definition: InlineCost.h:129
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::InlineCostAnnotationPrinterPass::OS
raw_ostream & OS
Definition: InlineCost.h:281
llvm::InlineParams::ColdCallSiteThreshold
Optional< int > ColdCallSiteThreshold
Threshold to use when the callsite is considered cold.
Definition: InlineCost.h:184
llvm::InlineCostAnnotationPrinterPass
Definition: InlineCost.h:279
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:120
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:144
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:54
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:2508
llvm::InlineParams::HintThreshold
Optional< int > HintThreshold
Threshold to use for callees with inline hint.
Definition: InlineCost.h:165
llvm::InlineConstants::ColdccPenalty
const int ColdccPenalty
Definition: InlineCost.h:48
llvm::InlineCost::getAlways
static InlineCost getAlways(const char *Reason)
Definition: InlineCost.h:92
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:208
llvm::InlineResult::failure
static InlineResult failure(const char *Reason)
Definition: InlineCost.h:140
llvm::InlineConstants::OptMinSizeThreshold
const int OptMinSizeThreshold
Use when minsize (-Oz) is specified.
Definition: InlineCost.h:38
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:2483
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:2440
llvm::InlineConstants::LastCallToStaticBonus
const int LastCallToStaticBonus
Definition: InlineCost.h:47
Threshold
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1164
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:104
llvm::InlineParams::HotCallSiteThreshold
Optional< int > HotCallSiteThreshold
Threshold to use when the callsite is considered hot.
Definition: InlineCost.h:177
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:51
llvm::InlineParams::EnableDeferral
Optional< bool > EnableDeferral
Indicate whether we should allow inline deferral.
Definition: InlineCost.h:190
llvm::InlineResult
InlineResult is basically true or false.
Definition: InlineCost.h:134
llvm::InlineParams::OptSizeThreshold
Optional< int > OptSizeThreshold
Threshold to use when the caller is optimized for size.
Definition: InlineCost.h:171
llvm::codeview::PublicSymFlags::Function
@ Function