InlineCost.h revision 86953b5795007eaa98838297360a6987e33e92e7
193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===// 293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// 393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// The LLVM Compiler Infrastructure 493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// 593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// This file is distributed under the University of Illinois Open Source 693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// License. See LICENSE.TXT for details. 793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// 893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//===----------------------------------------------------------------------===// 993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// 1093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// This file implements heuristics for inlining decisions. 1193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)// 1293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)//===----------------------------------------------------------------------===// 1393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 1493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#ifndef LLVM_ANALYSIS_INLINECOST_H 1593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#define LLVM_ANALYSIS_INLINECOST_H 1693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 1793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#include "llvm/Analysis/CodeMetrics.h" 1893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#include "llvm/Analysis/CallGraphSCCPass.h" 1993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#include <cassert> 2093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)#include <climits> 2193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 2293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)namespace llvm { 2393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)class CallSite; 2493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)class DataLayout; 2593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)class Function; 2693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 2793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)namespace InlineConstants { 2893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) // Various magic constants used to adjust heuristics. 29323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles) const int InstrCost = 5; 3093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) const int IndirectCallThreshold = 100; 3109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) const int CallPenalty = 25; 3293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) const int LastCallToStaticBonus = -15000; 3393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) const int ColdccPenalty = 2000; 3451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) const int NoreturnPenalty = 10000; 3593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) /// Do not inline functions which allocate this many bytes on the stack 3693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) /// when the caller is recursive. 3793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) const unsigned TotalAllocaSizeRecursiveCaller = 1024; 3893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)} 3993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 4093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/// \brief Represents the cost of inlining a function. 4193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/// 4293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/// This supports special values for functions which should "always" or 4393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/// "never" be inlined. Otherwise, the cost represents a unitless amount; 4493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/// smaller values increase the likelihood of the function being inlined. 4593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/// 4693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/// Objects of this type also provide the adjusted threshold for inlining 4793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/// based on the information available for a particular callsite. They can be 4893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/// directly tested to determine if inlining should occur given the cost and 4909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)/// threshold for this cost metric. 5009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)class InlineCost { 5109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) enum SentinelValues { 5209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) AlwaysInlineCost = INT_MIN, 5309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) NeverInlineCost = INT_MAX 5409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) }; 551e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 561e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) /// \brief The estimated cost of inlining this callsite. 5709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) const int Cost; 581e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 591e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) /// \brief The adjusted threshold against which this cost was computed. 6093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) const int Threshold; 611e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 621e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Trivial constructor, interesting logic in the factory functions below. 6393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) InlineCost(int Cost, int Threshold) : Cost(Cost), Threshold(Threshold) {} 641e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 651e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)public: 6693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) static InlineCost get(int Cost, int Threshold) { 6793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); 6893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); 6909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) return InlineCost(Cost, Threshold); 7009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 7193ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) static InlineCost getAlways() { 7293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) return InlineCost(AlwaysInlineCost, 0); 7393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) } 7493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) static InlineCost getNever() { 7593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) return InlineCost(NeverInlineCost, 0); 7609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 7709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) 7893ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) /// \brief Test whether the inline cost is low enough for inlining. 7993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) operator bool() const { 8051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) return Cost < Threshold; 8151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) } 8293ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 8393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) bool isAlways() const { return Cost == AlwaysInlineCost; } 841e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) bool isNever() const { return Cost == NeverInlineCost; } 85323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles) bool isVariable() const { return !isAlways() && !isNever(); } 861e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 871e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) /// \brief Get the inline cost estimate. 8809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) /// It is an error to call this on an "always" or "never" InlineCost. 891e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) int getCost() const { 901e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) assert(isVariable() && "Invalid access of InlineCost"); 911e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) return Cost; 92f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu } 9393ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 9493ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) /// \brief Get the cost delta from the threshold for inlining. 9593ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) /// Only valid if the cost is of the variable kind. Returns a negative 9693ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) /// value if the cost is too high to inline. 9793ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) int getCostDelta() const { return Threshold - getCost(); } 9851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)}; 9993ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles) 10093ac45cfc74041c8ae536ce58a9534d46db2024eTorne (Richard Coles)/// \brief Cost analyzer used by inliner. 101class InlineCostAnalysis : public CallGraphSCCPass { 102 const DataLayout *TD; 103 104public: 105 static char ID; 106 107 InlineCostAnalysis(); 108 ~InlineCostAnalysis(); 109 110 // Pass interface implementation. 111 void getAnalysisUsage(AnalysisUsage &AU) const; 112 bool runOnSCC(CallGraphSCC &SCC); 113 114 /// \brief Get an InlineCost object representing the cost of inlining this 115 /// callsite. 116 /// 117 /// Note that threshold is passed into this function. Only costs below the 118 /// threshold are computed with any accuracy. The threshold can be used to 119 /// bound the computation necessary to determine whether the cost is 120 /// sufficiently low to warrant inlining. 121 /// 122 /// Also note that calling this function *dynamically* computes the cost of 123 /// inlining the callsite. It is an expensive, heavyweight call. 124 InlineCost getInlineCost(CallSite CS, int Threshold); 125 126 /// \brief Get an InlineCost with the callee explicitly specified. 127 /// This allows you to calculate the cost of inlining a function via a 128 /// pointer. This behaves exactly as the version with no explicit callee 129 /// parameter in all other respects. 130 // 131 // Note: This is used by out-of-tree passes, please do not remove without 132 // adding a replacement API. 133 InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold); 134 135 /// \brief Minimal filter to detect invalid constructs for inlining. 136 bool isInlineViable(Function &Callee); 137}; 138 139} 140 141#endif 142