Use fixed-point representation for BranchProbability

[congh]

Summary

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 UINT32_MAX. 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/2 may not be exactly identical to 1 / 2 (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 (see http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20150803/291610.html for the proposal and discussions). 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.

Most test cases are updated with this change, except those of BranchProbability and BlockFrequency unit tests, which fail due to imprecise representation. If this patch is approved I will update them later.

[chapuni]

Could we introduce fixed-point arithmetic class for general use?
(It'd be not urgent)

[davidxl]

For block frequency print, I think it might make sense to set a fixed precision in the print. For instance, when the value is less than 1, do the following to filter noise in testing:

OS << format("%.2f", float_freq)

otherwise

OS << format("%.1f", flat_freq)

include/llvm/Support/BranchProbability.h

49 ↗

(On Diff #33893)

Do we really need this method? If update is done properly, this is not needed. Similar method can be defined for verification purpose.

51 ↗

(On Diff #33893)

Should be a private method.

52 ↗

(On Diff #33893)

Make this private.

lib/Support/BranchProbability.cpp

35 ↗

(On Diff #33893)

To make result with the right rounding, do this

Prob64 = n * (D + d/2) / d

test/Analysis/BlockFrequencyInfo/basic.ll

71 ↗

(On Diff #33893)

where does the coma come from?

[congh]

In D12603#240665, @davidxl wrote:

For block frequency print, I think it might make sense to set a fixed precision in the print. For instance, when the value is less than 1, do the following to filter noise in testing:

OS << format("%.2f", float_freq)

otherwise

OS << format("%.1f", flat_freq)

Do we really need this precision to represent subtle differences?

include/llvm/Support/BranchProbability.h

49 ↗

(On Diff #33893)

This is not needed in this patch but will be needed when substituting weights with probabilities. This is a utility function that is used to normalize several probabilities assigned to all successors. I can remove it from this patch and add it later.

51 ↗

(On Diff #33893)

It will be used in branch probability unit test.

52 ↗

(On Diff #33893)

Ditto.

lib/Support/BranchProbability.cpp

35 ↗

(On Diff #33893)

OK.

test/Analysis/BlockFrequencyInfo/basic.ll

71 ↗

(On Diff #33893)

With this patch, the result is not 0.8 but 0.8000000001. Removing the comma is a quick way to capture 0.8 but not those zeros behind it. Maybe I should use regex here?

[congh]

Update the patch by addressing issues pointed by Duncan and David.

[davidxl]

test/CodeGen/AArch64/aarch64-deferred-spilling.ll

26 ↗

(On Diff #33893)

register name change?

test/CodeGen/ARM/cmpxchg-weak.ll

11 ↗

(On Diff #34296)

unrelated change?

34 ↗

(On Diff #34296)

unrelated change?

test/CodeGen/ARM/ifcvt-branch-weight-bug.ll

26 ↗

(On Diff #34296)

bb#4->bb#5 : unrelated change.

test/CodeGen/ARM/vector-promotion.ll

56 ↗

(On Diff #34296)

unrelated change

[congh]

Update the patch by considering rounding when scaling an integer by a probability. Also update test cases accordingly.

[congh]

test/CodeGen/AArch64/aarch64-deferred-spilling.ll

26 ↗

(On Diff #33893)

Fixed. This test case keeps unchanged after the patch update. See explains below.

test/CodeGen/ARM/cmpxchg-weak.ll

11 ↗

(On Diff #34296)

This change is caused by fixed point probability representation. After investigating the root cause, I found that it is from if-conversion. More specifically, when determine whether to do if-conversion there is a cost model measurement in which the branch probability is used to scale some cost (in integers). The current scale method does not round the result, which may be a problem. For example, ARMBaseInstrInfo::isProfitableToIfCvt() has the following statements:

unsigned TUnpredCost = Probability.scale(TCycles);
unsigned FUnpredCost = Probability.getCompl().scale(FCycles);
unsigned UnpredCost = TUnpredCost + FUnpredCost;

Now assume Probability is 0.5 and both TCycles and FCycles are 1. If scale() does not round, then TUnpredCost and FUnpredCost are 0, and hence UnpredCost = TUnpredCost + FUnpredCost is also zero. This doesn't make sense as here if we calculate the cost in floating point we should get ~1 as UnpredCost.

We we do round in scale(), it is possible to get both TUnpredCost and FUnpredCost as 1, which is also incorrect. However, in our fixed point representation, 0.5 is actually a little less than 0.5, and its complement is a little greater than 0.5. Therefore we will have TUnpredCost = 0, and FUnpredCost = 1 after rounding. This is very hacky.

So I think we do need scale() to have rounding behavior, but in ARMBaseInstrInfo::isProfitableToIfCvt() to avoid precision related issues it is better to scale TCycles/FCycles up (e.g. x1000) before scaling them by Probability. This is find as the function returns the value of

return (TCycles + FCycles + TExtra + FExtra) <= UnpredCost;

and we can scale every operands up.

What do you think?

[congh]

After supporing rounding in scale(), the if-conversion is enabled for several test cases and that is why they are updated accordingly.

[congh]

In D12603#239967, @chapuni wrote:

Could we introduce fixed-point arithmetic class for general use?
(It'd be not urgent)

Sorry for the late reply! Do we need such a class in LLVM? Except BlockMass, do we have other usages or demands of fixed-point class? If yes, it is not difficult to abstract such a class from the new BranchProbability in this patch.

[davidxl]

I think this can be done as a follow up patch -- having
BranchProbability derive from Ratio which is derived from FixedPoint
Rep.

David

[davidxl]

You explanation makes sense -- I saw the other patch to fix the
rounding bug in ifcvt.

David

[congh]

Update the patch by fixing block frequency / branch probability unit tests failures.

I am not sure if this is the right way to update the unit tests. The fixed-point representation has precision issues comparing to the previous rational representation and that is why we need to update the comparison right answers in unit tests.

[davidxl]

Cong, It is more common to use power of 2 as the scaling factor in
fixed point representation for computation efficiency. For 32bit
width, 0x80000000 is common (noted as Q31). Here are the benefits

1. it is much faster to do the scale operation with Q31 -- instead of

using the current slow version of scale, it can call a faster version
to be introduced.

This will probably help resolve bug
https://llvm.org/bugs/show_bug.cgi?id=24620 where 20% of the time is
spent in the slow version of the scale method.

2. it allows negative fractional number to be represented

3. it is more precise for lots of common cases. For instance,

representation of 0.5, 0.25, 0.75 (i.e. 1/2, 1/4, 3/4) etc are
actually lossless with Q31 while the current choice of using
uint32_max can not represent them precisely.

(if needed in the future, we can also extend this to be a template
class where number of bits in the scaling factor is a template
parameter to support values > 1

template <int bits> class FixedPoint {
  static const int ScalingFactor = 1 << bits;

};
)

In the IR dump, I find it is easier to read

1. percentage,
2. M/N form when N is less than 10.

Current dump of 0x10ffff/0xffffffff form is hard to read -- can then
be simplified to make the denominator < 10?

Duncan, what is your opinion?

thanks,

David

[congh]

Update the patch by using 1<<31 instead of UINT32_MAX as the constant denominator.

[davidxl]

lib/Support/BranchProbability.cpp

98 ↗

(On Diff #34607)

Should D/2 be added to ProductLow above (and check overflow and carry bit)?

Besides, independent on what scale factor to use for BP, I think this change should not be included in this patch. It changes the rounding behavior of the scale() method (instead of truncating) which is irrelevant to the main purpose of the patch. This should be done as a follow up patch if it is desirable.

[congh]

lib/Support/BranchProbability.cpp

98 ↗

(On Diff #34607)

It is the division by D that may cause precision loss and I think this is the proper place to add D/2.

It is OK to separate this change to another patch (if it is necessary). This will cause many test failures and I will fix them as long as this patch is approved.

[davidxl]

lib/Support/BranchProbability.cpp

98 ↗

(On Diff #34607)

I would expect more test failures with this particular change as it differs from existing implementation. How many more tests fail without this change? (note that the rounding in the BP construction is still needed and kept)

[congh]

lib/Support/BranchProbability.cpp

98 ↗

(On Diff #34607)

There are three regression test failures if we remove D/2 here and two are caused by changes on test cases in this patch. That is two say, without D/2 we only have one more test failure. Other failures are branch probability unit tests.

[davidxl]

Without modifying any test cases, how many failures are there with D/2 vs
without?

David

llvm/trunk/include/llvm/Analysis/BlockFrequencyInfoImpl.h

BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
   return true;
 }
 
 template <class BT>
 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)
+  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";
   return OS;
 }
 
 } // end namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif

llvm/trunk/include/llvm/Support/BranchProbability.h

 
 #include "llvm/Support/DataTypes.h"
 #include <cassert>
 
 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;
 
   void dump() const;
 
   /// \brief Scale a large integer.
   ///
   /// Scales \c Num.  Guarantees full precision.  Returns the floor of the
   /// result.
   ///
   /// \return \c Num times \c this.
   uint64_t scale(uint64_t Num) const;
 
   /// \brief Scale a large integer by the inverse.
   ///
   /// Scales \c Num by the inverse of \c this.  Guarantees full precision.
   /// Returns the floor of the result.
   ///
   /// \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;
   }
-  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;
   }
+
+  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); }
 };
 
 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

llvm/trunk/lib/Support/BranchProbability.cpp

 // This file implements Branch Probability class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/BranchProbability.h"
 #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.
   if (!Num || D == N)
     return Num;
 
   // Split Num into upper and lower parts to multiply, then recombine.
   uint64_t ProductHigh = (Num >> 32) * N;
inline uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {
   uint64_t LowerQ = Rem / D;
   uint64_t Q = (UpperQ << 32) + LowerQ;
 
   // Check for overflow.
   return Q < LowerQ ? UINT64_MAX : Q;
 }
 
 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);
 }

llvm/trunk/test/Analysis/BlockFrequencyInfo/basic.ll

 entry:
   br label %for.cond1.preheader
 
 ; CHECK-NEXT: for.cond1.preheader: float = 4001.0,
 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
   tail call void @g(i32 %add7)
   %inc = add i32 %z.022, 1
   %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
   br i1 %cmp2, label %for.inc11, label %for.cond4.preheader, !prof !2
 
 ; CHECK-NEXT: for.inc11: float = 4001.0,
 for.inc11:
   %inc12 = add i32 %x.024, 1

llvm/trunk/test/Analysis/BlockFrequencyInfo/loops_with_profile_info.ll

for.body3:                                        ; preds = %for.cond1
   store i32 0, i32* %k, align 4
   br label %for.cond4
 
 for.cond4:                                        ; preds = %for.inc, %for.body3
   %2 = load i32, i32* %k, align 4
   %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
 
 for.inc:                                          ; preds = %for.body6
   %3 = load i32, i32* %k, align 4
   %inc = add nsw i32 %3, 1
   store i32 %inc, i32* %k, align 4
for.body15:                                       ; preds = %for.cond13
   store i32 0, i32* %j, align 4
   br label %for.cond16
 
 for.cond16:                                       ; preds = %for.inc19, %for.body15
   %8 = load i32, i32* %j, align 4
   %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
 
 for.inc19:                                        ; preds = %for.body18
   %9 = load i32, i32* %j, align 4
   %inc20 = add nsw i32 %9, 1
   store i32 %inc20, i32* %j, align 4
for.end24:                                        ; preds = %for.cond13
   store i32 0, i32* %i, align 4
   br label %for.cond26
 
 for.cond26:                                       ; preds = %for.inc29, %for.end24
   %12 = load i32, i32* %i, align 4
   %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
 
 for.inc29:                                        ; preds = %for.body28
   %13 = load i32, i32* %i, align 4
   %inc30 = add nsw i32 %13, 1
   store i32 %inc30, i32* %i, align 4

llvm/trunk/test/Analysis/BranchProbabilityInfo/basic.ll

 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
 
 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 ]
   %base = phi i32 [ 0, %entry ], [ %sum, %body ]
   %arrayidx = getelementptr inbounds i32, i32* %a, i32 %iv
   %0 = load i32, i32* %arrayidx
   %sum = add nsw i32 %0, %base
   %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
 }
 
 define i32 @test2(i32 %i, i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'test2'
 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 ]
   ret i32 %result
 }
 
 !0 = !{!"branch_weights", i32 64, i32 4}
 
 define i32 @test3(i32 %i, i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) {
 ; CHECK: Printing analysis {{.*}} for function 'test3'
 entry:
   switch i32 %i, label %case_a [ i32 1, label %case_b
                                  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 ],
                     [ %b, %case_b ],
                     [ %c, %case_c ],
                     [ %d, %case_d ],
                     [ %e, %case_e ]
   ret i32 %result
 }
 
 !1 = !{!"branch_weights", i32 4, i32 4, i32 64, i32 4, i32 4}
 
 define i32 @test4(i32 %x) nounwind uwtable readnone ssp {
 ; CHECK: Printing analysis {{.*}} for function 'test4'
 entry:
   %conv = sext i32 %x to i64
   switch i64 %conv, label %return [
     i64 0, label %sw.bb
     i64 1, label %sw.bb
     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
 
 sw.bb1:
   br label %return
 
 return:
   %retval.0 = phi i32 [ 5, %sw.bb1 ], [ 1, %sw.bb ], [ 0, %entry ]
   ret i32 %retval.0
 }
 
 !2 = !{!"branch_weights", i32 7, i32 6, i32 4, i32 4, i32 64}
 
 declare void @coldfunc() cold
 
 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 ]
   ret i32 %result
 }
 
 declare i32 @regular_function(i32 %i)
 
 define i32 @test_cold_call_sites(i32* %a) {
 ; Test that edges to blocks post-dominated by cold call sites
 ; are marked as not expected to be taken.
 ; TODO(dnovillo) The calls to regular_function should not be merged, but
 ; they are currently being merged. Convert this into a code generation test
 ; 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
   %val1 = load i32, i32* %gep1
   %cond1 = icmp ugt i32 %val1, 1
   br i1 %cond1, label %then, label %else
 
 then:
exit:
   ret i32 %ret
 }
 
 define i32 @zero1(i32 %i, i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'zero1'
 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
 
 else:
   br label %exit
 
 exit:
   %result = phi i32 [ %a, %then ], [ %b, %else ]
   ret i32 %result
 }
 
 define i32 @zero2(i32 %i, i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'zero2'
 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
 
 else:
   br label %exit
 
 exit:
   %result = phi i32 [ %a, %then ], [ %b, %else ]
   ret i32 %result
 }
 
 define i32 @zero3(i32 %i, i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'zero3'
 entry:
 ; AND'ing with a single bit bitmask essentially leads to a bool comparison,
 ; meaning we don't have probability information.
   %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
 ; usual probabilities.
   %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
 
 exit:
   %result = phi i32 [ %a, %then ], [ %b, %else ]
   ret i32 %result
 }
 

llvm/trunk/test/Analysis/BranchProbabilityInfo/loop.ll

 ; Test the static branch probability heuristics for no-return functions.
 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
 
 declare void @g1()
 declare void @g2()
 declare void @g3()
 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 ]
   call void @g2()
   %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()
   ret void
 }
 
 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 ]
   call void @g2()
   %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()
   ret void
 }
 
 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 ]
   call void @g1()
   %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 ]
   call void @g2()
   %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()
   ret void
 }
 
 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 ]
   call void @g1()
   %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 ]
   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 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
 }
 
 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
 }
 
 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 ]
   call void @g2()
   %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
 }
 
 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 ]
   call void @g2()
   %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()
   ret void
 }
 
 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()
   ret void
 }

