include/llvm/Analysis/InlineCost.h

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