Pass to compute dynamic instruction count

[eraman]

Summary

An analysis pass in the new PM to compute estimated dynamic instruction count of a function based on the static instruction count and block frequency info. The intention is to use this in inline cost analysis to estimate speedup due to inlining (as discussed in the RFC I sent earlier).

We want the static instruction counts to be closely tied to the cost model used in inline cost analysis. I have moved the CallAnalyzer interface to the header file. When used on out-of-line function, the code in CallAnalyzer that tries to simplify instructions is mostly irrelevant. In most cases, this works fine based on the fact that the initial map of known values is empty. In some cases, I need an explicit flag to distinguish whether I'm using the analyzer during inlining or not.

[echristo]

Drive by question:

Why a pass and not a utility?

(Admittedly not read the code, just the description)

Thanks!

-eric

[davidxl]

Can you split the patch the move the call analyzer to the header into a separate one? That is an ok one by its own.

[davidxl]

include/llvm/Analysis/InlineCost.h

162

Can you explain why it is needed for out-of-line functions -- basically explain how DynamicInstructionCountAnalysis is going to be used. Also why can't the use of frequency/profile information be baked into CallAnalyzer itself?

[hfinkel]

include/llvm/Analysis/InlineCost.h

165

I like the fact that the inlining-specific behavior can be explicitly disabled using this flag, but this needs to be better documented. At least give a few examples here of what kind of inlining-specific behavior this enables.

[eraman]

I'm dropping the patch for now. The argument for making this as a pass is
to allow it to be shared by some client other than inliner (LoopUnroller?
something else?). But then, tying it to the cost model used by inliner
doesn't make sense. I can't rewrite this patch as a library now before
switching to the new pass manager, so I'll drop this now and revisit this
later.

include/llvm/Analysis/BlockFrequencyInfo.h

 #define LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H
 
 #include "llvm/Pass.h"
 #include "llvm/Support/BlockFrequency.h"
 #include <climits>
 
 namespace llvm {
 
+// FIXME: Replace this brittle forward declaration with the include of the new
+// PassManager.h when doing so doesn't break the PassManagerBuilder.
+template <typename IRUnitT>
+class AnalysisManager;
 class BranchProbabilityInfo;
 class LoopInfo;
 template <class BlockT> class BlockFrequencyInfoImpl;
 
 /// BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to
 /// estimate IR basic block frequencies.
 class BlockFrequencyInfo {
   typedef BlockFrequencyInfoImpl<BasicBlock> ImplType;
public:
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnFunction(Function &F) override;
   void releaseMemory() override;
   void print(raw_ostream &OS, const Module *M) const override;
 };
 
+/// \brief Analysis pass that exposes the \c BlockFrequencyInfo for a function.
+class BlockFrequencyAnalysis {
+  static char PassID;
+
+ public:
+  typedef BlockFrequencyInfo Result;
+
+  /// \brief Opaque, unique identifier for this analysis pass.
+  static void *ID() { return (void *)&PassID; }
+
+  /// \brief Provide a name for the analysis for debugging and logging.
+  static StringRef name() { return "BlockFrequencyAnalysis"; }
+
+  BlockFrequencyInfo run(Function &F, AnalysisManager<Function> *AM);
+};
 }
 
 #endif

include/llvm/Analysis/BranchProbabilityInfo.h

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/BranchProbability.h"
 
 namespace llvm {
+// FIXME: Replace this brittle forward declaration with the include of the new
+// PassManager.h when doing so doesn't break the PassManagerBuilder.
+template <typename IRUnitT>
+class AnalysisManager;
 class LoopInfo;
 class raw_ostream;
 
 /// \brief Analysis providing branch probability information.
 ///
 /// This is a function analysis which provides information on the relative
 /// probabilities of each "edge" in the function's CFG where such an edge is
 /// defined by a pair (PredBlock and an index in the successors). The
public:
   const BranchProbabilityInfo &getBPI() const { return BPI; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
   bool runOnFunction(Function &F) override;
   void releaseMemory() override;
   void print(raw_ostream &OS, const Module *M = nullptr) const override;
 };
 
+/// \brief Analysis pass that exposes the \c BranchProbabilityInfo for a
+/// function.
+class BranchProbabilityAnalysis {
+  static char PassID;
+
+ public:
+  typedef BranchProbabilityInfo Result;
+
+  /// \brief Opaque, unique identifier for this analysis pass.
+  static void *ID() { return (void *)&PassID; }
+
+  /// \brief Provide a name for the analysis for debugging and logging.
+  static StringRef name() { return "BranchProbabilityAnalysis"; }
+
+  BranchProbabilityInfo run(Function &F, AnalysisManager<Function> *AM);
+};
 }
 
 #endif