llvm/trunk/test/Analysis/BranchProbabilityInfo/noreturn.ll

 ; Test the static branch probability heuristics for no-return functions.
 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
 
 declare void @abort() noreturn
 
 define i32 @test1(i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'test1'
 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
   unreachable
 
 exit:
   ret i32 %b
 }
 
 define i32 @test2(i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'test2'
 entry:
   switch i32 %a, label %exit [i32 1, label %case_a
                               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
 
 case_b:
   br label %case_c
 
 case_c:
   br label %case_d
 
 case_d:
   call void @abort() noreturn
   unreachable
 
 exit:
   ret i32 %b
 }
 
 define i32 @test3(i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'test3'
 ; Make sure we unify across multiple conditional branches.
 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
 
 idom2:
   br label %abort
 
 abort:
   call void @abort() noreturn
   unreachable
 
 exit:
   ret i32 %b
 }

llvm/trunk/test/Analysis/BranchProbabilityInfo/pr18705.ll

 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
 
 ; Since neither of while.body's out-edges is an exit or a back edge,
 ; 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:
   %tobool8 = icmp eq i32 %n, 0
   br i1 %tobool8, label %while.end, label %while.body.lr.ph
 
 while.body.lr.ph:
   %0 = sext i32 %n to i64

llvm/trunk/test/Analysis/BranchProbabilityInfo/pr22718.ll

 ; RUN: opt < %s -analyze -branch-prob | FileCheck %s
 
 ; In this test, the else clause is taken about 90% of the time. This was not
 ; 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
 @.str = private unnamed_addr constant [17 x i8] c"x = %lu\0Ay = %lu\0A\00", align 1
 
 ; Function Attrs: inlinehint nounwind uwtable
 define i32 @main() #0 {
 entry:

llvm/trunk/test/CodeGen/AArch64/aarch64-deferred-spilling.ll

if.then.72:                                       ; preds = %while.body.68.backedge, %sw.bb.65
   store i32 %sub76, i32* %sunkaddr518, align 4
   %currBlockNo = getelementptr inbounds %struct.DState, %struct.DState* %s, i64 0, i32 11
   %tmp17 = load i32, i32* %currBlockNo, align 4
   %inc117 = add nsw i32 %tmp17, 1
   store i32 %inc117, i32* %currBlockNo, align 4
   %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 ]
   %tmp19 = phi i32 [ %tmp14, %if.end.82.lr.ph ], [ %add97, %while.body.68.backedge ]
   %cmp85 = icmp eq i32 %lsr.iv480, -1
   br i1 %cmp85, label %save_state_and_return, label %if.end.88
 
 if.end.88:                                        ; preds = %if.end.82
