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