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 const int NoreturnPenalty = 10000; 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 } 54 55 /// \brief Represents the cost of inlining a function. 56 /// 57 /// This supports special values for functions which should "always" or 58 /// "never" be inlined. Otherwise, the cost represents a unitless amount; 59 /// smaller values increase the likelihood of the function being inlined. 60 /// 61 /// Objects of this type also provide the adjusted threshold for inlining 62 /// based on the information available for a particular callsite. They can be 63 /// directly tested to determine if inlining should occur given the cost and 64 /// threshold for this cost metric. 65 class InlineCost { 66 enum SentinelValues { 67 AlwaysInlineCost = INT_MIN, 68 NeverInlineCost = INT_MAX 69 }; 70 71 /// \brief The estimated cost of inlining this callsite. 72 const int Cost; 73 74 /// \brief The adjusted threshold against which this cost was computed. 75 const int Threshold; 76 77 // Trivial constructor, interesting logic in the factory functions below. 78 InlineCost(int Cost, int Threshold) : Cost(Cost), Threshold(Threshold) {} 79 80 public: 81 static InlineCost get(int Cost, int Threshold) { 82 assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); 83 assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); 84 return InlineCost(Cost, Threshold); 85 } 86 static InlineCost getAlways() { 87 return InlineCost(AlwaysInlineCost, 0); 88 } 89 static InlineCost getNever() { 90 return InlineCost(NeverInlineCost, 0); 91 } 92 93 /// \brief Test whether the inline cost is low enough for inlining. 94 explicit operator bool() const { 95 return Cost < Threshold; 96 } 97 98 bool isAlways() const { return Cost == AlwaysInlineCost; } 99 bool isNever() const { return Cost == NeverInlineCost; } 100 bool isVariable() const { return !isAlways() && !isNever(); } 101 102 /// \brief Get the inline cost estimate. 103 /// It is an error to call this on an "always" or "never" InlineCost. 104 int getCost() const { 105 assert(isVariable() && "Invalid access of InlineCost"); 106 return Cost; 107 } 108 109 /// \brief Get the threshold against which the cost was computed 110 int getThreshold() const { 111 assert(isVariable() && "Invalid access of InlineCost"); 112 return Threshold; 113 } 114 115 /// \brief Get the cost delta from the threshold for inlining. 116 /// Only valid if the cost is of the variable kind. Returns a negative 117 /// value if the cost is too high to inline. 118 int getCostDelta() const { return Threshold - getCost(); } 119 }; 120 121 /// Thresholds to tune inline cost analysis. The inline cost analysis decides 122 /// the condition to apply a threshold and applies it. Otherwise, 123 /// DefaultThreshold is used. If a threshold is Optional, it is applied only 124 /// when it has a valid value. Typically, users of inline cost analysis 125 /// obtain an InlineParams object through one of the \c getInlineParams methods 126 /// and pass it to \c getInlineCost. Some specialized versions of inliner 127 /// (such as the pre-inliner) might have custom logic to compute \c InlineParams 128 /// object. 129 130 struct InlineParams { 131 /// The default threshold to start with for a callee. 132 int DefaultThreshold; 133 134 /// Threshold to use for callees with inline hint. 135 Optional<int> HintThreshold; 136 137 /// Threshold to use for cold callees. 138 Optional<int> ColdThreshold; 139 140 /// Threshold to use when the caller is optimized for size. 141 Optional<int> OptSizeThreshold; 142 143 /// Threshold to use when the caller is optimized for minsize. 144 Optional<int> OptMinSizeThreshold; 145 146 /// Threshold to use when the callsite is considered hot. 147 Optional<int> HotCallSiteThreshold; 148 149 /// Threshold to use when the callsite is considered hot relative to function 150 /// entry. 151 Optional<int> LocallyHotCallSiteThreshold; 152 153 /// Threshold to use when the callsite is considered cold. 154 Optional<int> ColdCallSiteThreshold; 155 156 /// Compute inline cost even when the cost has exceeded the threshold. 157 Optional<bool> ComputeFullInlineCost; 158 }; 159 160 /// Generate the parameters to tune the inline cost analysis based only on the 161 /// commandline options. 162 InlineParams getInlineParams(); 163 164 /// Generate the parameters to tune the inline cost analysis based on command 165 /// line options. If -inline-threshold option is not explicitly passed, 166 /// \p Threshold is used as the default threshold. 167 InlineParams getInlineParams(int Threshold); 168 169 /// Generate the parameters to tune the inline cost analysis based on command 170 /// line options. If -inline-threshold option is not explicitly passed, 171 /// the default threshold is computed from \p OptLevel and \p SizeOptLevel. 172 /// An \p OptLevel value above 3 is considered an aggressive optimization mode. 173 /// \p SizeOptLevel of 1 corresponds to the the -Os flag and 2 corresponds to 174 /// the -Oz flag. 175 InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel); 176 177 /// Return the cost associated with a callsite, including parameter passing 178 /// and the call/return instruction. 179 int getCallsiteCost(CallSite CS, const DataLayout &DL); 180 181 /// \brief Get an InlineCost object representing the cost of inlining this 182 /// callsite. 183 /// 184 /// Note that a default threshold is passed into this function. This threshold 185 /// could be modified based on callsite's properties and only costs below this 186 /// new threshold are computed with any accuracy. The new threshold can be 187 /// used to bound the computation necessary to determine whether the cost is 188 /// sufficiently low to warrant inlining. 189 /// 190 /// Also note that calling this function *dynamically* computes the cost of 191 /// inlining the callsite. It is an expensive, heavyweight call. 192 InlineCost getInlineCost( 193 CallSite CS, const InlineParams &Params, TargetTransformInfo &CalleeTTI, 194 std::function<AssumptionCache &(Function &)> &GetAssumptionCache, 195 Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI, 196 ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE = nullptr); 197 198 /// \brief Get an InlineCost with the callee explicitly specified. 199 /// This allows you to calculate the cost of inlining a function via a 200 /// pointer. This behaves exactly as the version with no explicit callee 201 /// parameter in all other respects. 202 // 203 InlineCost 204 getInlineCost(CallSite CS, Function *Callee, const InlineParams &Params, 205 TargetTransformInfo &CalleeTTI, 206 std::function<AssumptionCache &(Function &)> &GetAssumptionCache, 207 Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI, 208 ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE); 209 210 /// \brief Minimal filter to detect invalid constructs for inlining. 211 bool isInlineViable(Function &Callee); 212 } 213 214 #endif 215