save_state_and_return:                            ; preds = %sw.default, %if.end.140, %if.then.130, %if.end.82, %if.end.33, %if.then.29
   store i32 %tmp69, i32* %save_N15.pre-phi444, align 4
   store i32 %tmp70, i32* %save_curr16.pre-phi442, align 4
   store i32 %tmp71, i32* %save_zt17.pre-phi440, align 4
   store i32 %tmp72, i32* %save_zn18.pre-phi438, align 4
   store i32 %tmp73, i32* %save_zvec19.pre-phi436, align 4
   store i32 %tmp74, i32* %save_zj20.pre-phi434, align 4
   ret i32 %retVal.0
 }
+
+!0 = !{!"branch_weights", i32 10, i32 1}

llvm/trunk/test/Transforms/SampleProfile/branch.ll

 define i32 @main(i32 %argc, i8** nocapture readonly %argv) #0 {
 ; CHECK: Printing analysis 'Branch Probability Analysis' for function 'main':
 
 entry:
   tail call void @llvm.dbg.value(metadata i32 %argc, i64 0, metadata !13, metadata !DIExpression()), !dbg !27
   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
   %0 = load i8*, i8** %arrayidx, align 8, !dbg !30, !tbaa !31
   %call = tail call i32 @atoi(i8* %0) #4, !dbg !30
   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 ]
   %s.015 = phi double [ %sub, %for.body ], [ 0x40370ABE6A337A81, %if.end ]
   %add = fadd double %s.015, 3.049000e+00, !dbg !36
   %conv = sitofp i32 %u.016 to double, !dbg !36
   %add4 = fadd double %add, %conv, !dbg !36
   tail call void @llvm.dbg.value(metadata double %add4, i64 0, metadata !18, metadata !DIExpression()), !dbg !36
   %div = fdiv double 3.940000e+00, %s.015, !dbg !37
   %mul = fmul double %div, 3.200000e-01, !dbg !37
   %add5 = fadd double %add4, %mul, !dbg !37
   %sub = fsub double %add4, %add5, !dbg !37
   tail call void @llvm.dbg.value(metadata double %sub, i64 0, metadata !18, metadata !DIExpression()), !dbg !37
   %inc = add nsw i32 %u.016, 1, !dbg !38
   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 ]
   ret i32 %retval.0, !dbg !41
 }
 
 ; Function Attrs: nounwind readonly
 declare i32 @atoi(i8* nocapture) #1

