X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FInlineCost.h;h=35f991cb3f67496bc615e34664efddf97db8f702;hp=ab0b84524af1ee461b717d751f95458620ea8589;hb=0651a407f6a408caa02b76a1cdaf0d8fa54f29fb;hpb=899dd9be7fb91c089ef1ae20ef44b2a286433313 diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index ab0b84524af..35f991cb3f6 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -1,4 +1,4 @@ -//===- InlineCost.cpp - Cost analysis for inliner ---------------*- C++ -*-===// +//===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -14,187 +14,115 @@ #ifndef LLVM_ANALYSIS_INLINECOST_H #define LLVM_ANALYSIS_INLINECOST_H +#include "llvm/Analysis/CallGraphSCCPass.h" #include #include -#include -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/ValueMap.h" namespace llvm { +class AssumptionCacheTracker; +class CallSite; +class DataLayout; +class Function; +class TargetTransformInfo; + +namespace InlineConstants { + // Various magic constants used to adjust heuristics. + const int InstrCost = 5; + const int IndirectCallThreshold = 100; + const int CallPenalty = 25; + const int LastCallToStaticBonus = -15000; + const int ColdccPenalty = 2000; + const int NoreturnPenalty = 10000; + /// Do not inline functions which allocate this many bytes on the stack + /// when the caller is recursive. + const unsigned TotalAllocaSizeRecursiveCaller = 1024; +} - class Value; - class Function; - class BasicBlock; - class CallSite; - template - class SmallPtrSet; - - // CodeMetrics - Calculate size and a few similar metrics for a set of - // basic blocks. - struct CodeMetrics { - /// NeverInline - True if this callee should never be inlined into a - /// caller. - bool NeverInline; - - /// usesDynamicAlloca - True if this function calls alloca (in the C sense). - bool usesDynamicAlloca; - - /// NumInsts, NumBlocks - Keep track of how large each function is, which - /// is used to estimate the code size cost of inlining it. - unsigned NumInsts, NumBlocks; - - /// NumBBInsts - Keeps track of basic block code size estimates. - DenseMap NumBBInsts; +/// \brief Represents the cost of inlining a function. +/// +/// This supports special values for functions which should "always" or +/// "never" be inlined. Otherwise, the cost represents a unitless amount; +/// smaller values increase the likelihood of the function being inlined. +/// +/// Objects of this type also provide the adjusted threshold for inlining +/// based on the information available for a particular callsite. They can be +/// directly tested to determine if inlining should occur given the cost and +/// threshold for this cost metric. +class InlineCost { + enum SentinelValues { + AlwaysInlineCost = INT_MIN, + NeverInlineCost = INT_MAX + }; - /// NumCalls - Keep track of the number of calls to 'big' functions. - unsigned NumCalls; + /// \brief The estimated cost of inlining this callsite. + const int Cost; - /// NumVectorInsts - Keep track of how many instructions produce vector - /// values. The inliner is being more aggressive with inlining vector - /// kernels. - unsigned NumVectorInsts; + /// \brief The adjusted threshold against which this cost was computed. + const int Threshold; - /// NumRets - Keep track of how many Ret instructions the block contains. - unsigned NumRets; + // Trivial constructor, interesting logic in the factory functions below. + InlineCost(int Cost, int Threshold) : Cost(Cost), Threshold(Threshold) {} - CodeMetrics() : NeverInline(false), usesDynamicAlloca(false), NumInsts(0), - NumBlocks(0), NumCalls(0), NumVectorInsts(0), NumRets(0) {} +public: + static InlineCost get(int Cost, int Threshold) { + assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); + assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); + return InlineCost(Cost, Threshold); + } + static InlineCost getAlways() { + return InlineCost(AlwaysInlineCost, 0); + } + static InlineCost getNever() { + return InlineCost(NeverInlineCost, 0); + } - /// analyzeBasicBlock - Add information about the specified basic block - /// to the current structure. - void analyzeBasicBlock(const BasicBlock *BB); + /// \brief Test whether the inline cost is low enough for inlining. + explicit operator bool() const { + return Cost < Threshold; + } - /// analyzeFunction - Add information about the specified function - /// to the current structure. - void analyzeFunction(Function *F); - }; + bool isAlways() const { return Cost == AlwaysInlineCost; } + bool isNever() const { return Cost == NeverInlineCost; } + bool isVariable() const { return !isAlways() && !isNever(); } - namespace InlineConstants { - // Various magic constants used to adjust heuristics. - const int InstrCost = 5; - const int IndirectCallBonus = 500; - const int CallPenalty = 25; - const int LastCallToStaticBonus = -15000; - const int ColdccPenalty = 2000; - const int NoreturnPenalty = 10000; + /// \brief Get the inline cost estimate. + /// It is an error to call this on an "always" or "never" InlineCost. + int getCost() const { + assert(isVariable() && "Invalid access of InlineCost"); + return Cost; } - /// InlineCost - Represent the cost of inlining a function. This - /// supports special values for functions which should "always" or - /// "never" be inlined. Otherwise, the cost represents a unitless - /// amount; smaller values increase the likelyhood of the function - /// being inlined. - class InlineCost { - enum Kind { - Value, - Always, - Never - }; - - // This is a do-it-yourself implementation of - // int Cost : 30; - // unsigned Type : 2; - // We used to use bitfields, but they were sometimes miscompiled (PR3822). - enum { TYPE_BITS = 2 }; - enum { COST_BITS = unsigned(sizeof(unsigned)) * CHAR_BIT - TYPE_BITS }; - unsigned TypedCost; // int Cost : COST_BITS; unsigned Type : TYPE_BITS; - - Kind getType() const { - return Kind(TypedCost >> COST_BITS); - } - - int getCost() const { - // Sign-extend the bottom COST_BITS bits. - return (int(TypedCost << TYPE_BITS)) >> TYPE_BITS; - } - - InlineCost(int C, int T) { - TypedCost = (unsigned(C << TYPE_BITS) >> TYPE_BITS) | (T << COST_BITS); - assert(getCost() == C && "Cost exceeds InlineCost precision"); - } - public: - static InlineCost get(int Cost) { return InlineCost(Cost, Value); } - static InlineCost getAlways() { return InlineCost(0, Always); } - static InlineCost getNever() { return InlineCost(0, Never); } - - bool isVariable() const { return getType() == Value; } - bool isAlways() const { return getType() == Always; } - bool isNever() const { return getType() == Never; } - - /// getValue() - Return a "variable" inline cost's amount. It is - /// an error to call this on an "always" or "never" InlineCost. - int getValue() const { - assert(getType() == Value && "Invalid access of InlineCost"); - return getCost(); - } - }; - - /// InlineCostAnalyzer - Cost analyzer used by inliner. - class InlineCostAnalyzer { - struct ArgInfo { - public: - unsigned ConstantWeight; - unsigned AllocaWeight; - - ArgInfo(unsigned CWeight, unsigned AWeight) - : ConstantWeight(CWeight), AllocaWeight(AWeight) {} - }; - - struct FunctionInfo { - CodeMetrics Metrics; - - /// ArgumentWeights - Each formal argument of the function is inspected to - /// see if it is used in any contexts where making it a constant or alloca - /// would reduce the code size. If so, we add some value to the argument - /// entry here. - std::vector ArgumentWeights; - - /// CountCodeReductionForConstant - Figure out an approximation for how - /// many instructions will be constant folded if the specified value is - /// constant. - unsigned CountCodeReductionForConstant(Value *V); - - /// CountCodeReductionForAlloca - Figure out an approximation of how much - /// smaller the function will be if it is inlined into a context where an - /// argument becomes an alloca. - /// - unsigned CountCodeReductionForAlloca(Value *V); - - /// analyzeFunction - Add information about the specified function - /// to the current structure. - void analyzeFunction(Function *F); - }; - - // The Function* for a function can be changed (by ArgumentPromotion); - // the ValueMap will update itself when this happens. - ValueMap CachedFunctionInfo; - - public: - - /// getInlineCost - The heuristic used to determine if we should inline the - /// function call or not. - /// - InlineCost getInlineCost(CallSite CS, - SmallPtrSet &NeverInline); - - /// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a - /// higher threshold to determine if the function call should be inlined. - float getInlineFudgeFactor(CallSite CS); - - /// resetCachedFunctionInfo - erase any cached cost info for this function. - void resetCachedCostInfo(Function* Caller) { - CachedFunctionInfo[Caller] = FunctionInfo(); - } - - /// growCachedCostInfo - update the cached cost info for Caller after Callee - /// has been inlined. If Callee is NULL it means a dead call has been - /// eliminated. - void growCachedCostInfo(Function* Caller, Function* Callee); - }; + /// \brief Get the cost delta from the threshold for inlining. + /// Only valid if the cost is of the variable kind. Returns a negative + /// value if the cost is too high to inline. + int getCostDelta() const { return Threshold - getCost(); } +}; + +/// \brief Get an InlineCost object representing the cost of inlining this +/// callsite. +/// +/// Note that threshold is passed into this function. Only costs below the +/// threshold are computed with any accuracy. The threshold can be used to +/// bound the computation necessary to determine whether the cost is +/// sufficiently low to warrant inlining. +/// +/// Also note that calling this function *dynamically* computes the cost of +/// inlining the callsite. It is an expensive, heavyweight call. +InlineCost getInlineCost(CallSite CS, int Threshold, + TargetTransformInfo &CalleeTTI, + AssumptionCacheTracker *ACT); + +/// \brief Get an InlineCost with the callee explicitly specified. +/// This allows you to calculate the cost of inlining a function via a +/// pointer. This behaves exactly as the version with no explicit callee +/// parameter in all other respects. +// +InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold, + TargetTransformInfo &CalleeTTI, + AssumptionCacheTracker *ACT); - /// callIsSmall - If a call is likely to lower to a single target instruction, - /// or is otherwise deemed small return true. - bool callIsSmall(const Function *Callee); +/// \brief Minimal filter to detect invalid constructs for inlining. +bool isInlineViable(Function &Callee); } #endif