[PM] Port BranchProbability Analysis to the new pass manager

[davidxl]

Summary

This patch ports the Analysis pass that computes BPI to the new pass manager.

There is a slight difference in printer output -- the header line format is different. This should be revisited later.

[davidxl]

Updated patch according to Justin's comments.

include/llvm/Analysis/BranchProbabilityInfo.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
 #define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/PassManager.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/BranchProbability.h"
 
 namespace llvm {
 class LoopInfo;
 class raw_ostream;
 

 /// value 10.
 class BranchProbabilityInfo {
 public:
   BranchProbabilityInfo() {}
   BranchProbabilityInfo(const Function &F, const LoopInfo &LI) {
     calculate(F, LI);
   }
 
+  BranchProbabilityInfo(BranchProbabilityInfo &&Arg)
+      : Probs(std::move(Arg.Probs)), LastF(Arg.LastF),
+        PostDominatedByUnreachable(std::move(Arg.PostDominatedByUnreachable)),
+        PostDominatedByColdCall(std::move(Arg.PostDominatedByColdCall)) {}
+
+  BranchProbabilityInfo &operator=(BranchProbabilityInfo &&RHS) {
+    releaseMemory();
+    Probs = std::move(RHS.Probs);
+    PostDominatedByColdCall = std::move(RHS.PostDominatedByColdCall);
+    PostDominatedByUnreachable = std::move(RHS.PostDominatedByUnreachable);
+    return *this;
+  }
+
   void releaseMemory();
 
   void print(raw_ostream &OS) const;
 
   /// \brief Get an edge's probability, relative to other out-edges of the Src.
   ///
   /// This routine provides access to the fractional probability between zero
   /// (0%) and one (100%) of this edge executing, relative to other edges
public:
   static BranchProbability getBranchProbStackProtector(bool IsLikely) {
     static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);
     return IsLikely ? LikelyProb : LikelyProb.getCompl();
   }
 
   void calculate(const Function &F, const LoopInfo &LI);
 
 private:
+  void operator=(const BranchProbabilityInfo &) = delete;
+  BranchProbabilityInfo(const BranchProbabilityInfo &) = delete;
+
   // Since we allow duplicate edges from one basic block to another, we use
   // a pair (PredBlock and an index in the successors) to specify an edge.
   typedef std::pair<const BasicBlock *, unsigned> Edge;
 
   // Default weight value. Used when we don't have information about the edge.
   // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of
   // the successors have a weight yet. But it doesn't make sense when providing
   // weight to an edge that may have siblings with non-zero weights. This can
private:
   bool calcColdCallHeuristics(const BasicBlock *BB);
   bool calcPointerHeuristics(const BasicBlock *BB);
   bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI);
   bool calcZeroHeuristics(const BasicBlock *BB);
   bool calcFloatingPointHeuristics(const BasicBlock *BB);
   bool calcInvokeHeuristics(const BasicBlock *BB);
 };
 
+/// \brief Analysis pass which computes \c BranchProbabilityInfo.
+class BranchProbabilityAnalysis
+    : public AnalysisInfoMixin<BranchProbabilityAnalysis> {
+  friend AnalysisInfoMixin<BranchProbabilityAnalysis>;
+  static char PassID;
+
+public:
+  /// \brief Provide the result typedef for this analysis pass.
+  typedef BranchProbabilityInfo Result;
+
+  /// \brief Run the analysis pass over a function and produce BPI.
+  BranchProbabilityInfo run(Function &F, AnalysisManager<Function> &AM);
+};
+
+/// \brief Printer pass for the \c BranchProbabilityAnalysis results.
+class BranchProbabilityPrinterPass
+    : public PassInfoMixin<BranchProbabilityPrinterPass> {
+  raw_ostream &OS;
+
+public:
+  explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {}
+  PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
+};
+
 /// \brief Legacy analysis pass which computes \c BranchProbabilityInfo.
 class BranchProbabilityInfoWrapperPass : public FunctionPass {
   BranchProbabilityInfo BPI;
 
 public:
   static char ID;
 
   BranchProbabilityInfoWrapperPass() : FunctionPass(ID) {

lib/Analysis/BranchProbabilityInfo.cpp

 }
 
 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;
+}
+
+PreservedAnalyses
+BranchProbabilityPrinterPass::run(Function &F, AnalysisManager<Function> &AM) {
+  OS << "Printing analysis results of BPI for function "
+     << "'" << F.getName() << "':"
+     << "\n";
+  AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
+  return PreservedAnalyses::all();
+}

lib/Passes/PassBuilder.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Passes/PassBuilder.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFLAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/DemandedBits.h"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LoopInfo.h"