include/llvm/Analysis/DynamicInstructionCount.h

+//===- DynamicInstructionCount.h - Dynamic Instruction Count Analysis
+//----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a pass that computes the estimated dynamic instruction
+// count of a function. The dynamic instruction count computed is per invocation
+// of the function. This pass is intended to be used by the inliner and uses
+// InlineCost to calculate the static instruction count. This is weighted by
+// BlockFrequencyInfo to arrive at the dynamic instruction count.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_ANALYSIS_DYNAMIC_INSTRUCTION_COUNT_H
+#define LLVM_ANALYSIS_DYNAMIC_INSTRUCTION_COUNT_H
+
+#include "llvm/IR/Function.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+class DynamicInstructionCount {
+ public:
+  uint64_t getCount() const { return Count; }
+  void setCount(uint64_t NewCount) { Count = NewCount; }
+
+ private:
+  uint64_t Count;
+};
+
+/// \brief Analysis pass that calculates dynamic instr count for a function.
+class DynamicInstructionCountAnalysis {
+  static char PassID;
+
+ public:
+  typedef DynamicInstructionCount Result;
+
+  /// \brief Opaque, unique identifier for this analysis pass.
+  static void *ID() { return (void *)&PassID; }
+
+  /// \brief Provide a name for the analysis for debugging and logging.
+  static StringRef name() { return "DynamicInstructionCountAnalysis"; }
+
+  Result run(Function &F, AnalysisManager<Function> *AM);
+};
+
+/// \brief Printer pass for the \c DynamicInstructionCountAnalysis results.
+class DynamicInstructionCountPrinterPass {
+  raw_ostream &OS;
+
+ public:
+  explicit DynamicInstructionCountPrinterPass(raw_ostream &OS) : OS(OS) {}
+  PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
+
+  static StringRef name() { return "DynamicInstructionCountPrinterPass"; }
+};
+}
+#endif

include/llvm/Analysis/InlineCost.h

 // This file implements heuristics for inlining decisions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_INLINECOST_H
 #define LLVM_ANALYSIS_INLINECOST_H
 
 #include "llvm/Analysis/CallGraphSCCPass.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/GetElementPtrTypeIterator.h"
+#include "llvm/IR/InstVisitor.h"
 #include <cassert>
 #include <climits>
 
 namespace llvm {
 class AssumptionCacheTracker;
 class CallSite;
 class DataLayout;
 class Function;
public:
   }
 
   /// \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(); }
 };
 
