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/CallGraphSCCPass.h" 18 #include <cassert> 19 #include <climits> 20 21 namespace llvm { 22 class CallSite; 23 class DataLayout; 24 class Function; 25 class TargetTransformInfo; 26 27 namespace InlineConstants { 28 // Various magic constants used to adjust heuristics. 29 const int InstrCost = 5; 30 const int IndirectCallThreshold = 100; 31 const int CallPenalty = 25; 32 const int LastCallToStaticBonus = -15000; 33 const int ColdccPenalty = 2000; 34 const int NoreturnPenalty = 10000; 35 /// Do not inline functions which allocate this many bytes on the stack 36 /// when the caller is recursive. 37 const unsigned TotalAllocaSizeRecursiveCaller = 1024; 38 } 39 40 /// \brief Represents the cost of inlining a function. 41 /// 42 /// This supports special values for functions which should "always" or 43 /// "never" be inlined. Otherwise, the cost represents a unitless amount; 44 /// smaller values increase the likelihood of the function being inlined. 45 /// 46 /// Objects of this type also provide the adjusted threshold for inlining 47 /// based on the information available for a particular callsite. They can be 48 /// directly tested to determine if inlining should occur given the cost and 49 /// threshold for this cost metric. 50 class InlineCost { 51 enum SentinelValues { 52 AlwaysInlineCost = INT_MIN, 53 NeverInlineCost = INT_MAX 54 }; 55 56 /// \brief The estimated cost of inlining this callsite. 57 const int Cost; 58 59 /// \brief The adjusted threshold against which this cost was computed. 60 const int Threshold; 61 62 // Trivial constructor, interesting logic in the factory functions below. InlineCost(int Cost,int Threshold)63 InlineCost(int Cost, int Threshold) : Cost(Cost), Threshold(Threshold) {} 64 65 public: get(int Cost,int Threshold)66 static InlineCost get(int Cost, int Threshold) { 67 assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); 68 assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); 69 return InlineCost(Cost, Threshold); 70 } getAlways()71 static InlineCost getAlways() { 72 return InlineCost(AlwaysInlineCost, 0); 73 } getNever()74 static InlineCost getNever() { 75 return InlineCost(NeverInlineCost, 0); 76 } 77 78 /// \brief Test whether the inline cost is low enough for inlining. 79 LLVM_EXPLICIT operator bool() const { 80 return Cost < Threshold; 81 } 82 isAlways()83 bool isAlways() const { return Cost == AlwaysInlineCost; } isNever()84 bool isNever() const { return Cost == NeverInlineCost; } isVariable()85 bool isVariable() const { return !isAlways() && !isNever(); } 86 87 /// \brief Get the inline cost estimate. 88 /// It is an error to call this on an "always" or "never" InlineCost. getCost()89 int getCost() const { 90 assert(isVariable() && "Invalid access of InlineCost"); 91 return Cost; 92 } 93 94 /// \brief Get the cost delta from the threshold for inlining. 95 /// Only valid if the cost is of the variable kind. Returns a negative 96 /// value if the cost is too high to inline. getCostDelta()97 int getCostDelta() const { return Threshold - getCost(); } 98 }; 99 100 /// \brief Cost analyzer used by inliner. 101 class InlineCostAnalysis : public CallGraphSCCPass { 102 const DataLayout *TD; 103 const TargetTransformInfo *TTI; 104 105 public: 106 static char ID; 107 108 InlineCostAnalysis(); 109 ~InlineCostAnalysis(); 110 111 // Pass interface implementation. 112 void getAnalysisUsage(AnalysisUsage &AU) const; 113 bool runOnSCC(CallGraphSCC &SCC); 114 115 /// \brief Get an InlineCost object representing the cost of inlining this 116 /// callsite. 117 /// 118 /// Note that threshold is passed into this function. Only costs below the 119 /// threshold are computed with any accuracy. The threshold can be used to 120 /// bound the computation necessary to determine whether the cost is 121 /// sufficiently low to warrant inlining. 122 /// 123 /// Also note that calling this function *dynamically* computes the cost of 124 /// inlining the callsite. It is an expensive, heavyweight call. 125 InlineCost getInlineCost(CallSite CS, int Threshold); 126 127 /// \brief Get an InlineCost with the callee explicitly specified. 128 /// This allows you to calculate the cost of inlining a function via a 129 /// pointer. This behaves exactly as the version with no explicit callee 130 /// parameter in all other respects. 131 // 132 // Note: This is used by out-of-tree passes, please do not remove without 133 // adding a replacement API. 134 InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold); 135 136 /// \brief Minimal filter to detect invalid constructs for inlining. 137 bool isInlineViable(Function &Callee); 138 }; 139 140 } 141 142 #endif 143