Index: include/llvm/Analysis/BlockFrequencyInfoImpl.h =================================================================== --- include/llvm/Analysis/BlockFrequencyInfoImpl.h +++ include/llvm/Analysis/BlockFrequencyInfoImpl.h @@ -1190,10 +1190,11 @@ 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"; Index: include/llvm/Support/BranchProbability.h =================================================================== --- include/llvm/Support/BranchProbability.h +++ include/llvm/Support/BranchProbability.h @@ -21,30 +21,43 @@ 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 UINT32_MAX for maximum +// precision). class BranchProbability { // Numerator uint32_t N; - // Denominator - uint32_t D; + // Denominator, which is a constant value. + static const uint32_t D = UINT32_MAX; + + // Construct a BranchProbability with only numerator assuming the denominator + // is UINT32_MAX. For internal use only. + explicit BranchProbability(uint32_t n) : N(n) {} public: - BranchProbability(uint32_t n, uint32_t d) : N(n), D(d) { - assert(d > 0 && "Denominator cannot be 0!"); - assert(n <= d && "Probability cannot be bigger than 1!"); - } + BranchProbability() : N(0) {} + BranchProbability(uint32_t n, uint32_t d); + + 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 UINT32_MAX + // as denominator. + static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); } + + // Normalize given probabilties so that the sum of them becomes approximate + // one. + template + 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; @@ -66,15 +79,31 @@ /// \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(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); } @@ -84,6 +113,16 @@ return Prob.print(OS); } +template +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 Index: lib/Support/BranchProbability.cpp =================================================================== --- lib/Support/BranchProbability.cpp +++ lib/Support/BranchProbability.cpp @@ -15,16 +15,54 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/Format.h" #include "llvm/Support/raw_ostream.h" +#include 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'; } +BranchProbability::BranchProbability(uint32_t n, uint32_t d) { + assert(d > 0 && "Denominator cannot be 0!"); + assert(n <= d && "Probability cannot be bigger than 1!"); + if (d == D) + N = n; + else { + uint64_t Prob64 = (n * static_cast(D) + d / 2) / d; + N = static_cast(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; +} + static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) { assert(D && "divide by 0"); @@ -57,7 +95,7 @@ return UINT64_MAX; Rem = ((Rem % D) << 32) | Lower32; - uint64_t LowerQ = Rem / D; + uint64_t LowerQ = (Rem + D / 2) / D; uint64_t Q = (UpperQ << 32) + LowerQ; // Check for overflow. Index: lib/Target/ARM/ARMBaseInstrInfo.cpp =================================================================== --- lib/Target/ARM/ARMBaseInstrInfo.cpp +++ lib/Target/ARM/ARMBaseInstrInfo.cpp @@ -1670,11 +1670,14 @@ } // Attempt to estimate the relative costs of predication versus branching. - unsigned UnpredCost = Probability.scale(NumCycles); - UnpredCost += 1; // The branch itself - UnpredCost += Subtarget.getMispredictionPenalty() / 10; - - return (NumCycles + ExtraPredCycles) <= UnpredCost; + // Here we scale up each component of UnpredCost to avoid precision issue when + // scaling NumCycles by Probability. + const unsigned ScalingUpFactor = 1024; + unsigned UnpredCost = Probability.scale(NumCycles * ScalingUpFactor); + UnpredCost += 1 * ScalingUpFactor; // The branch itself + UnpredCost += Subtarget.getMispredictionPenalty() * ScalingUpFactor / 10; + + return (NumCycles + ExtraPredCycles) * ScalingUpFactor <= UnpredCost; } bool ARMBaseInstrInfo:: @@ -1687,13 +1690,17 @@ return false; // Attempt to estimate the relative costs of predication versus branching. - unsigned TUnpredCost = Probability.scale(TCycles); - unsigned FUnpredCost = Probability.getCompl().scale(FCycles); + // Here we scale up each component of UnpredCost to avoid precision issue when + // scaling TCycles/FCycles by Probability. + const unsigned ScalingUpFactor = 1024; + unsigned TUnpredCost = Probability.scale(TCycles * ScalingUpFactor); + unsigned FUnpredCost = + Probability.getCompl().scale(FCycles * ScalingUpFactor); unsigned UnpredCost = TUnpredCost + FUnpredCost; - UnpredCost += 1; // The branch itself - UnpredCost += Subtarget.getMispredictionPenalty() / 10; + UnpredCost += 1 * ScalingUpFactor; // The branch itself + UnpredCost += Subtarget.getMispredictionPenalty() * ScalingUpFactor / 10; - return (TCycles + FCycles + TExtra + FExtra) <= UnpredCost; + return (TCycles + FCycles + TExtra + FExtra) * ScalingUpFactor <= UnpredCost; } bool Index: test/Analysis/BlockFrequencyInfo/basic.ll =================================================================== --- test/Analysis/BlockFrequencyInfo/basic.ll +++ test/Analysis/BlockFrequencyInfo/basic.ll @@ -104,13 +104,13 @@ %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 = 16008014.6, 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 = 64048093511.9, for.body6: %z.022 = phi i32 [ 0, %for.cond4.preheader ], [ %inc, %for.body6 ] %add7 = add i32 %add, %z.022 @@ -119,7 +119,7 @@ %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 = 16008014.6, for.inc8: %inc9 = add i32 %y.023, 1 %cmp2 = icmp ugt i32 %inc9, %a Index: test/Analysis/BlockFrequencyInfo/loops_with_profile_info.ll =================================================================== --- test/Analysis/BlockFrequencyInfo/loops_with_profile_info.ll +++ test/Analysis/BlockFrequencyInfo/loops_with_profile_info.ll @@ -143,7 +143,7 @@ %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 = 500001.0, int = 4000008 for.body18: ; preds = %for.cond16 call void @bar() br label %for.inc19 @@ -175,7 +175,7 @@ %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 Index: test/Analysis/BranchProbabilityInfo/basic.ll =================================================================== --- test/Analysis/BranchProbabilityInfo/basic.ll +++ test/Analysis/BranchProbabilityInfo/basic.ll @@ -4,7 +4,7 @@ ; 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] body: %iv = phi i32 [ 0, %entry ], [ %next, %body ] @@ -15,8 +15,8 @@ %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 0x08000000 / 0xffffffff = 3.13% +; CHECK: edge body -> body probability is 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] exit: ret i32 %sum @@ -27,16 +27,16 @@ 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 0xf0f0f0f0 / 0xffffffff = 94.12% [HOT edge] +; CHECK: edge entry -> else probability is 0x0f0f0f0f / 0xffffffff = 5.88% then: br label %exit -; CHECK: edge then -> exit probability is 16 / 16 = 100% +; CHECK: edge then -> exit probability is 0xffffffff / 0xffffffff = 100.00% [HOT edge] else: br label %exit -; CHECK: edge else -> exit probability is 16 / 16 = 100% +; CHECK: edge else -> exit probability is 0xffffffff / 0xffffffff = 100.00% [HOT edge] exit: %result = phi i32 [ %a, %then ], [ %b, %else ] @@ -52,31 +52,31 @@ 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 0x0ccccccd / 0xffffffff = 5.00% +; CHECK: edge entry -> case_b probability is 0x0ccccccd / 0xffffffff = 5.00% +; CHECK: edge entry -> case_c probability is 0xcccccccc / 0xffffffff = 80.00% +; CHECK: edge entry -> case_d probability is 0x0ccccccd / 0xffffffff = 5.00% +; CHECK: edge entry -> case_e probability is 0x0ccccccd / 0xffffffff = 5.00% case_a: br label %exit -; CHECK: edge case_a -> exit probability is 16 / 16 = 100% +; CHECK: edge case_a -> exit probability is 0xffffffff / 0xffffffff = 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 0xffffffff / 0xffffffff = 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 0xffffffff / 0xffffffff = 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 0xffffffff / 0xffffffff = 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] exit: %result = phi i32 [ %a, %case_a ], @@ -99,9 +99,9 @@ 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 0x15151515 / 0xffffffff = 8.24% +; CHECK: edge entry -> sw.bb probability is 0x2a2a2a2a / 0xffffffff = 16.47% +; CHECK: edge entry -> sw.bb1 probability is 0xc0c0c0c0 / 0xffffffff = 75.29% sw.bb: br label %return @@ -122,17 +122,17 @@ ; 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 0x0f0f0f0f / 0xffffffff = 5.88% +; CHECK: edge entry -> else probability is 0xf0f0f0f0 / 0xffffffff = 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] else: br label %exit -; CHECK: edge else -> exit probability is 16 / 16 = 100% +; CHECK: edge else -> exit probability is 0xffffffff / 0xffffffff = 100.00% [HOT edge] exit: %result = phi i32 [ %a, %then ], [ %b, %else ] @@ -149,8 +149,8 @@ ; 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 0x0f0f0f0f / 0xffffffff = 5.88% +; CHECK: edge entry -> else probability is 0xf0f0f0f0 / 0xffffffff = 94.12% [HOT edge] entry: %gep1 = getelementptr i32, i32* %a, i32 1 @@ -179,8 +179,8 @@ 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 0x60000000 / 0xffffffff = 37.50% +; CHECK: edge entry -> else probability is 0x9fffffff / 0xffffffff = 62.50% then: br label %exit @@ -198,8 +198,8 @@ 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 0x9fffffff / 0xffffffff = 62.50% +; CHECK: edge entry -> else probability is 0x60000000 / 0xffffffff = 37.50% then: br label %exit @@ -220,8 +220,8 @@ %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 0x80000000 / 0xffffffff = 50.00% +; CHECK: edge entry -> else probability is 0x80000000 / 0xffffffff = 50.00% then: ; AND'ing with other bitmask might be something else, so we still assume the @@ -229,8 +229,8 @@ %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 0x60000000 / 0xffffffff = 37.50% +; CHECK: edge then -> exit probability is 0x9fffffff / 0xffffffff = 62.50% else: br label %exit Index: test/Analysis/BranchProbabilityInfo/loop.ll =================================================================== --- test/Analysis/BranchProbabilityInfo/loop.ll +++ test/Analysis/BranchProbabilityInfo/loop.ll @@ -9,13 +9,13 @@ 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 0xffffffff / 0xffffffff = 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] do.body1: %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.body1 ] @@ -23,16 +23,16 @@ %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 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] +; CHECK: edge do.body1 -> do.end probability is 0x08000000 / 0xffffffff = 3.13% 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 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] +; CHECK: edge do.end -> do.end5 probability is 0x08000000 / 0xffffffff = 3.13% do.end5: call void @g4() @@ -43,20 +43,20 @@ 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 0x9fffffff / 0xffffffff = 62.50% +; CHECK: edge entry -> for.end6 probability is 0x60000000 / 0xffffffff = 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 0xffffffff / 0xffffffff = 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 0x9fffffff / 0xffffffff = 62.50% +; CHECK: edge for.body -> for.end probability is 0x60000000 / 0xffffffff = 37.50% for.body3: %j.08 = phi i32 [ %inc, %for.body3 ], [ 0, %for.body ] @@ -64,16 +64,16 @@ %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 0x08000000 / 0xffffffff = 3.13% +; CHECK: edge for.body3 -> for.body3 probability is 0xf7ffffff / 0xffffffff = 96.87% [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 0x08000000 / 0xffffffff = 3.13% +; CHECK: edge for.end -> for.body probability is 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] for.end6: call void @g4() @@ -83,7 +83,7 @@ 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] do.body: %i.0 = phi i32 [ 0, %entry ], [ %inc4, %if.end ] @@ -91,8 +91,8 @@ %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 0x80000000 / 0xffffffff = 50.00% +; CHECK: edge do.body -> if.end probability is 0x80000000 / 0xffffffff = 50.00% do.body1: %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ] @@ -100,16 +100,16 @@ %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 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] +; CHECK: edge do.body1 -> if.end probability is 0x08000000 / 0xffffffff = 3.13% 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 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] +; CHECK: edge if.end -> do.end6 probability is 0x08000000 / 0xffffffff = 3.13% do.end6: call void @g4() @@ -119,7 +119,7 @@ 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] do.body: %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ] @@ -127,8 +127,8 @@ %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 0x08000000 / 0xffffffff = 3.13% +; CHECK: edge do.body -> do.body1 probability is 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] do.body1: %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ] @@ -136,21 +136,21 @@ %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 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] +; CHECK: edge do.body1 -> do.end probability is 0x08000000 / 0xffffffff = 3.13% 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 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] +; CHECK: edge do.end -> do.end6 probability is 0x08000000 / 0xffffffff = 3.13% 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] return: ret void @@ -159,42 +159,42 @@ 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 0xffffffff / 0xffffffff = 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 0xffffffff / 0xffffffff = 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 0x08000000 / 0xffffffff = 3.13% +; CHECK: edge do.body1 -> if.end probability is 0xf7ffffff / 0xffffffff = 96.87% [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 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] +; CHECK: edge if.end -> do.end probability is 0x08000000 / 0xffffffff = 3.13% 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 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] +; CHECK: edge do.end -> do.end6 probability is 0x08000000 / 0xffffffff = 3.13% 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] return: ret void @@ -203,13 +203,13 @@ 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 0xffffffff / 0xffffffff = 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] do.body1: %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.cond ] @@ -217,28 +217,28 @@ %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 0x08000000 / 0xffffffff = 3.13% +; CHECK: edge do.body1 -> do.cond probability is 0xf7ffffff / 0xffffffff = 96.87% [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 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] +; CHECK: edge do.cond -> do.end probability is 0x08000000 / 0xffffffff = 3.13% 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 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] +; CHECK: edge do.end -> do.end6 probability is 0x08000000 / 0xffffffff = 3.13% 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] return: ret void @@ -248,27 +248,27 @@ 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 0x9fffffff / 0xffffffff = 62.50% +; CHECK: edge entry -> for.end7 probability is 0x60000000 / 0xffffffff = 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 0xffffffff / 0xffffffff = 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 0x80000000 / 0xffffffff = 50.00% +; CHECK: edge for.body -> if.end probability is 0x80000000 / 0xffffffff = 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 0x9fffffff / 0xffffffff = 62.50% +; CHECK: edge if.end -> for.end probability is 0x60000000 / 0xffffffff = 37.50% for.body4: %j.09 = phi i32 [ %inc, %for.body4 ], [ 0, %if.end ] @@ -276,20 +276,20 @@ %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 0x08000000 / 0xffffffff = 3.13% +; CHECK: edge for.body4 -> for.body4 probability is 0xf7ffffff / 0xffffffff = 96.87% [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 0xffffffff / 0xffffffff = 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 0x08000000 / 0xffffffff = 3.13% +; CHECK: edge for.inc5 -> for.body probability is 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] for.end7: call void @g4() @@ -300,64 +300,64 @@ 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 0x9fffffff / 0xffffffff = 62.50% +; CHECK: edge entry -> for.end15 probability is 0x60000000 / 0xffffffff = 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 0xffffffff / 0xffffffff = 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 0x9fffffff / 0xffffffff = 62.50% +; CHECK: edge for.body -> for.end probability is 0x60000000 / 0xffffffff = 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 0x80000000 / 0xffffffff = 50.00% +; CHECK: edge for.body3 -> if.end probability is 0x80000000 / 0xffffffff = 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 0x80000000 / 0xffffffff = 50.00% +; CHECK: edge if.end -> if.end8 probability is 0x80000000 / 0xffffffff = 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 0x80000000 / 0xffffffff = 50.00% +; CHECK: edge if.end8 -> if.end12 probability is 0x80000000 / 0xffffffff = 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 0xffffffff / 0xffffffff = 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 0x08000000 / 0xffffffff = 3.13% +; CHECK: edge for.inc -> for.body3 probability is 0xf7ffffff / 0xffffffff = 96.87% [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 0x08000000 / 0xffffffff = 3.13% +; CHECK: edge for.end -> for.body probability is 0xf7ffffff / 0xffffffff = 96.87% [HOT edge] for.end15: call void @g4() Index: test/Analysis/BranchProbabilityInfo/noreturn.ll =================================================================== --- test/Analysis/BranchProbabilityInfo/noreturn.ll +++ test/Analysis/BranchProbabilityInfo/noreturn.ll @@ -8,8 +8,8 @@ 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 0xffffefff / 0xffffffff = 100.00% [HOT edge] +; CHECK: edge entry -> abort probability is 0x00001000 / 0xffffffff = 0.00% abort: call void @abort() noreturn @@ -26,11 +26,11 @@ 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 0xffffbfff / 0xffffffff = 100.00% [HOT edge] +; CHECK: edge entry -> case_a probability is 0x00001000 / 0xffffffff = 0.00% +; CHECK: edge entry -> case_b probability is 0x00001000 / 0xffffffff = 0.00% +; CHECK: edge entry -> case_c probability is 0x00001000 / 0xffffffff = 0.00% +; CHECK: edge entry -> case_d probability is 0x00001000 / 0xffffffff = 0.00% case_a: br label %case_b @@ -55,14 +55,14 @@ 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 0xffffefff / 0xffffffff = 100.00% [HOT edge] +; CHECK: edge entry -> dom probability is 0x00001000 / 0xffffffff = 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 0x80000000 / 0xffffffff = 50.00% +; CHECK: edge dom -> idom2 probability is 0x80000000 / 0xffffffff = 50.00% idom1: br label %abort Index: test/Analysis/BranchProbabilityInfo/pr18705.ll =================================================================== --- test/Analysis/BranchProbabilityInfo/pr18705.ll +++ 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 0x9fffffff / 0xffffffff = 62.50% +; CHECK: edge while.body -> if.else probability is 0x60000000 / 0xffffffff = 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: Index: test/Analysis/BranchProbabilityInfo/pr22718.ll =================================================================== --- test/Analysis/BranchProbabilityInfo/pr22718.ll +++ 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 0x1999748b / 0xffffffff = 10.00% +; CHECK: edge for.body -> if.else probability is 0xe6668b74 / 0xffffffff = 90.00% [HOT edge] @y = common global i64 0, align 8 @x = common global i64 0, align 8 Index: test/CodeGen/AArch64/fast-isel-branch-cond-split.ll =================================================================== --- test/CodeGen/AArch64/fast-isel-branch-cond-split.ll +++ test/CodeGen/AArch64/fast-isel-branch-cond-split.ll @@ -19,8 +19,8 @@ } ; CHECK-LABEL: test_and -; CHECK: cbz w0, {{LBB[0-9]+_2}} -; CHECK: cbnz w1, {{LBB[0-9]+_3}} +; CHECK: cbnz w0, {{LBB[0-9]+_2}} +; CHECK: cbz w1, {{LBB[0-9]+_1}} define i64 @test_and(i32 %a, i32 %b) { bb1: %0 = icmp ne i32 %a, 0 Index: test/CodeGen/ARM/2013-10-11-select-stalls.ll =================================================================== --- test/CodeGen/ARM/2013-10-11-select-stalls.ll +++ test/CodeGen/ARM/2013-10-11-select-stalls.ll @@ -1,7 +1,10 @@ ; REQUIRES: asserts -; RUN: llc < %s -mtriple=thumbv7-apple-ios -stats 2>&1 | not grep "Number of pipeline stalls" +; RUN: llc < %s -mtriple=thumbv7-apple-ios -stats 2>&1 | grep "Number of pipeline stalls" ; Evaluate the two vld1.8 instructions in separate MBB's, ; instead of stalling on one and conditionally overwriting its result. +; +; Update: After if-conversion the two vld1.8 instructions are in the same MBB +; again. define <16 x i8> @multiselect(i32 %avail, i8* %foo, i8* %bar) { entry: Index: test/CodeGen/ARM/ifcvt4.ll =================================================================== --- test/CodeGen/ARM/ifcvt4.ll +++ test/CodeGen/ARM/ifcvt4.ll @@ -1,10 +1,8 @@ ; RUN: llc -mtriple=arm-eabi %s -o - | FileCheck %s -; Do not if-convert when branches go to the different loops. ; CHECK-LABEL: t: -; CHECK-NOT: subgt -; CHECK-NOT: suble -; Don't use +; CHECK: subgt +; CHECK: suble define i32 @t(i32 %a, i32 %b) { entry: %tmp1434 = icmp eq i32 %a, %b ; [#uses=1] Index: test/CodeGen/ARM/sjlj-prepare-critical-edge.ll =================================================================== --- test/CodeGen/ARM/sjlj-prepare-critical-edge.ll +++ test/CodeGen/ARM/sjlj-prepare-critical-edge.ll @@ -77,8 +77,8 @@ ; CHECK: blx __Znwm ; CHECK: {{.*}}@ %entry.do.body.i.i.i_crit_edge ; CHECK: str r0, [sp, [[OFFSET:#[0-9]+]]] -; CHECK: ldr [[R0:r[0-9]+]], [sp, [[OFFSET]]] ; CHECK: {{.*}}@ %do.body.i.i.i +; CHECK: ldr [[R0:r[0-9]+]], [sp, [[OFFSET]]] ; CHECK: cbz [[R0]] %"class.std::__1::basic_string" = type { %"class.std::__1::__compressed_pair" } Index: test/CodeGen/ARM/tail-merge-branch-weight.ll =================================================================== --- test/CodeGen/ARM/tail-merge-branch-weight.ll +++ test/CodeGen/ARM/tail-merge-branch-weight.ll @@ -9,7 +9,7 @@ ; = 0.2 * 0.4 + 0.8 * 0.7 = 0.64 ; CHECK: # Machine code for function test0: -; CHECK: Successors according to CFG: BB#{{[0-9]+}}(13) BB#{{[0-9]+}}(24) +; CHECK: Successors according to CFG: BB#{{[0-9]+}}(14) BB#{{[0-9]+}}(25) ; CHECK: BB#{{[0-9]+}}: ; CHECK: BB#{{[0-9]+}}: ; CHECK: # End machine code for function test0. Index: test/CodeGen/ARM/test-sharedidx.ll =================================================================== --- test/CodeGen/ARM/test-sharedidx.ll +++ test/CodeGen/ARM/test-sharedidx.ll @@ -59,9 +59,6 @@ br i1 %cmp.1, label %for.body.2, label %for.end for.body.2: ; preds = %for.body.1 -; CHECK: %for.body.2 -; CHECK: ldrb {{r[0-9]+|lr}}, [{{r[0-9]+|lr}}, {{r[0-9]+|lr}}]! -; CHECK: ldrb {{r[0-9]+|lr}}, [{{r[0-9]+|lr}}, {{r[0-9]+|lr}}]! %arrayidx.2 = getelementptr inbounds i8, i8* %a, i32 %add5.1 %4 = load i8, i8* %arrayidx.2, align 1 %conv6.2 = zext i8 %4 to i32 Index: test/CodeGen/Thumb2/thumb2-ifcvt1.ll =================================================================== --- test/CodeGen/Thumb2/thumb2-ifcvt1.ll +++ test/CodeGen/Thumb2/thumb2-ifcvt1.ll @@ -24,11 +24,10 @@ define i32 @t2(i32 %a, i32 %b) nounwind { entry: -; Do not if-convert when branches go to the different loops. ; CHECK-LABEL: t2: -; CHECK-NOT: ite gt -; CHECK-NOT: subgt -; CHECK-NOT: suble +; CHECK: ite gt +; CHECK: subgt +; CHECK: suble %tmp1434 = icmp eq i32 %a, %b ; [#uses=1] br i1 %tmp1434, label %bb17, label %bb.outer Index: test/Transforms/SampleProfile/branch.ll =================================================================== --- test/Transforms/SampleProfile/branch.ll +++ test/Transforms/SampleProfile/branch.ll @@ -36,8 +36,8 @@ 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 / 0xffffffff = 0.00% +; CHECK: edge entry -> if.end probability is 0xffffffff / 0xffffffff = 100.00% [HOT edge] if.end: ; preds = %entry %arrayidx = getelementptr inbounds i8*, i8** %argv, i64 1, !dbg !30 @@ -46,8 +46,8 @@ 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 / 0xffffffff = 0.00% +; CHECK: edge if.end -> if.end6 probability is 0xffffffff / 0xffffffff = 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 @@ 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 / 0xffffffff = 0.00% +; CHECK: edge for.body -> for.body probability is 0xffffffff / 0xffffffff = 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] return: ; preds = %entry, %if.end6 %retval.0 = phi i32 [ 0, %if.end6 ], [ 1, %entry ] Index: test/Transforms/SampleProfile/calls.ll =================================================================== --- test/Transforms/SampleProfile/calls.ll +++ test/Transforms/SampleProfile/calls.ll @@ -52,8 +52,8 @@ 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] +; CHECK: edge while.cond -> while.end probability is 0x00000000 / 0xffffffff = 0.00% while.body: ; preds = %while.cond %1 = load i32, i32* %i, align 4, !dbg !16 @@ -63,8 +63,8 @@ ; 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 0xffffffff / 0xffffffff = 100.00% [HOT edge] +; CHECK: edge while.body -> if.else probability is 0x00000000 / 0xffffffff = 0.00% if.then: ; preds = %while.body Index: test/Transforms/SampleProfile/discriminator.ll =================================================================== --- test/Transforms/SampleProfile/discriminator.ll +++ test/Transforms/SampleProfile/discriminator.ll @@ -34,15 +34,15 @@ %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 0xfd7720f2 / 0xffffffff = 99.01% [HOT edge] +; CHECK: edge while.cond -> while.end probability is 0x0288df0d / 0xffffffff = 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 0x0ccccccd / 0xffffffff = 5.00% +; CHECK: edge while.body -> if.end probability is 0xf3333332 / 0xffffffff = 95.00% [HOT edge] if.then: ; preds = %while.body %2 = load i32, i32* %x, align 4, !dbg !17 Index: test/Transforms/SampleProfile/fnptr.ll =================================================================== --- test/Transforms/SampleProfile/fnptr.ll +++ 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 0x349e72b2 / 0xffffffff = 20.55% +; CHECK: edge for.body3 -> if.else probability is 0xcb618d4d / 0xffffffff = 79.45% +; CHECK: edge for.inc -> for.inc12 probability is 0x67a94982 / 0xffffffff = 40.49% +; CHECK: edge for.inc -> for.body3 probability is 0x9856b67d / 0xffffffff = 59.51% +; CHECK: edge for.inc12 -> for.end14 probability is 0x7e0da09b / 0xffffffff = 49.24% +; CHECK: edge for.inc12 -> for.cond1.preheader probability is 0x81f25f64 / 0xffffffff = 50.76% ; Original C++ test case. ; Index: test/Transforms/SampleProfile/propagate.ll =================================================================== --- test/Transforms/SampleProfile/propagate.ll +++ test/Transforms/SampleProfile/propagate.ll @@ -73,8 +73,8 @@ %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 0xffffffff / 0xffffffff = 100.00% [HOT edge] +; CHECK: edge for.cond -> for.end18 probability is 0x00000000 / 0xffffffff = 0.00% for.body: ; preds = %for.cond %6 = load i64, i64* %i, align 8, !dbg !18 @@ -82,8 +82,8 @@ %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 0x33333333 / 0xffffffff = 20.00% +; CHECK: edge for.body -> if.end probability is 0xcccccccc / 0xffffffff = 80.00% if.then3: ; preds = %for.body %8 = load i32, i32* %x.addr, align 4, !dbg !21 @@ -97,8 +97,8 @@ %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 0x001f003e / 0xffffffff = 0.05% +; CHECK: edge if.end -> if.else7 probability is 0xffe0ffc1 / 0xffffffff = 99.95% [HOT edge] if.then6: ; preds = %if.end %11 = load i32, i32* %y.addr, align 4, !dbg !24 @@ -119,8 +119,8 @@ %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 0xffffffff / 0xffffffff = 100.00% [HOT edge] +; CHECK: edge for.cond8 -> for.end probability is 0x00000000 / 0xffffffff = 0.00% for.body11: ; preds = %for.cond8 %15 = load i32, i32* %j, align 4, !dbg !31 Index: unittests/Support/BlockFrequencyTest.cpp =================================================================== --- unittests/Support/BlockFrequencyTest.cpp +++ unittests/Support/BlockFrequencyTest.cpp @@ -19,7 +19,7 @@ TEST(BlockFrequencyTest, OneToZero) { BlockFrequency Freq(1); - BranchProbability Prob(UINT32_MAX - 1, UINT32_MAX); + BranchProbability Prob(UINT32_MAX / 2, UINT32_MAX); Freq *= Prob; EXPECT_EQ(Freq.getFrequency(), 0u); @@ -30,12 +30,18 @@ TEST(BlockFrequencyTest, OneToOne) { BlockFrequency Freq(1); - BranchProbability Prob(UINT32_MAX, UINT32_MAX); - Freq *= Prob; + BranchProbability Prob1(UINT32_MAX - 1, UINT32_MAX); + BranchProbability Prob2(UINT32_MAX, UINT32_MAX); + + EXPECT_EQ((Freq * Prob1).getFrequency(), 1u); + EXPECT_EQ((Freq * Prob2).getFrequency(), 1u); + + Freq = BlockFrequency(1); + Freq *= Prob1; EXPECT_EQ(Freq.getFrequency(), 1u); Freq = BlockFrequency(1); - Freq *= Prob; + Freq *= Prob2; EXPECT_EQ(Freq.getFrequency(), 1u); } @@ -91,7 +97,7 @@ TEST(BlockFrequency, Divide) { BlockFrequency Freq(0x3333333333333333ULL); Freq /= BranchProbability(1, 2); - EXPECT_EQ(Freq.getFrequency(), 0x6666666666666666ULL); + EXPECT_EQ(Freq.getFrequency(), 0x6666666600000000ULL); } TEST(BlockFrequencyTest, Saturate) { @@ -102,13 +108,13 @@ 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(33496313625853537ULL, Freq.getFrequency()); } TEST(BlockFrequencyTest, SaturatingRightShift) { Index: unittests/Support/BranchProbabilityTest.cpp =================================================================== --- unittests/Support/BranchProbabilityTest.cpp +++ unittests/Support/BranchProbabilityTest.cpp @@ -22,12 +22,12 @@ typedef BranchProbability BP; TEST(BranchProbabilityTest, Accessors) { - EXPECT_EQ(1u, BP(1, 7).getNumerator()); - EXPECT_EQ(7u, BP(1, 7).getDenominator()); + EXPECT_EQ(613566756u, BP(1, 7).getNumerator()); + EXPECT_EQ(UINT32_MAX, 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(UINT32_MAX, BP::getZero().getDenominator()); + EXPECT_EQ(UINT32_MAX, BP::getOne().getNumerator()); + EXPECT_EQ(UINT32_MAX, BP::getOne().getDenominator()); } TEST(BranchProbabilityTest, Operators) { @@ -134,15 +134,15 @@ auto Two31 = UINT64_C(1) << 31; // Multiply by 0.5. - EXPECT_EQ(Two63 - 1, BP(1, 2).scale(UINT64_MAX)); + EXPECT_EQ(0x8000000080000000ULL, 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(Two31 + 1, BP(Two31, UINT32_MAX).scale(Two31 * 2)); EXPECT_EQ(Two63 + Two31, BP(Two31, UINT32_MAX).scale(UINT64_MAX)); // High precision. - EXPECT_EQ(UINT64_C(9223372047592194055), + EXPECT_EQ(UINT64_C(9223372047592194050ULL), BP(Two31 + 1, UINT32_MAX - 2).scale(UINT64_MAX)); } @@ -165,11 +165,11 @@ 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)); + EXPECT_EQ(0xfffffffefffffffeULL, BP(1, 2).scaleByInverse(Two63 - 1)); + EXPECT_EQ(0xffffffff00000000ULL, 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)); @@ -177,10 +177,10 @@ // 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(18446744065119617045ULL), BP(Two31 + 2, UINT32_MAX - 2) - .scaleByInverse(UINT64_C(9223372047592194055))); - EXPECT_EQ(UINT64_C(18446744065119617026), + .scaleByInverse(UINT64_C(9223372047592194055ULL))); + EXPECT_EQ(UINT64_C(18446744065119617027ULL), BP(Two31 + 1, UINT32_MAX).scaleByInverse(Two63 + Two31)); } @@ -192,86 +192,86 @@ } Tests[] = { // Data for scaling that results in <= 64 bit division. { 0x1423e2a50ULL, { 0x64819521, 0x7765dd13 }, 0x10f418889ULL }, - { 0x35ef14ceULL, { 0x28ade3c7, 0x304532ae }, 0x2d73c33aULL }, - { 0xd03dbfbe24ULL, { 0x790079, 0xe419f3 }, 0x6e776fc1fdULL }, + { 0x35ef14ceULL, { 0x28ade3c7, 0x304532ae }, 0x2d73c33bULL }, + { 0xd03dbfbe24ULL, { 0x790079, 0xe419f3 }, 0x6e776fc263ULL }, { 0x21d67410bULL, { 0x302a9dc2, 0x3ddb4442 }, 0x1a5948fd6ULL }, - { 0x8664aeadULL, { 0x3d523513, 0x403523b1 }, 0x805a04cfULL }, - { 0x201db0cf4ULL, { 0x35112a7b, 0x79fc0c74 }, 0xdf8b07f6ULL }, - { 0x13f1e4430aULL, { 0x21c92bf, 0x21e63aae }, 0x13e0cba15ULL }, + { 0x8664aeadULL, { 0x3d523513, 0x403523b1 }, 0x805a04d0ULL }, + { 0x201db0cf4ULL, { 0x35112a7b, 0x79fc0c74 }, 0xdf8b07f7ULL }, + { 0x13f1e4430aULL, { 0x21c92bf, 0x21e63aae }, 0x13e0cba14ULL }, { 0x16c83229ULL, { 0x3793f66f, 0x53180dea }, 0xf3ce7b6ULL }, - { 0xc62415be8ULL, { 0x9cc4a63, 0x4327ae9b }, 0x1ce8b71caULL }, - { 0x6fac5e434ULL, { 0xe5f9170, 0x1115e10b }, 0x5df23dd4cULL }, - { 0x1929375f2ULL, { 0x3a851375, 0x76c08456 }, 0xc662b082ULL }, - { 0x243c89db6ULL, { 0x354ebfc0, 0x450ef197 }, 0x1bf8c1661ULL }, + { 0xc62415be8ULL, { 0x9cc4a63, 0x4327ae9b }, 0x1ce8b71d0ULL }, + { 0x6fac5e434ULL, { 0xe5f9170, 0x1115e10b }, 0x5df23dd4bULL }, + { 0x1929375f2ULL, { 0x3a851375, 0x76c08456 }, 0xc662b083ULL }, + { 0x243c89db6ULL, { 0x354ebfc0, 0x450ef197 }, 0x1bf8c1660ULL }, { 0x310e9b31aULL, { 0x1b1b8acf, 0x2d3629f0 }, 0x1d69c93f9ULL }, - { 0xa1fae921dULL, { 0xa7a098c, 0x10469f44 }, 0x684413d6cULL }, - { 0xc1582d957ULL, { 0x498e061, 0x59856bc }, 0x9edc5f4e7ULL }, + { 0xa1fae921dULL, { 0xa7a098c, 0x10469f44 }, 0x684413d6bULL }, + { 0xc1582d957ULL, { 0x498e061, 0x59856bc }, 0x9edc5f4ebULL }, { 0x57cfee75ULL, { 0x1d061dc3, 0x7c8bfc17 }, 0x1476a220ULL }, - { 0x139220080ULL, { 0x294a6c71, 0x2a2b07c9 }, 0x1329e1c76ULL }, - { 0x1665d353cULL, { 0x7080db5, 0xde0d75c }, 0xb590d9fbULL }, - { 0xe8f14541ULL, { 0x5188e8b2, 0x736527ef }, 0xa4971be5ULL }, + { 0x139220080ULL, { 0x294a6c71, 0x2a2b07c9 }, 0x1329e1c75ULL }, + { 0x1665d353cULL, { 0x7080db5, 0xde0d75c }, 0xb590d9fcULL }, + { 0xe8f14541ULL, { 0x5188e8b2, 0x736527ef }, 0xa4971be6ULL }, { 0x2f4775f29ULL, { 0x254ef0fe, 0x435fcf50 }, 0x1a2e449c1ULL }, - { 0x27b85d8d7ULL, { 0x304c8220, 0x5de678f2 }, 0x146e3bef9ULL }, + { 0x27b85d8d7ULL, { 0x304c8220, 0x5de678f2 }, 0x146e3befaULL }, { 0x1d362e36bULL, { 0x36c85b12, 0x37a66f55 }, 0x1cc19b8e6ULL }, - { 0x155fd48c7ULL, { 0xf5894d, 0x1256108 }, 0x11e383602ULL }, - { 0xb5db2d15ULL, { 0x39bb26c5, 0x5bdcda3e }, 0x72499259ULL }, - { 0x153990298ULL, { 0x48921c09, 0x706eb817 }, 0xdb3268e8ULL }, - { 0x28a7c3ed7ULL, { 0x1f776fd7, 0x349f7a70 }, 0x184f73ae1ULL }, + { 0x155fd48c7ULL, { 0xf5894d, 0x1256108 }, 0x11e383603ULL }, + { 0xb5db2d15ULL, { 0x39bb26c5, 0x5bdcda3e }, 0x7249925aULL }, + { 0x153990298ULL, { 0x48921c09, 0x706eb817 }, 0xdb3268e9ULL }, + { 0x28a7c3ed7ULL, { 0x1f776fd7, 0x349f7a70 }, 0x184f73ae2ULL }, { 0x724dbeabULL, { 0x1bd149f5, 0x253a085e }, 0x5569c0b3ULL }, { 0xd8f0c513ULL, { 0x18c8cc4c, 0x1b72bad0 }, 0xc3e30643ULL }, { 0x17ce3dcbULL, { 0x1e4c6260, 0x233b359e }, 0x1478f4afULL }, { 0x1ce036ce0ULL, { 0x29e3c8af, 0x5318dd4a }, 0xe8e76196ULL }, { 0x1473ae2aULL, { 0x29b897ba, 0x2be29378 }, 0x13718185ULL }, - { 0x1dd41aa68ULL, { 0x3d0a4441, 0x5a0e8f12 }, 0x1437b6bbfULL }, - { 0x1b49e4a53ULL, { 0x3430c1fe, 0x5a204aed }, 0xfcd6852fULL }, - { 0x217941b19ULL, { 0x12ced2bd, 0x21b68310 }, 0x12aca65b1ULL }, + { 0x1dd41aa68ULL, { 0x3d0a4441, 0x5a0e8f12 }, 0x1437b6bc1ULL }, + { 0x1b49e4a53ULL, { 0x3430c1fe, 0x5a204aed }, 0xfcd6852eULL }, + { 0x217941b19ULL, { 0x12ced2bd, 0x21b68310 }, 0x12aca65b2ULL }, { 0xac6a4dc8ULL, { 0x3ed68da8, 0x6fdca34c }, 0x60da926dULL }, - { 0x1c503a4e7ULL, { 0xfcbbd32, 0x11e48d17 }, 0x18fec7d38ULL }, + { 0x1c503a4e7ULL, { 0xfcbbd32, 0x11e48d17 }, 0x18fec7d39ULL }, { 0x1c885855ULL, { 0x213e919d, 0x25941897 }, 0x193de743ULL }, - { 0x29b9c168eULL, { 0x2b644aea, 0x45725ee7 }, 0x1a122e5d5ULL }, - { 0x806a33f2ULL, { 0x30a80a23, 0x5063733a }, 0x4db9a264ULL }, + { 0x29b9c168eULL, { 0x2b644aea, 0x45725ee7 }, 0x1a122e5d4ULL }, + { 0x806a33f2ULL, { 0x30a80a23, 0x5063733a }, 0x4db9a265ULL }, { 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 }, 0x1f0301e5e66b6badULL }, + { 0x5e4f2468142265e3ULL, { 0x1ddf5837, 0x32189233 }, 0x383ca7baaff2be1cULL }, + { 0x277a1a6f6b266bf6ULL, { 0x415d81a8, 0x61eb5e1e }, 0x1a5a3e1d36f8c35dULL }, + { 0x1bdbb49a237035cbULL, { 0xea5bf17, 0x1d25ffb3 }, 0xdffc51c4ed92d74ULL }, + { 0x2bce6d29b64fb8ULL, { 0x3bfd5631, 0x7525c9bb }, 0x166ebeddabf0bcULL }, + { 0x3a02116103df5013ULL, { 0x2ee18a83, 0x3299aea8 }, 0x35be8922a8357a29ULL }, + { 0x7b5762390799b18cULL, { 0x12f8e5b9, 0x2563bcd4 }, 0x3e960077a7ec561bULL }, + { 0x69cfd72537021579ULL, { 0x4c35f468, 0x6a40feee }, 0x4be4cb384b6f4344ULL }, + { 0x49dfdf835120f1c1ULL, { 0x8cb3759, 0x559eb891 }, 0x79663f7353f1c71ULL }, + { 0x74b5be5c27676381ULL, { 0x47e4c5e0, 0x7c7b19ff }, 0x4367d2dff5930545ULL }, + { 0x4f50f97075e7f431ULL, { 0x9a50a17, 0x11cd1185 }, 0x2af952b32e6e4636ULL }, + { 0x2f8b0d712e393be4ULL, { 0x1487e386, 0x15aa356e }, 0x2d0df3646922f27fULL }, + { 0x224c1c75999d3deULL, { 0x3b2df0ea, 0x4523b100 }, 0x1d5b481d111d046ULL }, + { 0x2bcbcea22a399a76ULL, { 0x28b58212, 0x48dd013e }, 0x187814d079849f27ULL }, + { 0x1dbfca91257cb2d1ULL, { 0x1a8c04d9, 0x5e92502c }, 0x859cf7d04823fbcULL }, + { 0x7f20039b57cda935ULL, { 0xeccf651, 0x323f476e }, 0x25720cd9a9d84532ULL }, + { 0x40512c6a586aa087ULL, { 0x113b0423, 0x398c9eab }, 0x1341c03dcea7e093ULL }, + { 0x63d802693f050a11ULL, { 0xf50cdd6, 0xfce2a44 }, 0x60c0177bc73a6766ULL }, + { 0x2d956b422838de77ULL, { 0xb2d345b, 0x1321e557 }, 0x1aa0ed16cb354473ULL }, + { 0x5a1cdf0c1657bc91ULL, { 0x1d77bb0c, 0x1f991ff1 }, 0x54097ee9304251bcULL }, + { 0x3801b26d7e00176bULL, { 0xeed25da, 0x1a819d8b }, 0x1f89e96a48f3d1bbULL }, + { 0x37655e74338e1e45ULL, { 0x300e170a, 0x5a1595fe }, 0x1d8cfb55e5920a9eULL }, + { 0x7b38703f2a84e6ULL, { 0x66d9053, 0xc79b6b9 }, 0x3f7d4c917df495ULL }, + { 0x2245063c0acb3215ULL, { 0x30ce2f5b, 0x610e7271 }, 0x113b91646739b6c5ULL }, + { 0x6bc195877b7b8a7eULL, { 0x392004aa, 0x4a24e60c }, 0x530594fb12cdb1bfULL }, + { 0x40a3fde23c7b43dbULL, { 0x4e712195, 0x6553e56e }, 0x320a799bb36c4347ULL }, + { 0x1d3dfc2866fbccbaULL, { 0x5075b517, 0x5fc42245 }, 0x18917f006fb03a59ULL }, + { 0x19aeb14045a61121ULL, { 0x1bf6edec, 0x707e2f4b }, 0x662667296df563dULL }, + { 0x44ff90486c531e9fULL, { 0x66598a, 0x8a90dc }, 0x32f6f2b03ff7e7b8ULL }, + { 0x3f3e7121092c5bcbULL, { 0x1c754df7, 0x5951a1b9 }, 0x14267f50a97f23b3ULL }, + { 0x60e2dafb7e50a67eULL, { 0x4d96c66e, 0x65bd878d }, 0x49e31715a758ff9aULL }, + { 0x656286667e0e6e29ULL, { 0x9d971a2, 0xacda23b }, 0x5c6ee315fa8ccdd9ULL }, + { 0x1114e0974255d507ULL, { 0x1c693, 0x2d6ff }, 0xaae42e4b7f901dbULL }, + { 0x508c8baf3a70ff5aULL, { 0x3b26b779, 0x6ad78745 }, 0x2c98387644270e27ULL }, + { 0x5b47bc666bf1f9cfULL, { 0x10a87ed6, 0x187d358a }, 0x3e1767157a01d920ULL }, + { 0x50954e3744460395ULL, { 0x7a42263, 0xcdaa048 }, 0x2fe739f0c4313c2dULL }, + { 0x20020b406550dd8fULL, { 0x3318539, 0x42eead0 }, 0x186f326320300be9ULL }, + { 0x5bcb0b872439ffd5ULL, { 0x6f61fb2, 0x9af7344 }, 0x41fa1e3bd254ff3bULL }, + { 0x7a670f365db87a53ULL, { 0x417e102, 0x3bb54c67 }, 0x8642a559fda7b3cULL }, + { 0x1ef0db1e7bab1cd0ULL, { 0x2b60cf38, 0x4188f78f }, 0x147ae0d6165981f4ULL } }; for (const auto &T : Tests) {