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/InlineModelFeatureMaps.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 CallBase; 27 class DataLayout; 28 class Function; 29 class ProfileSummaryInfo; 30 class TargetTransformInfo; 31 class TargetLibraryInfo; 32 33 namespace InlineConstants { 34 // Various thresholds used by inline cost analysis. 35 /// Use when optsize (-Os) is specified. 36 const int OptSizeThreshold = 50; 37 38 /// Use when minsize (-Oz) is specified. 39 const int OptMinSizeThreshold = 5; 40 41 /// Use when -O3 is specified. 42 const int OptAggressiveThreshold = 250; 43 44 // Various magic constants used to adjust heuristics. 45 const int InstrCost = 5; 46 const int IndirectCallThreshold = 100; 47 const int LoopPenalty = 25; 48 const int LastCallToStaticBonus = 15000; 49 const int ColdccPenalty = 2000; 50 /// Do not inline functions which allocate this many bytes on the stack 51 /// when the caller is recursive. 52 const unsigned TotalAllocaSizeRecursiveCaller = 1024; 53 /// Do not inline dynamic allocas that have been constant propagated to be 54 /// static allocas above this amount in bytes. 55 const uint64_t MaxSimplifiedDynamicAllocaToInline = 65536; 56 } // namespace InlineConstants 57 58 // The cost-benefit pair computed by cost-benefit analysis. 59 class CostBenefitPair { 60 public: CostBenefitPair(APInt Cost,APInt Benefit)61 CostBenefitPair(APInt Cost, APInt Benefit) : Cost(Cost), Benefit(Benefit) {} 62 getCost()63 const APInt &getCost() const { return Cost; } 64 getBenefit()65 const APInt &getBenefit() const { return Benefit; } 66 67 private: 68 APInt Cost; 69 APInt Benefit; 70 }; 71 72 /// Represents the cost of inlining a function. 73 /// 74 /// This supports special values for functions which should "always" or 75 /// "never" be inlined. Otherwise, the cost represents a unitless amount; 76 /// smaller values increase the likelihood of the function being inlined. 77 /// 78 /// Objects of this type also provide the adjusted threshold for inlining 79 /// based on the information available for a particular callsite. They can be 80 /// directly tested to determine if inlining should occur given the cost and 81 /// threshold for this cost metric. 82 class InlineCost { 83 enum SentinelValues { AlwaysInlineCost = INT_MIN, NeverInlineCost = INT_MAX }; 84 85 /// The estimated cost of inlining this callsite. 86 int Cost = 0; 87 88 /// The adjusted threshold against which this cost was computed. 89 int Threshold = 0; 90 91 /// Must be set for Always and Never instances. 92 const char *Reason = nullptr; 93 94 /// The cost-benefit pair computed by cost-benefit analysis. 95 Optional<CostBenefitPair> CostBenefit = None; 96 97 // Trivial constructor, interesting logic in the factory functions below. 98 InlineCost(int Cost, int Threshold, const char *Reason = nullptr, 99 Optional<CostBenefitPair> CostBenefit = None) Cost(Cost)100 : Cost(Cost), Threshold(Threshold), Reason(Reason), 101 CostBenefit(CostBenefit) { 102 assert((isVariable() || Reason) && 103 "Reason must be provided for Never or Always"); 104 } 105 106 public: get(int Cost,int Threshold)107 static InlineCost get(int Cost, int Threshold) { 108 assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); 109 assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); 110 return InlineCost(Cost, Threshold); 111 } 112 static InlineCost getAlways(const char *Reason, 113 Optional<CostBenefitPair> CostBenefit = None) { 114 return InlineCost(AlwaysInlineCost, 0, Reason, CostBenefit); 115 } 116 static InlineCost getNever(const char *Reason, 117 Optional<CostBenefitPair> CostBenefit = None) { 118 return InlineCost(NeverInlineCost, 0, Reason, CostBenefit); 119 } 120 121 /// Test whether the inline cost is low enough for inlining. 122 explicit operator bool() const { return Cost < Threshold; } 123 isAlways()124 bool isAlways() const { return Cost == AlwaysInlineCost; } isNever()125 bool isNever() const { return Cost == NeverInlineCost; } isVariable()126 bool isVariable() const { return !isAlways() && !isNever(); } 127 128 /// Get the inline cost estimate. 129 /// It is an error to call this on an "always" or "never" InlineCost. getCost()130 int getCost() const { 131 assert(isVariable() && "Invalid access of InlineCost"); 132 return Cost; 133 } 134 135 /// Get the threshold against which the cost was computed getThreshold()136 int getThreshold() const { 137 assert(isVariable() && "Invalid access of InlineCost"); 138 return Threshold; 139 } 140 141 /// Get the cost-benefit pair which was computed by cost-benefit analysis getCostBenefit()142 Optional<CostBenefitPair> getCostBenefit() const { return CostBenefit; } 143 144 /// Get the reason of Always or Never. getReason()145 const char *getReason() const { 146 assert((Reason || isVariable()) && 147 "InlineCost reason must be set for Always or Never"); 148 return Reason; 149 } 150 151 /// Get the cost delta from the threshold for inlining. 152 /// Only valid if the cost is of the variable kind. Returns a negative 153 /// value if the cost is too high to inline. getCostDelta()154 int getCostDelta() const { return Threshold - getCost(); } 155 }; 156 157 /// InlineResult is basically true or false. For false results the message 158 /// describes a reason. 159 class InlineResult { 160 const char *Message = nullptr; Message(Message)161 InlineResult(const char *Message = nullptr) : Message(Message) {} 162 163 public: success()164 static InlineResult success() { return {}; } failure(const char * Reason)165 static InlineResult failure(const char *Reason) { 166 return InlineResult(Reason); 167 } isSuccess()168 bool isSuccess() const { return Message == nullptr; } getFailureReason()169 const char *getFailureReason() const { 170 assert(!isSuccess() && 171 "getFailureReason should only be called in failure cases"); 172 return Message; 173 } 174 }; 175 176 /// Thresholds to tune inline cost analysis. The inline cost analysis decides 177 /// the condition to apply a threshold and applies it. Otherwise, 178 /// DefaultThreshold is used. If a threshold is Optional, it is applied only 179 /// when it has a valid value. Typically, users of inline cost analysis 180 /// obtain an InlineParams object through one of the \c getInlineParams methods 181 /// and pass it to \c getInlineCost. Some specialized versions of inliner 182 /// (such as the pre-inliner) might have custom logic to compute \c InlineParams 183 /// object. 184 185 struct InlineParams { 186 /// The default threshold to start with for a callee. 187 int DefaultThreshold = -1; 188 189 /// Threshold to use for callees with inline hint. 190 Optional<int> HintThreshold; 191 192 /// Threshold to use for cold callees. 193 Optional<int> ColdThreshold; 194 195 /// Threshold to use when the caller is optimized for size. 196 Optional<int> OptSizeThreshold; 197 198 /// Threshold to use when the caller is optimized for minsize. 199 Optional<int> OptMinSizeThreshold; 200 201 /// Threshold to use when the callsite is considered hot. 202 Optional<int> HotCallSiteThreshold; 203 204 /// Threshold to use when the callsite is considered hot relative to function 205 /// entry. 206 Optional<int> LocallyHotCallSiteThreshold; 207 208 /// Threshold to use when the callsite is considered cold. 209 Optional<int> ColdCallSiteThreshold; 210 211 /// Compute inline cost even when the cost has exceeded the threshold. 212 Optional<bool> ComputeFullInlineCost; 213 214 /// Indicate whether we should allow inline deferral. 215 Optional<bool> EnableDeferral = true; 216 }; 217 218 /// Generate the parameters to tune the inline cost analysis based only on the 219 /// commandline options. 220 InlineParams getInlineParams(); 221 222 /// Generate the parameters to tune the inline cost analysis based on command 223 /// line options. If -inline-threshold option is not explicitly passed, 224 /// \p Threshold is used as the default threshold. 225 InlineParams getInlineParams(int Threshold); 226 227 /// Generate the parameters to tune the inline cost analysis based on command 228 /// line options. If -inline-threshold option is not explicitly passed, 229 /// the default threshold is computed from \p OptLevel and \p SizeOptLevel. 230 /// An \p OptLevel value above 3 is considered an aggressive optimization mode. 231 /// \p SizeOptLevel of 1 corresponds to the -Os flag and 2 corresponds to 232 /// the -Oz flag. 233 InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel); 234 235 /// Return the cost associated with a callsite, including parameter passing 236 /// and the call/return instruction. 237 int getCallsiteCost(CallBase &Call, const DataLayout &DL); 238 239 /// Get an InlineCost object representing the cost of inlining this 240 /// callsite. 241 /// 242 /// Note that a default threshold is passed into this function. This threshold 243 /// could be modified based on callsite's properties and only costs below this 244 /// new threshold are computed with any accuracy. The new threshold can be 245 /// used to bound the computation necessary to determine whether the cost is 246 /// sufficiently low to warrant inlining. 247 /// 248 /// Also note that calling this function *dynamically* computes the cost of 249 /// inlining the callsite. It is an expensive, heavyweight call. 250 InlineCost 251 getInlineCost(CallBase &Call, const InlineParams &Params, 252 TargetTransformInfo &CalleeTTI, 253 function_ref<AssumptionCache &(Function &)> GetAssumptionCache, 254 function_ref<const TargetLibraryInfo &(Function &)> GetTLI, 255 function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr, 256 ProfileSummaryInfo *PSI = nullptr, 257 OptimizationRemarkEmitter *ORE = nullptr); 258 259 /// Get an InlineCost with the callee explicitly specified. 260 /// This allows you to calculate the cost of inlining a function via a 261 /// pointer. This behaves exactly as the version with no explicit callee 262 /// parameter in all other respects. 263 // 264 InlineCost 265 getInlineCost(CallBase &Call, Function *Callee, const InlineParams &Params, 266 TargetTransformInfo &CalleeTTI, 267 function_ref<AssumptionCache &(Function &)> GetAssumptionCache, 268 function_ref<const TargetLibraryInfo &(Function &)> GetTLI, 269 function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr, 270 ProfileSummaryInfo *PSI = nullptr, 271 OptimizationRemarkEmitter *ORE = nullptr); 272 273 /// Returns InlineResult::success() if the call site should be always inlined 274 /// because of user directives, and the inlining is viable. Returns 275 /// InlineResult::failure() if the inlining may never happen because of user 276 /// directives or incompatibilities detectable without needing callee traversal. 277 /// Otherwise returns None, meaning that inlining should be decided based on 278 /// other criteria (e.g. cost modeling). 279 Optional<InlineResult> getAttributeBasedInliningDecision( 280 CallBase &Call, Function *Callee, TargetTransformInfo &CalleeTTI, 281 function_ref<const TargetLibraryInfo &(Function &)> GetTLI); 282 283 /// Get the cost estimate ignoring thresholds. This is similar to getInlineCost 284 /// when passed InlineParams::ComputeFullInlineCost, or a non-null ORE. It 285 /// uses default InlineParams otherwise. 286 /// Contrary to getInlineCost, which makes a threshold-based final evaluation of 287 /// should/shouldn't inline, captured in InlineResult, getInliningCostEstimate 288 /// returns: 289 /// - None, if the inlining cannot happen (is illegal) 290 /// - an integer, representing the cost. 291 Optional<int> getInliningCostEstimate( 292 CallBase &Call, TargetTransformInfo &CalleeTTI, 293 function_ref<AssumptionCache &(Function &)> GetAssumptionCache, 294 function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr, 295 ProfileSummaryInfo *PSI = nullptr, 296 OptimizationRemarkEmitter *ORE = nullptr); 297 298 /// Get the expanded cost features. The features are returned unconditionally, 299 /// even if inlining is impossible. 300 Optional<InlineCostFeatures> getInliningCostFeatures( 301 CallBase &Call, TargetTransformInfo &CalleeTTI, 302 function_ref<AssumptionCache &(Function &)> GetAssumptionCache, 303 function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr, 304 ProfileSummaryInfo *PSI = nullptr, 305 OptimizationRemarkEmitter *ORE = nullptr); 306 307 /// Minimal filter to detect invalid constructs for inlining. 308 InlineResult isInlineViable(Function &Callee); 309 310 // This pass is used to annotate instructions during the inline process for 311 // debugging and analysis. The main purpose of the pass is to see and test 312 // inliner's decisions when creating new optimizations to InlineCost. 313 struct InlineCostAnnotationPrinterPass 314 : PassInfoMixin<InlineCostAnnotationPrinterPass> { 315 raw_ostream &OS; 316 317 public: InlineCostAnnotationPrinterPassInlineCostAnnotationPrinterPass318 explicit InlineCostAnnotationPrinterPass(raw_ostream &OS) : OS(OS) {} 319 PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); 320 }; 321 } // namespace llvm 322 323 #endif 324