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 23namespace llvm { 24class AssumptionCacheTracker; 25class BlockFrequencyInfo; 26class CallSite; 27class DataLayout; 28class Function; 29class ProfileSummaryInfo; 30class TargetTransformInfo; 31 32namespace InlineConstants { 33// Various thresholds used by inline cost analysis. 34/// Use when optsize (-Os) is specified. 35const int OptSizeThreshold = 50; 36 37/// Use when minsize (-Oz) is specified. 38const int OptMinSizeThreshold = 5; 39 40/// Use when -O3 is specified. 41const int OptAggressiveThreshold = 250; 42 43// Various magic constants used to adjust heuristics. 44const int InstrCost = 5; 45const int IndirectCallThreshold = 100; 46const int CallPenalty = 25; 47const int LastCallToStaticBonus = 15000; 48const int ColdccPenalty = 2000; 49const int NoreturnPenalty = 10000; 50/// Do not inline functions which allocate this many bytes on the stack 51/// when the caller is recursive. 52const 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. 65class 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 80public: 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 130struct 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. 162InlineParams 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. 167InlineParams 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. 175InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel); 176 177/// Return the cost associated with a callsite, including parameter passing 178/// and the call/return instruction. 179int 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. 192InlineCost 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// 203InlineCost 204getInlineCost(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. 211bool isInlineViable(Function &Callee); 212} 213 214#endif 215