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 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) Cost(Cost)81 : Cost(Cost), Threshold(Threshold), Reason(Reason) { 82 assert((isVariable() || Reason) && 83 "Reason must be provided for Never or Always"); 84 } 85 86 public: get(int Cost,int Threshold)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 } getAlways(const char * Reason)92 static InlineCost getAlways(const char *Reason) { 93 return InlineCost(AlwaysInlineCost, 0, Reason); 94 } getNever(const char * Reason)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 isAlways()102 bool isAlways() const { return Cost == AlwaysInlineCost; } isNever()103 bool isNever() const { return Cost == NeverInlineCost; } isVariable()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. getCost()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 getThreshold()114 int getThreshold() const { 115 assert(isVariable() && "Invalid access of InlineCost"); 116 return Threshold; 117 } 118 119 /// Get the reason of Always or Never. getReason()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. getCostDelta()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. 134 class InlineResult { 135 const char *Message = nullptr; Message(Message)136 InlineResult(const char *Message = nullptr) : Message(Message) {} 137 138 public: success()139 static InlineResult success() { return {}; } failure(const char * Reason)140 static InlineResult failure(const char *Reason) { 141 return InlineResult(Reason); 142 } isSuccess()143 bool isSuccess() const { return Message == nullptr; } getFailureReason()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. 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. 195 InlineParams 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. 200 InlineParams 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. 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. 225 InlineCost 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 // 239 InlineCost 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). 254 Optional<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. 266 Optional<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. 274 InlineResult 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. 279 struct InlineCostAnnotationPrinterPass 280 : PassInfoMixin<InlineCostAnnotationPrinterPass> { 281 raw_ostream &OS; 282 283 public: InlineCostAnnotationPrinterPassInlineCostAnnotationPrinterPass284 explicit InlineCostAnnotationPrinterPass(raw_ostream &OS) : OS(OS) {} 285 PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); 286 }; 287 } // namespace llvm 288 289 #endif 290