+class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
+  typedef InstVisitor<CallAnalyzer, bool> Base;
+  friend class InstVisitor<CallAnalyzer, bool>;
+
+  /// The TargetTransformInfo available for this compilation.
+  const TargetTransformInfo &TTI;
+
+  /// The cache of @llvm.assume intrinsics.
+  AssumptionCacheTracker *ACT;
+
+  // The called function.
+  Function &F;
+
+  // The candidate callsite being analyzed. Please do not use this to do
+  // analysis in the caller function; we want the inline cost query to be
+  // easily cacheable. Instead, use the cover function paramHasAttr.
+  CallSite *CandidateCS;
+
+  int Threshold;
+  int Cost;
+
+  bool IsCallerRecursive;
+  bool IsRecursiveCall;
+  bool ExposesReturnsTwice;
+  bool HasDynamicAlloca;
+  bool ContainsNoDuplicateCall;
+  bool HasReturn;
+  bool HasIndirectBr;
+  bool HasFrameEscape;
+
+  /// Number of bytes allocated statically by the callee.
+  uint64_t AllocatedSize;
+  unsigned NumInstructions, NumVectorInstructions;
+  int FiftyPercentVectorBonus, TenPercentVectorBonus;
+  int VectorBonus;
+
+  // While we walk the potentially-inlined instructions, we build up and
+  // maintain a mapping of simplified values specific to this callsite. The
+  // idea is to propagate any special information we have about arguments to
+  // this call through the inlinable section of the function, and account for
+  // likely simplifications post-inlining. The most important aspect we track
+  // is CFG altering simplifications -- when we prove a basic block dead, that
+  // can cause dramatic shifts in the cost of inlining a function.
+  DenseMap<Value *, Constant *> SimplifiedValues;
+
+  // Keep track of the values which map back (through function arguments) to
+  // allocas on the caller stack which could be simplified through SROA.
+  DenseMap<Value *, Value *> SROAArgValues;
+
+  // The mapping of caller Alloca values to their accumulated cost savings. If
+  // we have to disable SROA for one of the allocas, this tells us how much
+  // cost must be added.
+  DenseMap<Value *, int> SROAArgCosts;
+
+  // Keep track of values which map to a pointer base and constant offset.
+  DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs;
+
+  // The call cost analyzer can be used to compute the cost of out-of-line
+  // functions as well. This flag tells whether it is used for inlining or
+  // not.
+  const bool Inlining;
+
+  // Custom simplification helper routines.
+  bool isAllocaDerivedArg(Value *V);
+  bool lookupSROAArgAndCost(Value *V, Value *&Arg,
+                            DenseMap<Value *, int>::iterator &CostIt);
+  void disableSROA(DenseMap<Value *, int>::iterator CostIt);
+  void disableSROA(Value *V);
+  void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
+                          int InstructionCost);
+  bool isGEPOffsetConstant(GetElementPtrInst &GEP);
+  bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
+  bool simplifyCallSite(Function *F, CallSite CS);
+  ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
+
+  /// Return true if the given argument to the function being considered for
+  /// inlining has the given attribute set either at the call site or the
+  /// function declaration.  Primarily used to inspect call site specific
+  /// attributes since these can be more precise than the ones on the callee
+  /// itself.
+  bool paramHasAttr(Argument *A, Attribute::AttrKind Attr);
+
+  /// Return true if the given value is known non null within the callee if
+  /// inlined through this particular callsite.
+  bool isKnownNonNullInCallee(Value *V);
+
+  // Custom analysis routines.
+
+  // Disable several entry points to the visitor so we don't accidentally use
+  // them by declaring but not defining them here.
+  void visit(Module *);
+  void visit(Module &);
+  void visit(Function *);
+  void visit(Function &);
+  void visit(BasicBlock *);
+  void visit(BasicBlock &);
+
+  // Provide base case for our instruction visit.
+  bool visitInstruction(Instruction &I);
+
+  // Our visit overrides.
+  bool visitAlloca(AllocaInst &I);
+  bool visitPHI(PHINode &I);
+  bool visitGetElementPtr(GetElementPtrInst &I);
+  bool visitBitCast(BitCastInst &I);
+  bool visitPtrToInt(PtrToIntInst &I);
+  bool visitIntToPtr(IntToPtrInst &I);
+  bool visitCastInst(CastInst &I);
+  bool visitUnaryInstruction(UnaryInstruction &I);
+  bool visitCmpInst(CmpInst &I);
+  bool visitSub(BinaryOperator &I);
+  bool visitBinaryOperator(BinaryOperator &I);
+  bool visitLoad(LoadInst &I);
+  bool visitStore(StoreInst &I);
+  bool visitExtractValue(ExtractValueInst &I);
+  bool visitInsertValue(InsertValueInst &I);
+  bool visitCallSite(CallSite CS);
+  bool visitReturnInst(ReturnInst &RI);
+  bool visitBranchInst(BranchInst &BI);
+  bool visitSwitchInst(SwitchInst &SI);
+  bool visitIndirectBrInst(IndirectBrInst &IBI);
+  bool visitResumeInst(ResumeInst &RI);
+  bool visitCleanupReturnInst(CleanupReturnInst &RI);
+  bool visitCatchReturnInst(CatchReturnInst &RI);
+  bool visitUnreachableInst(UnreachableInst &I);
+
+ public:
+  CallAnalyzer(const TargetTransformInfo &TTI, AssumptionCacheTracker *ACT,
+               Function &Callee, int Threshold, CallSite *CSArg,
+               bool Inlining = true);
+
+  bool analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues);
+  bool analyzeCall(CallSite CS);
+
+  int getThreshold() { return Threshold; }
+  int getCost() { return Cost; }
+
+  // Keep a bunch of stats about the cost savings found so we can print them
+  // out when debugging.
+  unsigned NumConstantArgs;
+  unsigned NumConstantOffsetPtrArgs;
+  unsigned NumAllocaArgs;
+  unsigned NumConstantPtrCmps;
+  unsigned NumConstantPtrDiffs;
+  unsigned NumInstructionsSimplified;
+  unsigned SROACostSavings;
+  unsigned SROACostSavingsLost;
+
+  void dump();
+};
+
 /// \brief Cost analyzer used by inliner.
 class InlineCostAnalysis : public CallGraphSCCPass {
   TargetTransformInfoWrapperPass *TTIWP;
   AssumptionCacheTracker *ACT;
 
 public:
   static char ID;
 

lib/Analysis/BlockFrequencyInfo.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/PassManager.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GraphWriter.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "block-freq"

 
 bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
   BranchProbabilityInfo &BPI =
       getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   BFI.calculate(F, BPI, LI);
   return false;
 }
