InlineCost.h revision 92df026f0da91dc65ef6186e97ff87b1f53e8cd0
1282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski//===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===// 2282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// 3282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// The LLVM Compiler Infrastructure 4282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// 5282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// This file is distributed under the University of Illinois Open Source 6282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// License. See LICENSE.TXT for details. 7282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// 8282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski//===----------------------------------------------------------------------===// 9282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// 10282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// This file implements heuristics for inlining decisions. 11282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// 12282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski//===----------------------------------------------------------------------===// 13282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 14282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#ifndef LLVM_ANALYSIS_INLINECOST_H 15282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#define LLVM_ANALYSIS_INLINECOST_H 16282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 17282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include "llvm/Function.h" 18282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include "llvm/ADT/DenseMap.h" 19282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include "llvm/ADT/SmallPtrSet.h" 20282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include "llvm/ADT/ValueMap.h" 21282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include "llvm/Analysis/CodeMetrics.h" 22282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include <cassert> 23282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include <climits> 24282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include <vector> 25282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 26282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskinamespace llvm { 27282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 28282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski class CallSite; 29282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski class TargetData; 30282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 31282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski namespace InlineConstants { 32282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Various magic constants used to adjust heuristics. 33282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const int InstrCost = 5; 34282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const int IndirectCallThreshold = 100; 35282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const int CallPenalty = 25; 36282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const int LastCallToStaticBonus = -15000; 37282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const int ColdccPenalty = 2000; 38282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const int NoreturnPenalty = 10000; 39282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// Do not inline functions which allocate this many bytes on the stack 40282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// when the caller is recursive. 41282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const int TotalAllocaSizeRecursiveCaller = 1024; 42282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 43282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 44282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// \brief Represents the cost of inlining a function. 45282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// 46282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// This supports special values for functions which should "always" or 47282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// "never" be inlined. Otherwise, the cost represents a unitless amount; 48282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// smaller values increase the likelihood of the function being inlined. 49282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// 50282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// Objects of this type also provide the adjusted threshold for inlining 51282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// based on the information available for a particular callsite. They can be 52282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// directly tested to determine if inlining should occur given the cost and 53282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// threshold for this cost metric. 54282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski class InlineCost { 55282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski enum SentinelValues { 56282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski AlwaysInlineCost = INT_MIN, 57282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski NeverInlineCost = INT_MAX 58282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski }; 59282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 60282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// \brief The estimated cost of inlining this callsite. 61282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const int Cost; 62282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 63282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// \brief The adjusted threshold against which this cost was computed. 64282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const int Threshold; 65282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 66282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Trivial constructor, interesting logic in the factory functions below. 67282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski InlineCost(int Cost, int Threshold) 68282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski : Cost(Cost), Threshold(Threshold) {} 69282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 70282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public: 71282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski static InlineCost get(int Cost, int Threshold) { 72282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); 73282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); 74282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return InlineCost(Cost, Threshold); 75282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 76282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski static InlineCost getAlways() { 77282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return InlineCost(AlwaysInlineCost, 0); 78282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 79282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski static InlineCost getNever() { 80282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return InlineCost(NeverInlineCost, 0); 81282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 82282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 83282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// \brief Test whether the inline cost is low enough for inlining. 84282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski operator bool() const { 85282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return Cost < Threshold; 86282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 87282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 88282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski bool isAlways() const { return Cost == AlwaysInlineCost; } 89282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski bool isNever() const { return Cost == NeverInlineCost; } 90282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski bool isVariable() const { return !isAlways() && !isNever(); } 91282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 92282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// \brief Get the inline cost estimate. 93282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// It is an error to call this on an "always" or "never" InlineCost. 94282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int getCost() const { 95282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski assert(isVariable() && "Invalid access of InlineCost"); 96282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return Cost; 97282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 98282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 99282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// \brief Get the cost delta from the threshold for inlining. 100282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// Only valid if the cost is of the variable kind. Returns a negative 101282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// value if the cost is too high to inline. 102282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski int getCostDelta() const { return Threshold - getCost(); } 103282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski }; 104282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 105282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// InlineCostAnalyzer - Cost analyzer used by inliner. 106282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski class InlineCostAnalyzer { 107282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // TargetData if available, or null. 108282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const TargetData *TD; 109282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 110282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski public: 111282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski InlineCostAnalyzer(): TD(0) {} 112282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 113282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski void setTargetData(const TargetData *TData) { TD = TData; } 114282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 115282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// \brief Get an InlineCost object representing the cost of inlining this 116282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// callsite. 117282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// 118282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// Note that threshold is passed into this function. Only costs below the 119282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// threshold are computed with any accuracy. The threshold can be used to 120282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// bound the computation necessary to determine whether the cost is 121282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// sufficiently low to warrant inlining. 122282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski InlineCost getInlineCost(CallSite CS, int Threshold); 123282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// getCalledFunction - The heuristic used to determine if we should inline 124282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// the function call or not. The callee is explicitly specified, to allow 125282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// you to calculate the cost of inlining a function via a pointer. This 126282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// behaves exactly as the version with no explicit callee parameter in all 127282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski /// other respects. 128282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // 129282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // Note: This is used by out-of-tree passes, please do not remove without 130282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // adding a replacement API. 131282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold); 132282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski }; 133282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 134282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 135282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#endif 136282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski