1207618Srdivacky//===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===// 2198090Srdivacky// 3198090Srdivacky// The LLVM Compiler Infrastructure 4198090Srdivacky// 5198090Srdivacky// This file is distributed under the University of Illinois Open Source 6198090Srdivacky// License. See LICENSE.TXT for details. 7198090Srdivacky// 8198090Srdivacky//===----------------------------------------------------------------------===// 9198090Srdivacky// 10198090Srdivacky// This file implements heuristics for inlining decisions. 11198090Srdivacky// 12198090Srdivacky//===----------------------------------------------------------------------===// 13198090Srdivacky 14198090Srdivacky#ifndef LLVM_ANALYSIS_INLINECOST_H 15198090Srdivacky#define LLVM_ANALYSIS_INLINECOST_H 16198090Srdivacky 17249423Sdim#include "llvm/Analysis/CallGraphSCCPass.h" 18198090Srdivacky#include <cassert> 19198090Srdivacky#include <climits> 20198090Srdivacky 21198090Srdivackynamespace llvm { 22249423Sdimclass CallSite; 23249423Sdimclass DataLayout; 24249423Sdimclass Function; 25249423Sdimclass TargetTransformInfo; 26198090Srdivacky 27249423Sdimnamespace InlineConstants { 28249423Sdim // Various magic constants used to adjust heuristics. 29249423Sdim const int InstrCost = 5; 30249423Sdim const int IndirectCallThreshold = 100; 31249423Sdim const int CallPenalty = 25; 32249423Sdim const int LastCallToStaticBonus = -15000; 33249423Sdim const int ColdccPenalty = 2000; 34249423Sdim const int NoreturnPenalty = 10000; 35249423Sdim /// Do not inline functions which allocate this many bytes on the stack 36249423Sdim /// when the caller is recursive. 37249423Sdim const unsigned TotalAllocaSizeRecursiveCaller = 1024; 38249423Sdim} 39198090Srdivacky 40249423Sdim/// \brief Represents the cost of inlining a function. 41249423Sdim/// 42249423Sdim/// This supports special values for functions which should "always" or 43249423Sdim/// "never" be inlined. Otherwise, the cost represents a unitless amount; 44249423Sdim/// smaller values increase the likelihood of the function being inlined. 45249423Sdim/// 46249423Sdim/// Objects of this type also provide the adjusted threshold for inlining 47249423Sdim/// based on the information available for a particular callsite. They can be 48249423Sdim/// directly tested to determine if inlining should occur given the cost and 49249423Sdim/// threshold for this cost metric. 50249423Sdimclass InlineCost { 51249423Sdim enum SentinelValues { 52249423Sdim AlwaysInlineCost = INT_MIN, 53249423Sdim NeverInlineCost = INT_MAX 54249423Sdim }; 55249423Sdim 56249423Sdim /// \brief The estimated cost of inlining this callsite. 57249423Sdim const int Cost; 58249423Sdim 59249423Sdim /// \brief The adjusted threshold against which this cost was computed. 60249423Sdim const int Threshold; 61249423Sdim 62249423Sdim // Trivial constructor, interesting logic in the factory functions below. 63249423Sdim InlineCost(int Cost, int Threshold) : Cost(Cost), Threshold(Threshold) {} 64249423Sdim 65249423Sdimpublic: 66249423Sdim static InlineCost get(int Cost, int Threshold) { 67249423Sdim assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); 68249423Sdim assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); 69249423Sdim return InlineCost(Cost, Threshold); 70198090Srdivacky } 71249423Sdim static InlineCost getAlways() { 72249423Sdim return InlineCost(AlwaysInlineCost, 0); 73249423Sdim } 74249423Sdim static InlineCost getNever() { 75249423Sdim return InlineCost(NeverInlineCost, 0); 76249423Sdim } 77198090Srdivacky 78249423Sdim /// \brief Test whether the inline cost is low enough for inlining. 79263508Sdim LLVM_EXPLICIT operator bool() const { 80249423Sdim return Cost < Threshold; 81249423Sdim } 82198090Srdivacky 83249423Sdim bool isAlways() const { return Cost == AlwaysInlineCost; } 84249423Sdim bool isNever() const { return Cost == NeverInlineCost; } 85249423Sdim bool isVariable() const { return !isAlways() && !isNever(); } 86198090Srdivacky 87249423Sdim /// \brief Get the inline cost estimate. 88249423Sdim /// It is an error to call this on an "always" or "never" InlineCost. 89249423Sdim int getCost() const { 90249423Sdim assert(isVariable() && "Invalid access of InlineCost"); 91249423Sdim return Cost; 92249423Sdim } 93198090Srdivacky 94249423Sdim /// \brief Get the cost delta from the threshold for inlining. 95249423Sdim /// Only valid if the cost is of the variable kind. Returns a negative 96249423Sdim /// value if the cost is too high to inline. 97249423Sdim int getCostDelta() const { return Threshold - getCost(); } 98249423Sdim}; 99234353Sdim 100249423Sdim/// \brief Cost analyzer used by inliner. 101249423Sdimclass InlineCostAnalysis : public CallGraphSCCPass { 102249423Sdim const DataLayout *TD; 103249423Sdim const TargetTransformInfo *TTI; 104198090Srdivacky 105249423Sdimpublic: 106249423Sdim static char ID; 107198090Srdivacky 108249423Sdim InlineCostAnalysis(); 109249423Sdim ~InlineCostAnalysis(); 110198090Srdivacky 111249423Sdim // Pass interface implementation. 112249423Sdim void getAnalysisUsage(AnalysisUsage &AU) const; 113249423Sdim bool runOnSCC(CallGraphSCC &SCC); 114234353Sdim 115249423Sdim /// \brief Get an InlineCost object representing the cost of inlining this 116249423Sdim /// callsite. 117249423Sdim /// 118249423Sdim /// Note that threshold is passed into this function. Only costs below the 119249423Sdim /// threshold are computed with any accuracy. The threshold can be used to 120249423Sdim /// bound the computation necessary to determine whether the cost is 121249423Sdim /// sufficiently low to warrant inlining. 122249423Sdim /// 123249423Sdim /// Also note that calling this function *dynamically* computes the cost of 124249423Sdim /// inlining the callsite. It is an expensive, heavyweight call. 125249423Sdim InlineCost getInlineCost(CallSite CS, int Threshold); 126203954Srdivacky 127249423Sdim /// \brief Get an InlineCost with the callee explicitly specified. 128249423Sdim /// This allows you to calculate the cost of inlining a function via a 129249423Sdim /// pointer. This behaves exactly as the version with no explicit callee 130249423Sdim /// parameter in all other respects. 131249423Sdim // 132249423Sdim // Note: This is used by out-of-tree passes, please do not remove without 133249423Sdim // adding a replacement API. 134249423Sdim InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold); 135226633Sdim 136249423Sdim /// \brief Minimal filter to detect invalid constructs for inlining. 137249423Sdim bool isInlineViable(Function &Callee); 138249423Sdim}; 139198090Srdivacky 140198090Srdivacky} 141198090Srdivacky 142198090Srdivacky#endif 143