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 <cassert> 18 #include <climits> 19 #include <vector> 20 #include "llvm/ADT/DenseMap.h" 21 #include "llvm/ADT/ValueMap.h" 22 #include "llvm/Analysis/CodeMetrics.h" 23 24 namespace llvm { 25 26 class Value; 27 class Function; 28 class BasicBlock; 29 class CallSite; 30 template<class PtrType, unsigned SmallSize> 31 class SmallPtrSet; 32 class TargetData; 33 34 namespace InlineConstants { 35 // Various magic constants used to adjust heuristics. 36 const int InstrCost = 5; 37 const int IndirectCallBonus = -100; 38 const int CallPenalty = 25; 39 const int LastCallToStaticBonus = -15000; 40 const int ColdccPenalty = 2000; 41 const int NoreturnPenalty = 10000; 42 } 43 44 /// InlineCost - Represent the cost of inlining a function. This 45 /// supports special values for functions which should "always" or 46 /// "never" be inlined. Otherwise, the cost represents a unitless 47 /// amount; smaller values increase the likelihood of the function 48 /// being inlined. 49 class InlineCost { 50 enum Kind { 51 Value, 52 Always, 53 Never 54 }; 55 56 // This is a do-it-yourself implementation of 57 // int Cost : 30; 58 // unsigned Type : 2; 59 // We used to use bitfields, but they were sometimes miscompiled (PR3822). 60 enum { TYPE_BITS = 2 }; 61 enum { COST_BITS = unsigned(sizeof(unsigned)) * CHAR_BIT - TYPE_BITS }; 62 unsigned TypedCost; // int Cost : COST_BITS; unsigned Type : TYPE_BITS; 63 64 Kind getType() const { 65 return Kind(TypedCost >> COST_BITS); 66 } 67 68 int getCost() const { 69 // Sign-extend the bottom COST_BITS bits. 70 return (int(TypedCost << TYPE_BITS)) >> TYPE_BITS; 71 } 72 73 InlineCost(int C, int T) { 74 TypedCost = (unsigned(C << TYPE_BITS) >> TYPE_BITS) | (T << COST_BITS); 75 assert(getCost() == C && "Cost exceeds InlineCost precision"); 76 } 77 public: 78 static InlineCost get(int Cost) { return InlineCost(Cost, Value); } 79 static InlineCost getAlways() { return InlineCost(0, Always); } 80 static InlineCost getNever() { return InlineCost(0, Never); } 81 82 bool isVariable() const { return getType() == Value; } 83 bool isAlways() const { return getType() == Always; } 84 bool isNever() const { return getType() == Never; } 85 86 /// getValue() - Return a "variable" inline cost's amount. It is 87 /// an error to call this on an "always" or "never" InlineCost. 88 int getValue() const { 89 assert(getType() == Value && "Invalid access of InlineCost"); 90 return getCost(); 91 } 92 }; 93 94 /// InlineCostAnalyzer - Cost analyzer used by inliner. 95 class InlineCostAnalyzer { 96 struct ArgInfo { 97 public: 98 unsigned ConstantWeight; 99 unsigned AllocaWeight; 100 101 ArgInfo(unsigned CWeight, unsigned AWeight) 102 : ConstantWeight(CWeight), AllocaWeight(AWeight) 103 {} 104 }; 105 106 struct FunctionInfo { 107 CodeMetrics Metrics; 108 109 /// ArgumentWeights - Each formal argument of the function is inspected to 110 /// see if it is used in any contexts where making it a constant or alloca 111 /// would reduce the code size. If so, we add some value to the argument 112 /// entry here. 113 std::vector<ArgInfo> ArgumentWeights; 114 115 /// analyzeFunction - Add information about the specified function 116 /// to the current structure. 117 void analyzeFunction(Function *F, const TargetData *TD); 118 119 /// NeverInline - Returns true if the function should never be 120 /// inlined into any caller. 121 bool NeverInline(); 122 }; 123 124 // The Function* for a function can be changed (by ArgumentPromotion); 125 // the ValueMap will update itself when this happens. 126 ValueMap<const Function *, FunctionInfo> CachedFunctionInfo; 127 128 // TargetData if available, or null. 129 const TargetData *TD; 130 131 int CountBonusForConstant(Value *V, Constant *C = NULL); 132 int ConstantFunctionBonus(CallSite CS, Constant *C); 133 int getInlineSize(CallSite CS, Function *Callee); 134 int getInlineBonuses(CallSite CS, Function *Callee); 135 public: 136 InlineCostAnalyzer(): TD(0) {} 137 138 void setTargetData(const TargetData *TData) { TD = TData; } 139 140 /// getInlineCost - The heuristic used to determine if we should inline the 141 /// function call or not. 142 /// 143 InlineCost getInlineCost(CallSite CS, 144 SmallPtrSet<const Function *, 16> &NeverInline); 145 /// getCalledFunction - The heuristic used to determine if we should inline 146 /// the function call or not. The callee is explicitly specified, to allow 147 /// you to calculate the cost of inlining a function via a pointer. The 148 /// result assumes that the inlined version will always be used. You should 149 /// weight it yourself in cases where this callee will not always be called. 150 InlineCost getInlineCost(CallSite CS, 151 Function *Callee, 152 SmallPtrSet<const Function *, 16> &NeverInline); 153 154 /// getSpecializationBonus - The heuristic used to determine the per-call 155 /// performance boost for using a specialization of Callee with argument 156 /// SpecializedArgNos replaced by a constant. 157 int getSpecializationBonus(Function *Callee, 158 SmallVectorImpl<unsigned> &SpecializedArgNo); 159 160 /// getSpecializationCost - The heuristic used to determine the code-size 161 /// impact of creating a specialized version of Callee with argument 162 /// SpecializedArgNo replaced by a constant. 163 InlineCost getSpecializationCost(Function *Callee, 164 SmallVectorImpl<unsigned> &SpecializedArgNo); 165 166 /// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a 167 /// higher threshold to determine if the function call should be inlined. 168 float getInlineFudgeFactor(CallSite CS); 169 170 /// resetCachedFunctionInfo - erase any cached cost info for this function. 171 void resetCachedCostInfo(Function* Caller) { 172 CachedFunctionInfo[Caller] = FunctionInfo(); 173 } 174 175 /// growCachedCostInfo - update the cached cost info for Caller after Callee 176 /// has been inlined. If Callee is NULL it means a dead call has been 177 /// eliminated. 178 void growCachedCostInfo(Function* Caller, Function* Callee); 179 180 /// clear - empty the cache of inline costs 181 void clear(); 182 }; 183 184 /// callIsSmall - If a call is likely to lower to a single target instruction, 185 /// or is otherwise deemed small return true. 186 bool callIsSmall(const Function *Callee); 187 } 188 189 #endif 190
