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/Analysis/AssumptionCache.h"
17#include "llvm/Analysis/CallGraphSCCPass.h"
18#include "llvm/Analysis/OptimizationRemarkEmitter.h"
19#include <cassert>
20#include <climits>
21
22namespace llvm {
23class AssumptionCacheTracker;
24class BlockFrequencyInfo;
25class CallBase;
26class DataLayout;
27class Function;
28class ProfileSummaryInfo;
29class TargetTransformInfo;
30class TargetLibraryInfo;
31
32namespace InlineConstants {
33// Various thresholds used by inline cost analysis.
34/// Use when optsize (-Os) is specified.
35const int OptSizeThreshold = 50;
36
37/// Use when minsize (-Oz) is specified.
38const int OptMinSizeThreshold = 5;
39
40/// Use when -O3 is specified.
41const int OptAggressiveThreshold = 250;
42
43// Various magic constants used to adjust heuristics.
44const int InstrCost = 5;
45const int IndirectCallThreshold = 100;
46const int CallPenalty = 25;
47const int LastCallToStaticBonus = 15000;
48const int ColdccPenalty = 2000;
49/// Do not inline functions which allocate this many bytes on the stack
50/// when the caller is recursive.
51const unsigned TotalAllocaSizeRecursiveCaller = 1024;
52/// Do not inline dynamic allocas that have been constant propagated to be
53/// static allocas above this amount in bytes.
54const 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.
67class 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
86public:
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.
134class InlineResult {
135  const char *Message = nullptr;
136  InlineResult(const char *Message = nullptr) : Message(Message) {}
137
138public:
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
160struct InlineParams {
161  /// The default threshold to start with for a callee.
162  int DefaultThreshold = -1;
163
164  /// Threshold to use for callees with inline hint.
165  Optional<int> HintThreshold;
166
167  /// Threshold to use for cold callees.
168  Optional<int> ColdThreshold;
169
170  /// Threshold to use when the caller is optimized for size.
171  Optional<int> OptSizeThreshold;
172
173  /// Threshold to use when the caller is optimized for minsize.
174  Optional<int> OptMinSizeThreshold;
175
176  /// Threshold to use when the callsite is considered hot.
177  Optional<int> HotCallSiteThreshold;
178
179  /// Threshold to use when the callsite is considered hot relative to function
180  /// entry.
181  Optional<int> LocallyHotCallSiteThreshold;
182
183  /// Threshold to use when the callsite is considered cold.
184  Optional<int> ColdCallSiteThreshold;
185
186  /// Compute inline cost even when the cost has exceeded the threshold.
187  Optional<bool> ComputeFullInlineCost;
188
189  /// Indicate whether we should allow inline deferral.
190  Optional<bool> EnableDeferral = true;
191};
192
193/// Generate the parameters to tune the inline cost analysis based only on the
194/// commandline options.
195InlineParams getInlineParams();
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.
200InlineParams getInlineParams(int 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.
208InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel);
209
210/// Return the cost associated with a callsite, including parameter passing
211/// and the call/return instruction.
212int 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.
225InlineCost
226getInlineCost(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//
239InlineCost
240getInlineCost(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).
254Optional<InlineResult> getAttributeBasedInliningDecision(
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.
266Optional<int> getInliningCostEstimate(
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.
274InlineResult isInlineViable(Function &Callee);
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.
279struct InlineCostAnnotationPrinterPass
280    : PassInfoMixin<InlineCostAnnotationPrinterPass> {
281  raw_ostream &OS;
282
283public:
284  explicit InlineCostAnnotationPrinterPass(raw_ostream &OS) : OS(OS) {}
285  PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
286};
287} // namespace llvm
288
289#endif
290