[BPI] Look-up tables for non-loop branches. NFC.

[SjoerdMeijer]

Summary

I wanted to check and cross reference which heuristics we have implemented and didn't find it very easy to extract that information because everything is inlined in different functions. That's why I have created different lookup tables that should make this clearer.

[nikic]

This doesn't really look better than the previous code to me personally, but I'm not involved with BPI either...

[yrouban]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

132–133

not needed

[yrouban]

instead of storing a bool value (swap the probability or not) it would be better to store final array of branch probabilities to set so it would not need to define probabilities every time and optionally swap them.

auto Search = PointerTable.find(CI->getPredicate());
if (Search == PointerTable.end())
  return false;
setEdgeProbability(BB, Search->second);
return true;

llvm/lib/Analysis/BranchProbabilityInfo.cpp

87

+const

[SjoerdMeijer]

Thanks for the suggestion, the probabilities are now encoded directly into the tables.

I thought this table based approach to be compacter and thus easier to check. If this is not the case, we can revisit it, or I can abandon change as as I don't have too strong opinions (but again, I thought it would help a bit) . And while doing this, I noticed tests for pointer heuristics are missing, so added them.

[yrouban]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

130–131

I do not see any diff between these two lines. I think one is enough: p != q -> Likely.

132

value followed by comment would be more concise, like the following:

{ ICmpInst::ICMP_NE, { PtrTakenProb, PtrUntakenProb } }, // p != q  ->  Likely.

[SjoerdMeijer]

Thanks for reviewing, and I will address your comments before committing.

llvm/lib/Analysis/BranchProbabilityInfo.cpp

 //
 // Using "Loop Branch Heuristics" we predict weights of edges for the
 // block BB2.
 //         ...
 //          |
 //          V
 //         BB1<-+
 //          |   |
 //          |   | (Weight = 124)
 //          V   |
 //         BB2--+
 //          |
 //          | (Weight = 4)
 //          V
 //         BB3
 //
 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
 static const uint32_t LBH_TAKEN_WEIGHT = 124;
 static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
 
 /// Unreachable-terminating branch taken probability.
 ///
 /// This is the probability for a branch being taken to a block that terminates
 /// (eventually) in unreachable. These are predicted as unlikely as possible.
 /// All reachable probability will proportionally share the remaining part.
 static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
 
+/// Heuristics and lookup tables for non-loop branches:
+/// Pointer Heuristics (PH)
 static const uint32_t PH_TAKEN_WEIGHT = 20;
 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
+static const BranchProbability
+    PtrTakenProb(PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
+static const BranchProbability
+    PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
+
+using ProbabilityList = SmallVector<BranchProbability>;
+using ProbabilityTable = std::map<CmpInst::Predicate, ProbabilityList>;
+
+/// Pointer comparisons:
+static const ProbabilityTable PointerTable{
+    {ICmpInst::ICMP_NE, {PtrTakenProb, PtrUntakenProb}}, /// p != q -> Likely
+    {ICmpInst::ICMP_EQ, {PtrUntakenProb, PtrTakenProb}}, /// p == q -> Unlikely
+};
 
+/// Zero Heuristics (ZH)
 static const uint32_t ZH_TAKEN_WEIGHT = 20;
 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
+static const BranchProbability
+    ZeroTakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
+static const BranchProbability
+    ZeroUntakenProb(ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
+
+/// Integer compares with 0:
+static const ProbabilityTable ICmpWithZeroTable{
+    {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}},  /// X == 0 -> Unlikely
+    {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}},  /// X != 0 -> Likely
+    {CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}}, /// X < 0  -> Unlikely
+    {CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}}, /// X > 0  -> Likely
+};
+
+/// Integer compares with -1:
+static const ProbabilityTable ICmpWithMinusOneTable{
+    {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}},  /// X == -1 -> Unlikely
+    {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}},  /// X != -1 -> Likely
+    // InstCombine canonicalizes X >= 0 into X > -1
+    {CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}}, /// X >= 0  -> Likely
+};
+
+/// Integer compares with 1:
+static const ProbabilityTable ICmpWithOneTable{
+    // InstCombine canonicalizes X <= 0 into X < 1
+    {CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}}, /// X <= 0 -> Unlikely
+};
+
+/// strcmp and similar functions return zero, negative, or positive, if the
+/// first string is equal, less, or greater than the second. We consider it
+/// likely that the strings are not equal, so a comparison with zero is
+/// probably false, but also a comparison with any other number is also
+/// probably false given that what exactly is returned for nonzero values is
+/// not specified. Any kind of comparison other than equality we know
+/// nothing about.
+static const ProbabilityTable ICmpWithLibCallTable{
+    {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}},
+    {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}},
+};
 
