LLVM API Documentation

InlineCost.h

Go to the documentation of this file.
00001 //===- InlineCost.cpp - Cost analysis for inliner ---------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements heuristics for inlining decisions.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_TRANSFORMS_UTILS_INLINECOST_H
00015 #define LLVM_TRANSFORMS_UTILS_INLINECOST_H
00016 
00017 #include "llvm/ADT/SmallPtrSet.h"
00018 #include <cassert>
00019 #include <climits>
00020 #include <map>
00021 #include <vector>
00022 
00023 namespace llvm {
00024 
00025   class Value;
00026   class Function;
00027   class CallSite;
00028 
00029   /// InlineCost - Represent the cost of inlining a function. This
00030   /// supports special values for functions which should "always" or
00031   /// "never" be inlined. Otherwise, the cost represents a unitless
00032   /// amount; smaller values increase the likelyhood of the function
00033   /// being inlined.
00034   class InlineCost {
00035     enum Kind {
00036       Value,
00037       Always,
00038       Never
00039     };
00040 
00041     // This is a do-it-yourself implementation of
00042     //   int Cost : 30;
00043     //   unsigned Type : 2;
00044     // We used to use bitfields, but they were sometimes miscompiled (PR3822).
00045     enum { TYPE_BITS = 2 };
00046     enum { COST_BITS = unsigned(sizeof(unsigned)) * CHAR_BIT - TYPE_BITS };
00047     unsigned TypedCost; // int Cost : COST_BITS; unsigned Type : TYPE_BITS;
00048 
00049     Kind getType() const {
00050       return Kind(TypedCost >> COST_BITS);
00051     }
00052 
00053     int getCost() const {
00054       // Sign-extend the bottom COST_BITS bits.
00055       return (int(TypedCost << TYPE_BITS)) >> TYPE_BITS;
00056     }
00057 
00058     InlineCost(int C, int T) {
00059       TypedCost = (unsigned(C << TYPE_BITS) >> TYPE_BITS) | (T << COST_BITS);
00060       assert(getCost() == C && "Cost exceeds InlineCost precision");
00061     }
00062   public:
00063     static InlineCost get(int Cost) { return InlineCost(Cost, Value); }
00064     static InlineCost getAlways() { return InlineCost(0, Always); }
00065     static InlineCost getNever() { return InlineCost(0, Never); }
00066 
00067     bool isVariable() const { return getType() == Value; }
00068     bool isAlways() const { return getType() == Always; }
00069     bool isNever() const { return getType() == Never; }
00070 
00071     /// getValue() - Return a "variable" inline cost's amount. It is
00072     /// an error to call this on an "always" or "never" InlineCost.
00073     int getValue() const {
00074       assert(getType() == Value && "Invalid access of InlineCost");
00075       return getCost();
00076     }
00077   };
00078   
00079   /// InlineCostAnalyzer - Cost analyzer used by inliner.
00080   class InlineCostAnalyzer {
00081     struct ArgInfo {
00082     public:
00083       unsigned ConstantWeight;
00084       unsigned AllocaWeight;
00085       
00086       ArgInfo(unsigned CWeight, unsigned AWeight)
00087         : ConstantWeight(CWeight), AllocaWeight(AWeight) {}
00088     };
00089     
00090     // FunctionInfo - For each function, calculate the size of it in blocks and
00091     // instructions.
00092     struct FunctionInfo {
00093       /// NeverInline - True if this callee should never be inlined into a
00094       /// caller.
00095       bool NeverInline;
00096       
00097       /// usesDynamicAlloca - True if this function calls alloca (in the C sense).
00098       bool usesDynamicAlloca;
00099 
00100       /// NumInsts, NumBlocks - Keep track of how large each function is, which
00101       /// is used to estimate the code size cost of inlining it.
00102       unsigned NumInsts, NumBlocks;
00103 
00104       /// NumVectorInsts - Keep track of how many instructions produce vector
00105       /// values.  The inliner is being more aggressive with inlining vector
00106       /// kernels.
00107       unsigned NumVectorInsts;
00108       
00109       /// ArgumentWeights - Each formal argument of the function is inspected to
00110       /// see if it is used in any contexts where making it a constant or alloca
00111       /// would reduce the code size.  If so, we add some value to the argument
00112       /// entry here.
00113       std::vector<ArgInfo> ArgumentWeights;
00114       
00115       FunctionInfo() : NeverInline(false), usesDynamicAlloca(false), NumInsts(0),
00116                        NumBlocks(0), NumVectorInsts(0) {}
00117       
00118       /// analyzeFunction - Fill in the current structure with information
00119       /// gleaned from the specified function.
00120       void analyzeFunction(Function *F);
00121 
00122       /// CountCodeReductionForConstant - Figure out an approximation for how
00123       /// many instructions will be constant folded if the specified value is
00124       /// constant.
00125       unsigned CountCodeReductionForConstant(Value *V);
00126       
00127       /// CountCodeReductionForAlloca - Figure out an approximation of how much
00128       /// smaller the function will be if it is inlined into a context where an
00129       /// argument becomes an alloca.
00130       ///
00131       unsigned CountCodeReductionForAlloca(Value *V);
00132     };
00133 
00134     std::map<const Function *, FunctionInfo> CachedFunctionInfo;
00135 
00136   public:
00137 
00138     /// getInlineCost - The heuristic used to determine if we should inline the
00139     /// function call or not.
00140     ///
00141     InlineCost getInlineCost(CallSite CS,
00142                              SmallPtrSet<const Function *, 16> &NeverInline);
00143 
00144     /// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a
00145     /// higher threshold to determine if the function call should be inlined.
00146     float getInlineFudgeFactor(CallSite CS);
00147 
00148     /// resetCachedFunctionInfo - erase any cached cost info for this function.
00149     void resetCachedCostInfo(Function* Caller) {
00150       CachedFunctionInfo[Caller].NumBlocks = 0;
00151     }
00152   };
00153 }
00154 
00155 #endif