+
+char BlockFrequencyAnalysis::PassID;
+
+BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
+                                               AnalysisManager<Function> *AM) {
+  BlockFrequencyInfo BFI;
+  BFI.calculate(F, AM->getResult<BranchProbabilityAnalysis>(F),
+                AM->getResult<LoopAnalysis>(F));
+  return BFI;
+}

lib/Analysis/BranchProbabilityInfo.cpp

 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
+#include "llvm/IR/PassManager.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "branch-prob"
 
 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",

 }
 
 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
 
 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
                                              const Module *) const {
   BPI.print(OS);
 }
+
+char BranchProbabilityAnalysis::PassID;
+
+BranchProbabilityInfo BranchProbabilityAnalysis::run(
+    Function &F, AnalysisManager<Function> *AM) {
+  BranchProbabilityInfo BPI;
+  BPI.calculate(F, AM->getResult<LoopAnalysis>(F));
+  return BPI;
+}

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   CodeMetrics.cpp
   ConstantFolding.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DominanceFrontier.cpp
+  DynamicInstructionCount.cpp
   GlobalsModRef.cpp
   IVUsers.cpp
   InlineCost.cpp
   InstCount.cpp
   InstructionSimplify.cpp
   Interval.cpp
   IntervalPartition.cpp
   IteratedDominanceFrontier.cpp

lib/Analysis/DynamicInstructionCount.cpp

+//===- DynamicInstructionCount.cpp - Dynamic Instruction Count analysis ---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements dynamic instruction count analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/DynamicInstructionCount.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/InlineCost.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+
+char DynamicInstructionCountAnalysis::PassID;
+
+#define DEBUG_TYPE "dyninscount"
+
+DynamicInstructionCount DynamicInstructionCountAnalysis::run(
+    Function &F, AnalysisManager<Function> *AM) {
+  DynamicInstructionCount DIC;
+  CallAnalyzer CA(AM->getResult<TargetIRAnalysis>(F), nullptr, F, INT_MAX,
+                  nullptr, false);
+  SmallPtrSet<const Value *, 32> EphValues;
+  int Cost = 0, BBCost = 0;
+  uint64_t DynInsCount = 0;
+  BlockFrequencyInfo &BFI = AM->getResult<BlockFrequencyAnalysis>(F);
+  for (BasicBlock &BB : F) {
+    CA.analyzeBlock(&BB, EphValues);
+    BBCost = CA.getCost() - Cost;
+    Cost = CA.getCost();
+    BBCost /= InlineConstants::InstrCost;
+    BlockFrequency BF = BFI.getBlockFreq(&BB);
+    DEBUG(llvm::dbgs() << " BB = " << BB.getName() << " Cost = " << BBCost
+                       << " Frequency = " << BF.getFrequency() << "...\n");
+    DynInsCount += (BF.getFrequency() * BBCost);
+  }
+  uint64_t EntryFreq = BFI.getEntryFreq();
+  DynInsCount = (DynInsCount + EntryFreq / 2) / EntryFreq;
+  DIC.setCount(DynInsCount);
+  return DIC;
+}
+
+PreservedAnalyses DynamicInstructionCountPrinterPass::run(
+    Function &F, AnalysisManager<Function> *AM) {
+  DynamicInstructionCount DIC =
+      AM->getResult<DynamicInstructionCountAnalysis>(F);
+  OS << "Dynamic instruction count of " << F.getName() << ": " << DIC.getCount()
+     << "\n";
+  return PreservedAnalyses::all();
+}

