contrib/llvm/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/Analysis/AssumptionCache.h"
  18 #include "llvm/Analysis/CallGraphSCCPass.h"
  19 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  20 #include <cassert>
  21 #include <climits>
  22
  23 namespace llvm {
  24 class AssumptionCacheTracker;
  25 class BlockFrequencyInfo;
  26 class CallSite;
  27 class DataLayout;
  28 class Function;
  29 class ProfileSummaryInfo;
  30 class TargetTransformInfo;
  31
  32 namespace InlineConstants {
  33 // Various thresholds used by inline cost analysis.
  34 /// Use when optsize (-Os) is specified.
  35 const int OptSizeThreshold = 50;
  36
  37 /// Use when minsize (-Oz) is specified.
  38 const int OptMinSizeThreshold = 5;
  39
  40 /// Use when -O3 is specified.
  41 const int OptAggressiveThreshold = 250;
  42
  43 // Various magic constants used to adjust heuristics.
  44 const int InstrCost = 5;
  45 const int IndirectCallThreshold = 100;
  46 const int CallPenalty = 25;
  47 const int LastCallToStaticBonus = 15000;
  48 const int ColdccPenalty = 2000;
  49 /// Do not inline functions which allocate this many bytes on the stack
  50 /// when the caller is recursive.
  51 const unsigned TotalAllocaSizeRecursiveCaller = 1024;
  52 }
  53
  54 /// Represents the cost of inlining a function.
  55 ///
  56 /// This supports special values for functions which should "always" or
  57 /// "never" be inlined. Otherwise, the cost represents a unitless amount;
  58 /// smaller values increase the likelihood of the function being inlined.
  59 ///
  60 /// Objects of this type also provide the adjusted threshold for inlining
  61 /// based on the information available for a particular callsite. They can be
  62 /// directly tested to determine if inlining should occur given the cost and
  63 /// threshold for this cost metric.
  64 class InlineCost {
  65   enum SentinelValues {
  66     AlwaysInlineCost = INT_MIN,
  67     NeverInlineCost = INT_MAX
  68   };
  69
  70   /// The estimated cost of inlining this callsite.
  71   const int Cost;
  72
  73   /// The adjusted threshold against which this cost was computed.
  74   const int Threshold;
  75
  76   /// Must be set for Always and Never instances.
  77   const char *Reason = nullptr;
  78
  79   // Trivial constructor, interesting logic in the factory functions below.
  80   InlineCost(int Cost, int Threshold, const char *Reason = nullptr)
  81       : Cost(Cost), Threshold(Threshold), Reason(Reason) {
  82     assert((isVariable() || Reason) &&
  83            "Reason must be provided for Never or Always");
  84   }
  85
  86 public:
  87   static InlineCost get(int Cost, int Threshold) {
  88     assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value");
  89     assert(Cost < NeverInlineCost && "Cost crosses sentinel value");
  90     return InlineCost(Cost, Threshold);
  91   }
  92   static InlineCost getAlways(const char *Reason) {
  93     return InlineCost(AlwaysInlineCost, 0, Reason);
  94   }
  95   static InlineCost getNever(const char *Reason) {
  96     return InlineCost(NeverInlineCost, 0, Reason);
  97   }
  98
  99   /// Test whether the inline cost is low enough for inlining.
 100   explicit operator bool() const {
 101     return Cost < Threshold;
 102   }
 103
 104   bool isAlways() const { return Cost == AlwaysInlineCost; }
 105   bool isNever() const { return Cost == NeverInlineCost; }
 106   bool isVariable() const { return !isAlways() && !isNever(); }
 107
 108   /// Get the inline cost estimate.
 109   /// It is an error to call this on an "always" or "never" InlineCost.
 110   int getCost() const {
 111     assert(isVariable() && "Invalid access of InlineCost");
 112     return Cost;
 113   }
 114
 115   /// Get the threshold against which the cost was computed
 116   int getThreshold() const {
 117     assert(isVariable() && "Invalid access of InlineCost");
 118     return Threshold;
 119   }
 120
 121   /// Get the reason of Always or Never.
 122   const char *getReason() const {
 123     assert((Reason || isVariable()) &&
 124            "InlineCost reason must be set for Always or Never");
 125     return Reason;
 126   }
 127
 128   /// Get the cost delta from the threshold for inlining.
 129   /// Only valid if the cost is of the variable kind. Returns a negative
 130   /// value if the cost is too high to inline.
 131   int getCostDelta() const { return Threshold - getCost(); }
 132 };
 133
 134 /// InlineResult is basically true or false. For false results the message
 135 /// describes a reason why it is decided not to inline.
 136 struct InlineResult {
 137   const char *message = nullptr;
 138   InlineResult(bool result, const char *message = nullptr)
 139       : message(result ? nullptr : (message ? message : "cost > threshold")) {}
 140   InlineResult(const char *message = nullptr) : message(message) {}
 141   operator bool() const { return !message; }
 142   operator const char *() const { return message; }
 143 };
 144
 145 /// Thresholds to tune inline cost analysis. The inline cost analysis decides
 146 /// the condition to apply a threshold and applies it. Otherwise,
 147 /// DefaultThreshold is used. If a threshold is Optional, it is applied only
 148 /// when it has a valid value. Typically, users of inline cost analysis
 149 /// obtain an InlineParams object through one of the \c getInlineParams methods
 150 /// and pass it to \c getInlineCost. Some specialized versions of inliner
 151 /// (such as the pre-inliner) might have custom logic to compute \c InlineParams
 152 /// object.
 153
 154 struct InlineParams {
 155   /// The default threshold to start with for a callee.
 156   int DefaultThreshold;
 157
 158   /// Threshold to use for callees with inline hint.
 159   Optional<int> HintThreshold;
 160
 161   /// Threshold to use for cold callees.
 162   Optional<int> ColdThreshold;
 163
 164   /// Threshold to use when the caller is optimized for size.
 165   Optional<int> OptSizeThreshold;
 166
 167   /// Threshold to use when the caller is optimized for minsize.
 168   Optional<int> OptMinSizeThreshold;
 169
 170   /// Threshold to use when the callsite is considered hot.
 171   Optional<int> HotCallSiteThreshold;
 172
 173   /// Threshold to use when the callsite is considered hot relative to function
 174   /// entry.
 175   Optional<int> LocallyHotCallSiteThreshold;
 176
 177   /// Threshold to use when the callsite is considered cold.
 178   Optional<int> ColdCallSiteThreshold;
 179
 180   /// Compute inline cost even when the cost has exceeded the threshold.
 181   Optional<bool> ComputeFullInlineCost;
 182 };
 183
 184 /// Generate the parameters to tune the inline cost analysis based only on the
 185 /// commandline options.
 186 InlineParams getInlineParams();
 187
 188 /// Generate the parameters to tune the inline cost analysis based on command
 189 /// line options. If -inline-threshold option is not explicitly passed,
 190 /// \p Threshold is used as the default threshold.
 191 InlineParams getInlineParams(int Threshold);
 192
 193 /// Generate the parameters to tune the inline cost analysis based on command
 194 /// line options. If -inline-threshold option is not explicitly passed,
 195 /// the default threshold is computed from \p OptLevel and \p SizeOptLevel.
 196 /// An \p OptLevel value above 3 is considered an aggressive optimization mode.
 197 /// \p SizeOptLevel of 1 corresponds to the -Os flag and 2 corresponds to
 198 /// the -Oz flag.
 199 InlineParams getInlineParams(unsigned OptLevel, unsigned SizeOptLevel);
 200
 201 /// Return the cost associated with a callsite, including parameter passing
 202 /// and the call/return instruction.
 203 int getCallsiteCost(CallSite CS, const DataLayout &DL);
 204
 205 /// Get an InlineCost object representing the cost of inlining this
 206 /// callsite.
 207 ///
 208 /// Note that a default threshold is passed into this function. This threshold
 209 /// could be modified based on callsite's properties and only costs below this
 210 /// new threshold are computed with any accuracy. The new threshold can be
 211 /// used to bound the computation necessary to determine whether the cost is
 212 /// sufficiently low to warrant inlining.
 213 ///
 214 /// Also note that calling this function *dynamically* computes the cost of
 215 /// inlining the callsite. It is an expensive, heavyweight call.
 216 InlineCost getInlineCost(
 217     CallSite CS, const InlineParams &Params, TargetTransformInfo &CalleeTTI,
 218     std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
 219     Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
 220     ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE = nullptr);
 221
 222 /// Get an InlineCost with the callee explicitly specified.
 223 /// This allows you to calculate the cost of inlining a function via a
 224 /// pointer. This behaves exactly as the version with no explicit callee
 225 /// parameter in all other respects.
 226 //
 227 InlineCost
 228 getInlineCost(CallSite CS, Function *Callee, const InlineParams &Params,
 229               TargetTransformInfo &CalleeTTI,
 230               std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
 231               Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
 232               ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE);
 233
 234 /// Minimal filter to detect invalid constructs for inlining.
 235 bool isInlineViable(Function &Callee);
 236 }
 237
 238 #endif