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