lib/Passes/PassRegistry.def

 CGSCC_PASS("no-op-cgscc", NoOpCGSCCPass())
 #undef CGSCC_PASS
 
 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ANALYSIS("aa", AAManager())
 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())
+FUNCTION_ANALYSIS("branch-prob", BranchProbabilityAnalysis())
 FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis())
 FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis())
 FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis())
 FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
 FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis())
 FUNCTION_ANALYSIS("regions", RegionInfoAnalysis())
 FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis())

 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("gvn", GVN())
 FUNCTION_PASS("print", PrintFunctionPass(dbgs()))
 FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs()))
+FUNCTION_PASS("print<branch-prob>", BranchProbabilityPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<demanded-bits>", DemandedBitsPrinterPass(dbgs()))
 FUNCTION_PASS("print<domfrontier>", DominanceFrontierPrinterPass(dbgs()))
 FUNCTION_PASS("print<loops>", LoopPrinterPass(dbgs()))
 FUNCTION_PASS("print<regions>", RegionInfoPrinterPass(dbgs()))
 FUNCTION_PASS("print<scalar-evolution>", ScalarEvolutionPrinterPass(dbgs()))
 FUNCTION_PASS("reassociate", ReassociatePass())

test/Analysis/BranchProbabilityInfo/basic.ll

 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+; RUN: opt < %s -passes='print<branch-prob>' -disable-output 2>&1 | FileCheck %s
 
 define i32 @test1(i32 %i, i32* %a) {
 ; CHECK: Printing analysis {{.*}} for function 'test1'
 entry:
   br label %body
 ; CHECK: edge entry -> body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 body:

test/Analysis/BranchProbabilityInfo/deopt-intrinsic.ll

 ; RUN: opt -analyze -branch-prob < %s | FileCheck %s
+; RUN: opt < %s -passes='print<branch-prob>' -disable-output 2>&1 | FileCheck %s
 
 declare i32 @llvm.experimental.deoptimize.i32(...)
 
 define i32 @test1(i32 %a, i32 %b) {
-; CHECK-LABEL: Printing analysis 'Branch Probability Analysis' for function 'test1':
+; CHECK-LABEL: Printing analysis {{.*}} for function 'test1':
 entry:
   %cond = icmp eq i32 %a, 42
   br i1 %cond, label %exit, label %deopt
 
 ; CHECK:  edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
 ; CHECK:  edge entry -> deopt probability is 0x00000800 / 0x80000000 = 0.00%
 
 deopt:
   %rval = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"() ]
   ret i32 %rval
 
 exit:
   ret i32 %b
 }

test/Analysis/BranchProbabilityInfo/loop.ll

 ; Test the static branch probability heuristics for no-return functions.
 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+; RUN: opt < %s -passes='print<branch-prob>' --disable-output 2>&1 | FileCheck %s
 
 declare void @g1()
 declare void @g2()
 declare void @g3()
 declare void @g4()
 
 define void @test1(i32 %a, i32 %b) {
 entry:

test/Analysis/BranchProbabilityInfo/noreturn.ll

 ; Test the static branch probability heuristics for no-return functions.
 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+; RUN: opt < %s -passes='print<branch-prob>' -disable-output 2>&1 | FileCheck %s
 
 declare void @abort() noreturn
 
 define i32 @test1(i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'test1'
 entry:
   %cond = icmp eq i32 %a, 42
   br i1 %cond, label %exit, label %abort

test/Analysis/BranchProbabilityInfo/pr18705.ll

 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+; RUN: opt < %s -passes='print<branch-prob>' -disable-output 2>&1 | FileCheck %s
 
 ; Since neither of while.body's out-edges is an exit or a back edge,
 ; calcLoopBranchHeuristics should return early without setting the weights.
 ; calcFloatingPointHeuristics, which is run later, sets the weights.
 ;
 ; CHECK: edge while.body -> if.then probability is 0x50000000 / 0x80000000 = 62.50%
 ; CHECK: edge while.body -> if.else probability is 0x30000000 / 0x80000000 = 37.50%
 

test/Analysis/BranchProbabilityInfo/pr22718.ll

 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+; RUN: opt < %s -passes='print<branch-prob>' -disable-output 2>&1 | FileCheck %s
 
 ; In this test, the else clause is taken about 90% of the time. This was not
 ; reflected in the probability computation because the weight is larger than
 ; the branch weight cap (about 2 billion).
 ;
 ; CHECK: edge for.body -> if.then probability is 0x0cccba45 / 0x80000000 = 10.00%
 ; CHECK: edge for.body -> if.else probability is 0x733345bb / 0x80000000 = 90.00% [HOT edge]