From fed6bd86172fe5286db1aba61998f42ebaefd9f3 Mon Sep 17 00:00:00 2001
From: Cong Hou <congh@google.com>
Date: Fri, 25 Sep 2015 23:09:59 +0000
Subject: [PATCH] Use fixed-point representation for BranchProbability.

BranchProbability now is represented by its numerator and denominator in uint32_t type. This patch changes this representation into a fixed point that is represented by the numerator in uint32_t type and a constant denominator 1<<31. This is quite similar to the representation of BlockMass in BlockFrequencyInfoImpl.h. There are several pros and cons of this change:

Pros:

1. It uses only a half space of the current one.
2. Some operations are much faster like plus, subtraction, comparison, and scaling by an integer.

Cons:

1. Constructing a probability using arbitrary numerator and denominator needs additional calculations.
2. It is a little less precise than before as we use a fixed denominator. For example, 1 - 1/3 may not be exactly identical to 1 / 3 (this will lead to many BranchProbability unit test failures). This should not matter when we only use it for branch probability. If we use it like a rational value for some precise calculations we may need another construct like ValueRatio.

One important reason for this change is that we propose to store branch probabilities instead of edge weights in MachineBasicBlock. We also want clients to use probability instead of weight when adding successors to a MBB. The current BranchProbability has more space which may be a concern.

Differential revision: http://reviews.llvm.org/D12603



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@248633 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../llvm/Analysis/BlockFrequencyInfoImpl.h    |   9 +-
 include/llvm/Support/BranchProbability.h      |  78 +++++---
 lib/Support/BranchProbability.cpp             |  56 +++++-
 test/Analysis/BlockFrequencyInfo/basic.ll     |   6 +-
 .../loops_with_profile_info.ll                |   6 +-
 test/Analysis/BranchProbabilityInfo/basic.ll  |  68 +++----
 test/Analysis/BranchProbabilityInfo/loop.ll   | 152 ++++++++--------
 .../BranchProbabilityInfo/noreturn.ll         |  22 +--
 .../Analysis/BranchProbabilityInfo/pr18705.ll |   4 +-
 .../Analysis/BranchProbabilityInfo/pr22718.ll |   4 +-
 .../AArch64/aarch64-deferred-spilling.ll      |   4 +-
 test/Transforms/SampleProfile/branch.ll       |  14 +-
 test/Transforms/SampleProfile/calls.ll        |   8 +-
 .../Transforms/SampleProfile/discriminator.ll |   8 +-
 test/Transforms/SampleProfile/fnptr.ll        |  12 +-
 test/Transforms/SampleProfile/propagate.ll    |  16 +-
 unittests/Support/BlockFrequencyTest.cpp      |  12 +-
 unittests/Support/BranchProbabilityTest.cpp   | 166 +++++++++---------
 18 files changed, 370 insertions(+), 275 deletions(-)

diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
index de53515dbfc..42d6cbc2e6e 100644
--- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h
+++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
@@ -1190,10 +1190,11 @@ raw_ostream &BlockFrequencyInfoImpl<BT>::print(raw_ostream &OS) const {
   if (!F)
     return OS;
   OS << "block-frequency-info: " << F->getName() << "\n";
-  for (const BlockT &BB : *F)
-    OS << " - " << bfi_detail::getBlockName(&BB)
-       << ": float = " << getFloatingBlockFreq(&BB)
-       << ", int = " << getBlockFreq(&BB).getFrequency() << "\n";
+  for (const BlockT &BB : *F) {
+    OS << " - " << bfi_detail::getBlockName(&BB) << ": float = ";
+    getFloatingBlockFreq(&BB).print(OS, 5)
+        << ", int = " << getBlockFreq(&BB).getFrequency() << "\n";
+  }
 
   // Add an extra newline for readability.
   OS << "\n";
diff --git a/include/llvm/Support/BranchProbability.h b/include/llvm/Support/BranchProbability.h
index 7bef0b699c3..dd43857fa22 100644
--- a/include/llvm/Support/BranchProbability.h
+++ b/include/llvm/Support/BranchProbability.h
@@ -21,31 +21,43 @@ namespace llvm {
 
 class raw_ostream;
 
-// This class represents Branch Probability as a non-negative fraction.
+// This class represents Branch Probability as a non-negative fraction that is
+// no greater than 1. It uses a fixed-point-like implementation, in which the
+// denominator is always a constant value (here we use 1<<31 for maximum
+// precision).
 class BranchProbability {
   // Numerator
   uint32_t N;
 
-  // Denominator
-  uint32_t D;
+  // Denominator, which is a constant value.
+  static const uint32_t D = 1u << 31;
+
+  // Construct a BranchProbability with only numerator assuming the denominator
+  // is 1<<31. For internal use only.
+  explicit BranchProbability(uint32_t n) : N(n) {}
 
 public:
-  BranchProbability(uint32_t Numerator, uint32_t Denominator)
-      : N(Numerator), D(Denominator) {
-    assert(D > 0 && "Denominator cannot be 0!");
-    assert(N <= D && "Probability cannot be bigger than 1!");
-  }
+  BranchProbability() : N(0) {}
+  BranchProbability(uint32_t Numerator, uint32_t Denominator);
+
+  bool isZero() const { return N == 0; }
 
-  static BranchProbability getZero() { return BranchProbability(0, 1); }
-  static BranchProbability getOne() { return BranchProbability(1, 1); }
+  static BranchProbability getZero() { return BranchProbability(0); }
+  static BranchProbability getOne() { return BranchProbability(D); }
+  // Create a BranchProbability object with the given numerator and 1<<31
+  // as denominator.
+  static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); }
+
+  // Normalize given probabilties so that the sum of them becomes approximate
+  // one.
+  template <class ProbabilityList>
+  static void normalizeProbabilities(ProbabilityList &Probs);
 
   uint32_t getNumerator() const { return N; }
-  uint32_t getDenominator() const { return D; }
+  static uint32_t getDenominator() { return D; }
 
   // Return (1 - Probability).
-  BranchProbability getCompl() const {
-    return BranchProbability(D - N, D);
-  }
+  BranchProbability getCompl() const { return BranchProbability(D - N); }
 
   raw_ostream &print(raw_ostream &OS) const;
 
@@ -67,15 +79,31 @@ public:
   /// \return \c Num divided by \c this.
   uint64_t scaleByInverse(uint64_t Num) const;
 
-  bool operator==(BranchProbability RHS) const {
-    return (uint64_t)N * RHS.D == (uint64_t)D * RHS.N;
+  BranchProbability &operator+=(BranchProbability RHS);
+  BranchProbability &operator-=(BranchProbability RHS);
+  BranchProbability &operator*=(BranchProbability RHS) {
+    N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
+    return *this;
+  }
+
+  BranchProbability operator+(BranchProbability RHS) const {
+    BranchProbability Prob(*this);
+    return Prob += RHS;
   }
-  bool operator!=(BranchProbability RHS) const {
-    return !(*this == RHS);
+
+  BranchProbability operator-(BranchProbability RHS) const {
+    BranchProbability Prob(*this);
+    return Prob -= RHS;
   }
-  bool operator<(BranchProbability RHS) const {
-    return (uint64_t)N * RHS.D < (uint64_t)D * RHS.N;
+
+  BranchProbability operator*(BranchProbability RHS) const {
+    BranchProbability Prob(*this);
+    return Prob *= RHS;
   }
+
+  bool operator==(BranchProbability RHS) const { return N == RHS.N; }
+  bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
+  bool operator<(BranchProbability RHS) const { return N < RHS.N; }
   bool operator>(BranchProbability RHS) const { return RHS < *this; }
   bool operator<=(BranchProbability RHS) const { return !(RHS < *this); }
   bool operator>=(BranchProbability RHS) const { return !(*this < RHS); }
@@ -85,6 +113,16 @@ inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
   return Prob.print(OS);
 }
 
+template <class ProbabilityList>
+void BranchProbability::normalizeProbabilities(ProbabilityList &Probs) {
+  uint64_t Sum = 0;
+  for (auto Prob : Probs)
+    Sum += Prob.N;
+  assert(Sum > 0);
+  for (auto &Prob : Probs)
+    Prob.N = (Prob.N * uint64_t(D) + Sum / 2) / Sum;
+}
+
 }
 
 #endif
diff --git a/lib/Support/BranchProbability.cpp b/lib/Support/BranchProbability.cpp
index 65878d6e302..47b06c2e0ff 100644
--- a/lib/Support/BranchProbability.cpp
+++ b/lib/Support/BranchProbability.cpp
@@ -15,17 +15,63 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
+#include <cassert>
 
 using namespace llvm;
 
 raw_ostream &BranchProbability::print(raw_ostream &OS) const {
-  return OS << N << " / " << D << " = "
-            << format("%g%%", ((double)N / D) * 100.0);
+  auto GetHexDigit = [](int Val) -> char {
+    assert(Val < 16);
+    if (Val < 10)
+      return '0' + Val;
+    return 'a' + Val - 10;
+  };
+  OS << "0x";
+  for (int Digits = 0; Digits < 8; ++Digits)
+    OS << GetHexDigit(N >> (28 - Digits * 4) & 0xf);
+  OS << " / 0x";
+  for (int Digits = 0; Digits < 8; ++Digits)
+    OS << GetHexDigit(D >> (28 - Digits * 4) & 0xf);
+  OS << " = " << format("%.2f%%", ((double)N / D) * 100.0);
+  return OS;
 }
 
 void BranchProbability::dump() const { print(dbgs()) << '\n'; }
 
-static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {
+BranchProbability::BranchProbability(uint32_t Numerator, uint32_t Denominator) {
+  assert(Denominator > 0 && "Denominator cannot be 0!");
+  assert(Numerator <= Denominator && "Probability cannot be bigger than 1!");
+  if (Denominator == D)
+    N = Numerator;
+  else {
+    uint64_t Prob64 =
+        (Numerator * static_cast<uint64_t>(D) + Denominator / 2) / Denominator;
+    N = static_cast<uint32_t>(Prob64);
+  }
+}
+
+BranchProbability &BranchProbability::operator+=(BranchProbability RHS) {
+  assert(N <= D - RHS.N &&
+         "The sum of branch probabilities should not exceed one!");
+  N += RHS.N;
+  return *this;
+}
+
+BranchProbability &BranchProbability::operator-=(BranchProbability RHS) {
+  assert(N >= RHS.N &&
+         "Can only subtract a smaller probability from a larger one!");
+  N -= RHS.N;
+  return *this;
+}
+
+// If ConstD is not zero, then replace D by ConstD so that division and modulo
+// operations by D can be optimized, in case this function is not inlined by the
+// compiler.
+template <uint32_t ConstD>
+inline uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {
+  if (ConstD > 0)
+    D = ConstD;
+
   assert(D && "divide by 0");
 
   // Fast path for multiplying by 1.0.
@@ -65,9 +111,9 @@ static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {
 }
 
 uint64_t BranchProbability::scale(uint64_t Num) const {
-  return ::scale(Num, N, D);
+  return ::scale<D>(Num, N, D);
 }
 
 uint64_t BranchProbability::scaleByInverse(uint64_t Num) const {
-  return ::scale(Num, D, N);
+  return ::scale<0>(Num, D, N);
 }
diff --git a/test/Analysis/BlockFrequencyInfo/basic.ll b/test/Analysis/BlockFrequencyInfo/basic.ll
index 728adf007f4..8e81cc2ea31 100644
--- a/test/Analysis/BlockFrequencyInfo/basic.ll
+++ b/test/Analysis/BlockFrequencyInfo/basic.ll
@@ -104,13 +104,13 @@ for.cond1.preheader:
   %x.024 = phi i32 [ 0, %entry ], [ %inc12, %for.inc11 ]
   br label %for.cond4.preheader
 
-; CHECK-NEXT: for.cond4.preheader: float = 16008001.0,
+; CHECK-NEXT: for.cond4.preheader: float = 16007984.8,
 for.cond4.preheader:
   %y.023 = phi i32 [ 0, %for.cond1.preheader ], [ %inc9, %for.inc8 ]
   %add = add i32 %y.023, %x.024
   br label %for.body6
 
-; CHECK-NEXT: for.body6: float = 64048012001.0,
+; CHECK-NEXT: for.body6: float = 64047914563.9,
 for.body6:
   %z.022 = phi i32 [ 0, %for.cond4.preheader ], [ %inc, %for.body6 ]
   %add7 = add i32 %add, %z.022
@@ -119,7 +119,7 @@ for.body6:
   %cmp5 = icmp ugt i32 %inc, %a
   br i1 %cmp5, label %for.inc8, label %for.body6, !prof !2
 
-; CHECK-NEXT: for.inc8: float = 16008001.0,
+; CHECK-NEXT: for.inc8: float = 16007984.8,
 for.inc8:
   %inc9 = add i32 %y.023, 1
   %cmp2 = icmp ugt i32 %inc9, %a
diff --git a/test/Analysis/BlockFrequencyInfo/loops_with_profile_info.ll b/test/Analysis/BlockFrequencyInfo/loops_with_profile_info.ll
index 534c4ad0e94..29a9f3b29fb 100644
--- a/test/Analysis/BlockFrequencyInfo/loops_with_profile_info.ll
+++ b/test/Analysis/BlockFrequencyInfo/loops_with_profile_info.ll
@@ -93,7 +93,7 @@ for.cond4:                                        ; preds = %for.inc, %for.body3
   %cmp5 = icmp slt i32 %2, 100
   br i1 %cmp5, label %for.body6, label %for.end, !prof !3
 
-; CHECK: - for.body6: float = 500000.5, int = 4000003
+; CHECK: - for.body6: float = 500000.5, int = 4000004
 for.body6:                                        ; preds = %for.cond4
   call void @bar()
   br label %for.inc
@@ -143,7 +143,7 @@ for.cond16:                                       ; preds = %for.inc19, %for.bod
   %cmp17 = icmp slt i32 %8, 10000
   br i1 %cmp17, label %for.body18, label %for.end21, !prof !4
 
-; CHECK: - for.body18: float = 500000.5, int = 4000003
+; CHECK: - for.body18: float = 499999.9, int = 3999998
 for.body18:                                       ; preds = %for.cond16
   call void @bar()
   br label %for.inc19
@@ -175,7 +175,7 @@ for.cond26:                                       ; preds = %for.inc29, %for.end
   %cmp27 = icmp slt i32 %12, 1000000
   br i1 %cmp27, label %for.body28, label %for.end31, !prof !5
 
-; CHECK: - for.body28: float = 500000.5, int = 4000003
+; CHECK: - for.body28: float = 499995.2, int = 3999961
 for.body28:                                       ; preds = %for.cond26
   call void @bar()
   br label %for.inc29
diff --git a/test/Analysis/BranchProbabilityInfo/basic.ll b/test/Analysis/BranchProbabilityInfo/basic.ll
index 2c9c1561868..d833b8339aa 100644
--- a/test/Analysis/BranchProbabilityInfo/basic.ll
+++ b/test/Analysis/BranchProbabilityInfo/basic.ll
@@ -4,7 +4,7 @@ define i32 @test1(i32 %i, i32* %a) {
 ; CHECK: Printing analysis {{.*}} for function 'test1'
 entry:
   br label %body
-; CHECK: edge entry -> body probability is 16 / 16 = 100%
+; CHECK: edge entry -> body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 body:
   %iv = phi i32 [ 0, %entry ], [ %next, %body ]
@@ -15,8 +15,8 @@ body:
   %next = add i32 %iv, 1
   %exitcond = icmp eq i32 %next, %i
   br i1 %exitcond, label %exit, label %body
-; CHECK: edge body -> exit probability is 4 / 128
-; CHECK: edge body -> body probability is 124 / 128
+; CHECK: edge body -> exit probability is 0x04000000 / 0x80000000 = 3.12%
+; CHECK: edge body -> body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 
 exit:
   ret i32 %sum
@@ -27,16 +27,16 @@ define i32 @test2(i32 %i, i32 %a, i32 %b) {
 entry:
   %cond = icmp ult i32 %i, 42
   br i1 %cond, label %then, label %else, !prof !0
-; CHECK: edge entry -> then probability is 64 / 68
-; CHECK: edge entry -> else probability is 4 / 68
+; CHECK: edge entry -> then probability is 0x78787878 / 0x80000000 = 94.12% [HOT edge]
+; CHECK: edge entry -> else probability is 0x07878788 / 0x80000000 = 5.88%
 
 then:
   br label %exit
-; CHECK: edge then -> exit probability is 16 / 16 = 100%
+; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 else:
   br label %exit
-; CHECK: edge else -> exit probability is 16 / 16 = 100%
+; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 exit:
   %result = phi i32 [ %a, %then ], [ %b, %else ]
@@ -52,31 +52,31 @@ entry:
                                  i32 2, label %case_c
                                  i32 3, label %case_d
                                  i32 4, label %case_e ], !prof !1
-; CHECK: edge entry -> case_a probability is 4 / 80
-; CHECK: edge entry -> case_b probability is 4 / 80
-; CHECK: edge entry -> case_c probability is 64 / 80
-; CHECK: edge entry -> case_d probability is 4 / 80
-; CHECK: edge entry -> case_e probability is 4 / 80
+; CHECK: edge entry -> case_a probability is 0x06666666 / 0x80000000 = 5.00%
+; CHECK: edge entry -> case_b probability is 0x06666666 / 0x80000000 = 5.00%
+; CHECK: edge entry -> case_c probability is 0x66666666 / 0x80000000 = 80.00%
+; CHECK: edge entry -> case_d probability is 0x06666666 / 0x80000000 = 5.00%
+; CHECK: edge entry -> case_e probability is 0x06666666 / 0x80000000 = 5.00%
 
 case_a:
   br label %exit
-; CHECK: edge case_a -> exit probability is 16 / 16 = 100%
+; CHECK: edge case_a -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 case_b:
   br label %exit
-; CHECK: edge case_b -> exit probability is 16 / 16 = 100%
+; CHECK: edge case_b -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 case_c:
   br label %exit
-; CHECK: edge case_c -> exit probability is 16 / 16 = 100%
+; CHECK: edge case_c -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 case_d:
   br label %exit
-; CHECK: edge case_d -> exit probability is 16 / 16 = 100%
+; CHECK: edge case_d -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 case_e:
   br label %exit
-; CHECK: edge case_e -> exit probability is 16 / 16 = 100%
+; CHECK: edge case_e -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 exit:
   %result = phi i32 [ %a, %case_a ],
@@ -99,9 +99,9 @@ entry:
     i64 2, label %sw.bb
     i64 5, label %sw.bb1
   ], !prof !2
-; CHECK: edge entry -> return probability is 7 / 85
-; CHECK: edge entry -> sw.bb probability is 14 / 85
-; CHECK: edge entry -> sw.bb1 probability is 64 / 85
+; CHECK: edge entry -> return probability is 0x0a8a8a8b / 0x80000000 = 8.24%
+; CHECK: edge entry -> sw.bb probability is 0x15151515 / 0x80000000 = 16.47%
+; CHECK: edge entry -> sw.bb1 probability is 0x60606060 / 0x80000000 = 75.29%
 
 sw.bb:
   br label %return
@@ -122,17 +122,17 @@ define i32 @test5(i32 %a, i32 %b, i1 %flag) {
 ; CHECK: Printing analysis {{.*}} for function 'test5'
 entry:
   br i1 %flag, label %then, label %else
-; CHECK: edge entry -> then probability is 4 / 68
-; CHECK: edge entry -> else probability is 64 / 68
+; CHECK: edge entry -> then probability is 0x07878788 / 0x80000000 = 5.88%
+; CHECK: edge entry -> else probability is 0x78787878 / 0x80000000 = 94.12% [HOT edge]
 
 then:
   call void @coldfunc()
   br label %exit
-; CHECK: edge then -> exit probability is 16 / 16 = 100%
+; CHECK: edge then -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 else:
   br label %exit
-; CHECK: edge else -> exit probability is 16 / 16 = 100%
+; CHECK: edge else -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 exit:
   %result = phi i32 [ %a, %then ], [ %b, %else ]
@@ -149,8 +149,8 @@ define i32 @test_cold_call_sites(i32* %a) {
 ; after that is fixed.
 
 ; CHECK: Printing analysis {{.*}} for function 'test_cold_call_sites'
-; CHECK: edge entry -> then probability is 4 / 68 = 5.88235%
-; CHECK: edge entry -> else probability is 64 / 68 = 94.1176% [HOT edge]
+; CHECK: edge entry -> then probability is 0x07878788 / 0x80000000 = 5.88%
+; CHECK: edge entry -> else probability is 0x78787878 / 0x80000000 = 94.12% [HOT edge]
 
 entry:
   %gep1 = getelementptr i32, i32* %a, i32 1
@@ -179,8 +179,8 @@ define i32 @zero1(i32 %i, i32 %a, i32 %b) {
 entry:
   %cond = icmp eq i32 %i, 0
   br i1 %cond, label %then, label %else
-; CHECK: edge entry -> then probability is 12 / 32
-; CHECK: edge entry -> else probability is 20 / 32
+; CHECK: edge entry -> then probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge entry -> else probability is 0x50000000 / 0x80000000 = 62.50%
 
 then:
   br label %exit
@@ -198,8 +198,8 @@ define i32 @zero2(i32 %i, i32 %a, i32 %b) {
 entry:
   %cond = icmp ne i32 %i, -1
   br i1 %cond, label %then, label %else
-; CHECK: edge entry -> then probability is 20 / 32
-; CHECK: edge entry -> else probability is 12 / 32
+; CHECK: edge entry -> then probability is 0x50000000 / 0x80000000 = 62.50%
+; CHECK: edge entry -> else probability is 0x30000000 / 0x80000000 = 37.50%
 
 then:
   br label %exit
@@ -220,8 +220,8 @@ entry:
   %and = and i32 %i, 2
   %tobool = icmp eq i32 %and, 0
   br i1 %tobool, label %then, label %else
-; CHECK: edge entry -> then probability is 16 / 32
-; CHECK: edge entry -> else probability is 16 / 32
+; CHECK: edge entry -> then probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge entry -> else probability is 0x40000000 / 0x80000000 = 50.00%
 
 then:
 ; AND'ing with other bitmask might be something else, so we still assume the
@@ -229,8 +229,8 @@ then:
   %and2 = and i32 %i, 5
   %tobool2 = icmp eq i32 %and2, 0
   br i1 %tobool2, label %else, label %exit
-; CHECK: edge then -> else probability is 12 / 32
-; CHECK: edge then -> exit probability is 20 / 32
+; CHECK: edge then -> else probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge then -> exit probability is 0x50000000 / 0x80000000 = 62.50%
 
 else:
   br label %exit
diff --git a/test/Analysis/BranchProbabilityInfo/loop.ll b/test/Analysis/BranchProbabilityInfo/loop.ll
index e792790f84f..5be7adf3909 100644
--- a/test/Analysis/BranchProbabilityInfo/loop.ll
+++ b/test/Analysis/BranchProbabilityInfo/loop.ll
@@ -9,13 +9,13 @@ declare void @g4()
 define void @test1(i32 %a, i32 %b) {
 entry:
   br label %do.body
-; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
+; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc3, %do.end ]
   call void @g1()
   br label %do.body1
-; CHECK: edge do.body -> do.body1 probability is 16 / 16 = 100%
+; CHECK: edge do.body -> do.body1 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 do.body1:
   %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.body1 ]
@@ -23,16 +23,16 @@ do.body1:
   %inc = add nsw i32 %j.0, 1
   %cmp = icmp slt i32 %inc, %b
   br i1 %cmp, label %do.body1, label %do.end
-; CHECK: edge do.body1 -> do.body1 probability is 124 / 128
-; CHECK: edge do.body1 -> do.end probability is 4 / 128
+; CHECK: edge do.body1 -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge do.body1 -> do.end probability is 0x04000000 / 0x80000000 = 3.12%
 
 do.end:
   call void @g3()
   %inc3 = add nsw i32 %i.0, 1
   %cmp4 = icmp slt i32 %inc3, %a
   br i1 %cmp4, label %do.body, label %do.end5
-; CHECK: edge do.end -> do.body probability is 124 / 128
-; CHECK: edge do.end -> do.end5 probability is 4 / 128
+; CHECK: edge do.end -> do.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge do.end -> do.end5 probability is 0x04000000 / 0x80000000 = 3.12%
 
 do.end5:
   call void @g4()
@@ -43,20 +43,20 @@ define void @test2(i32 %a, i32 %b) {
 entry:
   %cmp9 = icmp sgt i32 %a, 0
   br i1 %cmp9, label %for.body.lr.ph, label %for.end6
-; CHECK: edge entry -> for.body.lr.ph probability is 20 / 32
-; CHECK: edge entry -> for.end6 probability is 12 / 32
+; CHECK: edge entry -> for.body.lr.ph probability is 0x50000000 / 0x80000000 = 62.50%
+; CHECK: edge entry -> for.end6 probability is 0x30000000 / 0x80000000 = 37.50%
 
 for.body.lr.ph:
   %cmp27 = icmp sgt i32 %b, 0
   br label %for.body
-; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
+; CHECK: edge for.body.lr.ph -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 for.body:
   %i.010 = phi i32 [ 0, %for.body.lr.ph ], [ %inc5, %for.end ]
   call void @g1()
   br i1 %cmp27, label %for.body3, label %for.end
-; CHECK: edge for.body -> for.body3 probability is 20 / 32 = 62.5%
-; CHECK: edge for.body -> for.end probability is 12 / 32 = 37.5%
+; CHECK: edge for.body -> for.body3 probability is 0x50000000 / 0x80000000 = 62.50%
+; CHECK: edge for.body -> for.end probability is 0x30000000 / 0x80000000 = 37.50%
 
 for.body3:
   %j.08 = phi i32 [ %inc, %for.body3 ], [ 0, %for.body ]
@@ -64,16 +64,16 @@ for.body3:
   %inc = add nsw i32 %j.08, 1
   %exitcond = icmp eq i32 %inc, %b
   br i1 %exitcond, label %for.end, label %for.body3
-; CHECK: edge for.body3 -> for.end probability is 4 / 128
-; CHECK: edge for.body3 -> for.body3 probability is 124 / 128
+; CHECK: edge for.body3 -> for.end probability is 0x04000000 / 0x80000000 = 3.12%
+; CHECK: edge for.body3 -> for.body3 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 
 for.end:
   call void @g3()
   %inc5 = add nsw i32 %i.010, 1
   %exitcond11 = icmp eq i32 %inc5, %a
   br i1 %exitcond11, label %for.end6, label %for.body
-; CHECK: edge for.end -> for.end6 probability is 4 / 128
-; CHECK: edge for.end -> for.body probability is 124 / 128
+; CHECK: edge for.end -> for.end6 probability is 0x04000000 / 0x80000000 = 3.12%
+; CHECK: edge for.end -> for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 
 for.end6:
   call void @g4()
@@ -83,7 +83,7 @@ for.end6:
 define void @test3(i32 %a, i32 %b, i32* %c) {
 entry:
   br label %do.body
-; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
+; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %if.end ]
@@ -91,8 +91,8 @@ do.body:
   %0 = load i32, i32* %c, align 4
   %cmp = icmp slt i32 %0, 42
   br i1 %cmp, label %do.body1, label %if.end
-; CHECK: edge do.body -> do.body1 probability is 16 / 32 = 50%
-; CHECK: edge do.body -> if.end probability is 16 / 32 = 50%
+; CHECK: edge do.body -> do.body1 probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge do.body -> if.end probability is 0x40000000 / 0x80000000 = 50.00%
 
 do.body1:
   %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ]
@@ -100,16 +100,16 @@ do.body1:
   %inc = add nsw i32 %j.0, 1
   %cmp2 = icmp slt i32 %inc, %b
   br i1 %cmp2, label %do.body1, label %if.end
-; CHECK: edge do.body1 -> do.body1 probability is 124 / 128
-; CHECK: edge do.body1 -> if.end probability is 4 / 128
+; CHECK: edge do.body1 -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge do.body1 -> if.end probability is 0x04000000 / 0x80000000 = 3.12%
 
 if.end:
   call void @g3()
   %inc4 = add nsw i32 %i.0, 1
   %cmp5 = icmp slt i32 %inc4, %a
   br i1 %cmp5, label %do.body, label %do.end6
-; CHECK: edge if.end -> do.body probability is 124 / 128
-; CHECK: edge if.end -> do.end6 probability is 4 / 128
+; CHECK: edge if.end -> do.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge if.end -> do.end6 probability is 0x04000000 / 0x80000000 = 3.12%
 
 do.end6:
   call void @g4()
@@ -119,7 +119,7 @@ do.end6:
 define void @test4(i32 %a, i32 %b, i32* %c) {
 entry:
   br label %do.body
-; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
+; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
@@ -127,8 +127,8 @@ do.body:
   %0 = load i32, i32* %c, align 4
   %cmp = icmp slt i32 %0, 42
   br i1 %cmp, label %return, label %do.body1
-; CHECK: edge do.body -> return probability is 4 / 128
-; CHECK: edge do.body -> do.body1 probability is 124 / 128
+; CHECK: edge do.body -> return probability is 0x04000000 / 0x80000000 = 3.12%
+; CHECK: edge do.body -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 
 do.body1:
   %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ]
@@ -136,21 +136,21 @@ do.body1:
   %inc = add nsw i32 %j.0, 1
   %cmp2 = icmp slt i32 %inc, %b
   br i1 %cmp2, label %do.body1, label %do.end
-; CHECK: edge do.body1 -> do.body1 probability is 124 / 128
-; CHECK: edge do.body1 -> do.end probability is 4 / 128
+; CHECK: edge do.body1 -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge do.body1 -> do.end probability is 0x04000000 / 0x80000000 = 3.12%
 
 do.end:
   call void @g3()
   %inc4 = add nsw i32 %i.0, 1
   %cmp5 = icmp slt i32 %inc4, %a
   br i1 %cmp5, label %do.body, label %do.end6
-; CHECK: edge do.end -> do.body probability is 124 / 128
-; CHECK: edge do.end -> do.end6 probability is 4 / 128
+; CHECK: edge do.end -> do.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge do.end -> do.end6 probability is 0x04000000 / 0x80000000 = 3.12%
 
 do.end6:
   call void @g4()
   br label %return
-; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
+; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 return:
   ret void
@@ -159,42 +159,42 @@ return:
 define void @test5(i32 %a, i32 %b, i32* %c) {
 entry:
   br label %do.body
-; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
+; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
   call void @g1()
   br label %do.body1
-; CHECK: edge do.body -> do.body1 probability is 16 / 16 = 100%
+; CHECK: edge do.body -> do.body1 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 do.body1:
   %j.0 = phi i32 [ 0, %do.body ], [ %inc, %if.end ]
   %0 = load i32, i32* %c, align 4
   %cmp = icmp slt i32 %0, 42
   br i1 %cmp, label %return, label %if.end
-; CHECK: edge do.body1 -> return probability is 4 / 128
-; CHECK: edge do.body1 -> if.end probability is 124 / 128
+; CHECK: edge do.body1 -> return probability is 0x04000000 / 0x80000000 = 3.12%
+; CHECK: edge do.body1 -> if.end probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 
 if.end:
   call void @g2()
   %inc = add nsw i32 %j.0, 1
   %cmp2 = icmp slt i32 %inc, %b
   br i1 %cmp2, label %do.body1, label %do.end
-; CHECK: edge if.end -> do.body1 probability is 124 / 128
-; CHECK: edge if.end -> do.end probability is 4 / 128
+; CHECK: edge if.end -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge if.end -> do.end probability is 0x04000000 / 0x80000000 = 3.12%
 
 do.end:
   call void @g3()
   %inc4 = add nsw i32 %i.0, 1
   %cmp5 = icmp slt i32 %inc4, %a
   br i1 %cmp5, label %do.body, label %do.end6
-; CHECK: edge do.end -> do.body probability is 124 / 128
-; CHECK: edge do.end -> do.end6 probability is 4 / 128
+; CHECK: edge do.end -> do.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge do.end -> do.end6 probability is 0x04000000 / 0x80000000 = 3.12%
 
 do.end6:
   call void @g4()
   br label %return
-; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
+; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 return:
   ret void
@@ -203,13 +203,13 @@ return:
 define void @test6(i32 %a, i32 %b, i32* %c) {
 entry:
   br label %do.body
-; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
+; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
   call void @g1()
   br label %do.body1
-; CHECK: edge do.body -> do.body1 probability is 16 / 16 = 100%
+; CHECK: edge do.body -> do.body1 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 do.body1:
   %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.cond ]
@@ -217,28 +217,28 @@ do.body1:
   %0 = load i32, i32* %c, align 4
   %cmp = icmp slt i32 %0, 42
   br i1 %cmp, label %return, label %do.cond
-; CHECK: edge do.body1 -> return probability is 4 / 128
-; CHECK: edge do.body1 -> do.cond probability is 124 / 128
+; CHECK: edge do.body1 -> return probability is 0x04000000 / 0x80000000 = 3.12%
+; CHECK: edge do.body1 -> do.cond probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 
 do.cond:
   %inc = add nsw i32 %j.0, 1
   %cmp2 = icmp slt i32 %inc, %b
   br i1 %cmp2, label %do.body1, label %do.end
-; CHECK: edge do.cond -> do.body1 probability is 124 / 128
-; CHECK: edge do.cond -> do.end probability is 4 / 128
+; CHECK: edge do.cond -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge do.cond -> do.end probability is 0x04000000 / 0x80000000 = 3.12%
 
 do.end:
   call void @g3()
   %inc4 = add nsw i32 %i.0, 1
   %cmp5 = icmp slt i32 %inc4, %a
   br i1 %cmp5, label %do.body, label %do.end6
-; CHECK: edge do.end -> do.body probability is 124 / 128
-; CHECK: edge do.end -> do.end6 probability is 4 / 128
+; CHECK: edge do.end -> do.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge do.end -> do.end6 probability is 0x04000000 / 0x80000000 = 3.12%
 
 do.end6:
   call void @g4()
   br label %return
-; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
+; CHECK: edge do.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 return:
   ret void
@@ -248,27 +248,27 @@ define void @test7(i32 %a, i32 %b, i32* %c) {
 entry:
   %cmp10 = icmp sgt i32 %a, 0
   br i1 %cmp10, label %for.body.lr.ph, label %for.end7
-; CHECK: edge entry -> for.body.lr.ph probability is 20 / 32
-; CHECK: edge entry -> for.end7 probability is 12 / 32
+; CHECK: edge entry -> for.body.lr.ph probability is 0x50000000 / 0x80000000 = 62.50%
+; CHECK: edge entry -> for.end7 probability is 0x30000000 / 0x80000000 = 37.50%
 
 for.body.lr.ph:
   %cmp38 = icmp sgt i32 %b, 0
   br label %for.body
-; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
+; CHECK: edge for.body.lr.ph -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 for.body:
   %i.011 = phi i32 [ 0, %for.body.lr.ph ], [ %inc6, %for.inc5 ]
   %0 = load i32, i32* %c, align 4
   %cmp1 = icmp eq i32 %0, %i.011
   br i1 %cmp1, label %for.inc5, label %if.end
-; CHECK: edge for.body -> for.inc5 probability is 16 / 32 = 50%
-; CHECK: edge for.body -> if.end probability is 16 / 32 = 50%
+; CHECK: edge for.body -> for.inc5 probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge for.body -> if.end probability is 0x40000000 / 0x80000000 = 50.00%
 
 if.end:
   call void @g1()
   br i1 %cmp38, label %for.body4, label %for.end
-; CHECK: edge if.end -> for.body4 probability is 20 / 32 = 62.5%
-; CHECK: edge if.end -> for.end probability is 12 / 32 = 37.5%
+; CHECK: edge if.end -> for.body4 probability is 0x50000000 / 0x80000000 = 62.50%
+; CHECK: edge if.end -> for.end probability is 0x30000000 / 0x80000000 = 37.50%
 
 for.body4:
   %j.09 = phi i32 [ %inc, %for.body4 ], [ 0, %if.end ]
@@ -276,20 +276,20 @@ for.body4:
   %inc = add nsw i32 %j.09, 1
   %exitcond = icmp eq i32 %inc, %b
   br i1 %exitcond, label %for.end, label %for.body4
-; CHECK: edge for.body4 -> for.end probability is 4 / 128
-; CHECK: edge for.body4 -> for.body4 probability is 124 / 128
+; CHECK: edge for.body4 -> for.end probability is 0x04000000 / 0x80000000 = 3.12%
+; CHECK: edge for.body4 -> for.body4 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 
 for.end:
   call void @g3()
   br label %for.inc5
-; CHECK: edge for.end -> for.inc5 probability is 16 / 16 = 100%
+; CHECK: edge for.end -> for.inc5 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 for.inc5:
   %inc6 = add nsw i32 %i.011, 1
   %exitcond12 = icmp eq i32 %inc6, %a
   br i1 %exitcond12, label %for.end7, label %for.body
-; CHECK: edge for.inc5 -> for.end7 probability is 4 / 128
-; CHECK: edge for.inc5 -> for.body probability is 124 / 128
+; CHECK: edge for.inc5 -> for.end7 probability is 0x04000000 / 0x80000000 = 3.12%
+; CHECK: edge for.inc5 -> for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 
 for.end7:
   call void @g4()
@@ -300,64 +300,64 @@ define void @test8(i32 %a, i32 %b, i32* %c) {
 entry:
   %cmp18 = icmp sgt i32 %a, 0
   br i1 %cmp18, label %for.body.lr.ph, label %for.end15
-; CHECK: edge entry -> for.body.lr.ph probability is 20 / 32
-; CHECK: edge entry -> for.end15 probability is 12 / 32
+; CHECK: edge entry -> for.body.lr.ph probability is 0x50000000 / 0x80000000 = 62.50%
+; CHECK: edge entry -> for.end15 probability is 0x30000000 / 0x80000000 = 37.50%
 
 for.body.lr.ph:
   %cmp216 = icmp sgt i32 %b, 0
   %arrayidx5 = getelementptr inbounds i32, i32* %c, i64 1
   %arrayidx9 = getelementptr inbounds i32, i32* %c, i64 2
   br label %for.body
-; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
+; CHECK: edge for.body.lr.ph -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 for.body:
   %i.019 = phi i32 [ 0, %for.body.lr.ph ], [ %inc14, %for.end ]
   call void @g1()
   br i1 %cmp216, label %for.body3, label %for.end
-; CHECK: edge for.body -> for.body3 probability is 20 / 32 = 62.5%
-; CHECK: edge for.body -> for.end probability is 12 / 32 = 37.5%
+; CHECK: edge for.body -> for.body3 probability is 0x50000000 / 0x80000000 = 62.50%
+; CHECK: edge for.body -> for.end probability is 0x30000000 / 0x80000000 = 37.50%
 
 for.body3:
   %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
   %0 = load i32, i32* %c, align 4
   %cmp4 = icmp eq i32 %0, %j.017
   br i1 %cmp4, label %for.inc, label %if.end
-; CHECK: edge for.body3 -> for.inc probability is 16 / 32 = 50%
-; CHECK: edge for.body3 -> if.end probability is 16 / 32 = 50%
+; CHECK: edge for.body3 -> for.inc probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge for.body3 -> if.end probability is 0x40000000 / 0x80000000 = 50.00%
 
 if.end:
   %1 = load i32, i32* %arrayidx5, align 4
   %cmp6 = icmp eq i32 %1, %j.017
   br i1 %cmp6, label %for.inc, label %if.end8
-; CHECK: edge if.end -> for.inc probability is 16 / 32 = 50%
-; CHECK: edge if.end -> if.end8 probability is 16 / 32 = 50%
+; CHECK: edge if.end -> for.inc probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge if.end -> if.end8 probability is 0x40000000 / 0x80000000 = 50.00%
 
 if.end8:
   %2 = load i32, i32* %arrayidx9, align 4
   %cmp10 = icmp eq i32 %2, %j.017
   br i1 %cmp10, label %for.inc, label %if.end12
-; CHECK: edge if.end8 -> for.inc probability is 16 / 32 = 50%
-; CHECK: edge if.end8 -> if.end12 probability is 16 / 32 = 50%
+; CHECK: edge if.end8 -> for.inc probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge if.end8 -> if.end12 probability is 0x40000000 / 0x80000000 = 50.00%
 
 if.end12:
   call void @g2()
   br label %for.inc
-; CHECK: edge if.end12 -> for.inc probability is 16 / 16 = 100%
+; CHECK: edge if.end12 -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 for.inc:
   %inc = add nsw i32 %j.017, 1
   %exitcond = icmp eq i32 %inc, %b
   br i1 %exitcond, label %for.end, label %for.body3
-; CHECK: edge for.inc -> for.end probability is 4 / 128
-; CHECK: edge for.inc -> for.body3 probability is 124 / 128
+; CHECK: edge for.inc -> for.end probability is 0x04000000 / 0x80000000 = 3.12%
+; CHECK: edge for.inc -> for.body3 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 
 for.end:
   call void @g3()
   %inc14 = add nsw i32 %i.019, 1
   %exitcond20 = icmp eq i32 %inc14, %a
   br i1 %exitcond20, label %for.end15, label %for.body
-; CHECK: edge for.end -> for.end15 probability is 4 / 128
-; CHECK: edge for.end -> for.body probability is 124 / 128
+; CHECK: edge for.end -> for.end15 probability is 0x04000000 / 0x80000000 = 3.12%
+; CHECK: edge for.end -> for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 
 for.end15:
   call void @g4()
diff --git a/test/Analysis/BranchProbabilityInfo/noreturn.ll b/test/Analysis/BranchProbabilityInfo/noreturn.ll
index 8b9ae11f7d3..63926370cda 100644
--- a/test/Analysis/BranchProbabilityInfo/noreturn.ll
+++ b/test/Analysis/BranchProbabilityInfo/noreturn.ll
@@ -8,8 +8,8 @@ define i32 @test1(i32 %a, i32 %b) {
 entry:
   %cond = icmp eq i32 %a, 42
   br i1 %cond, label %exit, label %abort
-; CHECK: edge entry -> exit probability is 1048575 / 1048576
-; CHECK: edge entry -> abort probability is 1 / 1048576
+; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> abort probability is 0x00000800 / 0x80000000 = 0.00%
 
 abort:
   call void @abort() noreturn
@@ -26,11 +26,11 @@ entry:
                               i32 2, label %case_b
                               i32 3, label %case_c
                               i32 4, label %case_d]
-; CHECK: edge entry -> exit probability is 1048575 / 1048579
-; CHECK: edge entry -> case_a probability is 1 / 1048579
-; CHECK: edge entry -> case_b probability is 1 / 1048579
-; CHECK: edge entry -> case_c probability is 1 / 1048579
-; CHECK: edge entry -> case_d probability is 1 / 1048579
+; CHECK: edge entry -> exit probability is 0x7fffe000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> case_a probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_b probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_c probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_d probability is 0x00000800 / 0x80000000 = 0.00%
 
 case_a:
   br label %case_b
@@ -55,14 +55,14 @@ define i32 @test3(i32 %a, i32 %b) {
 entry:
   %cond1 = icmp eq i32 %a, 42
   br i1 %cond1, label %exit, label %dom
-; CHECK: edge entry -> exit probability is 1048575 / 1048576
-; CHECK: edge entry -> dom probability is 1 / 1048576
+; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> dom probability is 0x00000800 / 0x80000000 = 0.00%
 
 dom:
   %cond2 = icmp ult i32 %a, 42
   br i1 %cond2, label %idom1, label %idom2
-; CHECK: edge dom -> idom1 probability is 1 / 2
-; CHECK: edge dom -> idom2 probability is 1 / 2
+; CHECK: edge dom -> idom1 probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge dom -> idom2 probability is 0x40000000 / 0x80000000 = 50.00%
 
 idom1:
   br label %abort
diff --git a/test/Analysis/BranchProbabilityInfo/pr18705.ll b/test/Analysis/BranchProbabilityInfo/pr18705.ll
index aff08a63d50..f5f9612fcdb 100644
--- a/test/Analysis/BranchProbabilityInfo/pr18705.ll
+++ b/test/Analysis/BranchProbabilityInfo/pr18705.ll
@@ -4,8 +4,8 @@
 ; calcLoopBranchHeuristics should return early without setting the weights.
 ; calcFloatingPointHeuristics, which is run later, sets the weights.
 ;
-; CHECK: edge while.body -> if.then probability is 20 / 32 = 62.5%
-; CHECK: edge while.body -> if.else probability is 12 / 32 = 37.5%
+; CHECK: edge while.body -> if.then probability is 0x50000000 / 0x80000000 = 62.50%
+; CHECK: edge while.body -> if.else probability is 0x30000000 / 0x80000000 = 37.50%
 
 define void @foo1(i32 %n, i32* nocapture %b, i32* nocapture %c, i32* nocapture %d, float* nocapture readonly %f0, float* nocapture readonly %f1) {
 entry:
diff --git a/test/Analysis/BranchProbabilityInfo/pr22718.ll b/test/Analysis/BranchProbabilityInfo/pr22718.ll
index 0de4d643c9c..51bbd13e83c 100644
--- a/test/Analysis/BranchProbabilityInfo/pr22718.ll
+++ b/test/Analysis/BranchProbabilityInfo/pr22718.ll
@@ -4,8 +4,8 @@
 ; 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 216661881 / 2166666667 = 9.9
-; CHECK: edge for.body -> if.else probability is 1950004786 / 2166666667 = 90.0
+; 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]
 
 @y = common global i64 0, align 8
 @x = common global i64 0, align 8
diff --git a/test/CodeGen/AArch64/aarch64-deferred-spilling.ll b/test/CodeGen/AArch64/aarch64-deferred-spilling.ll
index f38925a0e87..7accdced7d4 100644
--- a/test/CodeGen/AArch64/aarch64-deferred-spilling.ll
+++ b/test/CodeGen/AArch64/aarch64-deferred-spilling.ll
@@ -260,7 +260,7 @@ if.then.72:                                       ; preds = %while.body.68.backe
   %verbosity = getelementptr inbounds %struct.DState, %struct.DState* %s, i64 0, i32 12
   %tmp18 = load i32, i32* %verbosity, align 4
   %cmp118 = icmp sgt i32 %tmp18, 1
-  br i1 %cmp118, label %if.then.120, label %sw.bb.123
+  br i1 %cmp118, label %if.then.120, label %sw.bb.123, !prof !0
 
 if.end.82:                                        ; preds = %while.body.68.backedge, %if.end.82.lr.ph
   %lsr.iv480 = phi i32 [ %tmp16, %if.end.82.lr.ph ], [ %lsr.iv.next481, %while.body.68.backedge ]
@@ -510,3 +510,5 @@ save_state_and_return:                            ; preds = %sw.default, %if.end
   store i32 %tmp74, i32* %save_zj20.pre-phi434, align 4
   ret i32 %retVal.0
 }
+
+!0 = !{!"branch_weights", i32 10, i32 1}
diff --git a/test/Transforms/SampleProfile/branch.ll b/test/Transforms/SampleProfile/branch.ll
index 051a73847b2..d367a8495bd 100644
--- a/test/Transforms/SampleProfile/branch.ll
+++ b/test/Transforms/SampleProfile/branch.ll
@@ -36,8 +36,8 @@ entry:
   tail call void @llvm.dbg.value(metadata i8** %argv, i64 0, metadata !14, metadata !DIExpression()), !dbg !27
   %cmp = icmp slt i32 %argc, 2, !dbg !28
   br i1 %cmp, label %return, label %if.end, !dbg !28
-; CHECK: edge entry -> return probability is 0 / 1 = 0%
-; CHECK: edge entry -> if.end probability is 1 / 1 = 100%
+; CHECK: edge entry -> return probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge entry -> if.end probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 if.end:                                           ; preds = %entry
   %arrayidx = getelementptr inbounds i8*, i8** %argv, i64 1, !dbg !30
@@ -46,8 +46,8 @@ if.end:                                           ; preds = %entry
   tail call void @llvm.dbg.value(metadata i32 %call, i64 0, metadata !17, metadata !DIExpression()), !dbg !30
   %cmp1 = icmp sgt i32 %call, 100, !dbg !35
   br i1 %cmp1, label %for.body, label %if.end6, !dbg !35
-; CHECK: edge if.end -> for.body probability is 0 / 1 = 0%
-; CHECK: edge if.end -> if.end6 probability is 1 / 1 = 100%
+; CHECK: edge if.end -> for.body probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge if.end -> if.end6 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 for.body:                                         ; preds = %if.end, %for.body
   %u.016 = phi i32 [ %inc, %for.body ], [ 0, %if.end ]
@@ -65,14 +65,14 @@ for.body:                                         ; preds = %if.end, %for.body
   tail call void @llvm.dbg.value(metadata i32 %inc, i64 0, metadata !21, metadata !DIExpression()), !dbg !38
   %exitcond = icmp eq i32 %inc, %call, !dbg !38
   br i1 %exitcond, label %if.end6, label %for.body, !dbg !38
-; CHECK: edge for.body -> if.end6 probability is 0 / 10226 = 0%
-; CHECK: edge for.body -> for.body probability is 10226 / 10226 = 100% [HOT edge]
+; CHECK: edge for.body -> if.end6 probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge for.body -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 if.end6:                                          ; preds = %for.body, %if.end
   %result.0 = phi double [ 0.000000e+00, %if.end ], [ %sub, %for.body ]
   %call7 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i64 0, i64 0), double %result.0), !dbg !39
   br label %return, !dbg !40
-; CHECK: edge if.end6 -> return probability is 16 / 16 = 100% [HOT edge]
+; CHECK: edge if.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 return:                                           ; preds = %entry, %if.end6
   %retval.0 = phi i32 [ 0, %if.end6 ], [ 1, %entry ]
diff --git a/test/Transforms/SampleProfile/calls.ll b/test/Transforms/SampleProfile/calls.ll
index 9db4f5dc6fd..aa176434cc2 100644
--- a/test/Transforms/SampleProfile/calls.ll
+++ b/test/Transforms/SampleProfile/calls.ll
@@ -52,8 +52,8 @@ while.cond:                                       ; preds = %if.end, %entry
   store i32 %inc, i32* %i, align 4, !dbg !14
   %cmp = icmp slt i32 %0, 400000000, !dbg !14
   br i1 %cmp, label %while.body, label %while.end, !dbg !14
-; CHECK: edge while.cond -> while.body probability is 5391 / 5391 = 100% [HOT edge]
-; CHECK: edge while.cond -> while.end probability is 0 / 5391 = 0%
+; CHECK: edge while.cond -> while.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge while.cond -> while.end probability is 0x00000000 / 0x80000000 = 0.00%
 
 while.body:                                       ; preds = %while.cond
   %1 = load i32, i32* %i, align 4, !dbg !16
@@ -63,8 +63,8 @@ while.body:                                       ; preds = %while.cond
 ; both branches out of while.body had the same weight. In reality,
 ; the edge while.body->if.then is taken most of the time.
 ;
-; CHECK: edge while.body -> if.then probability is 5752 / 5752 = 100% [HOT edge]
-; CHECK: edge while.body -> if.else probability is 0 / 5752 = 0%
+; CHECK: edge while.body -> if.then probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge while.body -> if.else probability is 0x00000000 / 0x80000000 = 0.00%
 
 
 if.then:                                          ; preds = %while.body
diff --git a/test/Transforms/SampleProfile/discriminator.ll b/test/Transforms/SampleProfile/discriminator.ll
index bffeaca0cb8..ffc474b82fd 100644
--- a/test/Transforms/SampleProfile/discriminator.ll
+++ b/test/Transforms/SampleProfile/discriminator.ll
@@ -34,15 +34,15 @@ while.cond:                                       ; preds = %if.end, %entry
   %0 = load i32, i32* %i.addr, align 4, !dbg !12
   %cmp = icmp slt i32 %0, 100, !dbg !12
   br i1 %cmp, label %while.body, label %while.end, !dbg !12
-; CHECK: edge while.cond -> while.body probability is 100 / 101 = 99.0099% [HOT edge]
-; CHECK: edge while.cond -> while.end probability is 1 / 101 = 0.990099%
+; CHECK: edge while.cond -> while.body probability is 0x7ebb907a / 0x80000000 = 99.01% [HOT edge]
+; CHECK: edge while.cond -> while.end probability is 0x01446f86 / 0x80000000 = 0.99%
 
 while.body:                                       ; preds = %while.cond
   %1 = load i32, i32* %i.addr, align 4, !dbg !14
   %cmp1 = icmp slt i32 %1, 50, !dbg !14
   br i1 %cmp1, label %if.then, label %if.end, !dbg !14
-; CHECK: edge while.body -> if.then probability is 5 / 100 = 5%
-; CHECK: edge while.body -> if.end probability is 95 / 100 = 95% [HOT edge]
+; CHECK: edge while.body -> if.then probability is 0x06666666 / 0x80000000 = 5.00%
+; CHECK: edge while.body -> if.end probability is 0x7999999a / 0x80000000 = 95.00% [HOT edge]
 
 if.then:                                          ; preds = %while.body
   %2 = load i32, i32* %x, align 4, !dbg !17
diff --git a/test/Transforms/SampleProfile/fnptr.ll b/test/Transforms/SampleProfile/fnptr.ll
index 3064ad8f636..f95bf9797d9 100644
--- a/test/Transforms/SampleProfile/fnptr.ll
+++ b/test/Transforms/SampleProfile/fnptr.ll
@@ -5,12 +5,12 @@
 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/fnptr.prof | opt -analyze -branch-prob | FileCheck %s
 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/fnptr.binprof | opt -analyze -branch-prob | FileCheck %s
 
-; CHECK:   edge for.body3 -> if.then probability is 534 / 2598 = 20.5543%
-; CHECK:   edge for.body3 -> if.else probability is 2064 / 2598 = 79.4457%
-; CHECK:   edge for.inc -> for.inc12 probability is 1052 / 2598 = 40.4927%
-; CHECK:   edge for.inc -> for.body3 probability is 1546 / 2598 = 59.5073%
-; CHECK:   edge for.inc12 -> for.end14 probability is 518 / 1052 = 49.2395%
-; CHECK:   edge for.inc12 -> for.cond1.preheader probability is 534 / 1052 = 50.7605%
+; CHECK:   edge for.body3 -> if.then probability is 0x1a4f3959 / 0x80000000 = 20.55%
+; CHECK:   edge for.body3 -> if.else probability is 0x65b0c6a7 / 0x80000000 = 79.45%
+; CHECK:   edge for.inc -> for.inc12 probability is 0x33d4a4c1 / 0x80000000 = 40.49%
+; CHECK:   edge for.inc -> for.body3 probability is 0x4c2b5b3f / 0x80000000 = 59.51%
+; CHECK:   edge for.inc12 -> for.end14 probability is 0x3f06d04e / 0x80000000 = 49.24%
+; CHECK:   edge for.inc12 -> for.cond1.preheader probability is 0x40f92fb2 / 0x80000000 = 50.76%
 
 ; Original C++ test case.
 ;
diff --git a/test/Transforms/SampleProfile/propagate.ll b/test/Transforms/SampleProfile/propagate.ll
index 7d5ce7368a2..ca58d17302d 100644
--- a/test/Transforms/SampleProfile/propagate.ll
+++ b/test/Transforms/SampleProfile/propagate.ll
@@ -73,8 +73,8 @@ for.cond:                                         ; preds = %for.inc16, %if.else
   %5 = load i64, i64* %N.addr, align 8, !dbg !15
   %cmp1 = icmp slt i64 %4, %5, !dbg !15
   br i1 %cmp1, label %for.body, label %for.end18, !dbg !15
-; CHECK: edge for.cond -> for.body probability is 10 / 10 = 100% [HOT edge]
-; CHECK: edge for.cond -> for.end18 probability is 0 / 10 = 0%
+; CHECK: edge for.cond -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge for.cond -> for.end18 probability is 0x00000000 / 0x80000000 = 0.00%
 
 for.body:                                         ; preds = %for.cond
   %6 = load i64, i64* %i, align 8, !dbg !18
@@ -82,8 +82,8 @@ for.body:                                         ; preds = %for.cond
   %div = sdiv i64 %7, 3, !dbg !18
   %cmp2 = icmp sgt i64 %6, %div, !dbg !18
   br i1 %cmp2, label %if.then3, label %if.end, !dbg !18
-; CHECK: edge for.body -> if.then3 probability is 1 / 5 = 20%
-; CHECK: edge for.body -> if.end probability is 4 / 5 = 80%
+; CHECK: edge for.body -> if.then3 probability is 0x1999999a / 0x80000000 = 20.00%
+; CHECK: edge for.body -> if.end probability is 0x66666666 / 0x80000000 = 80.00%
 
 if.then3:                                         ; preds = %for.body
   %8 = load i32, i32* %x.addr, align 4, !dbg !21
@@ -97,8 +97,8 @@ if.end:                                           ; preds = %if.then3, %for.body
   %div4 = sdiv i64 %10, 4, !dbg !22
   %cmp5 = icmp sgt i64 %9, %div4, !dbg !22
   br i1 %cmp5, label %if.then6, label %if.else7, !dbg !22
-; CHECK: edge if.end -> if.then6 probability is 3 / 6342 = 0.0473037%
-; CHECK: edge if.end -> if.else7 probability is 6339 / 6342 = 99.9527% [HOT edge]
+; CHECK: edge if.end -> if.then6 probability is 0x000f801f / 0x80000000 = 0.05%
+; CHECK: edge if.end -> if.else7 probability is 0x7ff07fe1 / 0x80000000 = 99.95% [HOT edge]
 
 if.then6:                                         ; preds = %if.end
   %11 = load i32, i32* %y.addr, align 4, !dbg !24
@@ -119,8 +119,8 @@ for.cond8:                                        ; preds = %for.inc, %if.else7
   %14 = load i64, i64* %i, align 8, !dbg !28
   %cmp10 = icmp slt i64 %conv9, %14, !dbg !28
   br i1 %cmp10, label %for.body11, label %for.end, !dbg !28
-; CHECK: edge for.cond8 -> for.body11 probability is 16191 / 16191 = 100% [HOT edge]
-; CHECK: edge for.cond8 -> for.end probability is 0 / 16191 = 0%
+; CHECK: edge for.cond8 -> for.body11 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge for.cond8 -> for.end probability is 0x00000000 / 0x80000000 = 0.00%
 
 for.body11:                                       ; preds = %for.cond8
   %15 = load i32, i32* %j, align 4, !dbg !31
diff --git a/unittests/Support/BlockFrequencyTest.cpp b/unittests/Support/BlockFrequencyTest.cpp
index 0eac8bb8811..c3273bf4ab2 100644
--- a/unittests/Support/BlockFrequencyTest.cpp
+++ b/unittests/Support/BlockFrequencyTest.cpp
@@ -19,7 +19,7 @@ namespace {
 
 TEST(BlockFrequencyTest, OneToZero) {
   BlockFrequency Freq(1);
-  BranchProbability Prob(UINT32_MAX - 1, UINT32_MAX);
+  BranchProbability Prob(UINT32_MAX / 3, UINT32_MAX);
   Freq *= Prob;
   EXPECT_EQ(Freq.getFrequency(), 0u);
 
@@ -54,11 +54,11 @@ TEST(BlockFrequencyTest, MaxToHalfMax) {
   BlockFrequency Freq(UINT64_MAX);
   BranchProbability Prob(UINT32_MAX / 2, UINT32_MAX);
   Freq *= Prob;
-  EXPECT_EQ(Freq.getFrequency(), 9223372034707292159ULL);
+  EXPECT_EQ(Freq.getFrequency(), 9223372036854775807ULL);
 
   Freq = BlockFrequency(UINT64_MAX);
   Freq *= Prob;
-  EXPECT_EQ(Freq.getFrequency(), 9223372034707292159ULL);
+  EXPECT_EQ(Freq.getFrequency(), 9223372036854775807ULL);
 }
 
 TEST(BlockFrequencyTest, BigToBig) {
@@ -97,18 +97,18 @@ TEST(BlockFrequency, Divide) {
 TEST(BlockFrequencyTest, Saturate) {
   BlockFrequency Freq(0x3333333333333333ULL);
   Freq /= BranchProbability(100, 300);
-  EXPECT_EQ(Freq.getFrequency(), 0x9999999999999999ULL);
+  EXPECT_EQ(Freq.getFrequency(), 0x9999999866666668ULL);
   Freq /= BranchProbability(1, 2);
   EXPECT_EQ(Freq.getFrequency(), UINT64_MAX);
 
   Freq = 0x1000000000000000ULL;
-  Freq /= BranchProbability(10000, 160000);
+  Freq /= BranchProbability(10000, 170000);
   EXPECT_EQ(Freq.getFrequency(), UINT64_MAX);
 
   // Try to cheat the multiplication overflow check.
   Freq = 0x00000001f0000001ull;
   Freq /= BranchProbability(1000, 0xf000000f);
-  EXPECT_EQ(33506781356485509ULL, Freq.getFrequency());
+  EXPECT_EQ(33527736066704712ULL, Freq.getFrequency());
 }
 
 TEST(BlockFrequencyTest, SaturatingRightShift) {
diff --git a/unittests/Support/BranchProbabilityTest.cpp b/unittests/Support/BranchProbabilityTest.cpp
index 43bfa849f3a..87a25091947 100644
--- a/unittests/Support/BranchProbabilityTest.cpp
+++ b/unittests/Support/BranchProbabilityTest.cpp
@@ -22,12 +22,12 @@ namespace {
 
 typedef BranchProbability BP;
 TEST(BranchProbabilityTest, Accessors) {
-  EXPECT_EQ(1u, BP(1, 7).getNumerator());
-  EXPECT_EQ(7u, BP(1, 7).getDenominator());
+  EXPECT_EQ(306783378u, BP(1, 7).getNumerator());
+  EXPECT_EQ(1u << 31, BP(1, 7).getDenominator());
   EXPECT_EQ(0u, BP::getZero().getNumerator());
-  EXPECT_EQ(1u, BP::getZero().getDenominator());
-  EXPECT_EQ(1u, BP::getOne().getNumerator());
-  EXPECT_EQ(1u, BP::getOne().getDenominator());
+  EXPECT_EQ(1u << 31, BP::getZero().getDenominator());
+  EXPECT_EQ(1u << 31, BP::getOne().getNumerator());
+  EXPECT_EQ(1u << 31, BP::getOne().getDenominator());
 }
 
 TEST(BranchProbabilityTest, Operators) {
@@ -78,6 +78,12 @@ TEST(BranchProbabilityTest, Operators) {
   EXPECT_FALSE(BP(1, 7) != BP(2, 14));
   EXPECT_TRUE(BP(4, 7) != BP(1, 2));
   EXPECT_TRUE(BP(4, 7) != BP(3, 7));
+
+  EXPECT_TRUE(BP(1, 7) == BP(2, 14));
+  EXPECT_TRUE(BP(1, 7) == BP(3, 21));
+  EXPECT_TRUE(BP(5, 7) == BP(25, 35));
+  EXPECT_TRUE(BP(99999998, 100000000) < BP(99999999, 100000000));
+  EXPECT_TRUE(BP(4, 8) == BP(400000000, 800000000));
 }
 
 TEST(BranchProbabilityTest, MoreOperators) {
@@ -139,10 +145,10 @@ TEST(BranchProbabilityTest, scale) {
   // Big fractions.
   EXPECT_EQ(1u, BP(Two31, UINT32_MAX).scale(2));
   EXPECT_EQ(Two31, BP(Two31, UINT32_MAX).scale(Two31 * 2));
-  EXPECT_EQ(Two63 + Two31, BP(Two31, UINT32_MAX).scale(UINT64_MAX));
+  EXPECT_EQ(9223372036854775807ULL, BP(Two31, UINT32_MAX).scale(UINT64_MAX));
 
   // High precision.
-  EXPECT_EQ(UINT64_C(9223372047592194055),
+  EXPECT_EQ(UINT64_C(9223372045444710399),
             BP(Two31 + 1, UINT32_MAX - 2).scale(UINT64_MAX));
 }
 
@@ -155,11 +161,13 @@ TEST(BranchProbabilityTest, scaleByInverse) {
   EXPECT_EQ(0u, BP(1, 1).scaleByInverse(0));
   EXPECT_EQ(0u, BP(7, 7).scaleByInverse(0));
 
+  auto MAX_DENOMINATOR = BP::getDenominator();
+
   // Divide by something very small.
   EXPECT_EQ(UINT64_MAX, BP(1, UINT32_MAX).scaleByInverse(UINT64_MAX));
-  EXPECT_EQ(uint64_t(UINT32_MAX) * UINT32_MAX,
-            BP(1, UINT32_MAX).scaleByInverse(UINT32_MAX));
-  EXPECT_EQ(UINT32_MAX, BP(1, UINT32_MAX).scaleByInverse(1));
+  EXPECT_EQ(uint64_t(UINT32_MAX) * MAX_DENOMINATOR,
+            BP(1, MAX_DENOMINATOR).scaleByInverse(UINT32_MAX));
+  EXPECT_EQ(MAX_DENOMINATOR, BP(1, MAX_DENOMINATOR).scaleByInverse(1));
 
   auto Two63 = UINT64_C(1) << 63;
   auto Two31 = UINT64_C(1) << 31;
@@ -169,18 +177,18 @@ TEST(BranchProbabilityTest, scaleByInverse) {
   EXPECT_EQ(UINT64_MAX, BP(1, 2).scaleByInverse(Two63));
 
   // Big fractions.
-  EXPECT_EQ(1u, BP(Two31, UINT32_MAX).scaleByInverse(1));
+  EXPECT_EQ(2u, BP(Two31, UINT32_MAX).scaleByInverse(1));
   EXPECT_EQ(2u, BP(Two31 - 1, UINT32_MAX).scaleByInverse(1));
-  EXPECT_EQ(Two31 * 2 - 1, BP(Two31, UINT32_MAX).scaleByInverse(Two31));
-  EXPECT_EQ(Two31 * 2 + 1, BP(Two31 - 1, UINT32_MAX).scaleByInverse(Two31));
+  EXPECT_EQ(Two31 * 2, BP(Two31, UINT32_MAX).scaleByInverse(Two31));
+  EXPECT_EQ(Two31 * 2, BP(Two31 - 1, UINT32_MAX).scaleByInverse(Two31));
   EXPECT_EQ(UINT64_MAX, BP(Two31, UINT32_MAX).scaleByInverse(Two63 + Two31));
 
   // High precision.  The exact answers to these are close to the successors of
   // the floor.  If we were rounding, these would round up.
-  EXPECT_EQ(UINT64_C(18446744065119617030),
+  EXPECT_EQ(UINT64_C(18446744060824649767),
             BP(Two31 + 2, UINT32_MAX - 2)
-                .scaleByInverse(UINT64_C(9223372047592194055)));
-  EXPECT_EQ(UINT64_C(18446744065119617026),
+                .scaleByInverse(UINT64_C(9223372047592194056)));
+  EXPECT_EQ(UINT64_C(18446744060824649739),
             BP(Two31 + 1, UINT32_MAX).scaleByInverse(Two63 + Two31));
 }
 
@@ -191,87 +199,87 @@ TEST(BranchProbabilityTest, scaleBruteForce) {
     uint64_t Result;
   } Tests[] = {
     // Data for scaling that results in <= 64 bit division.
-    { 0x1423e2a50ULL, { 0x64819521, 0x7765dd13 }, 0x10f418889ULL },
-    { 0x35ef14ceULL, { 0x28ade3c7, 0x304532ae }, 0x2d73c33aULL },
-    { 0xd03dbfbe24ULL, { 0x790079, 0xe419f3 }, 0x6e776fc1fdULL },
-    { 0x21d67410bULL, { 0x302a9dc2, 0x3ddb4442 }, 0x1a5948fd6ULL },
+    { 0x1423e2a50ULL, { 0x64819521, 0x7765dd13 }, 0x10f418888ULL },
+    { 0x35ef14ceULL, { 0x28ade3c7, 0x304532ae }, 0x2d73c33bULL },
+    { 0xd03dbfbe24ULL, { 0x790079, 0xe419f3 }, 0x6e776fc2c4ULL },
+    { 0x21d67410bULL, { 0x302a9dc2, 0x3ddb4442 }, 0x1a5948fd4ULL },
     { 0x8664aeadULL, { 0x3d523513, 0x403523b1 }, 0x805a04cfULL },
-    { 0x201db0cf4ULL, { 0x35112a7b, 0x79fc0c74 }, 0xdf8b07f6ULL },
-    { 0x13f1e4430aULL, { 0x21c92bf, 0x21e63aae }, 0x13e0cba15ULL },
+    { 0x201db0cf4ULL, { 0x35112a7b, 0x79fc0c74 }, 0xdf8b07f8ULL },
+    { 0x13f1e4430aULL, { 0x21c92bf, 0x21e63aae }, 0x13e0cba26ULL },
     { 0x16c83229ULL, { 0x3793f66f, 0x53180dea }, 0xf3ce7b6ULL },
-    { 0xc62415be8ULL, { 0x9cc4a63, 0x4327ae9b }, 0x1ce8b71caULL },
+    { 0xc62415be8ULL, { 0x9cc4a63, 0x4327ae9b }, 0x1ce8b71c1ULL },
     { 0x6fac5e434ULL, { 0xe5f9170, 0x1115e10b }, 0x5df23dd4cULL },
-    { 0x1929375f2ULL, { 0x3a851375, 0x76c08456 }, 0xc662b082ULL },
-    { 0x243c89db6ULL, { 0x354ebfc0, 0x450ef197 }, 0x1bf8c1661ULL },
+    { 0x1929375f2ULL, { 0x3a851375, 0x76c08456 }, 0xc662b083ULL },
+    { 0x243c89db6ULL, { 0x354ebfc0, 0x450ef197 }, 0x1bf8c1663ULL },
     { 0x310e9b31aULL, { 0x1b1b8acf, 0x2d3629f0 }, 0x1d69c93f9ULL },
-    { 0xa1fae921dULL, { 0xa7a098c, 0x10469f44 }, 0x684413d6cULL },
-    { 0xc1582d957ULL, { 0x498e061, 0x59856bc }, 0x9edc5f4e7ULL },
+    { 0xa1fae921dULL, { 0xa7a098c, 0x10469f44 }, 0x684413d6eULL },
+    { 0xc1582d957ULL, { 0x498e061, 0x59856bc }, 0x9edc5f4ecULL },
     { 0x57cfee75ULL, { 0x1d061dc3, 0x7c8bfc17 }, 0x1476a220ULL },
-    { 0x139220080ULL, { 0x294a6c71, 0x2a2b07c9 }, 0x1329e1c76ULL },
-    { 0x1665d353cULL, { 0x7080db5, 0xde0d75c }, 0xb590d9fbULL },
+    { 0x139220080ULL, { 0x294a6c71, 0x2a2b07c9 }, 0x1329e1c75ULL },
+    { 0x1665d353cULL, { 0x7080db5, 0xde0d75c }, 0xb590d9faULL },
     { 0xe8f14541ULL, { 0x5188e8b2, 0x736527ef }, 0xa4971be5ULL },
     { 0x2f4775f29ULL, { 0x254ef0fe, 0x435fcf50 }, 0x1a2e449c1ULL },
-    { 0x27b85d8d7ULL, { 0x304c8220, 0x5de678f2 }, 0x146e3bef9ULL },
-    { 0x1d362e36bULL, { 0x36c85b12, 0x37a66f55 }, 0x1cc19b8e6ULL },
-    { 0x155fd48c7ULL, { 0xf5894d, 0x1256108 }, 0x11e383602ULL },
+    { 0x27b85d8d7ULL, { 0x304c8220, 0x5de678f2 }, 0x146e3befbULL },
+    { 0x1d362e36bULL, { 0x36c85b12, 0x37a66f55 }, 0x1cc19b8e7ULL },
+    { 0x155fd48c7ULL, { 0xf5894d, 0x1256108 }, 0x11e383604ULL },
     { 0xb5db2d15ULL, { 0x39bb26c5, 0x5bdcda3e }, 0x72499259ULL },
-    { 0x153990298ULL, { 0x48921c09, 0x706eb817 }, 0xdb3268e8ULL },
-    { 0x28a7c3ed7ULL, { 0x1f776fd7, 0x349f7a70 }, 0x184f73ae1ULL },
+    { 0x153990298ULL, { 0x48921c09, 0x706eb817 }, 0xdb3268e7ULL },
+    { 0x28a7c3ed7ULL, { 0x1f776fd7, 0x349f7a70 }, 0x184f73ae2ULL },
     { 0x724dbeabULL, { 0x1bd149f5, 0x253a085e }, 0x5569c0b3ULL },
-    { 0xd8f0c513ULL, { 0x18c8cc4c, 0x1b72bad0 }, 0xc3e30643ULL },
+    { 0xd8f0c513ULL, { 0x18c8cc4c, 0x1b72bad0 }, 0xc3e30642ULL },
     { 0x17ce3dcbULL, { 0x1e4c6260, 0x233b359e }, 0x1478f4afULL },
-    { 0x1ce036ce0ULL, { 0x29e3c8af, 0x5318dd4a }, 0xe8e76196ULL },
+    { 0x1ce036ce0ULL, { 0x29e3c8af, 0x5318dd4a }, 0xe8e76195ULL },
     { 0x1473ae2aULL, { 0x29b897ba, 0x2be29378 }, 0x13718185ULL },
     { 0x1dd41aa68ULL, { 0x3d0a4441, 0x5a0e8f12 }, 0x1437b6bbfULL },
     { 0x1b49e4a53ULL, { 0x3430c1fe, 0x5a204aed }, 0xfcd6852fULL },
     { 0x217941b19ULL, { 0x12ced2bd, 0x21b68310 }, 0x12aca65b1ULL },
     { 0xac6a4dc8ULL, { 0x3ed68da8, 0x6fdca34c }, 0x60da926dULL },
-    { 0x1c503a4e7ULL, { 0xfcbbd32, 0x11e48d17 }, 0x18fec7d38ULL },
-    { 0x1c885855ULL, { 0x213e919d, 0x25941897 }, 0x193de743ULL },
-    { 0x29b9c168eULL, { 0x2b644aea, 0x45725ee7 }, 0x1a122e5d5ULL },
+    { 0x1c503a4e7ULL, { 0xfcbbd32, 0x11e48d17 }, 0x18fec7d37ULL },
+    { 0x1c885855ULL, { 0x213e919d, 0x25941897 }, 0x193de742ULL },
+    { 0x29b9c168eULL, { 0x2b644aea, 0x45725ee7 }, 0x1a122e5d4ULL },
     { 0x806a33f2ULL, { 0x30a80a23, 0x5063733a }, 0x4db9a264ULL },
     { 0x282afc96bULL, { 0x143ae554, 0x1a9863ff }, 0x1e8de5204ULL },
     // Data for scaling that results in > 64 bit division.
-    { 0x23ca5f2f672ca41cULL, { 0xecbc641, 0x111373f7 }, 0x1f0301e5e8295ab5ULL },
-    { 0x5e4f2468142265e3ULL, { 0x1ddf5837, 0x32189233 }, 0x383ca7ba9fdd2c8cULL },
-    { 0x277a1a6f6b266bf6ULL, { 0x415d81a8, 0x61eb5e1e }, 0x1a5a3e1d41b30c0fULL },
-    { 0x1bdbb49a237035cbULL, { 0xea5bf17, 0x1d25ffb3 }, 0xdffc51c53d44b93ULL },
-    { 0x2bce6d29b64fb8ULL, { 0x3bfd5631, 0x7525c9bb }, 0x166ebedda7ac57ULL },
-    { 0x3a02116103df5013ULL, { 0x2ee18a83, 0x3299aea8 }, 0x35be8922ab1e2a84ULL },
-    { 0x7b5762390799b18cULL, { 0x12f8e5b9, 0x2563bcd4 }, 0x3e960077aca01209ULL },
-    { 0x69cfd72537021579ULL, { 0x4c35f468, 0x6a40feee }, 0x4be4cb3848be98a3ULL },
-    { 0x49dfdf835120f1c1ULL, { 0x8cb3759, 0x559eb891 }, 0x79663f7120edadeULL },
-    { 0x74b5be5c27676381ULL, { 0x47e4c5e0, 0x7c7b19ff }, 0x4367d2dff36a1028ULL },
-    { 0x4f50f97075e7f431ULL, { 0x9a50a17, 0x11cd1185 }, 0x2af952b34c032df4ULL },
-    { 0x2f8b0d712e393be4ULL, { 0x1487e386, 0x15aa356e }, 0x2d0df36478a776aaULL },
-    { 0x224c1c75999d3deULL, { 0x3b2df0ea, 0x4523b100 }, 0x1d5b481d145f08aULL },
-    { 0x2bcbcea22a399a76ULL, { 0x28b58212, 0x48dd013e }, 0x187814d084c47cabULL },
-    { 0x1dbfca91257cb2d1ULL, { 0x1a8c04d9, 0x5e92502c }, 0x859cf7d00f77545ULL },
-    { 0x7f20039b57cda935ULL, { 0xeccf651, 0x323f476e }, 0x25720cd976461a77ULL },
-    { 0x40512c6a586aa087ULL, { 0x113b0423, 0x398c9eab }, 0x1341c03de8696a7eULL },
-    { 0x63d802693f050a11ULL, { 0xf50cdd6, 0xfce2a44 }, 0x60c0177bb5e46846ULL },
-    { 0x2d956b422838de77ULL, { 0xb2d345b, 0x1321e557 }, 0x1aa0ed16b6aa5319ULL },
-    { 0x5a1cdf0c1657bc91ULL, { 0x1d77bb0c, 0x1f991ff1 }, 0x54097ee94ff87560ULL },
-    { 0x3801b26d7e00176bULL, { 0xeed25da, 0x1a819d8b }, 0x1f89e96a3a639526ULL },
-    { 0x37655e74338e1e45ULL, { 0x300e170a, 0x5a1595fe }, 0x1d8cfb55fddc0441ULL },
-    { 0x7b38703f2a84e6ULL, { 0x66d9053, 0xc79b6b9 }, 0x3f7d4c91774094ULL },
-    { 0x2245063c0acb3215ULL, { 0x30ce2f5b, 0x610e7271 }, 0x113b916468389235ULL },
-    { 0x6bc195877b7b8a7eULL, { 0x392004aa, 0x4a24e60c }, 0x530594fb17db6ba5ULL },
-    { 0x40a3fde23c7b43dbULL, { 0x4e712195, 0x6553e56e }, 0x320a799bc76a466aULL },
-    { 0x1d3dfc2866fbccbaULL, { 0x5075b517, 0x5fc42245 }, 0x18917f0061595bc3ULL },
-    { 0x19aeb14045a61121ULL, { 0x1bf6edec, 0x707e2f4b }, 0x6626672a070bcc7ULL },
-    { 0x44ff90486c531e9fULL, { 0x66598a, 0x8a90dc }, 0x32f6f2b0525199b0ULL },
-    { 0x3f3e7121092c5bcbULL, { 0x1c754df7, 0x5951a1b9 }, 0x14267f50b7ef375dULL },
-    { 0x60e2dafb7e50a67eULL, { 0x4d96c66e, 0x65bd878d }, 0x49e31715ac393f8bULL },
-    { 0x656286667e0e6e29ULL, { 0x9d971a2, 0xacda23b }, 0x5c6ee315ead6cb4fULL },
-    { 0x1114e0974255d507ULL, { 0x1c693, 0x2d6ff }, 0xaae42e4b35f6e60ULL },
-    { 0x508c8baf3a70ff5aULL, { 0x3b26b779, 0x6ad78745 }, 0x2c98387636c4b365ULL },
-    { 0x5b47bc666bf1f9cfULL, { 0x10a87ed6, 0x187d358a }, 0x3e1767155848368bULL },
-    { 0x50954e3744460395ULL, { 0x7a42263, 0xcdaa048 }, 0x2fe739f0aee1fee1ULL },
-    { 0x20020b406550dd8fULL, { 0x3318539, 0x42eead0 }, 0x186f326325fa346bULL },
-    { 0x5bcb0b872439ffd5ULL, { 0x6f61fb2, 0x9af7344 }, 0x41fa1e3bec3c1b30ULL },
-    { 0x7a670f365db87a53ULL, { 0x417e102, 0x3bb54c67 }, 0x8642a558304fd9eULL },
-    { 0x1ef0db1e7bab1cd0ULL, { 0x2b60cf38, 0x4188f78f }, 0x147ae0d6226b2ee6ULL }
+    { 0x23ca5f2f672ca41cULL, { 0xecbc641, 0x111373f7 }, 0x1f0301e5c76869c6ULL },
+    { 0x5e4f2468142265e3ULL, { 0x1ddf5837, 0x32189233 }, 0x383ca7bad6053ac9ULL },
+    { 0x277a1a6f6b266bf6ULL, { 0x415d81a8, 0x61eb5e1e }, 0x1a5a3e1d1c9e8540ULL },
+    { 0x1bdbb49a237035cbULL, { 0xea5bf17, 0x1d25ffb3 }, 0xdffc51c5cb51cf1ULL },
+    { 0x2bce6d29b64fb8ULL, { 0x3bfd5631, 0x7525c9bb }, 0x166ebedd9581fdULL },
+    { 0x3a02116103df5013ULL, { 0x2ee18a83, 0x3299aea8 }, 0x35be89227276f105ULL },
+    { 0x7b5762390799b18cULL, { 0x12f8e5b9, 0x2563bcd4 }, 0x3e960077695655a3ULL },
+    { 0x69cfd72537021579ULL, { 0x4c35f468, 0x6a40feee }, 0x4be4cb38695a4f30ULL },
+    { 0x49dfdf835120f1c1ULL, { 0x8cb3759, 0x559eb891 }, 0x79663f6e3c8d8f6ULL },
+    { 0x74b5be5c27676381ULL, { 0x47e4c5e0, 0x7c7b19ff }, 0x4367d2dfb22b3265ULL },
+    { 0x4f50f97075e7f431ULL, { 0x9a50a17, 0x11cd1185 }, 0x2af952b30374f382ULL },
+    { 0x2f8b0d712e393be4ULL, { 0x1487e386, 0x15aa356e }, 0x2d0df3649b2b19fcULL },
+    { 0x224c1c75999d3deULL, { 0x3b2df0ea, 0x4523b100 }, 0x1d5b481d160dd8bULL },
+    { 0x2bcbcea22a399a76ULL, { 0x28b58212, 0x48dd013e }, 0x187814d0610c8a56ULL },
+    { 0x1dbfca91257cb2d1ULL, { 0x1a8c04d9, 0x5e92502c }, 0x859cf7d19e83ad0ULL },
+    { 0x7f20039b57cda935ULL, { 0xeccf651, 0x323f476e }, 0x25720cd9054634bdULL },
+    { 0x40512c6a586aa087ULL, { 0x113b0423, 0x398c9eab }, 0x1341c03dbb662054ULL },
+    { 0x63d802693f050a11ULL, { 0xf50cdd6, 0xfce2a44 }, 0x60c0177b667a4feaULL },
+    { 0x2d956b422838de77ULL, { 0xb2d345b, 0x1321e557 }, 0x1aa0ed16b094575cULL },
+    { 0x5a1cdf0c1657bc91ULL, { 0x1d77bb0c, 0x1f991ff1 }, 0x54097ee9907290eaULL },
+    { 0x3801b26d7e00176bULL, { 0xeed25da, 0x1a819d8b }, 0x1f89e96a616b9abeULL },
+    { 0x37655e74338e1e45ULL, { 0x300e170a, 0x5a1595fe }, 0x1d8cfb55ff6a6dbcULL },
+    { 0x7b38703f2a84e6ULL, { 0x66d9053, 0xc79b6b9 }, 0x3f7d4c91b9afb9ULL },
+    { 0x2245063c0acb3215ULL, { 0x30ce2f5b, 0x610e7271 }, 0x113b916455fe2560ULL },
+    { 0x6bc195877b7b8a7eULL, { 0x392004aa, 0x4a24e60c }, 0x530594fabfc81cc3ULL },
+    { 0x40a3fde23c7b43dbULL, { 0x4e712195, 0x6553e56e }, 0x320a799bc205c78dULL },
+    { 0x1d3dfc2866fbccbaULL, { 0x5075b517, 0x5fc42245 }, 0x18917f00745cb781ULL },
+    { 0x19aeb14045a61121ULL, { 0x1bf6edec, 0x707e2f4b }, 0x6626672aa2ba10aULL },
+    { 0x44ff90486c531e9fULL, { 0x66598a, 0x8a90dc }, 0x32f6f2b097001598ULL },
+    { 0x3f3e7121092c5bcbULL, { 0x1c754df7, 0x5951a1b9 }, 0x14267f50d4971583ULL },
+    { 0x60e2dafb7e50a67eULL, { 0x4d96c66e, 0x65bd878d }, 0x49e317155d75e883ULL },
+    { 0x656286667e0e6e29ULL, { 0x9d971a2, 0xacda23b }, 0x5c6ee3159e1deac3ULL },
+    { 0x1114e0974255d507ULL, { 0x1c693, 0x2d6ff }, 0xaae42e4be5f9f8dULL },
+    { 0x508c8baf3a70ff5aULL, { 0x3b26b779, 0x6ad78745 }, 0x2c983876178ed5b1ULL },
+    { 0x5b47bc666bf1f9cfULL, { 0x10a87ed6, 0x187d358a }, 0x3e1767153bea720aULL },
+    { 0x50954e3744460395ULL, { 0x7a42263, 0xcdaa048 }, 0x2fe739f0944a023cULL },
+    { 0x20020b406550dd8fULL, { 0x3318539, 0x42eead0 }, 0x186f326307c0d985ULL },
+    { 0x5bcb0b872439ffd5ULL, { 0x6f61fb2, 0x9af7344 }, 0x41fa1e3c47f0f80dULL },
+    { 0x7a670f365db87a53ULL, { 0x417e102, 0x3bb54c67 }, 0x8642a551d0f41b0ULL },
+    { 0x1ef0db1e7bab1cd0ULL, { 0x2b60cf38, 0x4188f78f }, 0x147ae0d63fc0575aULL }
   };
 
   for (const auto &T : Tests) {
-- 
2.34.1