lib/Analysis/InlineCost.cpp

 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "inline-cost"
 
 STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
 
-namespace {
-
-class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
-  typedef InstVisitor<CallAnalyzer, bool> Base;
-  friend class InstVisitor<CallAnalyzer, bool>;
-
-  /// The TargetTransformInfo available for this compilation.
-  const TargetTransformInfo &TTI;
-
-  /// The cache of @llvm.assume intrinsics.
-  AssumptionCacheTracker *ACT;
-
-  // The called function.
-  Function &F;
-
-  // The candidate callsite being analyzed. Please do not use this to do
-  // analysis in the caller function; we want the inline cost query to be
-  // easily cacheable. Instead, use the cover function paramHasAttr.
-  CallSite CandidateCS;
-
-  int Threshold;
-  int Cost;
-
-  bool IsCallerRecursive;
-  bool IsRecursiveCall;
-  bool ExposesReturnsTwice;
-  bool HasDynamicAlloca;
-  bool ContainsNoDuplicateCall;
-  bool HasReturn;
-  bool HasIndirectBr;
-  bool HasFrameEscape;
-
-  /// Number of bytes allocated statically by the callee.
-  uint64_t AllocatedSize;
-  unsigned NumInstructions, NumVectorInstructions;
-  int FiftyPercentVectorBonus, TenPercentVectorBonus;
-  int VectorBonus;
-
-  // While we walk the potentially-inlined instructions, we build up and
-  // maintain a mapping of simplified values specific to this callsite. The
-  // idea is to propagate any special information we have about arguments to
-  // this call through the inlinable section of the function, and account for
-  // likely simplifications post-inlining. The most important aspect we track
-  // is CFG altering simplifications -- when we prove a basic block dead, that
-  // can cause dramatic shifts in the cost of inlining a function.
-  DenseMap<Value *, Constant *> SimplifiedValues;
-
-  // Keep track of the values which map back (through function arguments) to
-  // allocas on the caller stack which could be simplified through SROA.
-  DenseMap<Value *, Value *> SROAArgValues;
-
-  // The mapping of caller Alloca values to their accumulated cost savings. If
-  // we have to disable SROA for one of the allocas, this tells us how much
-  // cost must be added.
-  DenseMap<Value *, int> SROAArgCosts;
-
-  // Keep track of values which map to a pointer base and constant offset.
-  DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs;
-
-  // Custom simplification helper routines.
-  bool isAllocaDerivedArg(Value *V);
-  bool lookupSROAArgAndCost(Value *V, Value *&Arg,
-                            DenseMap<Value *, int>::iterator &CostIt);
-  void disableSROA(DenseMap<Value *, int>::iterator CostIt);
-  void disableSROA(Value *V);
-  void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
-                          int InstructionCost);
-  bool isGEPOffsetConstant(GetElementPtrInst &GEP);
-  bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
-  bool simplifyCallSite(Function *F, CallSite CS);
-  ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
-
-  /// Return true if the given argument to the function being considered for
-  /// inlining has the given attribute set either at the call site or the
-  /// function declaration.  Primarily used to inspect call site specific
-  /// attributes since these can be more precise than the ones on the callee
-  /// itself. 
-  bool paramHasAttr(Argument *A, Attribute::AttrKind Attr);
-  
-  /// Return true if the given value is known non null within the callee if
-  /// inlined through this particular callsite. 
-  bool isKnownNonNullInCallee(Value *V);
-
-  // Custom analysis routines.
-  bool analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues);
-
-  // Disable several entry points to the visitor so we don't accidentally use
-  // them by declaring but not defining them here.
-  void visit(Module *);     void visit(Module &);
-  void visit(Function *);   void visit(Function &);
-  void visit(BasicBlock *); void visit(BasicBlock &);
-
-  // Provide base case for our instruction visit.
-  bool visitInstruction(Instruction &I);
-
-  // Our visit overrides.
-  bool visitAlloca(AllocaInst &I);
-  bool visitPHI(PHINode &I);
-  bool visitGetElementPtr(GetElementPtrInst &I);
-  bool visitBitCast(BitCastInst &I);
-  bool visitPtrToInt(PtrToIntInst &I);
-  bool visitIntToPtr(IntToPtrInst &I);
-  bool visitCastInst(CastInst &I);
-  bool visitUnaryInstruction(UnaryInstruction &I);
-  bool visitCmpInst(CmpInst &I);
-  bool visitSub(BinaryOperator &I);
-  bool visitBinaryOperator(BinaryOperator &I);
-  bool visitLoad(LoadInst &I);
-  bool visitStore(StoreInst &I);
-  bool visitExtractValue(ExtractValueInst &I);
-  bool visitInsertValue(InsertValueInst &I);
-  bool visitCallSite(CallSite CS);
-  bool visitReturnInst(ReturnInst &RI);
-  bool visitBranchInst(BranchInst &BI);
-  bool visitSwitchInst(SwitchInst &SI);
-  bool visitIndirectBrInst(IndirectBrInst &IBI);
-  bool visitResumeInst(ResumeInst &RI);
-  bool visitCleanupReturnInst(CleanupReturnInst &RI);
-  bool visitCatchReturnInst(CatchReturnInst &RI);
-  bool visitUnreachableInst(UnreachableInst &I);
-
-public:
-  CallAnalyzer(const TargetTransformInfo &TTI, AssumptionCacheTracker *ACT,
-               Function &Callee, int Threshold, CallSite CSArg)
-    : TTI(TTI), ACT(ACT), F(Callee), CandidateCS(CSArg), Threshold(Threshold),
-        Cost(0), IsCallerRecursive(false), IsRecursiveCall(false),
-        ExposesReturnsTwice(false), HasDynamicAlloca(false),
-        ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
-        HasFrameEscape(false), AllocatedSize(0), NumInstructions(0),
-        NumVectorInstructions(0), FiftyPercentVectorBonus(0),
-        TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0),
-        NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0),
-        NumConstantPtrDiffs(0), NumInstructionsSimplified(0),
-        SROACostSavings(0), SROACostSavingsLost(0) {}
-
-  bool analyzeCall(CallSite CS);
-
-  int getThreshold() { return Threshold; }
-  int getCost() { return Cost; }
-
-  // Keep a bunch of stats about the cost savings found so we can print them
-  // out when debugging.
-  unsigned NumConstantArgs;
-  unsigned NumConstantOffsetPtrArgs;
-  unsigned NumAllocaArgs;
-  unsigned NumConstantPtrCmps;
-  unsigned NumConstantPtrDiffs;
-  unsigned NumInstructionsSimplified;
-  unsigned SROACostSavings;
-  unsigned SROACostSavingsLost;
-
-  void dump();
-};
-
-} // namespace
+CallAnalyzer::CallAnalyzer(const TargetTransformInfo &TTI,
+                           AssumptionCacheTracker *ACT, Function &Callee,
+                           int Threshold, CallSite *CSArg, bool Inlining)
+    : TTI(TTI),
+      ACT(ACT),
+      F(Callee),
+      CandidateCS(CSArg),
+      Threshold(Threshold),
+      Cost(0),
+      IsCallerRecursive(false),
+      IsRecursiveCall(false),
+      ExposesReturnsTwice(false),
+      HasDynamicAlloca(false),
+      ContainsNoDuplicateCall(false),
+      HasReturn(false),
+      HasIndirectBr(false),
+      HasFrameEscape(false),
+      AllocatedSize(0),
+      NumInstructions(0),
+      NumVectorInstructions(0),
+      FiftyPercentVectorBonus(0),
+      TenPercentVectorBonus(0),
+      VectorBonus(0),
+      Inlining(Inlining),
+      NumConstantArgs(0),
+      NumConstantOffsetPtrArgs(0),
+      NumAllocaArgs(0),
+      NumConstantPtrCmps(0),
+      NumConstantPtrDiffs(0),
+      NumInstructionsSimplified(0),
+      SROACostSavings(0),
+      SROACostSavingsLost(0) {}
 
 /// \brief Test whether the given value is an Alloca-derived function argument.
 bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
   return SROAArgValues.count(V);
 }
 
 /// \brief Lookup the SROA-candidate argument and cost iterator which V maps to.
 /// Returns false if V does not map to a SROA-candidate.
bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) {
   // Disable any SROA on the argument to arbitrary unary operators.
   disableSROA(Operand);
 
   return false;
 }
 
 bool CallAnalyzer::paramHasAttr(Argument *A, Attribute::AttrKind Attr) {
   unsigned ArgNo = A->getArgNo();
-  return CandidateCS.paramHasAttr(ArgNo+1, Attr);
+  return CandidateCS ? CandidateCS->paramHasAttr(ArgNo + 1, Attr) : false;
 }
 
 bool CallAnalyzer::isKnownNonNullInCallee(Value *V) {
   // Does the *call site* have the NonNull attribute set on an argument?  We
   // use the attribute on the call site to memoize any analysis done in the
   // caller. This will also trip if the callee function has a non-null
   // parameter attribute, but that's a less interesting case because hopefully
   // the callee would already have been simplified based on that.
if (Constant *C = ConstantFoldCall(F, ConstantArgs)) {
     SimplifiedValues[CS.getInstruction()] = C;
     return true;
   }
 
   return false;
 }
 
 bool CallAnalyzer::visitCallSite(CallSite CS) {
-  if (CS.hasFnAttr(Attribute::ReturnsTwice) &&
+  if (Inlining && CS.hasFnAttr(Attribute::ReturnsTwice) &&
       !F.hasFnAttribute(Attribute::ReturnsTwice)) {
     // This aborts the entire analysis.
     ExposesReturnsTwice = true;
     return false;
   }
   if (CS.isCall() &&
       cast<CallInst>(CS.getInstruction())->cannotDuplicate())
     ContainsNoDuplicateCall = true;
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
         // SROA can usually chew through these intrinsics, but they aren't free.
         return false;
       case Intrinsic::localescape:
         HasFrameEscape = true;
         return false;
       }
     }
 