llvm/trunk/test/Transforms/SampleProfile/calls.ll

entry:
   br label %while.cond, !dbg !13
 
 while.cond:                                       ; preds = %if.end, %entry
   %0 = load i32, i32* %i, align 4, !dbg !14
   %inc = add nsw i32 %0, 1, !dbg !14
   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
   %cmp1 = icmp ne i32 %1, 100, !dbg !16
   br i1 %cmp1, label %if.then, label %if.else, !dbg !16
 ; Without discriminator information, the profiler used to think that
 ; 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
   %2 = load i32, i32* %i, align 4, !dbg !18
   %3 = load i32, i32* %s, align 4, !dbg !18
   %call = call i32 @_Z3sumii(i32 %2, i32 %3), !dbg !18
   store i32 %call, i32* %s, align 4, !dbg !18
   br label %if.end, !dbg !18

llvm/trunk/test/Transforms/SampleProfile/discriminator.ll

entry:
   store i32 %i, i32* %i.addr, align 4
   store i32 0, i32* %x, align 4, !dbg !10
   br label %while.cond, !dbg !11
 
 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
   %dec = add nsw i32 %2, -1, !dbg !17
   store i32 %dec, i32* %x, align 4, !dbg !17
   br label %if.end, !dbg !17
 
 if.end:                                           ; preds = %if.then, %while.body

