1 files changed, 97 insertions, 104 deletions

diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp
index 33fdc8b628c5..856d7e90acb2 100644
--- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp
+++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp
@@ -104,12 +104,67 @@ static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
 /// 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;
 
@@ -120,6 +175,21 @@ static const uint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1;
 /// 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 {
@@ -468,21 +538,10 @@ 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)
-    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;
 }
 
@@ -949,86 +1008,33 @@ bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
       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;
 }
 
@@ -1042,34 +1048,21 @@ bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
   if (!FCmp)
     return false;
 
-  uint32_t TakenWeight = FPH_TAKEN_WEIGHT;
-  uint32_t NontakenWeight = FPH_NONTAKEN_WEIGHT;
-  bool isProb;
+  ProbabilityList ProbList;
   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;
+    ProbList = !FCmp->isTrueWhenEqual() ?
+      // f1 == f2 -> Unlikely
+      ProbabilityList({FPTakenProb, FPUntakenProb}) :
+      // f1 != f2 -> Likely
+      ProbabilityList({FPUntakenProb, FPTakenProb});
   } else {
-    return false;
+    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;
 }