1cd630f28SDuncan P. N. Exon Smith //===- unittest/Support/BranchProbabilityTest.cpp - BranchProbability tests -=//
2cd630f28SDuncan P. N. Exon Smith //
3*2946cd70SChandler Carruth // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*2946cd70SChandler Carruth // See https://llvm.org/LICENSE.txt for license information.
5*2946cd70SChandler Carruth // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6cd630f28SDuncan P. N. Exon Smith //
7cd630f28SDuncan P. N. Exon Smith //===----------------------------------------------------------------------===//
8cd630f28SDuncan P. N. Exon Smith
9cd630f28SDuncan P. N. Exon Smith #include "llvm/Support/BranchProbability.h"
10cd630f28SDuncan P. N. Exon Smith #include "llvm/Support/raw_ostream.h"
11cd630f28SDuncan P. N. Exon Smith #include "gtest/gtest.h"
12cd630f28SDuncan P. N. Exon Smith
13cd630f28SDuncan P. N. Exon Smith using namespace llvm;
14cd630f28SDuncan P. N. Exon Smith
15cd630f28SDuncan P. N. Exon Smith namespace llvm {
PrintTo(BranchProbability P,::std::ostream * os)16c536bd9eSCong Hou void PrintTo(BranchProbability P, ::std::ostream *os) {
17cd630f28SDuncan P. N. Exon Smith *os << P.getNumerator() << "/" << P.getDenominator();
18cd630f28SDuncan P. N. Exon Smith }
19cd630f28SDuncan P. N. Exon Smith }
20cd630f28SDuncan P. N. Exon Smith namespace {
21cd630f28SDuncan P. N. Exon Smith
22cd630f28SDuncan P. N. Exon Smith typedef BranchProbability BP;
TEST(BranchProbabilityTest,Accessors)23cd630f28SDuncan P. N. Exon Smith TEST(BranchProbabilityTest, Accessors) {
2415ea0163SCong Hou EXPECT_EQ(306783378u, BP(1, 7).getNumerator());
2515ea0163SCong Hou EXPECT_EQ(1u << 31, BP(1, 7).getDenominator());
26cd630f28SDuncan P. N. Exon Smith EXPECT_EQ(0u, BP::getZero().getNumerator());
2715ea0163SCong Hou EXPECT_EQ(1u << 31, BP::getZero().getDenominator());
2815ea0163SCong Hou EXPECT_EQ(1u << 31, BP::getOne().getNumerator());
2915ea0163SCong Hou EXPECT_EQ(1u << 31, BP::getOne().getDenominator());
30cd630f28SDuncan P. N. Exon Smith }
31cd630f28SDuncan P. N. Exon Smith
TEST(BranchProbabilityTest,Operators)32cd630f28SDuncan P. N. Exon Smith TEST(BranchProbabilityTest, Operators) {
33cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) < BP(2, 7));
34cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) < BP(1, 4));
35cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(5, 7) < BP(3, 4));
36cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) < BP(1, 7));
37cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) < BP(2, 14));
38cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(4, 7) < BP(1, 2));
39cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(4, 7) < BP(3, 7));
40cd630f28SDuncan P. N. Exon Smith
41cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) > BP(2, 7));
42cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) > BP(1, 4));
43cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(5, 7) > BP(3, 4));
44cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) > BP(1, 7));
45cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) > BP(2, 14));
46cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(4, 7) > BP(1, 2));
47cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(4, 7) > BP(3, 7));
48cd630f28SDuncan P. N. Exon Smith
49cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) <= BP(2, 7));
50cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) <= BP(1, 4));
51cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(5, 7) <= BP(3, 4));
52cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) <= BP(1, 7));
53cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) <= BP(2, 14));
54cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(4, 7) <= BP(1, 2));
55cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(4, 7) <= BP(3, 7));
56cd630f28SDuncan P. N. Exon Smith
57cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) >= BP(2, 7));
58cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) >= BP(1, 4));
59cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(5, 7) >= BP(3, 4));
60cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) >= BP(1, 7));
61cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) >= BP(2, 14));
62cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(4, 7) >= BP(1, 2));
63cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(4, 7) >= BP(3, 7));
64cd630f28SDuncan P. N. Exon Smith
65cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) == BP(2, 7));
66cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) == BP(1, 4));
67cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(5, 7) == BP(3, 4));
68cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) == BP(1, 7));
69cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) == BP(2, 14));
70cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(4, 7) == BP(1, 2));
71cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(4, 7) == BP(3, 7));
72cd630f28SDuncan P. N. Exon Smith
73cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) != BP(2, 7));
74cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(1, 7) != BP(1, 4));
75cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(5, 7) != BP(3, 4));
76cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) != BP(1, 7));
77cd630f28SDuncan P. N. Exon Smith EXPECT_FALSE(BP(1, 7) != BP(2, 14));
78cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(4, 7) != BP(1, 2));
79cd630f28SDuncan P. N. Exon Smith EXPECT_TRUE(BP(4, 7) != BP(3, 7));
8015ea0163SCong Hou
8115ea0163SCong Hou EXPECT_TRUE(BP(1, 7) == BP(2, 14));
8215ea0163SCong Hou EXPECT_TRUE(BP(1, 7) == BP(3, 21));
8315ea0163SCong Hou EXPECT_TRUE(BP(5, 7) == BP(25, 35));
8415ea0163SCong Hou EXPECT_TRUE(BP(99999998, 100000000) < BP(99999999, 100000000));
8515ea0163SCong Hou EXPECT_TRUE(BP(4, 8) == BP(400000000, 800000000));
86cd630f28SDuncan P. N. Exon Smith }
87cd630f28SDuncan P. N. Exon Smith
TEST(BranchProbabilityTest,MoreOperators)886e8d1ef9SDuncan P. N. Exon Smith TEST(BranchProbabilityTest, MoreOperators) {
897c8cf3e0SDuncan P. N. Exon Smith BP A(4, 5);
907c8cf3e0SDuncan P. N. Exon Smith BP B(4U << 29, 5U << 29);
917c8cf3e0SDuncan P. N. Exon Smith BP C(3, 4);
927c8cf3e0SDuncan P. N. Exon Smith
937c8cf3e0SDuncan P. N. Exon Smith EXPECT_TRUE(A == B);
947c8cf3e0SDuncan P. N. Exon Smith EXPECT_FALSE(A != B);
957c8cf3e0SDuncan P. N. Exon Smith EXPECT_FALSE(A < B);
967c8cf3e0SDuncan P. N. Exon Smith EXPECT_FALSE(A > B);
977c8cf3e0SDuncan P. N. Exon Smith EXPECT_TRUE(A <= B);
987c8cf3e0SDuncan P. N. Exon Smith EXPECT_TRUE(A >= B);
997c8cf3e0SDuncan P. N. Exon Smith
1007c8cf3e0SDuncan P. N. Exon Smith EXPECT_FALSE(B == C);
1017c8cf3e0SDuncan P. N. Exon Smith EXPECT_TRUE(B != C);
1027c8cf3e0SDuncan P. N. Exon Smith EXPECT_FALSE(B < C);
1037c8cf3e0SDuncan P. N. Exon Smith EXPECT_TRUE(B > C);
1047c8cf3e0SDuncan P. N. Exon Smith EXPECT_FALSE(B <= C);
1057c8cf3e0SDuncan P. N. Exon Smith EXPECT_TRUE(B >= C);
1067c8cf3e0SDuncan P. N. Exon Smith
1077c8cf3e0SDuncan P. N. Exon Smith BP BigZero(0, UINT32_MAX);
1087c8cf3e0SDuncan P. N. Exon Smith BP BigOne(UINT32_MAX, UINT32_MAX);
1097c8cf3e0SDuncan P. N. Exon Smith EXPECT_FALSE(BigZero == BigOne);
1107c8cf3e0SDuncan P. N. Exon Smith EXPECT_TRUE(BigZero != BigOne);
1117c8cf3e0SDuncan P. N. Exon Smith EXPECT_TRUE(BigZero < BigOne);
1127c8cf3e0SDuncan P. N. Exon Smith EXPECT_FALSE(BigZero > BigOne);
1137c8cf3e0SDuncan P. N. Exon Smith EXPECT_TRUE(BigZero <= BigOne);
1147c8cf3e0SDuncan P. N. Exon Smith EXPECT_FALSE(BigZero >= BigOne);
1157c8cf3e0SDuncan P. N. Exon Smith }
1167c8cf3e0SDuncan P. N. Exon Smith
TEST(BranchProbabilityTest,ArithmeticOperators)1175b817d02SSerguei Katkov TEST(BranchProbabilityTest, ArithmeticOperators) {
1185b817d02SSerguei Katkov BP Z(0, 1);
1195b817d02SSerguei Katkov BP O(1, 1);
1205b817d02SSerguei Katkov BP H(1, 2);
1215b817d02SSerguei Katkov BP Q(1, 4);
1225b817d02SSerguei Katkov BP Q3(3, 4);
1235b817d02SSerguei Katkov
1245b817d02SSerguei Katkov EXPECT_EQ(Z + O, O);
1255b817d02SSerguei Katkov EXPECT_EQ(H + Z, H);
1265b817d02SSerguei Katkov EXPECT_EQ(H + H, O);
1275b817d02SSerguei Katkov EXPECT_EQ(Q + H, Q3);
1285b817d02SSerguei Katkov EXPECT_EQ(Q + Q3, O);
1295b817d02SSerguei Katkov EXPECT_EQ(H + Q3, O);
1305b817d02SSerguei Katkov EXPECT_EQ(Q3 + Q3, O);
1315b817d02SSerguei Katkov
1325b817d02SSerguei Katkov EXPECT_EQ(Z - O, Z);
1335b817d02SSerguei Katkov EXPECT_EQ(O - Z, O);
1345b817d02SSerguei Katkov EXPECT_EQ(O - H, H);
1355b817d02SSerguei Katkov EXPECT_EQ(O - Q, Q3);
1365b817d02SSerguei Katkov EXPECT_EQ(Q3 - H, Q);
1375b817d02SSerguei Katkov EXPECT_EQ(Q - H, Z);
1385b817d02SSerguei Katkov EXPECT_EQ(Q - Q3, Z);
1395b817d02SSerguei Katkov
1405b817d02SSerguei Katkov EXPECT_EQ(Z * O, Z);
1415b817d02SSerguei Katkov EXPECT_EQ(H * H, Q);
1425b817d02SSerguei Katkov EXPECT_EQ(Q * O, Q);
1435b817d02SSerguei Katkov EXPECT_EQ(O * O, O);
1445b817d02SSerguei Katkov EXPECT_EQ(Z * Z, Z);
1455b817d02SSerguei Katkov
1465b817d02SSerguei Katkov EXPECT_EQ(Z * 3, Z);
1475b817d02SSerguei Katkov EXPECT_EQ(Q * 3, Q3);
1485b817d02SSerguei Katkov EXPECT_EQ(H * 3, O);
1495b817d02SSerguei Katkov EXPECT_EQ(Q3 * 2, O);
1505b817d02SSerguei Katkov EXPECT_EQ(O * UINT32_MAX, O);
1515b817d02SSerguei Katkov
1525b817d02SSerguei Katkov EXPECT_EQ(Z / 4, Z);
1535b817d02SSerguei Katkov EXPECT_EQ(O / 4, Q);
1545b817d02SSerguei Katkov EXPECT_EQ(Q3 / 3, Q);
1555b817d02SSerguei Katkov EXPECT_EQ(H / 2, Q);
1565b817d02SSerguei Katkov EXPECT_EQ(O / 2, H);
1575b817d02SSerguei Katkov EXPECT_EQ(H / UINT32_MAX, Z);
1585b817d02SSerguei Katkov
1595b817d02SSerguei Katkov BP Min(1, 1u << 31);
1605b817d02SSerguei Katkov
1615b817d02SSerguei Katkov EXPECT_EQ(O / UINT32_MAX, Z);
1625b817d02SSerguei Katkov EXPECT_EQ(Min * UINT32_MAX, O);
1635b817d02SSerguei Katkov }
1645b817d02SSerguei Katkov
TEST(BranchProbabilityTest,getCompl)165cd630f28SDuncan P. N. Exon Smith TEST(BranchProbabilityTest, getCompl) {
166cd630f28SDuncan P. N. Exon Smith EXPECT_EQ(BP(5, 7), BP(2, 7).getCompl());
167cd630f28SDuncan P. N. Exon Smith EXPECT_EQ(BP(2, 7), BP(5, 7).getCompl());
168cd630f28SDuncan P. N. Exon Smith EXPECT_EQ(BP::getZero(), BP(7, 7).getCompl());
169cd630f28SDuncan P. N. Exon Smith EXPECT_EQ(BP::getOne(), BP(0, 7).getCompl());
170cd630f28SDuncan P. N. Exon Smith }
171cd630f28SDuncan P. N. Exon Smith
TEST(BranchProbabilityTest,scale)172415e7656SDuncan P. N. Exon Smith TEST(BranchProbabilityTest, scale) {
173415e7656SDuncan P. N. Exon Smith // Multiply by 1.0.
174415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT64_MAX, BP(1, 1).scale(UINT64_MAX));
175415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT64_MAX, BP(7, 7).scale(UINT64_MAX));
176415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT32_MAX, BP(1, 1).scale(UINT32_MAX));
177415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT32_MAX, BP(7, 7).scale(UINT32_MAX));
178415e7656SDuncan P. N. Exon Smith EXPECT_EQ(0u, BP(1, 1).scale(0));
179415e7656SDuncan P. N. Exon Smith EXPECT_EQ(0u, BP(7, 7).scale(0));
180415e7656SDuncan P. N. Exon Smith
181415e7656SDuncan P. N. Exon Smith // Multiply by 0.0.
182415e7656SDuncan P. N. Exon Smith EXPECT_EQ(0u, BP(0, 1).scale(UINT64_MAX));
183415e7656SDuncan P. N. Exon Smith EXPECT_EQ(0u, BP(0, 1).scale(UINT64_MAX));
184415e7656SDuncan P. N. Exon Smith EXPECT_EQ(0u, BP(0, 1).scale(0));
185415e7656SDuncan P. N. Exon Smith
186415e7656SDuncan P. N. Exon Smith auto Two63 = UINT64_C(1) << 63;
187415e7656SDuncan P. N. Exon Smith auto Two31 = UINT64_C(1) << 31;
188415e7656SDuncan P. N. Exon Smith
189415e7656SDuncan P. N. Exon Smith // Multiply by 0.5.
190415e7656SDuncan P. N. Exon Smith EXPECT_EQ(Two63 - 1, BP(1, 2).scale(UINT64_MAX));
191415e7656SDuncan P. N. Exon Smith
192415e7656SDuncan P. N. Exon Smith // Big fractions.
193415e7656SDuncan P. N. Exon Smith EXPECT_EQ(1u, BP(Two31, UINT32_MAX).scale(2));
194415e7656SDuncan P. N. Exon Smith EXPECT_EQ(Two31, BP(Two31, UINT32_MAX).scale(Two31 * 2));
19515ea0163SCong Hou EXPECT_EQ(9223372036854775807ULL, BP(Two31, UINT32_MAX).scale(UINT64_MAX));
196415e7656SDuncan P. N. Exon Smith
197415e7656SDuncan P. N. Exon Smith // High precision.
19815ea0163SCong Hou EXPECT_EQ(UINT64_C(9223372045444710399),
199415e7656SDuncan P. N. Exon Smith BP(Two31 + 1, UINT32_MAX - 2).scale(UINT64_MAX));
200415e7656SDuncan P. N. Exon Smith }
201415e7656SDuncan P. N. Exon Smith
TEST(BranchProbabilityTest,scaleByInverse)202415e7656SDuncan P. N. Exon Smith TEST(BranchProbabilityTest, scaleByInverse) {
203415e7656SDuncan P. N. Exon Smith // Divide by 1.0.
204415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT64_MAX, BP(1, 1).scaleByInverse(UINT64_MAX));
205415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT64_MAX, BP(7, 7).scaleByInverse(UINT64_MAX));
206415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT32_MAX, BP(1, 1).scaleByInverse(UINT32_MAX));
207415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT32_MAX, BP(7, 7).scaleByInverse(UINT32_MAX));
208415e7656SDuncan P. N. Exon Smith EXPECT_EQ(0u, BP(1, 1).scaleByInverse(0));
209415e7656SDuncan P. N. Exon Smith EXPECT_EQ(0u, BP(7, 7).scaleByInverse(0));
210415e7656SDuncan P. N. Exon Smith
21115ea0163SCong Hou auto MAX_DENOMINATOR = BP::getDenominator();
21215ea0163SCong Hou
213415e7656SDuncan P. N. Exon Smith // Divide by something very small.
214415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT64_MAX, BP(1, UINT32_MAX).scaleByInverse(UINT64_MAX));
21515ea0163SCong Hou EXPECT_EQ(uint64_t(UINT32_MAX) * MAX_DENOMINATOR,
21615ea0163SCong Hou BP(1, MAX_DENOMINATOR).scaleByInverse(UINT32_MAX));
21715ea0163SCong Hou EXPECT_EQ(MAX_DENOMINATOR, BP(1, MAX_DENOMINATOR).scaleByInverse(1));
218415e7656SDuncan P. N. Exon Smith
219415e7656SDuncan P. N. Exon Smith auto Two63 = UINT64_C(1) << 63;
220415e7656SDuncan P. N. Exon Smith auto Two31 = UINT64_C(1) << 31;
221415e7656SDuncan P. N. Exon Smith
222415e7656SDuncan P. N. Exon Smith // Divide by 0.5.
223415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT64_MAX - 1, BP(1, 2).scaleByInverse(Two63 - 1));
224415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT64_MAX, BP(1, 2).scaleByInverse(Two63));
225415e7656SDuncan P. N. Exon Smith
226415e7656SDuncan P. N. Exon Smith // Big fractions.
22715ea0163SCong Hou EXPECT_EQ(2u, BP(Two31, UINT32_MAX).scaleByInverse(1));
228415e7656SDuncan P. N. Exon Smith EXPECT_EQ(2u, BP(Two31 - 1, UINT32_MAX).scaleByInverse(1));
22915ea0163SCong Hou EXPECT_EQ(Two31 * 2, BP(Two31, UINT32_MAX).scaleByInverse(Two31));
23015ea0163SCong Hou EXPECT_EQ(Two31 * 2, BP(Two31 - 1, UINT32_MAX).scaleByInverse(Two31));
231415e7656SDuncan P. N. Exon Smith EXPECT_EQ(UINT64_MAX, BP(Two31, UINT32_MAX).scaleByInverse(Two63 + Two31));
232415e7656SDuncan P. N. Exon Smith
233415e7656SDuncan P. N. Exon Smith // High precision. The exact answers to these are close to the successors of
234415e7656SDuncan P. N. Exon Smith // the floor. If we were rounding, these would round up.
23515ea0163SCong Hou EXPECT_EQ(UINT64_C(18446744060824649767),
236415e7656SDuncan P. N. Exon Smith BP(Two31 + 2, UINT32_MAX - 2)
23715ea0163SCong Hou .scaleByInverse(UINT64_C(9223372047592194056)));
23815ea0163SCong Hou EXPECT_EQ(UINT64_C(18446744060824649739),
239415e7656SDuncan P. N. Exon Smith BP(Two31 + 1, UINT32_MAX).scaleByInverse(Two63 + Two31));
240415e7656SDuncan P. N. Exon Smith }
241415e7656SDuncan P. N. Exon Smith
TEST(BranchProbabilityTest,scaleBruteForce)2426e8d1ef9SDuncan P. N. Exon Smith TEST(BranchProbabilityTest, scaleBruteForce) {
243a097c484SDuncan P. N. Exon Smith struct {
244a097c484SDuncan P. N. Exon Smith uint64_t Num;
245a097c484SDuncan P. N. Exon Smith uint32_t Prob[2];
246a097c484SDuncan P. N. Exon Smith uint64_t Result;
247a097c484SDuncan P. N. Exon Smith } Tests[] = {
248a097c484SDuncan P. N. Exon Smith // Data for scaling that results in <= 64 bit division.
24915ea0163SCong Hou { 0x1423e2a50ULL, { 0x64819521, 0x7765dd13 }, 0x10f418888ULL },
25015ea0163SCong Hou { 0x35ef14ceULL, { 0x28ade3c7, 0x304532ae }, 0x2d73c33bULL },
25115ea0163SCong Hou { 0xd03dbfbe24ULL, { 0x790079, 0xe419f3 }, 0x6e776fc2c4ULL },
25215ea0163SCong Hou { 0x21d67410bULL, { 0x302a9dc2, 0x3ddb4442 }, 0x1a5948fd4ULL },
253a097c484SDuncan P. N. Exon Smith { 0x8664aeadULL, { 0x3d523513, 0x403523b1 }, 0x805a04cfULL },
25415ea0163SCong Hou { 0x201db0cf4ULL, { 0x35112a7b, 0x79fc0c74 }, 0xdf8b07f8ULL },
25515ea0163SCong Hou { 0x13f1e4430aULL, { 0x21c92bf, 0x21e63aae }, 0x13e0cba26ULL },
256a097c484SDuncan P. N. Exon Smith { 0x16c83229ULL, { 0x3793f66f, 0x53180dea }, 0xf3ce7b6ULL },
25715ea0163SCong Hou { 0xc62415be8ULL, { 0x9cc4a63, 0x4327ae9b }, 0x1ce8b71c1ULL },
258a097c484SDuncan P. N. Exon Smith { 0x6fac5e434ULL, { 0xe5f9170, 0x1115e10b }, 0x5df23dd4cULL },
25915ea0163SCong Hou { 0x1929375f2ULL, { 0x3a851375, 0x76c08456 }, 0xc662b083ULL },
26015ea0163SCong Hou { 0x243c89db6ULL, { 0x354ebfc0, 0x450ef197 }, 0x1bf8c1663ULL },
261a097c484SDuncan P. N. Exon Smith { 0x310e9b31aULL, { 0x1b1b8acf, 0x2d3629f0 }, 0x1d69c93f9ULL },
26215ea0163SCong Hou { 0xa1fae921dULL, { 0xa7a098c, 0x10469f44 }, 0x684413d6eULL },
26315ea0163SCong Hou { 0xc1582d957ULL, { 0x498e061, 0x59856bc }, 0x9edc5f4ecULL },
264a097c484SDuncan P. N. Exon Smith { 0x57cfee75ULL, { 0x1d061dc3, 0x7c8bfc17 }, 0x1476a220ULL },
26515ea0163SCong Hou { 0x139220080ULL, { 0x294a6c71, 0x2a2b07c9 }, 0x1329e1c75ULL },
26615ea0163SCong Hou { 0x1665d353cULL, { 0x7080db5, 0xde0d75c }, 0xb590d9faULL },
267a097c484SDuncan P. N. Exon Smith { 0xe8f14541ULL, { 0x5188e8b2, 0x736527ef }, 0xa4971be5ULL },
268a097c484SDuncan P. N. Exon Smith { 0x2f4775f29ULL, { 0x254ef0fe, 0x435fcf50 }, 0x1a2e449c1ULL },
26915ea0163SCong Hou { 0x27b85d8d7ULL, { 0x304c8220, 0x5de678f2 }, 0x146e3befbULL },
27015ea0163SCong Hou { 0x1d362e36bULL, { 0x36c85b12, 0x37a66f55 }, 0x1cc19b8e7ULL },
27115ea0163SCong Hou { 0x155fd48c7ULL, { 0xf5894d, 0x1256108 }, 0x11e383604ULL },
272a097c484SDuncan P. N. Exon Smith { 0xb5db2d15ULL, { 0x39bb26c5, 0x5bdcda3e }, 0x72499259ULL },
27315ea0163SCong Hou { 0x153990298ULL, { 0x48921c09, 0x706eb817 }, 0xdb3268e7ULL },
27415ea0163SCong Hou { 0x28a7c3ed7ULL, { 0x1f776fd7, 0x349f7a70 }, 0x184f73ae2ULL },
275a097c484SDuncan P. N. Exon Smith { 0x724dbeabULL, { 0x1bd149f5, 0x253a085e }, 0x5569c0b3ULL },
27615ea0163SCong Hou { 0xd8f0c513ULL, { 0x18c8cc4c, 0x1b72bad0 }, 0xc3e30642ULL },
277a097c484SDuncan P. N. Exon Smith { 0x17ce3dcbULL, { 0x1e4c6260, 0x233b359e }, 0x1478f4afULL },
27815ea0163SCong Hou { 0x1ce036ce0ULL, { 0x29e3c8af, 0x5318dd4a }, 0xe8e76195ULL },
279a097c484SDuncan P. N. Exon Smith { 0x1473ae2aULL, { 0x29b897ba, 0x2be29378 }, 0x13718185ULL },
280a097c484SDuncan P. N. Exon Smith { 0x1dd41aa68ULL, { 0x3d0a4441, 0x5a0e8f12 }, 0x1437b6bbfULL },
281a097c484SDuncan P. N. Exon Smith { 0x1b49e4a53ULL, { 0x3430c1fe, 0x5a204aed }, 0xfcd6852fULL },
282a097c484SDuncan P. N. Exon Smith { 0x217941b19ULL, { 0x12ced2bd, 0x21b68310 }, 0x12aca65b1ULL },
283a097c484SDuncan P. N. Exon Smith { 0xac6a4dc8ULL, { 0x3ed68da8, 0x6fdca34c }, 0x60da926dULL },
28415ea0163SCong Hou { 0x1c503a4e7ULL, { 0xfcbbd32, 0x11e48d17 }, 0x18fec7d37ULL },
28515ea0163SCong Hou { 0x1c885855ULL, { 0x213e919d, 0x25941897 }, 0x193de742ULL },
28615ea0163SCong Hou { 0x29b9c168eULL, { 0x2b644aea, 0x45725ee7 }, 0x1a122e5d4ULL },
287a097c484SDuncan P. N. Exon Smith { 0x806a33f2ULL, { 0x30a80a23, 0x5063733a }, 0x4db9a264ULL },
288a097c484SDuncan P. N. Exon Smith { 0x282afc96bULL, { 0x143ae554, 0x1a9863ff }, 0x1e8de5204ULL },
289a097c484SDuncan P. N. Exon Smith // Data for scaling that results in > 64 bit division.
29015ea0163SCong Hou { 0x23ca5f2f672ca41cULL, { 0xecbc641, 0x111373f7 }, 0x1f0301e5c76869c6ULL },
29115ea0163SCong Hou { 0x5e4f2468142265e3ULL, { 0x1ddf5837, 0x32189233 }, 0x383ca7bad6053ac9ULL },
29215ea0163SCong Hou { 0x277a1a6f6b266bf6ULL, { 0x415d81a8, 0x61eb5e1e }, 0x1a5a3e1d1c9e8540ULL },
29315ea0163SCong Hou { 0x1bdbb49a237035cbULL, { 0xea5bf17, 0x1d25ffb3 }, 0xdffc51c5cb51cf1ULL },
29415ea0163SCong Hou { 0x2bce6d29b64fb8ULL, { 0x3bfd5631, 0x7525c9bb }, 0x166ebedd9581fdULL },
29515ea0163SCong Hou { 0x3a02116103df5013ULL, { 0x2ee18a83, 0x3299aea8 }, 0x35be89227276f105ULL },
29615ea0163SCong Hou { 0x7b5762390799b18cULL, { 0x12f8e5b9, 0x2563bcd4 }, 0x3e960077695655a3ULL },
29715ea0163SCong Hou { 0x69cfd72537021579ULL, { 0x4c35f468, 0x6a40feee }, 0x4be4cb38695a4f30ULL },
29815ea0163SCong Hou { 0x49dfdf835120f1c1ULL, { 0x8cb3759, 0x559eb891 }, 0x79663f6e3c8d8f6ULL },
29915ea0163SCong Hou { 0x74b5be5c27676381ULL, { 0x47e4c5e0, 0x7c7b19ff }, 0x4367d2dfb22b3265ULL },
30015ea0163SCong Hou { 0x4f50f97075e7f431ULL, { 0x9a50a17, 0x11cd1185 }, 0x2af952b30374f382ULL },
30115ea0163SCong Hou { 0x2f8b0d712e393be4ULL, { 0x1487e386, 0x15aa356e }, 0x2d0df3649b2b19fcULL },
30215ea0163SCong Hou { 0x224c1c75999d3deULL, { 0x3b2df0ea, 0x4523b100 }, 0x1d5b481d160dd8bULL },
30315ea0163SCong Hou { 0x2bcbcea22a399a76ULL, { 0x28b58212, 0x48dd013e }, 0x187814d0610c8a56ULL },
30415ea0163SCong Hou { 0x1dbfca91257cb2d1ULL, { 0x1a8c04d9, 0x5e92502c }, 0x859cf7d19e83ad0ULL },
30515ea0163SCong Hou { 0x7f20039b57cda935ULL, { 0xeccf651, 0x323f476e }, 0x25720cd9054634bdULL },
30615ea0163SCong Hou { 0x40512c6a586aa087ULL, { 0x113b0423, 0x398c9eab }, 0x1341c03dbb662054ULL },
30715ea0163SCong Hou { 0x63d802693f050a11ULL, { 0xf50cdd6, 0xfce2a44 }, 0x60c0177b667a4feaULL },
30815ea0163SCong Hou { 0x2d956b422838de77ULL, { 0xb2d345b, 0x1321e557 }, 0x1aa0ed16b094575cULL },
30915ea0163SCong Hou { 0x5a1cdf0c1657bc91ULL, { 0x1d77bb0c, 0x1f991ff1 }, 0x54097ee9907290eaULL },
31015ea0163SCong Hou { 0x3801b26d7e00176bULL, { 0xeed25da, 0x1a819d8b }, 0x1f89e96a616b9abeULL },
31115ea0163SCong Hou { 0x37655e74338e1e45ULL, { 0x300e170a, 0x5a1595fe }, 0x1d8cfb55ff6a6dbcULL },
31215ea0163SCong Hou { 0x7b38703f2a84e6ULL, { 0x66d9053, 0xc79b6b9 }, 0x3f7d4c91b9afb9ULL },
31315ea0163SCong Hou { 0x2245063c0acb3215ULL, { 0x30ce2f5b, 0x610e7271 }, 0x113b916455fe2560ULL },
31415ea0163SCong Hou { 0x6bc195877b7b8a7eULL, { 0x392004aa, 0x4a24e60c }, 0x530594fabfc81cc3ULL },
31515ea0163SCong Hou { 0x40a3fde23c7b43dbULL, { 0x4e712195, 0x6553e56e }, 0x320a799bc205c78dULL },
31615ea0163SCong Hou { 0x1d3dfc2866fbccbaULL, { 0x5075b517, 0x5fc42245 }, 0x18917f00745cb781ULL },
31715ea0163SCong Hou { 0x19aeb14045a61121ULL, { 0x1bf6edec, 0x707e2f4b }, 0x6626672aa2ba10aULL },
31815ea0163SCong Hou { 0x44ff90486c531e9fULL, { 0x66598a, 0x8a90dc }, 0x32f6f2b097001598ULL },
31915ea0163SCong Hou { 0x3f3e7121092c5bcbULL, { 0x1c754df7, 0x5951a1b9 }, 0x14267f50d4971583ULL },
32015ea0163SCong Hou { 0x60e2dafb7e50a67eULL, { 0x4d96c66e, 0x65bd878d }, 0x49e317155d75e883ULL },
32115ea0163SCong Hou { 0x656286667e0e6e29ULL, { 0x9d971a2, 0xacda23b }, 0x5c6ee3159e1deac3ULL },
32215ea0163SCong Hou { 0x1114e0974255d507ULL, { 0x1c693, 0x2d6ff }, 0xaae42e4be5f9f8dULL },
32315ea0163SCong Hou { 0x508c8baf3a70ff5aULL, { 0x3b26b779, 0x6ad78745 }, 0x2c983876178ed5b1ULL },
32415ea0163SCong Hou { 0x5b47bc666bf1f9cfULL, { 0x10a87ed6, 0x187d358a }, 0x3e1767153bea720aULL },
32515ea0163SCong Hou { 0x50954e3744460395ULL, { 0x7a42263, 0xcdaa048 }, 0x2fe739f0944a023cULL },
32615ea0163SCong Hou { 0x20020b406550dd8fULL, { 0x3318539, 0x42eead0 }, 0x186f326307c0d985ULL },
32715ea0163SCong Hou { 0x5bcb0b872439ffd5ULL, { 0x6f61fb2, 0x9af7344 }, 0x41fa1e3c47f0f80dULL },
32815ea0163SCong Hou { 0x7a670f365db87a53ULL, { 0x417e102, 0x3bb54c67 }, 0x8642a551d0f41b0ULL },
32915ea0163SCong Hou { 0x1ef0db1e7bab1cd0ULL, { 0x2b60cf38, 0x4188f78f }, 0x147ae0d63fc0575aULL }
330a097c484SDuncan P. N. Exon Smith };
331a097c484SDuncan P. N. Exon Smith
332a097c484SDuncan P. N. Exon Smith for (const auto &T : Tests) {
333a097c484SDuncan P. N. Exon Smith EXPECT_EQ(T.Result, BP(T.Prob[0], T.Prob[1]).scale(T.Num));
334a097c484SDuncan P. N. Exon Smith }
335a097c484SDuncan P. N. Exon Smith }
336a097c484SDuncan P. N. Exon Smith
TEST(BranchProbabilityTest,NormalizeProbabilities)3379f69cc02SCong Hou TEST(BranchProbabilityTest, NormalizeProbabilities) {
3387308f42dSCong Hou const auto UnknownProb = BranchProbability::getUnknown();
33972d44b1bSManman Ren {
3409f69cc02SCong Hou SmallVector<BranchProbability, 2> Probs{{0, 1}, {0, 1}};
3419f69cc02SCong Hou BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
3429f69cc02SCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator());
3439f69cc02SCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator());
34472d44b1bSManman Ren }
34572d44b1bSManman Ren {
3469f69cc02SCong Hou SmallVector<BranchProbability, 2> Probs{{0, 1}, {1, 1}};
3479f69cc02SCong Hou BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
3489f69cc02SCong Hou EXPECT_EQ(0u, Probs[0].getNumerator());
3499f69cc02SCong Hou EXPECT_EQ(BranchProbability::getDenominator(), Probs[1].getNumerator());
35072d44b1bSManman Ren }
35172d44b1bSManman Ren {
3529f69cc02SCong Hou SmallVector<BranchProbability, 2> Probs{{1, 100}, {1, 100}};
3539f69cc02SCong Hou BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
3549f69cc02SCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator());
3559f69cc02SCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator());
35672d44b1bSManman Ren }
35772d44b1bSManman Ren {
3589f69cc02SCong Hou SmallVector<BranchProbability, 2> Probs{{1, 1}, {1, 1}};
3599f69cc02SCong Hou BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
3609f69cc02SCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator());
3619f69cc02SCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator());
36272d44b1bSManman Ren }
36372d44b1bSManman Ren {
3649f69cc02SCong Hou SmallVector<BranchProbability, 3> Probs{{1, 1}, {1, 1}, {1, 1}};
3659f69cc02SCong Hou BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
3669f69cc02SCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1,
3679f69cc02SCong Hou Probs[0].getNumerator());
3689f69cc02SCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1,
3699f69cc02SCong Hou Probs[1].getNumerator());
3709f69cc02SCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1,
3719f69cc02SCong Hou Probs[2].getNumerator());
37272d44b1bSManman Ren }
3737308f42dSCong Hou {
3747308f42dSCong Hou SmallVector<BranchProbability, 2> Probs{{0, 1}, UnknownProb};
3757308f42dSCong Hou BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
376d7c0b735SNAKAMURA Takumi EXPECT_EQ(0U, Probs[0].getNumerator());
3777308f42dSCong Hou EXPECT_EQ(BranchProbability::getDenominator(), Probs[1].getNumerator());
3787308f42dSCong Hou }
3797308f42dSCong Hou {
3807308f42dSCong Hou SmallVector<BranchProbability, 2> Probs{{1, 1}, UnknownProb};
3817308f42dSCong Hou BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
3827308f42dSCong Hou EXPECT_EQ(BranchProbability::getDenominator(), Probs[0].getNumerator());
383d7c0b735SNAKAMURA Takumi EXPECT_EQ(0U, Probs[1].getNumerator());
3847308f42dSCong Hou }
3857308f42dSCong Hou {
3867308f42dSCong Hou SmallVector<BranchProbability, 2> Probs{{1, 2}, UnknownProb};
3877308f42dSCong Hou BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
3887308f42dSCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator());
3897308f42dSCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator());
3907308f42dSCong Hou }
3917308f42dSCong Hou {
3927308f42dSCong Hou SmallVector<BranchProbability, 4> Probs{
3937308f42dSCong Hou {1, 2}, {1, 2}, {1, 2}, UnknownProb};
3947308f42dSCong Hou BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
3957308f42dSCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1,
3967308f42dSCong Hou Probs[0].getNumerator());
3977308f42dSCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1,
3987308f42dSCong Hou Probs[1].getNumerator());
3997308f42dSCong Hou EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1,
4007308f42dSCong Hou Probs[2].getNumerator());
401d7c0b735SNAKAMURA Takumi EXPECT_EQ(0U, Probs[3].getNumerator());
4027308f42dSCong Hou }
40372d44b1bSManman Ren }
40472d44b1bSManman Ren
405cd630f28SDuncan P. N. Exon Smith }
406