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