include/llvm/Analysis/InlineCost.h

   1 //===- InlineCost.cpp - 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 <map>
  20 #include <vector>
  21
  22 namespace llvm {
  23
  24   class Value;
  25   class Function;
  26   class BasicBlock;
  27   class CallSite;
  28   template<class PtrType, unsigned SmallSize>
  29   class SmallPtrSet;
  30
  31   namespace InlineConstants {
  32     // Various magic constants used to adjust heuristics.
  33     const int CallPenalty = 5;
  34     const int LastCallToStaticBonus = -15000;
  35     const int ColdccPenalty = 2000;
  36     const int NoreturnPenalty = 10000;
  37   }
  38
  39   /// InlineCost - Represent the cost of inlining a function. This
  40   /// supports special values for functions which should "always" or
  41   /// "never" be inlined. Otherwise, the cost represents a unitless
  42   /// amount; smaller values increase the likelyhood of the function
  43   /// being inlined.
  44   class InlineCost {
  45     enum Kind {
  46       Value,
  47       Always,
  48       Never
  49     };
  50
  51     // This is a do-it-yourself implementation of
  52     //   int Cost : 30;
  53     //   unsigned Type : 2;
  54     // We used to use bitfields, but they were sometimes miscompiled (PR3822).
  55     enum { TYPE_BITS = 2 };
  56     enum { COST_BITS = unsigned(sizeof(unsigned)) * CHAR_BIT - TYPE_BITS };
  57     unsigned TypedCost; // int Cost : COST_BITS; unsigned Type : TYPE_BITS;
  58
  59     Kind getType() const {
  60       return Kind(TypedCost >> COST_BITS);
  61     }
  62
  63     int getCost() const {
  64       // Sign-extend the bottom COST_BITS bits.
  65       return (int(TypedCost << TYPE_BITS)) >> TYPE_BITS;
  66     }
  67
  68     InlineCost(int C, int T) {
  69       TypedCost = (unsigned(C << TYPE_BITS) >> TYPE_BITS) | (T << COST_BITS);
  70       assert(getCost() == C && "Cost exceeds InlineCost precision");
  71     }
  72   public:
  73     static InlineCost get(int Cost) { return InlineCost(Cost, Value); }
  74     static InlineCost getAlways() { return InlineCost(0, Always); }
  75     static InlineCost getNever() { return InlineCost(0, Never); }
  76
  77     bool isVariable() const { return getType() == Value; }
  78     bool isAlways() const { return getType() == Always; }
  79     bool isNever() const { return getType() == Never; }
  80
  81     /// getValue() - Return a "variable" inline cost's amount. It is
  82     /// an error to call this on an "always" or "never" InlineCost.
  83     int getValue() const {
  84       assert(getType() == Value && "Invalid access of InlineCost");
  85       return getCost();
  86     }
  87   };
  88
  89   /// InlineCostAnalyzer - Cost analyzer used by inliner.
  90   class InlineCostAnalyzer {
  91     struct ArgInfo {
  92     public:
  93       unsigned ConstantWeight;
  94       unsigned AllocaWeight;
  95
  96       ArgInfo(unsigned CWeight, unsigned AWeight)
  97         : ConstantWeight(CWeight), AllocaWeight(AWeight) {}
  98     };
  99
 100     // RegionInfo - Calculate size and a few related metrics for a set of
 101     // basic blocks.
 102     struct RegionInfo {
 103       /// NeverInline - True if this callee should never be inlined into a
 104       /// caller.
 105       bool NeverInline;
 106
 107       /// usesDynamicAlloca - True if this function calls alloca (in the C sense).
 108       bool usesDynamicAlloca;
 109
 110       /// NumInsts, NumBlocks - Keep track of how large each function is, which
 111       /// is used to estimate the code size cost of inlining it.
 112       unsigned NumInsts, NumBlocks;
 113
 114       /// NumVectorInsts - Keep track of how many instructions produce vector
 115       /// values.  The inliner is being more aggressive with inlining vector
 116       /// kernels.
 117       unsigned NumVectorInsts;
 118
 119       /// NumRets - Keep track of how many Ret instructions the block contains.
 120       unsigned NumRets;
 121
 122       /// ArgumentWeights - Each formal argument of the function is inspected to
 123       /// see if it is used in any contexts where making it a constant or alloca
 124       /// would reduce the code size.  If so, we add some value to the argument
 125       /// entry here.
 126       std::vector<ArgInfo> ArgumentWeights;
 127
 128       RegionInfo() : NeverInline(false), usesDynamicAlloca(false), NumInsts(0),
 129                      NumBlocks(0), NumVectorInsts(0), NumRets(0) {}
 130
 131       /// analyzeBasicBlock - Add information about the specified basic block
 132       /// to the current structure.
 133       void analyzeBasicBlock(const BasicBlock *BB);
 134
 135       /// analyzeFunction - Add information about the specified function
 136       /// to the current structure.
 137       void analyzeFunction(Function *F);
 138
 139       /// CountCodeReductionForConstant - Figure out an approximation for how
 140       /// many instructions will be constant folded if the specified value is
 141       /// constant.
 142       unsigned CountCodeReductionForConstant(Value *V);
 143
 144       /// CountCodeReductionForAlloca - Figure out an approximation of how much
 145       /// smaller the function will be if it is inlined into a context where an
 146       /// argument becomes an alloca.
 147       ///
 148       unsigned CountCodeReductionForAlloca(Value *V);
 149     };
 150
 151     std::map<const Function *, RegionInfo> CachedFunctionInfo;
 152
 153   public:
 154
 155     /// getInlineCost - The heuristic used to determine if we should inline the
 156     /// function call or not.
 157     ///
 158     InlineCost getInlineCost(CallSite CS,
 159                              SmallPtrSet<const Function *, 16> &NeverInline);
 160
 161     /// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a
 162     /// higher threshold to determine if the function call should be inlined.
 163     float getInlineFudgeFactor(CallSite CS);
 164
 165     /// resetCachedFunctionInfo - erase any cached cost info for this function.
 166     void resetCachedCostInfo(Function* Caller) {
 167       CachedFunctionInfo[Caller].NumBlocks = 0;
 168     }
 169   };
 170 }
 171
 172 #endif