llvm/trunk/test/Transforms/SampleProfile/fnptr.ll

 ; The two profiles used in this test are the same but encoded in different
 ; formats. This checks that we produce the same profile annotations regardless
 ; of the profile format.
 ;
 ; 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.
 ;
 ; #include <stdlib.h>
 ; #include <math.h>
 ; #include <stdio.h>
 ;
 ; #define N 10000

llvm/trunk/test/Transforms/SampleProfile/propagate.ll

if.else:                                          ; preds = %entry
   store i64 0, i64* %i, align 8, !dbg !15
   br label %for.cond, !dbg !15
 
 for.cond:                                         ; preds = %for.inc16, %if.else
   %4 = load i64, i64* %i, align 8, !dbg !15
   %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
   %7 = load i64, i64* %N.addr, align 8, !dbg !18
   %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
   %dec = add nsw i32 %8, -1, !dbg !21
   store i32 %dec, i32* %x.addr, align 4, !dbg !21
   br label %if.end, !dbg !21
 
 if.end:                                           ; preds = %if.then3, %for.body
   %9 = load i64, i64* %i, align 8, !dbg !22
   %10 = load i64, i64* %N.addr, align 8, !dbg !22
   %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
   %inc = add nsw i32 %11, 1, !dbg !24
   store i32 %inc, i32* %y.addr, align 4, !dbg !24
   %12 = load i32, i32* %x.addr, align 4, !dbg !26
   %add = add nsw i32 %12, 3, !dbg !26
   store i32 %add, i32* %x.addr, align 4, !dbg !26
   br label %if.end15, !dbg !27
 
 if.else7:                                         ; preds = %if.end
   store i32 0, i32* %j, align 4, !dbg !28
   br label %for.cond8, !dbg !28
 
 for.cond8:                                        ; preds = %for.inc, %if.else7
   %13 = load i32, i32* %j, align 4, !dbg !28
   %conv9 = zext i32 %13 to i64, !dbg !28
   %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
   %16 = load i32, i32* %x.addr, align 4, !dbg !31
   %add12 = add i32 %16, %15, !dbg !31
   store i32 %add12, i32* %x.addr, align 4, !dbg !31
   %17 = load i32, i32* %y.addr, align 4, !dbg !33
   %sub13 = sub nsw i32 %17, 3, !dbg !33