-    if (F == CS.getInstruction()->getParent()->getParent()) {
+    if (Inlining && F == CS.getInstruction()->getParent()->getParent()) {
       // This flag will fully abort the analysis, so don't bother with anything
       // else.
       IsRecursiveCall = true;
       return false;
     }
 
     if (TTI.isLoweredToCall(F)) {
       // We account for the average 1 instruction per call argument setup
bool CallAnalyzer::visitCallSite(CallSite CS) {
 
   // First, pay the price of the argument setup. We account for the average
   // 1 instruction per call argument setup here.
   Cost += CS.arg_size() * InlineConstants::InstrCost;
 
   // Next, check if this happens to be an indirect function call to a known
   // function in this inline context. If not, we've done all we can.
   Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee));
-  if (!F)
-    return Base::visitCallSite(CS);
+  if (!F || !Inlining) return Base::visitCallSite(CS);
 
   // If we have a constant that we are calling as a function, we can peer
   // through it and see the function target. This happens not infrequently
   // during devirtualization and so we want to give it a hefty bonus for
   // inlining, but cap that bonus in the event that inlining wouldn't pan
   // out. Pretend to inline the function, with a custom threshold.
-  CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold, CS);
+  CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold, &CS);
   if (CA.analyzeCall(CS)) {
     // We were able to inline the indirect call! Subtract the cost from the
     // bonus we want to apply, but don't go below zero.
     Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost());
   }
 
   return Base::visitCallSite(CS);
 }
 
 bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
   // At least one return instruction will be free after inlining.
-  bool Free = !HasReturn;
+  bool Free = !HasReturn && Inlining;
   HasReturn = true;
   return Free;
 }
 
 bool CallAnalyzer::visitBranchInst(BranchInst &BI) {
   // We model unconditional branches as essentially free -- they really
   // shouldn't exist at all, but handling them makes the behavior of the
   // inliner more regular and predictable. Interestingly, conditional branches
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
     // all of the per-instruction logic. The visit tree returns true if we
     // consumed the instruction in any way, and false if the instruction's base
     // cost should count against inlining.
     if (Base::visit(&*I))
       ++NumInstructionsSimplified;
     else
       Cost += InlineConstants::InstrCost;
 
+    if (!Inlining) continue;
+
     // If the visit this instruction detected an uninlinable pattern, abort.
     if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
         HasIndirectBr || HasFrameEscape)
       return false;
 
     // If the caller is a recursive function then we don't want to inline
     // functions which allocate a lot of stack space because it would increase
     // the caller stack usage dramatically.
InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, Function *Callee,
   // marked noinline.
   if (Callee->mayBeOverridden() ||
       Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline())
     return llvm::InlineCost::getNever();
 
   DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
         << "...\n");
 
-  CallAnalyzer CA(TTIWP->getTTI(*Callee), ACT, *Callee, Threshold, CS);
+  CallAnalyzer CA(TTIWP->getTTI(*Callee), ACT, *Callee, Threshold, &CS);
   bool ShouldInline = CA.analyzeCall(CS);
 
   DEBUG(CA.dump());
 
   // Check if there was a reason to force inlining or no inlining.
   if (!ShouldInline && CA.getCost() < CA.getThreshold())
     return InlineCost::getNever();
   if (ShouldInline && CA.getCost() >= CA.getThreshold())

lib/Passes/PassBuilder.cpp

 /// static pass registry as well as related functionality. It also provides
 /// helpers to aid in analyzing, debugging, and testing passes and pass
 /// pipelines.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Passes/PassBuilder.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/DynamicInstructionCount.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/PassManager.h"

lib/Passes/PassRegistry.def

 #undef CGSCC_PASS
 
 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())
 FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
+FUNCTION_ANALYSIS("branchprob", BranchProbabilityAnalysis())
+FUNCTION_ANALYSIS("blockfreq", BlockFrequencyAnalysis())
+FUNCTION_ANALYSIS("dyninscount", DynamicInstructionCountAnalysis())
 FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis())
 FUNCTION_ANALYSIS("scalar-evolution", ScalarEvolutionAnalysis())
 FUNCTION_ANALYSIS("targetlibinfo", TargetLibraryAnalysis())
 FUNCTION_ANALYSIS("targetir",
                   TM ? TM->getTargetIRAnalysis() : TargetIRAnalysis())
 #undef FUNCTION_ANALYSIS
 
 #ifndef FUNCTION_PASS
 #define FUNCTION_PASS(NAME, CREATE_PASS)
 #endif
 FUNCTION_PASS("early-cse", EarlyCSEPass())
 FUNCTION_PASS("instcombine", InstCombinePass())
 FUNCTION_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 FUNCTION_PASS("no-op-function", NoOpFunctionPass())
 FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass())
 FUNCTION_PASS("print", PrintFunctionPass(dbgs()))
 FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<loops>", LoopPrinterPass(dbgs()))
+FUNCTION_PASS("print<dyninscount>", DynamicInstructionCountPrinterPass(dbgs()))
 FUNCTION_PASS("print<scalar-evolution>", ScalarEvolutionPrinterPass(dbgs()))
 FUNCTION_PASS("simplify-cfg", SimplifyCFGPass())
 FUNCTION_PASS("sroa", SROA())
 FUNCTION_PASS("verify", VerifierPass())
 FUNCTION_PASS("verify<domtree>", DominatorTreeVerifierPass())
 #undef FUNCTION_PASS

test/Analysis/DynamicInstructionCount/basic.ll

+; RUN: opt < %s -passes='print<dyninscount>' -disable-output 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @f0() {
+; CHECK: Dynamic instruction count of f0: 1
+entry:
+  ret i32 0
+}
+
+define i32 @f1(i32 %i) {
+; CHECK: Dynamic instruction count of f1: 2
+entry:
+  %add = add nsw i32 %i, 1
+  ret i32 %add
+}
+
+define void @f2(i32* nocapture %ptr) {
+; CHECK: Dynamic instruction count of f2: 97
+entry:
+; Dynamic instructions in this block = 0 (unconditional branch)
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+; Dynamic instructions in this block = 1
+  ret void
+
+for.body:                                         ; preds = %for.body, %entry
+; Static instructions in this block = 3 (phi is not counted)
+; Dynamic instructions in this block = 3 * 32 = 96
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1000
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+define i32 @f3(i32 %i) {
+; CHECK: Dynamic instruction count of f3: 3
+entry:
+  %cmp = icmp sgt i32 %i, 10
+  br i1 %cmp, label %if.then, label %if.else
+if.then:
+  ret i32 0
+if.else:
+  ret i32 1
+}