InlineCost.h revision 234353
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 17234353Sdim#include "llvm/Function.h" 18234353Sdim#include "llvm/ADT/DenseMap.h" 19234353Sdim#include "llvm/ADT/SmallPtrSet.h" 20234353Sdim#include "llvm/ADT/ValueMap.h" 21234353Sdim#include "llvm/Analysis/CodeMetrics.h" 22198090Srdivacky#include <cassert> 23198090Srdivacky#include <climits> 24198090Srdivacky#include <vector> 25198090Srdivacky 26198090Srdivackynamespace llvm { 27198090Srdivacky 28198090Srdivacky class CallSite; 29226633Sdim class TargetData; 30198090Srdivacky 31198090Srdivacky namespace InlineConstants { 32198090Srdivacky // Various magic constants used to adjust heuristics. 33203954Srdivacky const int InstrCost = 5; 34234353Sdim const int IndirectCallThreshold = 100; 35203954Srdivacky const int CallPenalty = 25; 36198090Srdivacky const int LastCallToStaticBonus = -15000; 37198090Srdivacky const int ColdccPenalty = 2000; 38198090Srdivacky const int NoreturnPenalty = 10000; 39198090Srdivacky } 40198090Srdivacky 41234353Sdim /// \brief Represents the cost of inlining a function. 42234353Sdim /// 43234353Sdim /// This supports special values for functions which should "always" or 44234353Sdim /// "never" be inlined. Otherwise, the cost represents a unitless amount; 45234353Sdim /// smaller values increase the likelihood of the function being inlined. 46234353Sdim /// 47234353Sdim /// Objects of this type also provide the adjusted threshold for inlining 48234353Sdim /// based on the information available for a particular callsite. They can be 49234353Sdim /// directly tested to determine if inlining should occur given the cost and 50234353Sdim /// threshold for this cost metric. 51198090Srdivacky class InlineCost { 52234353Sdim enum SentinelValues { 53234353Sdim AlwaysInlineCost = INT_MIN, 54234353Sdim NeverInlineCost = INT_MAX 55198090Srdivacky }; 56198090Srdivacky 57234353Sdim /// \brief The estimated cost of inlining this callsite. 58234353Sdim const int Cost; 59198090Srdivacky 60234353Sdim /// \brief The adjusted threshold against which this cost was computed. 61234353Sdim const int Threshold; 62198090Srdivacky 63234353Sdim // Trivial constructor, interesting logic in the factory functions below. 64234353Sdim InlineCost(int Cost, int Threshold) 65234353Sdim : Cost(Cost), Threshold(Threshold) {} 66234353Sdim 67234353Sdim public: 68234353Sdim static InlineCost get(int Cost, int Threshold) { 69234353Sdim assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); 70234353Sdim assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); 71234353Sdim return InlineCost(Cost, Threshold); 72198090Srdivacky } 73234353Sdim static InlineCost getAlways() { 74234353Sdim return InlineCost(AlwaysInlineCost, 0); 75234353Sdim } 76234353Sdim static InlineCost getNever() { 77234353Sdim return InlineCost(NeverInlineCost, 0); 78234353Sdim } 79198090Srdivacky 80234353Sdim /// \brief Test whether the inline cost is low enough for inlining. 81234353Sdim operator bool() const { 82234353Sdim return Cost < Threshold; 83198090Srdivacky } 84198090Srdivacky 85234353Sdim bool isAlways() const { return Cost == AlwaysInlineCost; } 86234353Sdim bool isNever() const { return Cost == NeverInlineCost; } 87234353Sdim bool isVariable() const { return !isAlways() && !isNever(); } 88198090Srdivacky 89234353Sdim /// \brief Get the inline cost estimate. 90234353Sdim /// It is an error to call this on an "always" or "never" InlineCost. 91234353Sdim int getCost() const { 92234353Sdim assert(isVariable() && "Invalid access of InlineCost"); 93234353Sdim return Cost; 94198090Srdivacky } 95234353Sdim 96234353Sdim /// \brief Get the cost delta from the threshold for inlining. 97234353Sdim /// Only valid if the cost is of the variable kind. Returns a negative 98234353Sdim /// value if the cost is too high to inline. 99234353Sdim int getCostDelta() const { return Threshold - getCost(); } 100198090Srdivacky }; 101203954Srdivacky 102198090Srdivacky /// InlineCostAnalyzer - Cost analyzer used by inliner. 103198090Srdivacky class InlineCostAnalyzer { 104226633Sdim // TargetData if available, or null. 105226633Sdim const TargetData *TD; 106226633Sdim 107198090Srdivacky public: 108226633Sdim InlineCostAnalyzer(): TD(0) {} 109198090Srdivacky 110226633Sdim void setTargetData(const TargetData *TData) { TD = TData; } 111226633Sdim 112234353Sdim /// \brief Get an InlineCost object representing the cost of inlining this 113234353Sdim /// callsite. 114198090Srdivacky /// 115234353Sdim /// Note that threshold is passed into this function. Only costs below the 116234353Sdim /// threshold are computed with any accuracy. The threshold can be used to 117234353Sdim /// bound the computation necessary to determine whether the cost is 118234353Sdim /// sufficiently low to warrant inlining. 119234353Sdim InlineCost getInlineCost(CallSite CS, int Threshold); 120207618Srdivacky /// getCalledFunction - The heuristic used to determine if we should inline 121207618Srdivacky /// the function call or not. The callee is explicitly specified, to allow 122234353Sdim /// you to calculate the cost of inlining a function via a pointer. This 123234353Sdim /// behaves exactly as the version with no explicit callee parameter in all 124234353Sdim /// other respects. 125234353Sdim // 126234353Sdim // Note: This is used by out-of-tree passes, please do not remove without 127234353Sdim // adding a replacement API. 128234353Sdim InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold); 129198090Srdivacky }; 130207618Srdivacky 131207618Srdivacky /// callIsSmall - If a call is likely to lower to a single target instruction, 132207618Srdivacky /// or is otherwise deemed small return true. 133207618Srdivacky bool callIsSmall(const Function *Callee); 134198090Srdivacky} 135198090Srdivacky 136198090Srdivacky#endif 137