llvm/trunk/unittests/Support/BlockFrequencyTest.cpp

 #include <climits>
 
 using namespace llvm;
 
 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);
 
   Freq = BlockFrequency(1);
   Freq *= Prob;
   EXPECT_EQ(Freq.getFrequency(), 0u);
 }
 
TEST(BlockFrequencyTest, ThreeToOne) {
   Freq *= Prob;
   EXPECT_EQ(Freq.getFrequency(), 1u);
 }
 
 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) {
   const uint64_t Big = 387246523487234346LL;
   const uint32_t P = 123456789;
   BlockFrequency Freq(Big);
   BranchProbability Prob(P, P);
   Freq *= Prob;
TEST(BlockFrequency, Divide) {
   BlockFrequency Freq(0x3333333333333333ULL);
   Freq /= BranchProbability(1, 2);
   EXPECT_EQ(Freq.getFrequency(), 0x6666666666666666ULL);
 }
 
 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) {
   BlockFrequency Freq(0x10080ULL);
   Freq >>= 2;
   EXPECT_EQ(Freq.getFrequency(), 0x4020ULL);
   Freq >>= 20;
   EXPECT_EQ(Freq.getFrequency(), 0x1ULL);
 }
 
 }

llvm/trunk/unittests/Support/BranchProbabilityTest.cpp

 void PrintTo(BranchProbability P, ::std::ostream *os) {
   *os << P.getNumerator() << "/" << P.getDenominator();
 }
 }
 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) {
   EXPECT_TRUE(BP(1, 7) < BP(2, 7));
   EXPECT_TRUE(BP(1, 7) < BP(1, 4));
   EXPECT_TRUE(BP(5, 7) < BP(3, 4));
   EXPECT_FALSE(BP(1, 7) < BP(1, 7));
   EXPECT_FALSE(BP(1, 7) < BP(2, 14));
TEST(BranchProbabilityTest, Operators) {
 
   EXPECT_TRUE(BP(1, 7) != BP(2, 7));
   EXPECT_TRUE(BP(1, 7) != BP(1, 4));
   EXPECT_TRUE(BP(5, 7) != BP(3, 4));
   EXPECT_FALSE(BP(1, 7) != BP(1, 7));
   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) {
   BP A(4, 5);
   BP B(4U << 29, 5U << 29);
   BP C(3, 4);
 
   EXPECT_TRUE(A == B);
TEST(BranchProbabilityTest, scale) {
   auto Two31 = UINT64_C(1) << 31;
 
   // Multiply by 0.5.
   EXPECT_EQ(Two63 - 1, BP(1, 2).scale(UINT64_MAX));
 
   // 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));
 }
 
 TEST(BranchProbabilityTest, scaleByInverse) {
   // Divide by 1.0.
   EXPECT_EQ(UINT64_MAX, BP(1, 1).scaleByInverse(UINT64_MAX));
   EXPECT_EQ(UINT64_MAX, BP(7, 7).scaleByInverse(UINT64_MAX));
   EXPECT_EQ(UINT32_MAX, BP(1, 1).scaleByInverse(UINT32_MAX));
   EXPECT_EQ(UINT32_MAX, BP(7, 7).scaleByInverse(UINT32_MAX));
   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;
 
   // Divide by 0.5.
   EXPECT_EQ(UINT64_MAX - 1, BP(1, 2).scaleByInverse(Two63 - 1));
   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));
 }
 
 TEST(BranchProbabilityTest, scaleBruteForce) {
   struct {
     uint64_t Num;
     uint32_t Prob[2];
     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) {
     EXPECT_EQ(T.Result, BP(T.Prob[0], T.Prob[1]).scale(T.Num));
   }
 }
 
 }