[PGO] Dump branch condition type, branch probability and branch hotness as optimization remarks

[davidxl]

Summary

This feature is intended to be used to collect branch probability statistics and the statistics can be used to guided the tuning of static branch prediction (which has not been fully tuned).

Sample output from perlbmk:

: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 1) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 1) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 1061250) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 11633) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 13537184) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 146) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 1460) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 152) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 154393) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 154627) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 177) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 2) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 2) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 22) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 247756) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 3) [-Rpass-analysis=pgo-use-annot]
: eq_i32_Const is true with probability : 0x00000000 / 0x80000000 = 0.00% (total count : 3) [-Rpass-analysis=pgo-use-a

[danielcdh]

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

222

Why not directly output the const int as a number?

[davidxl]

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

222

The dump is used to collect data for static prediction tuning. Only special values like 0,1,-1 are of interest to the predictor. All other constants only need to be aggregated.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

                               "filtering option -view-bfi-func-name."));
 
 // Command line option to enable/disable memop intrinsic call.size profiling.
 static cl::opt<bool>
     PGOInstrMemOP("pgo-instr-memop", cl::init(true), cl::Hidden,
                   cl::desc("Use this option to turn on/off "
                            "memory instrinsic size profiling."));
 
+// Emit branch probability as optimization remarks.
+static cl::opt<bool>
+    EmitBranchProbability("pgo-emit-branch-prob", cl::init(false), cl::Hidden,
+                          cl::desc("When this option is on, the annotated "
+                                   "branch probability will be emitted as "
+                                   " optimization remarks: -Rpass-analysis="
+                                   "pgo-instr-use"));
+
 // Command line option to turn on CFG dot dump after profile annotation.
 // Defined in Analysis/BlockFrequencyInfo.cpp:  -pgo-view-counts
 extern cl::opt<bool> PGOViewCounts;
 
 // Command line option to specify the name of the function for CFG dump
 // Defined in Analysis/BlockFrequencyInfo.cpp:  -view-bfi-func-name=
 extern cl::opt<std::string> ViewBlockFreqFuncName;
 
 namespace {
 
+// Return a string describing the branch condition that can be
+// used in static branch probability heuristics:
+std::string getBranchCondString(Instruction *TI) {
+  BranchInst *BI = dyn_cast<BranchInst>(TI);
+  if (!BI || !BI->isConditional())
+    return std::string();
+
+  Value *Cond = BI->getCondition();
+  ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
+  if (!CI)
+    return std::string();
+
+  std::string result;
+  raw_string_ostream OS(result);
+  OS << CmpInst::getPredicateName(CI->getPredicate()) << "_";
+  CI->getOperand(0)->getType()->print(OS, true);
+
+  Value *RHS = CI->getOperand(1);
+  ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
+  if (CV) {
+    if (CV->isZero())
+      OS << "_Zero";
+    else if (CV->isOne())
+      OS << "_One";
+    else if (CV->isAllOnesValue())
+      OS << "_MinusOne";
+    else
+      OS << "_Const";
+  }
+  OS.flush();
+  return result;
+}
+
 /// The select instruction visitor plays three roles specified
 /// by the mode. In \c VM_counting mode, it simply counts the number of
 /// select instructions. In \c VM_instrument mode, it inserts code to count
 /// the number times TrueValue of select is taken. In \c VM_annotate mode,
 /// it reads the profile data and annotate the select instruction with metadata.
 enum VisitMode { VM_counting, VM_instrument, VM_annotate };
 class PGOUseFunc;
 

   SmallVector<unsigned, 4> Weights;
   for (const auto &ECI : EdgeCounts)
     Weights.push_back(scaleBranchCount(ECI, Scale));
 
   DEBUG(dbgs() << "Weight is: ";
         for (const auto &W : Weights) { dbgs() << W << " "; }
         dbgs() << "\n";);
   TI->setMetadata(llvm::LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
+  if (EmitBranchProbability) {
+    std::string BrCondStr = getBranchCondString(TI);
+    if (BrCondStr.empty())
+      return;
+
+    unsigned WSum =
+        std::accumulate(Weights.begin(), Weights.end(), 0,
+                        [](unsigned w1, unsigned w2) { return w1 + w2; });
+    uint64_t TotalCount =
+        std::accumulate(EdgeCounts.begin(), EdgeCounts.end(), 0,
+                        [](uint64_t c1, uint64_t c2) { return c1 + c2; });
+    BranchProbability BP(Weights[0], WSum);
+    std::string BranchProbStr;
+    raw_string_ostream OS(BranchProbStr);
+    OS << BP;
+    OS << " (total count : " << TotalCount << ")";
+    OS.flush();
+    Function *F = TI->getParent()->getParent();
+    emitOptimizationRemarkAnalysis(
+        F->getContext(), "pgo-use-annot", *F, TI->getDebugLoc(),
+        Twine(BrCondStr) +
+            " is true with probability : " + Twine(BranchProbStr));
+  }
 }
 
 template <> struct GraphTraits<PGOUseFunc *> {
   typedef const BasicBlock *NodeRef;
   typedef succ_const_iterator ChildIteratorType;
   typedef pointer_iterator<Function::const_iterator> nodes_iterator;
 
   static NodeRef getEntryNode(const PGOUseFunc *G) {

test/Transforms/PGOProfile/branch1.ll

 
 ; RUN: llvm-profdata merge %S/Inputs/branch1_large_count.proftext -o %t.l.profdata
 ; RUN: opt < %s -pgo-instr-use -pgo-test-profile-file=%t.l.profdata -S | FileCheck %s --check-prefix=USE-LARGE
 
 ; New PM
 ; RUN: opt < %s -passes=pgo-instr-use -pgo-test-profile-file=%t.profdata -S | FileCheck %s --check-prefix=USE
 ; RUN: opt < %s -passes=pgo-instr-use -pgo-test-profile-file=%t.l.profdata -S | FileCheck %s --check-prefix=USE-LARGE
 
+; RUN: opt < %s -pgo-instr-use -pgo-test-profile-file=%t.profdata -pass-remarks-analysis=pgo-use-annot -pgo-emit-branch-prob -S 2>&1| FileCheck %s --check-prefix=ANALYSIS
+; RUN: opt < %s -passes=pgo-instr-use -pgo-test-profile-file=%t.profdata -pass-remarks-analysis=pgo-use-annot -pgo-emit-branch-prob -S 2>&1| FileCheck %s --check-prefix=ANALYSIS
+
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 ; GEN-DARWIN-LINKONCE: target triple = "x86_64-apple-darwin"
 
 ; GEN-COMDAT: $__llvm_profile_raw_version = comdat any
 ; GEN-COMDAT: @__llvm_profile_raw_version = constant i64 {{[0-9]+}}, comdat
 ; GEN-LINKONCE: @__llvm_profile_raw_version = linkonce constant i64 {{[0-9]+}}
 ; GEN: @__profn_test_br_1 = private constant [9 x i8] c"test_br_1"

 ; GEN: if.end:
 ; GEN: call void @llvm.instrprof.increment(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @__profn_test_br_1, i32 0, i32 0), i64 25571299074, i32 2, i32 0)
   %retv = phi i32 [ %add, %if.then ], [ %i, %entry ]
   ret i32 %retv
 }
 ; USE-DAG: {{![0-9]+}} = !{i32 1, !"ProfileSummary", {{![0-9]+}}}
 ; USE-DAG: {{![0-9]+}} = !{!"DetailedSummary", {{![0-9]+}}}
 ; USE-DAG: ![[FUNC_ENTRY_COUNT]] = !{!"function_entry_count", i64 3}
+
+; ANALYSIS:remark: <unknown>:0:0: sgt_i32_Zero {{.*}}66.67% (total count : 3)