-//===- InlineCost.cpp - Cost analysis for inliner ---------------*- C++ -*-===//
+//===- InlineCost.h - Cost analysis for inliner -----------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
#ifndef LLVM_ANALYSIS_INLINECOST_H
#define LLVM_ANALYSIS_INLINECOST_H
+#include "llvm/Function.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/ValueMap.h"
+#include "llvm/Analysis/CodeMetrics.h"
#include <cassert>
#include <climits>
-#include <map>
#include <vector>
namespace llvm {
- class Value;
- class Function;
- class BasicBlock;
class CallSite;
template<class PtrType, unsigned SmallSize>
class SmallPtrSet;
+ class TargetData;
namespace InlineConstants {
// Various magic constants used to adjust heuristics.
- const int CallPenalty = 5;
+ const int InstrCost = 5;
+ const int IndirectCallBonus = -100;
+ const int CallPenalty = 25;
const int LastCallToStaticBonus = -15000;
const int ColdccPenalty = 2000;
const int NoreturnPenalty = 10000;
/// 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
+ /// amount; smaller values increase the likelihood of the function
/// being inlined.
class InlineCost {
enum Kind {
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) {}
+ : ConstantWeight(CWeight), AllocaWeight(AWeight)
+ {}
};
-
- // RegionInfo - Calculate size and a few related metrics for a set of
- // basic blocks.
- struct RegionInfo {
- /// 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;
-
- /// NumVectorInsts - Keep track of how many instructions produce vector
- /// values. The inliner is being more aggressive with inlining vector
- /// kernels.
- unsigned NumVectorInsts;
-
- /// NumRets - Keep track of how many Ret instructions the block contains.
- unsigned NumRets;
+
+ 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<ArgInfo> ArgumentWeights;
-
- RegionInfo() : NeverInline(false), usesDynamicAlloca(false), NumInsts(0),
- NumBlocks(0), NumVectorInsts(0), NumRets(0) {}
-
- /// analyzeBasicBlock - Add information about the specified basic block
- /// to the current structure.
- void analyzeBasicBlock(const BasicBlock *BB);
- /// analyzeFunction - Add information about the specified function
- /// to the current structure.
- void analyzeFunction(Function *F);
+ /// PointerArgPairWeights - Weights to use when giving an inline bonus to
+ /// a call site due to correlated pairs of pointers.
+ DenseMap<std::pair<unsigned, unsigned>, unsigned> PointerArgPairWeights;
- /// CountCodeReductionForConstant - Figure out an approximation for how
+ /// 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
+ unsigned countCodeReductionForConstant(const CodeMetrics &Metrics,
+ 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);
+ unsigned countCodeReductionForAlloca(const CodeMetrics &Metrics,
+ Value *V);
+
+ /// countCodeReductionForPointerPair - Count the bonus to apply to an
+ /// inline call site where a pair of arguments are pointers and one
+ /// argument is a constant offset from the other. The idea is to
+ /// recognize a common C++ idiom where a begin and end iterator are
+ /// actually pointers, and many operations on the pair of them will be
+ /// constants if the function is called with arguments that have
+ /// a constant offset.
+ void countCodeReductionForPointerPair(
+ const CodeMetrics &Metrics,
+ DenseMap<Value *, unsigned> &PointerArgs,
+ Value *V, unsigned ArgIdx);
+
+ /// analyzeFunction - Add information about the specified function
+ /// to the current structure.
+ void analyzeFunction(Function *F, const TargetData *TD);
+
+ /// NeverInline - Returns true if the function should never be
+ /// inlined into any caller.
+ bool NeverInline();
};
- std::map<const Function *, RegionInfo> CachedFunctionInfo;
+ // The Function* for a function can be changed (by ArgumentPromotion);
+ // the ValueMap will update itself when this happens.
+ ValueMap<const Function *, FunctionInfo> CachedFunctionInfo;
+
+ // TargetData if available, or null.
+ const TargetData *TD;
+ int CountBonusForConstant(Value *V, Constant *C = NULL);
+ int ConstantFunctionBonus(CallSite CS, Constant *C);
+ int getInlineSize(CallSite CS, Function *Callee);
+ int getInlineBonuses(CallSite CS, Function *Callee);
public:
+ InlineCostAnalyzer(): TD(0) {}
+
+ void setTargetData(const TargetData *TData) { TD = TData; }
/// getInlineCost - The heuristic used to determine if we should inline the
/// function call or not.
///
InlineCost getInlineCost(CallSite CS,
SmallPtrSet<const Function *, 16> &NeverInline);
+ /// getCalledFunction - The heuristic used to determine if we should inline
+ /// the function call or not. The callee is explicitly specified, to allow
+ /// you to calculate the cost of inlining a function via a pointer. The
+ /// result assumes that the inlined version will always be used. You should
+ /// weight it yourself in cases where this callee will not always be called.
+ InlineCost getInlineCost(CallSite CS,
+ Function *Callee,
+ SmallPtrSet<const Function *, 16> &NeverInline);
+
+ /// getSpecializationBonus - The heuristic used to determine the per-call
+ /// performance boost for using a specialization of Callee with argument
+ /// SpecializedArgNos replaced by a constant.
+ int getSpecializationBonus(Function *Callee,
+ SmallVectorImpl<unsigned> &SpecializedArgNo);
+
+ /// getSpecializationCost - The heuristic used to determine the code-size
+ /// impact of creating a specialized version of Callee with argument
+ /// SpecializedArgNo replaced by a constant.
+ InlineCost getSpecializationCost(Function *Callee,
+ SmallVectorImpl<unsigned> &SpecializedArgNo);
/// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a
/// higher threshold to determine if the function call should be inlined.
/// resetCachedFunctionInfo - erase any cached cost info for this function.
void resetCachedCostInfo(Function* Caller) {
- CachedFunctionInfo[Caller].NumBlocks = 0;
+ 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);
+
+ /// clear - empty the cache of inline costs
+ void clear();
};
+
+ /// 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);
}
#endif