1 //===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements heuristics for inlining decisions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ANALYSIS_INLINECOST_H 15 #define LLVM_ANALYSIS_INLINECOST_H 16 17 #include "llvm/Analysis/AssumptionCache.h" 18 #include "llvm/Analysis/CallGraphSCCPass.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 CallSite; 27 class DataLayout; 28 class Function; 29 class ProfileSummaryInfo; 30 class TargetTransformInfo; 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 } 53 54 /// Represents the cost of inlining a function. 55 /// 56 /// This supports special values for functions which should "always" or 57 /// "never" be inlined. Otherwise, the cost represents a unitless amount; 58 /// smaller values increase the likelihood of the function being inlined. 59 /// 60 /// Objects of this type also provide the adjusted threshold for inlining 61 /// based on the information available for a particular callsite. They can be 62 /// directly tested to determine if inlining should occur given the cost and 63 /// threshold for this cost metric. 64 class InlineCost { 65 enum SentinelValues { 66 AlwaysInlineCost = INT_MIN, 67 NeverInlineCost = INT_MAX 68 }; 69 70 /// The estimated cost of inlining this callsite. 71 const int Cost; 72 73 /// The adjusted threshold against which this cost was computed. 74 const int Threshold; 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 { 101 return Cost < Threshold; 102 } 103 isAlways()104 bool isAlways() const { return Cost == AlwaysInlineCost; } isNever()105 bool isNever() const { return Cost == NeverInlineCost; } isVariable()106 bool isVariable() const { return !isAlways() && !isNever(); } 107 108 /// Get the inline cost estimate. 109 /// It is an error to call this on an "always" or "never" InlineCost. getCost()110 int getCost() const { 111 assert(isVariable() && "Invalid access of InlineCost"); 112 return Cost; 113 } 114 115 /// Get the threshold against which the cost was computed getThreshold()116 int getThreshold() const { 117 assert(isVariable() && "Invalid access of InlineCost"); 118 return Threshold; 119 } 120 121 /// Get the reason of Always or Never. getReason()122 const char *getReason() const { 123 assert((Reason || isVariable()) && 124 "InlineCost reason must be set for Always or Never"); 125 return Reason; 126 } 127 128 /// Get the cost delta from the threshold for inlining. 129 /// Only valid if the cost is of the variable kind. Returns a negative 130 /// value if the cost is too high to inline. getCostDelta()131 int getCostDelta() const { return Threshold - getCost(); } 132 }; 133 134 /// InlineResult is basically true or false. For false results the message 135 /// describes a reason why it is decided not to inline. 136 struct InlineResult { 137 const char *message = nullptr; 138 InlineResult(bool result, const char *message = nullptr) 139 : message(result ? nullptr : (message ? message : "cost > threshold")) {} messageInlineResult140 InlineResult(const char *message = nullptr) : message(message) {} 141 operator bool() const { return !message; } 142 operator const char *() const { return message; } 143 }; 144 145 /// Thresholds to tune inline cost analysis. The inline cost analysis decides 146 /// the condition to apply a threshold and applies it. Otherwise, 147 /// DefaultThreshold is used. If a threshold is Optional, it is applied only 148 /// when it has a valid value. Typically, users of inline cost analysis 149 /// obtain an InlineParams object through one of the \c getInlineParams methods 150 /// and pass it to \c getInlineCost. Some specialized versions of inliner 151 /// (such as the pre-inliner) might have custom logic to compute \c InlineParams 152 /// object. 153 154 struct InlineParams { 155 /// The default threshold to start with for a callee. 156 int DefaultThreshold; 157 158 /// Threshold to use for callees with inline hint. 159 Optional<int> HintThreshold; 160 161 /// Threshold to use for cold callees. 162 Optional<int> ColdThreshold; 163 164 /// Threshold to use when the caller is optimized for size. 165 Optional<int> OptSizeThreshold; 166 167 /// Threshold to use when the caller is optimized for minsize. 168 Optional<int> OptMinSizeThreshold; 169 170 /// Threshold to use when the callsite is considered hot. 171 Optional<int> HotCallSiteThreshold; 172 173 /// Threshold to use when the callsite is considered hot relative to function 174 /// entry. 175 Optional<int> LocallyHotCallSiteThreshold; 176 177 /// Threshold to use when the callsite is considered cold. 178 Optional<int> ColdCallSiteThreshold; 179 180 /// Compute inline cost even when the cost has exceeded the threshold. 181 Optional<bool> ComputeFullInlineCost; 182 }; 183 184 /// Generate the parameters to tune the inline cost analysis based only on the 185 /// commandline options. 186 InlineParams getInlineParams(); 187 188 /// Generate the parameters to tune the inline cost analysis based on command 189 /// line options. If -inline-threshold option is not explicitly passed, 190 /// \p Threshold is used as the default threshold. 191 InlineParams getInlineParams(int Threshold); 192 193 /// Generate the parameters to tune the inline cost analysis based on command 194 /// line options. If -inline-threshold option is not explicitly passed, 195 /// the default threshold is computed from \p OptLevel and \p SizeOptLevel. 196 /// An \p OptLevel value above 3 is considered an aggressive optimization mode. 197 /// \p SizeOptLevel of 1 corresponds to the -Os flag and 2 corresponds to 198 /// the -Oz flag. 199 InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel); 200 201 /// Return the cost associated with a callsite, including parameter passing 202 /// and the call/return instruction. 203 int getCallsiteCost(CallSite CS, const DataLayout &DL); 204 205 /// Get an InlineCost object representing the cost of inlining this 206 /// callsite. 207 /// 208 /// Note that a default threshold is passed into this function. This threshold 209 /// could be modified based on callsite's properties and only costs below this 210 /// new threshold are computed with any accuracy. The new threshold can be 211 /// used to bound the computation necessary to determine whether the cost is 212 /// sufficiently low to warrant inlining. 213 /// 214 /// Also note that calling this function *dynamically* computes the cost of 215 /// inlining the callsite. It is an expensive, heavyweight call. 216 InlineCost getInlineCost( 217 CallSite CS, const InlineParams &Params, TargetTransformInfo &CalleeTTI, 218 std::function<AssumptionCache &(Function &)> &GetAssumptionCache, 219 Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI, 220 ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE = nullptr); 221 222 /// Get an InlineCost with the callee explicitly specified. 223 /// This allows you to calculate the cost of inlining a function via a 224 /// pointer. This behaves exactly as the version with no explicit callee 225 /// parameter in all other respects. 226 // 227 InlineCost 228 getInlineCost(CallSite CS, Function *Callee, const InlineParams &Params, 229 TargetTransformInfo &CalleeTTI, 230 std::function<AssumptionCache &(Function &)> &GetAssumptionCache, 231 Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI, 232 ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE); 233 234 /// Minimal filter to detect invalid constructs for inlining. 235 bool isInlineViable(Function &Callee); 236 } 237 238 #endif 239