LLVM API Documentation
00001 //===- InlineCost.cpp - Cost analysis for inliner ---------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements heuristics for inlining decisions. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_TRANSFORMS_UTILS_INLINECOST_H 00015 #define LLVM_TRANSFORMS_UTILS_INLINECOST_H 00016 00017 #include "llvm/ADT/SmallPtrSet.h" 00018 #include <cassert> 00019 #include <climits> 00020 #include <map> 00021 #include <vector> 00022 00023 namespace llvm { 00024 00025 class Value; 00026 class Function; 00027 class CallSite; 00028 00029 /// InlineCost - Represent the cost of inlining a function. This 00030 /// supports special values for functions which should "always" or 00031 /// "never" be inlined. Otherwise, the cost represents a unitless 00032 /// amount; smaller values increase the likelyhood of the function 00033 /// being inlined. 00034 class InlineCost { 00035 enum Kind { 00036 Value, 00037 Always, 00038 Never 00039 }; 00040 00041 // This is a do-it-yourself implementation of 00042 // int Cost : 30; 00043 // unsigned Type : 2; 00044 // We used to use bitfields, but they were sometimes miscompiled (PR3822). 00045 enum { TYPE_BITS = 2 }; 00046 enum { COST_BITS = unsigned(sizeof(unsigned)) * CHAR_BIT - TYPE_BITS }; 00047 unsigned TypedCost; // int Cost : COST_BITS; unsigned Type : TYPE_BITS; 00048 00049 Kind getType() const { 00050 return Kind(TypedCost >> COST_BITS); 00051 } 00052 00053 int getCost() const { 00054 // Sign-extend the bottom COST_BITS bits. 00055 return (int(TypedCost << TYPE_BITS)) >> TYPE_BITS; 00056 } 00057 00058 InlineCost(int C, int T) { 00059 TypedCost = (unsigned(C << TYPE_BITS) >> TYPE_BITS) | (T << COST_BITS); 00060 assert(getCost() == C && "Cost exceeds InlineCost precision"); 00061 } 00062 public: 00063 static InlineCost get(int Cost) { return InlineCost(Cost, Value); } 00064 static InlineCost getAlways() { return InlineCost(0, Always); } 00065 static InlineCost getNever() { return InlineCost(0, Never); } 00066 00067 bool isVariable() const { return getType() == Value; } 00068 bool isAlways() const { return getType() == Always; } 00069 bool isNever() const { return getType() == Never; } 00070 00071 /// getValue() - Return a "variable" inline cost's amount. It is 00072 /// an error to call this on an "always" or "never" InlineCost. 00073 int getValue() const { 00074 assert(getType() == Value && "Invalid access of InlineCost"); 00075 return getCost(); 00076 } 00077 }; 00078 00079 /// InlineCostAnalyzer - Cost analyzer used by inliner. 00080 class InlineCostAnalyzer { 00081 struct ArgInfo { 00082 public: 00083 unsigned ConstantWeight; 00084 unsigned AllocaWeight; 00085 00086 ArgInfo(unsigned CWeight, unsigned AWeight) 00087 : ConstantWeight(CWeight), AllocaWeight(AWeight) {} 00088 }; 00089 00090 // FunctionInfo - For each function, calculate the size of it in blocks and 00091 // instructions. 00092 struct FunctionInfo { 00093 /// NeverInline - True if this callee should never be inlined into a 00094 /// caller. 00095 bool NeverInline; 00096 00097 /// usesDynamicAlloca - True if this function calls alloca (in the C sense). 00098 bool usesDynamicAlloca; 00099 00100 /// NumInsts, NumBlocks - Keep track of how large each function is, which 00101 /// is used to estimate the code size cost of inlining it. 00102 unsigned NumInsts, NumBlocks; 00103 00104 /// NumVectorInsts - Keep track of how many instructions produce vector 00105 /// values. The inliner is being more aggressive with inlining vector 00106 /// kernels. 00107 unsigned NumVectorInsts; 00108 00109 /// ArgumentWeights - Each formal argument of the function is inspected to 00110 /// see if it is used in any contexts where making it a constant or alloca 00111 /// would reduce the code size. If so, we add some value to the argument 00112 /// entry here. 00113 std::vector<ArgInfo> ArgumentWeights; 00114 00115 FunctionInfo() : NeverInline(false), usesDynamicAlloca(false), NumInsts(0), 00116 NumBlocks(0), NumVectorInsts(0) {} 00117 00118 /// analyzeFunction - Fill in the current structure with information 00119 /// gleaned from the specified function. 00120 void analyzeFunction(Function *F); 00121 00122 /// CountCodeReductionForConstant - Figure out an approximation for how 00123 /// many instructions will be constant folded if the specified value is 00124 /// constant. 00125 unsigned CountCodeReductionForConstant(Value *V); 00126 00127 /// CountCodeReductionForAlloca - Figure out an approximation of how much 00128 /// smaller the function will be if it is inlined into a context where an 00129 /// argument becomes an alloca. 00130 /// 00131 unsigned CountCodeReductionForAlloca(Value *V); 00132 }; 00133 00134 std::map<const Function *, FunctionInfo> CachedFunctionInfo; 00135 00136 public: 00137 00138 /// getInlineCost - The heuristic used to determine if we should inline the 00139 /// function call or not. 00140 /// 00141 InlineCost getInlineCost(CallSite CS, 00142 SmallPtrSet<const Function *, 16> &NeverInline); 00143 00144 /// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a 00145 /// higher threshold to determine if the function call should be inlined. 00146 float getInlineFudgeFactor(CallSite CS); 00147 00148 /// resetCachedFunctionInfo - erase any cached cost info for this function. 00149 void resetCachedCostInfo(Function* Caller) { 00150 CachedFunctionInfo[Caller].NumBlocks = 0; 00151 } 00152 }; 00153 } 00154 00155 #endif