[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

180–181

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

182

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

 BranchProbabilityInfoWrapperPass::BranchProbabilityInfoWrapperPass()
     : FunctionPass(ID) {
   initializeBranchProbabilityInfoWrapperPassPass(
       *PassRegistry::getPassRegistry());
 }
 
 char BranchProbabilityInfoWrapperPass::ID = 0;
 
+/// Heuristics and lookup tables for non-loop branches:
+
+#define Unlikely false
+#define Likely true
+
+/// Integer compares with 0:
+///   X == 0  ->  Unlikely
+///   X != 0  ->  Likely
+///   X < 0   ->  Unlikely
+///   X > 0   ->  Likely
+static std::map<llvm::CmpInst::Predicate, bool> ICmpWithZeroTable {
+  { CmpInst::ICMP_EQ,  Unlikely },
+  { CmpInst::ICMP_NE,  Likely   },
+  { CmpInst::ICMP_SLT, Unlikely },
+  { CmpInst::ICMP_SGT, Likely   },
+};
+
+/// Integer compares with -1:
+///   X == -1  ->  Unlikely
+///   X != -1  ->  Likely
+///   X >= 0   ->  Likely   (InstCombine canonicalizes X >= 0 into X > -1)
+static std::map<llvm::CmpInst::Predicate, bool> ICmpWithMinusOneTable {
+  { CmpInst::ICMP_EQ,  Unlikely },
+  { CmpInst::ICMP_NE,  Likely   },
+  { CmpInst::ICMP_SGT, Likely   },
+};
+
+/// Integer compares with 1:
+///   X <= 0  ->  Unlikely
+///               (InstCombine canonicalizes X <= 0 into X < 1)
+static std::map<llvm::CmpInst::Predicate, bool> ICmpWithOneTable {
+  { CmpInst::ICMP_SLT, 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 std::map<llvm::CmpInst::Predicate, bool> ICmpWithLibCallTable {
+  { CmpInst::ICMP_EQ, Unlikely },
+  { CmpInst::ICMP_NE, Likely   },
+};
+
+/// Floating-Point compares:
+///   !isnan  ->  Likely
+///   isnan   ->  Unlikely
+static std::map<CmpInst::Predicate, bool> FCmpTable {
+  { FCmpInst::FCMP_ORD, Likely   },
+  { FCmpInst::FCMP_UNO, Unlikely },
+};
+
+/// Pointer comparisons:
+///   p != 0  ->  Likely
+///   p == 0  ->  Unlikely
+///   p != q  ->  Likely
+///   p == q  ->  Unlikely
+static std::map<CmpInst::Predicate, bool> PointerTable {
+  { ICmpInst::ICMP_NE, Unlikely },
+  { ICmpInst::ICMP_EQ, Likely   },
+};
+
 // Weights are for internal use only. They are used by heuristics to help to
 // estimate edges' probability. Example:
 //
 // Using "Loop Branch Heuristics" we predict weights of edges for the
 // block BB2.
 //         ...
 //          |
 //          V

 
 /// 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);
 
+// Pointer Heuristics (PH)
 static const uint32_t PH_TAKEN_WEIGHT = 20;
 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
 
+// Zero Heuristics (ZH)
 static const uint32_t ZH_TAKEN_WEIGHT = 20;
 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
 
+// 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;
 
 /// Set of dedicated "absolute" execution weights for a block. These weights are
bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
 
   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)
+  auto Search = PointerTable.find(CI->getPredicate());
+  if (Search == PointerTable.end())
+    return false;
+
+  if (!Search->second)
     std::swap(TakenProb, UntakenProb);
 
   setEdgeProbability(
       BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
   return true;
 }
 
 // Compute the unlikely successors to the block BB in the loop L, specifically
bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
 
   bool isProb;
   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:
+    auto Search = ICmpWithLibCallTable.find(CI->getPredicate());
+    if (Search == ICmpWithLibCallTable.end())
       return false;
-    }
+    isProb = Search->second;
   } 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:
+    auto Search = ICmpWithZeroTable.find(CI->getPredicate());
+    if (Search == ICmpWithZeroTable.end())
       return false;
-    }
-  } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
-    // InstCombine canonicalizes X <= 0 into X < 1.
-    // X <= 0   ->  Unlikely
-    isProb = false;
+    isProb = Search->second;
+  } else if (CV->isOne()) {
+    auto Search = ICmpWithOneTable.find(CI->getPredicate());
+    if (Search == ICmpWithOneTable.end())
+      return false;
+    isProb = Search->second;
   } 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:
+    auto Search = ICmpWithMinusOneTable.find(CI->getPredicate());
+    if (Search == ICmpWithMinusOneTable.end())
       return false;
-    }
+    isProb = Search->second;
   } 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);
bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
 
   uint32_t TakenWeight = FPH_TAKEN_WEIGHT;
   uint32_t NontakenWeight = FPH_NONTAKEN_WEIGHT;
   bool isProb;
   if (FCmp->isEquality()) {
     // f1 == f2 -> Unlikely
     // 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;
   } else {
+    auto Search = FCmpTable.find(FCmp->getPredicate());
+    if (Search == FCmpTable.end())
       return false;
+    isProb = Search->second;
+    TakenWeight = FPH_ORD_WEIGHT;
+    NontakenWeight = FPH_UNO_WEIGHT;
   }
 
   BranchProbability TakenProb(TakenWeight, TakenWeight + NontakenWeight);
   BranchProbability UntakenProb(NontakenWeight, TakenWeight + NontakenWeight);
   if (!isProb)
     std::swap(TakenProb, UntakenProb);
 
   setEdgeProbability(