+// Floating-Point Heuristics (FPH)
 static const uint32_t FPH_TAKEN_WEIGHT = 20;
 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
 
 /// This is the probability for an ordered floating point comparison.
 static const uint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1;
 /// This is the probability for an unordered floating point comparison, it means
 /// one or two of the operands are NaN. Usually it is used to test for an
 /// exceptional case, so the result is unlikely.
 static const uint32_t FPH_UNO_WEIGHT = 1;
 
+static const BranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT,
+                                              FPH_ORD_WEIGHT + FPH_UNO_WEIGHT);
+static const BranchProbability
+    FPOrdUntakenProb(FPH_UNO_WEIGHT, FPH_ORD_WEIGHT + FPH_UNO_WEIGHT);
+static const BranchProbability
+    FPTakenProb(FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
+static const BranchProbability
+    FPUntakenProb(FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
+
+/// Floating-Point compares:
+static const ProbabilityTable FCmpTable{
+    {FCmpInst::FCMP_ORD, {FPOrdTakenProb, FPOrdUntakenProb}}, /// !isnan -> Likely
+    {FCmpInst::FCMP_UNO, {FPOrdUntakenProb, FPOrdTakenProb}}, /// isnan -> Unlikely
+};
+
 /// Set of dedicated "absolute" execution weights for a block. These weights are
 /// meaningful relative to each other and their derivatives only.
 enum class BlockExecWeight : std::uint32_t {
   /// Special weight used for cases with exact zero probability.
   ZERO = 0x0,
   /// Minimal possible non zero weight.
   LOWEST_NON_ZERO = 0x1,
   /// Weight to an 'unreachable' block.
bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
 
   Value *LHS = CI->getOperand(0);
 
   if (!LHS->getType()->isPointerTy())
     return false;
 
   assert(CI->getOperand(1)->getType()->isPointerTy());
 
-  BranchProbability TakenProb(PH_TAKEN_WEIGHT,
-                              PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
-  BranchProbability UntakenProb(PH_NONTAKEN_WEIGHT,
-                                PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
-
-  // p != 0   ->   isProb = true
-  // p == 0   ->   isProb = false
-  // p != q   ->   isProb = true
-  // p == q   ->   isProb = false;
-  bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
-  if (!isProb)
-    std::swap(TakenProb, UntakenProb);
-
-  setEdgeProbability(
-      BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
+  auto Search = PointerTable.find(CI->getPredicate());
+  if (Search == PointerTable.end())
+    return false;
+  setEdgeProbability(BB, Search->second);
   return true;
 }
 
 // Compute the unlikely successors to the block BB in the loop L, specifically
 // those that are unlikely because this is a loop, and add them to the
 // UnlikelyBlocks set.
 static void
 computeUnlikelySuccessors(const BasicBlock *BB, Loop *L,
bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
 
   // Check if the LHS is the return value of a library function
   LibFunc Func = NumLibFuncs;
   if (TLI)
     if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
       if (Function *CalledFn = Call->getCalledFunction())
         TLI->getLibFunc(*CalledFn, Func);
 
-  bool isProb;
+  ProbabilityTable::const_iterator Search;
   if (Func == LibFunc_strcasecmp ||
       Func == LibFunc_strcmp ||
       Func == LibFunc_strncasecmp ||
       Func == LibFunc_strncmp ||
       Func == LibFunc_memcmp ||
       Func == LibFunc_bcmp) {
-    // strcmp and similar functions return zero, negative, or positive, if the
-    // first string is equal, less, or greater than the second. We consider it
-    // likely that the strings are not equal, so a comparison with zero is
-    // probably false, but also a comparison with any other number is also
-    // probably false given that what exactly is returned for nonzero values is
-    // not specified. Any kind of comparison other than equality we know
-    // nothing about.
-    switch (CI->getPredicate()) {
-    case CmpInst::ICMP_EQ:
-      isProb = false;
-      break;
-    case CmpInst::ICMP_NE:
-      isProb = true;
-      break;
-    default:
+    Search = ICmpWithLibCallTable.find(CI->getPredicate());
+    if (Search == ICmpWithLibCallTable.end())
       return false;
-    }
   } else if (CV->isZero()) {
-    switch (CI->getPredicate()) {
-    case CmpInst::ICMP_EQ:
-      // X == 0   ->  Unlikely
-      isProb = false;
-      break;
-    case CmpInst::ICMP_NE:
-      // X != 0   ->  Likely
-      isProb = true;
-      break;
-    case CmpInst::ICMP_SLT:
-      // X < 0   ->  Unlikely
-      isProb = false;
-      break;
-    case CmpInst::ICMP_SGT:
-      // X > 0   ->  Likely
-      isProb = true;
-      break;
-    default:
+    Search = ICmpWithZeroTable.find(CI->getPredicate());
+    if (Search == ICmpWithZeroTable.end())
+      return false;
+  } else if (CV->isOne()) {
+    Search = ICmpWithOneTable.find(CI->getPredicate());
+    if (Search == ICmpWithOneTable.end())
       return false;
-    }
-  } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
-    // InstCombine canonicalizes X <= 0 into X < 1.
-    // X <= 0   ->  Unlikely
-    isProb = false;
   } else if (CV->isMinusOne()) {
-    switch (CI->getPredicate()) {
-    case CmpInst::ICMP_EQ:
-      // X == -1  ->  Unlikely
-      isProb = false;
-      break;
-    case CmpInst::ICMP_NE:
-      // X != -1  ->  Likely
-      isProb = true;
-      break;
-    case CmpInst::ICMP_SGT:
-      // InstCombine canonicalizes X >= 0 into X > -1.
-      // X >= 0   ->  Likely
-      isProb = true;
-      break;
-    default:
+    Search = ICmpWithMinusOneTable.find(CI->getPredicate());
+    if (Search == ICmpWithMinusOneTable.end())
       return false;
-    }
   } else {
     return false;
   }
 
-  BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
-                              ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
-  BranchProbability UntakenProb(ZH_NONTAKEN_WEIGHT,
-                                ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
-  if (!isProb)
-    std::swap(TakenProb, UntakenProb);
-
-  setEdgeProbability(
-      BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
+  setEdgeProbability(BB, Search->second);
   return true;
 }
 
 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
   if (!BI || !BI->isConditional())
     return false;
 
   Value *Cond = BI->getCondition();
   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
   if (!FCmp)
     return false;
 
-  uint32_t TakenWeight = FPH_TAKEN_WEIGHT;
-  uint32_t NontakenWeight = FPH_NONTAKEN_WEIGHT;
-  bool isProb;
+  ProbabilityList ProbList;
   if (FCmp->isEquality()) {
+    ProbList = !FCmp->isTrueWhenEqual() ?
       // f1 == f2 -> Unlikely
+      ProbabilityList({FPTakenProb, FPUntakenProb}) :
       // f1 != f2 -> Likely
-    isProb = !FCmp->isTrueWhenEqual();
-  } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
-    // !isnan -> Likely
-    isProb = true;
-    TakenWeight = FPH_ORD_WEIGHT;
-    NontakenWeight = FPH_UNO_WEIGHT;
-  } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
-    // isnan -> Unlikely
-    isProb = false;
-    TakenWeight = FPH_ORD_WEIGHT;
-    NontakenWeight = FPH_UNO_WEIGHT;
+      ProbabilityList({FPUntakenProb, FPTakenProb});
   } else {
+    auto Search = FCmpTable.find(FCmp->getPredicate());
+    if (Search == FCmpTable.end())
       return false;
+    ProbList = Search->second;
   }
 
-  BranchProbability TakenProb(TakenWeight, TakenWeight + NontakenWeight);
-  BranchProbability UntakenProb(NontakenWeight, TakenWeight + NontakenWeight);
-  if (!isProb)
-    std::swap(TakenProb, UntakenProb);
-
-  setEdgeProbability(
-      BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
+  setEdgeProbability(BB, ProbList);
   return true;
 }
 
 void BranchProbabilityInfo::releaseMemory() {
   Probs.clear();
   Handles.clear();
 }
 

llvm/test/Analysis/BranchProbabilityInfo/pointer_heuristics.ll

+; RUN: opt < %s -passes='print<branch-prob>' -disable-output 2>&1 | FileCheck %s
+
+define i32 @cmp1(i32* readnone %0, i32* readnone %1) {
+; CHECK: Printing analysis results of BPI for function 'cmp1':
+  %3 = icmp eq i32* %0, %1
+  br i1 %3, label %4, label %6
+; CHECK:   edge  ->  probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK:   edge  ->  probability is 0x50000000 / 0x80000000 = 62.50%
+
+4:                                                ; preds = %2
+  %5 = tail call i32 bitcast (i32 (...)* @f to i32 ()*)() #2
+  br label %8
+; CHECK:   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+6:                                                ; preds = %2
+  %7 = tail call i32 bitcast (i32 (...)* @g to i32 ()*)() #2
+  br label %8
+; CHECK:   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+8:                                                ; preds = %6, %4
+  %9 = phi i32 [ %5, %4 ], [ %7, %6 ]
+  ret i32 %9
+}
+
+define i32 @cmp2(i32* readnone %0, i32* readnone %1) {
+; CHECK: Printing analysis results of BPI for function 'cmp2':
+  %3 = icmp eq i32* %0, %1
+  br i1 %3, label %6, label %4
+; CHECK:   edge  ->  probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK:   edge  ->  probability is 0x50000000 / 0x80000000 = 62.50%
+
+4:                                                ; preds = %2
+  %5 = tail call i32 bitcast (i32 (...)* @f to i32 ()*)() #2
+  br label %8
+; CHECK:   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+6:                                                ; preds = %2
+  %7 = tail call i32 bitcast (i32 (...)* @g to i32 ()*)() #2
+  br label %8
+; CHECK:   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+8:                                                ; preds = %6, %4
+  %9 = phi i32 [ %5, %4 ], [ %7, %6 ]
+  ret i32 %9
+}
+
+; CHECK: Printing analysis results of BPI for function 'cmp3':
+define i32 @cmp3(i32* readnone %0) {
+  %2 = icmp eq i32* %0, null
+  br i1 %2, label %3, label %5
+; CHECK:   edge  ->  probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK:   edge  ->  probability is 0x50000000 / 0x80000000 = 62.50%
+
+3:                                                ; preds = %1
+  %4 = tail call i32 bitcast (i32 (...)* @f to i32 ()*)() #2
+  br label %7
+; CHECK:   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+5:                                                ; preds = %1
+  %6 = tail call i32 bitcast (i32 (...)* @g to i32 ()*)() #2
+  br label %7
+; CHECK:   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+
+7:                                                ; preds = %5, %3
+  %8 = phi i32 [ %6, %5 ], [ %4, %3 ]
+  ret i32 %8
+}
+
+declare dso_local i32 @f(...) local_unnamed_addr #1
+declare dso_local i32 @g(...) local_unnamed_addr #1