178344Sobrien//===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===// 278344Sobrien// 398184Sgordon// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 478344Sobrien// See https://llvm.org/LICENSE.txt for license information. 578344Sobrien// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 678344Sobrien// 7240336Sobrien//===----------------------------------------------------------------------===// 898184Sgordon// 998184Sgordon// This file implements heuristics for inlining decisions. 10180564Sdougb// 1178344Sobrien//===----------------------------------------------------------------------===// 1298184Sgordon 1398184Sgordon#ifndef LLVM_ANALYSIS_INLINECOST_H 1498184Sgordon#define LLVM_ANALYSIS_INLINECOST_H 1578344Sobrien 1678344Sobrien#include "llvm/Analysis/AssumptionCache.h" 1778344Sobrien#include "llvm/Analysis/CallGraphSCCPass.h" 18230099Sdougb#include "llvm/Analysis/OptimizationRemarkEmitter.h" 1978344Sobrien#include <cassert> 20149606Sgshapiro#include <climits> 21127896Sfjoe 22127896Sfjoenamespace llvm { 23151809Syarclass AssumptionCacheTracker; 24151809Syarclass BlockFrequencyInfo; 25151809Syarclass CallBase; 2678344Sobrienclass DataLayout; 27256982Sjmgclass Function; 28256982Sjmgclass ProfileSummaryInfo; 29124622Smtmclass TargetTransformInfo; 30124622Smtmclass TargetLibraryInfo; 31124622Smtm 32124622Smtmnamespace InlineConstants { 33124622Smtm// Various thresholds used by inline cost analysis. 34124622Smtm/// Use when optsize (-Os) is specified. 35102864Sgordonconst int OptSizeThreshold = 50; 36102864Sgordon 37102864Sgordon/// Use when minsize (-Oz) is specified. 38133150Sgshapiroconst int OptMinSizeThreshold = 5; 39133150Sgshapiro 40133150Sgshapiro/// Use when -O3 is specified. 41133150Sgshapiroconst int OptAggressiveThreshold = 250; 42133150Sgshapiro 43133150Sgshapiro// Various magic constants used to adjust heuristics. 44133150Sgshapiroconst int InstrCost = 5; 45133150Sgshapiroconst int IndirectCallThreshold = 100; 46133150Sgshapiroconst int CallPenalty = 25; 47133150Sgshapiroconst int LastCallToStaticBonus = 15000; 48133150Sgshapiroconst int ColdccPenalty = 2000; 49256982Sjmg/// Do not inline functions which allocate this many bytes on the stack 50256982Sjmg/// when the caller is recursive. 51256982Sjmgconst unsigned TotalAllocaSizeRecursiveCaller = 1024; 52256982Sjmg/// Do not inline dynamic allocas that have been constant propagated to be 53256982Sjmg/// static allocas above this amount in bytes. 54256982Sjmgconst uint64_t MaxSimplifiedDynamicAllocaToInline = 65536; 55256982Sjmg} // namespace InlineConstants 56256982Sjmg 57256982Sjmg/// Represents the cost of inlining a function. 58256982Sjmg/// 59256982Sjmg/// This supports special values for functions which should "always" or 60256982Sjmg/// "never" be inlined. Otherwise, the cost represents a unitless amount; 61256982Sjmg/// smaller values increase the likelihood of the function being inlined. 62256982Sjmg/// 63256982Sjmg/// Objects of this type also provide the adjusted threshold for inlining 64256982Sjmg/// based on the information available for a particular callsite. They can be 65256982Sjmg/// directly tested to determine if inlining should occur given the cost and 66256982Sjmg/// threshold for this cost metric. 67256982Sjmgclass InlineCost { 68256982Sjmg enum SentinelValues { AlwaysInlineCost = INT_MIN, NeverInlineCost = INT_MAX }; 69256982Sjmg 70256982Sjmg /// The estimated cost of inlining this callsite. 71256982Sjmg int Cost = 0; 72256982Sjmg 73256982Sjmg /// The adjusted threshold against which this cost was computed. 74256982Sjmg int Threshold = 0; 75256982Sjmg 76256982Sjmg /// Must be set for Always and Never instances. 77256982Sjmg const char *Reason = nullptr; 78256982Sjmg 79256982Sjmg // Trivial constructor, interesting logic in the factory functions below. 80256982Sjmg InlineCost(int Cost, int Threshold, const char *Reason = nullptr) 81256982Sjmg : Cost(Cost), Threshold(Threshold), Reason(Reason) { 82256982Sjmg assert((isVariable() || Reason) && 83256982Sjmg "Reason must be provided for Never or Always"); 84256982Sjmg } 85256982Sjmg 86256982Sjmgpublic: 87256982Sjmg static InlineCost get(int Cost, int Threshold) { 88256982Sjmg assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); 89256982Sjmg assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); 90256982Sjmg return InlineCost(Cost, Threshold); 91256982Sjmg } 92256982Sjmg static InlineCost getAlways(const char *Reason) { 93256982Sjmg return InlineCost(AlwaysInlineCost, 0, Reason); 94256982Sjmg } 95256982Sjmg static InlineCost getNever(const char *Reason) { 96256982Sjmg return InlineCost(NeverInlineCost, 0, Reason); 97256982Sjmg } 98256982Sjmg 99256982Sjmg /// Test whether the inline cost is low enough for inlining. 100256982Sjmg explicit operator bool() const { return Cost < Threshold; } 101256982Sjmg 102256982Sjmg bool isAlways() const { return Cost == AlwaysInlineCost; } 103256982Sjmg bool isNever() const { return Cost == NeverInlineCost; } 104256982Sjmg bool isVariable() const { return !isAlways() && !isNever(); } 105256982Sjmg 106256982Sjmg /// Get the inline cost estimate. 107256982Sjmg /// It is an error to call this on an "always" or "never" InlineCost. 108256982Sjmg int getCost() const { 109256982Sjmg assert(isVariable() && "Invalid access of InlineCost"); 110256982Sjmg return Cost; 111256982Sjmg } 112256982Sjmg 113256982Sjmg /// Get the threshold against which the cost was computed 114256982Sjmg int getThreshold() const { 115256982Sjmg assert(isVariable() && "Invalid access of InlineCost"); 116256982Sjmg return Threshold; 117256982Sjmg } 118256982Sjmg 119256982Sjmg /// Get the reason of Always or Never. 120256982Sjmg const char *getReason() const { 121256982Sjmg assert((Reason || isVariable()) && 122256982Sjmg "InlineCost reason must be set for Always or Never"); 123256982Sjmg return Reason; 124256982Sjmg } 125256982Sjmg 126256982Sjmg /// Get the cost delta from the threshold for inlining. 127256982Sjmg /// Only valid if the cost is of the variable kind. Returns a negative 128256982Sjmg /// value if the cost is too high to inline. 129256982Sjmg int getCostDelta() const { return Threshold - getCost(); } 130256982Sjmg}; 131256982Sjmg 132256982Sjmg/// InlineResult is basically true or false. For false results the message 133256982Sjmg/// describes a reason. 134256982Sjmgclass InlineResult { 135256982Sjmg const char *Message = nullptr; 136256982Sjmg InlineResult(const char *Message = nullptr) : Message(Message) {} 137256982Sjmg 138256982Sjmgpublic: 139256982Sjmg static InlineResult success() { return {}; } 140256982Sjmg static InlineResult failure(const char *Reason) { 141256982Sjmg return InlineResult(Reason); 142256982Sjmg } 143256982Sjmg bool isSuccess() const { return Message == nullptr; } 144256982Sjmg const char *getFailureReason() const { 145256982Sjmg assert(!isSuccess() && 146256982Sjmg "getFailureReason should only be called in failure cases"); 147256982Sjmg return Message; 148256982Sjmg } 149256982Sjmg}; 150256982Sjmg 151256982Sjmg/// Thresholds to tune inline cost analysis. The inline cost analysis decides 152256982Sjmg/// the condition to apply a threshold and applies it. Otherwise, 153256982Sjmg/// DefaultThreshold is used. If a threshold is Optional, it is applied only 154256982Sjmg/// when it has a valid value. Typically, users of inline cost analysis 155256982Sjmg/// obtain an InlineParams object through one of the \c getInlineParams methods 156256982Sjmg/// and pass it to \c getInlineCost. Some specialized versions of inliner 157256982Sjmg/// (such as the pre-inliner) might have custom logic to compute \c InlineParams 158256982Sjmg/// object. 159256982Sjmg 160256982Sjmgstruct InlineParams { 16178344Sobrien /// The default threshold to start with for a callee. 16278344Sobrien int DefaultThreshold = -1; 16378344Sobrien 16478344Sobrien /// Threshold to use for callees with inline hint. 16578344Sobrien Optional<int> HintThreshold; 16698184Sgordon 16778344Sobrien /// Threshold to use for cold callees. 16878344Sobrien Optional<int> ColdThreshold; 16978344Sobrien 17078344Sobrien /// Threshold to use when the caller is optimized for size. 17178344Sobrien Optional<int> OptSizeThreshold; 17278344Sobrien 17378344Sobrien /// Threshold to use when the caller is optimized for minsize. 17478344Sobrien Optional<int> OptMinSizeThreshold; 175170618Sgshapiro 176170618Sgshapiro /// Threshold to use when the callsite is considered hot. 177170618Sgshapiro Optional<int> HotCallSiteThreshold; 178170618Sgshapiro 179170618Sgshapiro /// Threshold to use when the callsite is considered hot relative to function 180170618Sgshapiro /// entry. 181170618Sgshapiro Optional<int> LocallyHotCallSiteThreshold; 182170618Sgshapiro 18378344Sobrien /// Threshold to use when the callsite is considered cold. 184170618Sgshapiro Optional<int> ColdCallSiteThreshold; 185170618Sgshapiro 18678344Sobrien /// Compute inline cost even when the cost has exceeded the threshold. 18778344Sobrien Optional<bool> ComputeFullInlineCost; 188256982Sjmg 189256982Sjmg /// Indicate whether we should allow inline deferral. 190256982Sjmg Optional<bool> EnableDeferral = true; 191256982Sjmg}; 192256982Sjmg 193256982Sjmg/// Generate the parameters to tune the inline cost analysis based only on the 194256982Sjmg/// commandline options. 195256982SjmgInlineParams getInlineParams(); 196256982Sjmg 197256982Sjmg/// Generate the parameters to tune the inline cost analysis based on command 198256982Sjmg/// line options. If -inline-threshold option is not explicitly passed, 19978344Sobrien/// \p Threshold is used as the default threshold. 20078344SobrienInlineParams getInlineParams(int Threshold); 20178344Sobrien 20298184Sgordon/// Generate the parameters to tune the inline cost analysis based on command 203124622Smtm/// line options. If -inline-threshold option is not explicitly passed, 204104980Sschweikh/// the default threshold is computed from \p OptLevel and \p SizeOptLevel. 205128366Sfjoe/// An \p OptLevel value above 3 is considered an aggressive optimization mode. 206124622Smtm/// \p SizeOptLevel of 1 corresponds to the -Os flag and 2 corresponds to 207230099Sdougb/// the -Oz flag. 208124622SmtmInlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel); 209124622Smtm 21098184Sgordon/// Return the cost associated with a callsite, including parameter passing 211128366Sfjoe/// and the call/return instruction. 212124622Smtmint getCallsiteCost(CallBase &Call, const DataLayout &DL); 213230099Sdougb 214124622Smtm/// Get an InlineCost object representing the cost of inlining this 215124622Smtm/// callsite. 21698184Sgordon/// 217255654Shrs/// Note that a default threshold is passed into this function. This threshold 218124622Smtm/// could be modified based on callsite's properties and only costs below this 219255654Shrs/// new threshold are computed with any accuracy. The new threshold can be 220124622Smtm/// used to bound the computation necessary to determine whether the cost is 221124622Smtm/// 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