1 | //===- unittest/Support/BranchProbabilityTest.cpp - BranchProbability tests -=// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #include "llvm/Support/BranchProbability.h" |
10 | #include "llvm/Support/raw_ostream.h" |
11 | #include "gtest/gtest.h" |
12 | |
13 | using namespace llvm; |
14 | |
15 | namespace llvm { |
16 | void PrintTo(BranchProbability P, ::std::ostream *os) { |
17 | *os << P.getNumerator() << "/" << P.getDenominator(); |
18 | } |
19 | } |
20 | namespace { |
21 | |
22 | typedef BranchProbability BP; |
23 | TEST(BranchProbabilityTest, Accessors) { |
24 | EXPECT_EQ(306783378u, BP(1, 7).getNumerator()); |
25 | EXPECT_EQ(1u << 31, BP(1, 7).getDenominator()); |
26 | EXPECT_EQ(0u, BP::getZero().getNumerator()); |
27 | EXPECT_EQ(1u << 31, BP::getZero().getDenominator()); |
28 | EXPECT_EQ(1u << 31, BP::getOne().getNumerator()); |
29 | EXPECT_EQ(1u << 31, BP::getOne().getDenominator()); |
30 | } |
31 | |
32 | TEST(BranchProbabilityTest, Operators) { |
33 | EXPECT_TRUE(BP(1, 7) < BP(2, 7)); |
34 | EXPECT_TRUE(BP(1, 7) < BP(1, 4)); |
35 | EXPECT_TRUE(BP(5, 7) < BP(3, 4)); |
36 | EXPECT_FALSE(BP(1, 7) < BP(1, 7)); |
37 | EXPECT_FALSE(BP(1, 7) < BP(2, 14)); |
38 | EXPECT_FALSE(BP(4, 7) < BP(1, 2)); |
39 | EXPECT_FALSE(BP(4, 7) < BP(3, 7)); |
40 | |
41 | EXPECT_FALSE(BP(1, 7) > BP(2, 7)); |
42 | EXPECT_FALSE(BP(1, 7) > BP(1, 4)); |
43 | EXPECT_FALSE(BP(5, 7) > BP(3, 4)); |
44 | EXPECT_FALSE(BP(1, 7) > BP(1, 7)); |
45 | EXPECT_FALSE(BP(1, 7) > BP(2, 14)); |
46 | EXPECT_TRUE(BP(4, 7) > BP(1, 2)); |
47 | EXPECT_TRUE(BP(4, 7) > BP(3, 7)); |
48 | |
49 | EXPECT_TRUE(BP(1, 7) <= BP(2, 7)); |
50 | EXPECT_TRUE(BP(1, 7) <= BP(1, 4)); |
51 | EXPECT_TRUE(BP(5, 7) <= BP(3, 4)); |
52 | EXPECT_TRUE(BP(1, 7) <= BP(1, 7)); |
53 | EXPECT_TRUE(BP(1, 7) <= BP(2, 14)); |
54 | EXPECT_FALSE(BP(4, 7) <= BP(1, 2)); |
55 | EXPECT_FALSE(BP(4, 7) <= BP(3, 7)); |
56 | |
57 | EXPECT_FALSE(BP(1, 7) >= BP(2, 7)); |
58 | EXPECT_FALSE(BP(1, 7) >= BP(1, 4)); |
59 | EXPECT_FALSE(BP(5, 7) >= BP(3, 4)); |
60 | EXPECT_TRUE(BP(1, 7) >= BP(1, 7)); |
61 | EXPECT_TRUE(BP(1, 7) >= BP(2, 14)); |
62 | EXPECT_TRUE(BP(4, 7) >= BP(1, 2)); |
63 | EXPECT_TRUE(BP(4, 7) >= BP(3, 7)); |
64 | |
65 | EXPECT_FALSE(BP(1, 7) == BP(2, 7)); |
66 | EXPECT_FALSE(BP(1, 7) == BP(1, 4)); |
67 | EXPECT_FALSE(BP(5, 7) == BP(3, 4)); |
68 | EXPECT_TRUE(BP(1, 7) == BP(1, 7)); |
69 | EXPECT_TRUE(BP(1, 7) == BP(2, 14)); |
70 | EXPECT_FALSE(BP(4, 7) == BP(1, 2)); |
71 | EXPECT_FALSE(BP(4, 7) == BP(3, 7)); |
72 | |
73 | EXPECT_TRUE(BP(1, 7) != BP(2, 7)); |
74 | EXPECT_TRUE(BP(1, 7) != BP(1, 4)); |
75 | EXPECT_TRUE(BP(5, 7) != BP(3, 4)); |
76 | EXPECT_FALSE(BP(1, 7) != BP(1, 7)); |
77 | EXPECT_FALSE(BP(1, 7) != BP(2, 14)); |
78 | EXPECT_TRUE(BP(4, 7) != BP(1, 2)); |
79 | EXPECT_TRUE(BP(4, 7) != BP(3, 7)); |
80 | |
81 | EXPECT_TRUE(BP(1, 7) == BP(2, 14)); |
82 | EXPECT_TRUE(BP(1, 7) == BP(3, 21)); |
83 | EXPECT_TRUE(BP(5, 7) == BP(25, 35)); |
84 | EXPECT_TRUE(BP(99999998, 100000000) < BP(99999999, 100000000)); |
85 | EXPECT_TRUE(BP(4, 8) == BP(400000000, 800000000)); |
86 | } |
87 | |
88 | TEST(BranchProbabilityTest, MoreOperators) { |
89 | BP A(4, 5); |
90 | BP B(4U << 29, 5U << 29); |
91 | BP C(3, 4); |
92 | |
93 | EXPECT_TRUE(A == B); |
94 | EXPECT_FALSE(A != B); |
95 | EXPECT_FALSE(A < B); |
96 | EXPECT_FALSE(A > B); |
97 | EXPECT_TRUE(A <= B); |
98 | EXPECT_TRUE(A >= B); |
99 | |
100 | EXPECT_FALSE(B == C); |
101 | EXPECT_TRUE(B != C); |
102 | EXPECT_FALSE(B < C); |
103 | EXPECT_TRUE(B > C); |
104 | EXPECT_FALSE(B <= C); |
105 | EXPECT_TRUE(B >= C); |
106 | |
107 | BP BigZero(0, UINT32_MAX); |
108 | BP BigOne(UINT32_MAX, UINT32_MAX); |
109 | EXPECT_FALSE(BigZero == BigOne); |
110 | EXPECT_TRUE(BigZero != BigOne); |
111 | EXPECT_TRUE(BigZero < BigOne); |
112 | EXPECT_FALSE(BigZero > BigOne); |
113 | EXPECT_TRUE(BigZero <= BigOne); |
114 | EXPECT_FALSE(BigZero >= BigOne); |
115 | } |
116 | |
117 | TEST(BranchProbabilityTest, ArithmeticOperators) { |
118 | BP Z(0, 1); |
119 | BP O(1, 1); |
120 | BP H(1, 2); |
121 | BP Q(1, 4); |
122 | BP Q3(3, 4); |
123 | |
124 | EXPECT_EQ(Z + O, O); |
125 | EXPECT_EQ(H + Z, H); |
126 | EXPECT_EQ(H + H, O); |
127 | EXPECT_EQ(Q + H, Q3); |
128 | EXPECT_EQ(Q + Q3, O); |
129 | EXPECT_EQ(H + Q3, O); |
130 | EXPECT_EQ(Q3 + Q3, O); |
131 | |
132 | EXPECT_EQ(Z - O, Z); |
133 | EXPECT_EQ(O - Z, O); |
134 | EXPECT_EQ(O - H, H); |
135 | EXPECT_EQ(O - Q, Q3); |
136 | EXPECT_EQ(Q3 - H, Q); |
137 | EXPECT_EQ(Q - H, Z); |
138 | EXPECT_EQ(Q - Q3, Z); |
139 | |
140 | EXPECT_EQ(Z * O, Z); |
141 | EXPECT_EQ(H * H, Q); |
142 | EXPECT_EQ(Q * O, Q); |
143 | EXPECT_EQ(O * O, O); |
144 | EXPECT_EQ(Z * Z, Z); |
145 | |
146 | EXPECT_EQ(Z * 3, Z); |
147 | EXPECT_EQ(Q * 3, Q3); |
148 | EXPECT_EQ(H * 3, O); |
149 | EXPECT_EQ(Q3 * 2, O); |
150 | EXPECT_EQ(O * UINT32_MAX, O); |
151 | |
152 | EXPECT_EQ(Z / 4, Z); |
153 | EXPECT_EQ(O / 4, Q); |
154 | EXPECT_EQ(Q3 / 3, Q); |
155 | EXPECT_EQ(H / 2, Q); |
156 | EXPECT_EQ(O / 2, H); |
157 | EXPECT_EQ(H / UINT32_MAX, Z); |
158 | |
159 | BP Min(1, 1u << 31); |
160 | |
161 | EXPECT_EQ(O / UINT32_MAX, Z); |
162 | EXPECT_EQ(Min * UINT32_MAX, O); |
163 | } |
164 | |
165 | TEST(BranchProbabilityTest, getCompl) { |
166 | EXPECT_EQ(BP(5, 7), BP(2, 7).getCompl()); |
167 | EXPECT_EQ(BP(2, 7), BP(5, 7).getCompl()); |
168 | EXPECT_EQ(BP::getZero(), BP(7, 7).getCompl()); |
169 | EXPECT_EQ(BP::getOne(), BP(0, 7).getCompl()); |
170 | } |
171 | |
172 | TEST(BranchProbabilityTest, scale) { |
173 | // Multiply by 1.0. |
174 | EXPECT_EQ(UINT64_MAX, BP(1, 1).scale(UINT64_MAX)); |
175 | EXPECT_EQ(UINT64_MAX, BP(7, 7).scale(UINT64_MAX)); |
176 | EXPECT_EQ(UINT32_MAX, BP(1, 1).scale(UINT32_MAX)); |
177 | EXPECT_EQ(UINT32_MAX, BP(7, 7).scale(UINT32_MAX)); |
178 | EXPECT_EQ(0u, BP(1, 1).scale(0)); |
179 | EXPECT_EQ(0u, BP(7, 7).scale(0)); |
180 | |
181 | // Multiply by 0.0. |
182 | EXPECT_EQ(0u, BP(0, 1).scale(UINT64_MAX)); |
183 | EXPECT_EQ(0u, BP(0, 1).scale(UINT64_MAX)); |
184 | EXPECT_EQ(0u, BP(0, 1).scale(0)); |
185 | |
186 | auto Two63 = UINT64_C(1) << 63; |
187 | auto Two31 = UINT64_C(1) << 31; |
188 | |
189 | // Multiply by 0.5. |
190 | EXPECT_EQ(Two63 - 1, BP(1, 2).scale(UINT64_MAX)); |
191 | |
192 | // Big fractions. |
193 | EXPECT_EQ(1u, BP(Two31, UINT32_MAX).scale(2)); |
194 | EXPECT_EQ(Two31, BP(Two31, UINT32_MAX).scale(Two31 * 2)); |
195 | EXPECT_EQ(9223372036854775807ULL, BP(Two31, UINT32_MAX).scale(UINT64_MAX)); |
196 | |
197 | // High precision. |
198 | EXPECT_EQ(UINT64_C(9223372045444710399), |
199 | BP(Two31 + 1, UINT32_MAX - 2).scale(UINT64_MAX)); |
200 | } |
201 | |
202 | TEST(BranchProbabilityTest, scaleByInverse) { |
203 | // Divide by 1.0. |
204 | EXPECT_EQ(UINT64_MAX, BP(1, 1).scaleByInverse(UINT64_MAX)); |
205 | EXPECT_EQ(UINT64_MAX, BP(7, 7).scaleByInverse(UINT64_MAX)); |
206 | EXPECT_EQ(UINT32_MAX, BP(1, 1).scaleByInverse(UINT32_MAX)); |
207 | EXPECT_EQ(UINT32_MAX, BP(7, 7).scaleByInverse(UINT32_MAX)); |
208 | EXPECT_EQ(0u, BP(1, 1).scaleByInverse(0)); |
209 | EXPECT_EQ(0u, BP(7, 7).scaleByInverse(0)); |
210 | |
211 | auto MAX_DENOMINATOR = BP::getDenominator(); |
212 | |
213 | // Divide by something very small. |
214 | EXPECT_EQ(UINT64_MAX, BP(1, UINT32_MAX).scaleByInverse(UINT64_MAX)); |
215 | EXPECT_EQ(uint64_t(UINT32_MAX) * MAX_DENOMINATOR, |
216 | BP(1, MAX_DENOMINATOR).scaleByInverse(UINT32_MAX)); |
217 | EXPECT_EQ(MAX_DENOMINATOR, BP(1, MAX_DENOMINATOR).scaleByInverse(1)); |
218 | |
219 | auto Two63 = UINT64_C(1) << 63; |
220 | auto Two31 = UINT64_C(1) << 31; |
221 | |
222 | // Divide by 0.5. |
223 | EXPECT_EQ(UINT64_MAX - 1, BP(1, 2).scaleByInverse(Two63 - 1)); |
224 | EXPECT_EQ(UINT64_MAX, BP(1, 2).scaleByInverse(Two63)); |
225 | |
226 | // Big fractions. |
227 | EXPECT_EQ(2u, BP(Two31, UINT32_MAX).scaleByInverse(1)); |
228 | EXPECT_EQ(2u, BP(Two31 - 1, UINT32_MAX).scaleByInverse(1)); |
229 | EXPECT_EQ(Two31 * 2, BP(Two31, UINT32_MAX).scaleByInverse(Two31)); |
230 | EXPECT_EQ(Two31 * 2, BP(Two31 - 1, UINT32_MAX).scaleByInverse(Two31)); |
231 | EXPECT_EQ(UINT64_MAX, BP(Two31, UINT32_MAX).scaleByInverse(Two63 + Two31)); |
232 | |
233 | // High precision. The exact answers to these are close to the successors of |
234 | // the floor. If we were rounding, these would round up. |
235 | EXPECT_EQ(UINT64_C(18446744060824649767), |
236 | BP(Two31 + 2, UINT32_MAX - 2) |
237 | .scaleByInverse(UINT64_C(9223372047592194056))); |
238 | EXPECT_EQ(UINT64_C(18446744060824649739), |
239 | BP(Two31 + 1, UINT32_MAX).scaleByInverse(Two63 + Two31)); |
240 | } |
241 | |
242 | TEST(BranchProbabilityTest, scaleBruteForce) { |
243 | struct { |
244 | uint64_t Num; |
245 | uint32_t Prob[2]; |
246 | uint64_t Result; |
247 | } Tests[] = { |
248 | // Data for scaling that results in <= 64 bit division. |
249 | { .Num: 0x1423e2a50ULL, .Prob: { 0x64819521, 0x7765dd13 }, .Result: 0x10f418888ULL }, |
250 | { .Num: 0x35ef14ceULL, .Prob: { 0x28ade3c7, 0x304532ae }, .Result: 0x2d73c33bULL }, |
251 | { .Num: 0xd03dbfbe24ULL, .Prob: { 0x790079, 0xe419f3 }, .Result: 0x6e776fc2c4ULL }, |
252 | { .Num: 0x21d67410bULL, .Prob: { 0x302a9dc2, 0x3ddb4442 }, .Result: 0x1a5948fd4ULL }, |
253 | { .Num: 0x8664aeadULL, .Prob: { 0x3d523513, 0x403523b1 }, .Result: 0x805a04cfULL }, |
254 | { .Num: 0x201db0cf4ULL, .Prob: { 0x35112a7b, 0x79fc0c74 }, .Result: 0xdf8b07f8ULL }, |
255 | { .Num: 0x13f1e4430aULL, .Prob: { 0x21c92bf, 0x21e63aae }, .Result: 0x13e0cba26ULL }, |
256 | { .Num: 0x16c83229ULL, .Prob: { 0x3793f66f, 0x53180dea }, .Result: 0xf3ce7b6ULL }, |
257 | { .Num: 0xc62415be8ULL, .Prob: { 0x9cc4a63, 0x4327ae9b }, .Result: 0x1ce8b71c1ULL }, |
258 | { .Num: 0x6fac5e434ULL, .Prob: { 0xe5f9170, 0x1115e10b }, .Result: 0x5df23dd4cULL }, |
259 | { .Num: 0x1929375f2ULL, .Prob: { 0x3a851375, 0x76c08456 }, .Result: 0xc662b083ULL }, |
260 | { .Num: 0x243c89db6ULL, .Prob: { 0x354ebfc0, 0x450ef197 }, .Result: 0x1bf8c1663ULL }, |
261 | { .Num: 0x310e9b31aULL, .Prob: { 0x1b1b8acf, 0x2d3629f0 }, .Result: 0x1d69c93f9ULL }, |
262 | { .Num: 0xa1fae921dULL, .Prob: { 0xa7a098c, 0x10469f44 }, .Result: 0x684413d6eULL }, |
263 | { .Num: 0xc1582d957ULL, .Prob: { 0x498e061, 0x59856bc }, .Result: 0x9edc5f4ecULL }, |
264 | { .Num: 0x57cfee75ULL, .Prob: { 0x1d061dc3, 0x7c8bfc17 }, .Result: 0x1476a220ULL }, |
265 | { .Num: 0x139220080ULL, .Prob: { 0x294a6c71, 0x2a2b07c9 }, .Result: 0x1329e1c75ULL }, |
266 | { .Num: 0x1665d353cULL, .Prob: { 0x7080db5, 0xde0d75c }, .Result: 0xb590d9faULL }, |
267 | { .Num: 0xe8f14541ULL, .Prob: { 0x5188e8b2, 0x736527ef }, .Result: 0xa4971be5ULL }, |
268 | { .Num: 0x2f4775f29ULL, .Prob: { 0x254ef0fe, 0x435fcf50 }, .Result: 0x1a2e449c1ULL }, |
269 | { .Num: 0x27b85d8d7ULL, .Prob: { 0x304c8220, 0x5de678f2 }, .Result: 0x146e3befbULL }, |
270 | { .Num: 0x1d362e36bULL, .Prob: { 0x36c85b12, 0x37a66f55 }, .Result: 0x1cc19b8e7ULL }, |
271 | { .Num: 0x155fd48c7ULL, .Prob: { 0xf5894d, 0x1256108 }, .Result: 0x11e383604ULL }, |
272 | { .Num: 0xb5db2d15ULL, .Prob: { 0x39bb26c5, 0x5bdcda3e }, .Result: 0x72499259ULL }, |
273 | { .Num: 0x153990298ULL, .Prob: { 0x48921c09, 0x706eb817 }, .Result: 0xdb3268e7ULL }, |
274 | { .Num: 0x28a7c3ed7ULL, .Prob: { 0x1f776fd7, 0x349f7a70 }, .Result: 0x184f73ae2ULL }, |
275 | { .Num: 0x724dbeabULL, .Prob: { 0x1bd149f5, 0x253a085e }, .Result: 0x5569c0b3ULL }, |
276 | { .Num: 0xd8f0c513ULL, .Prob: { 0x18c8cc4c, 0x1b72bad0 }, .Result: 0xc3e30642ULL }, |
277 | { .Num: 0x17ce3dcbULL, .Prob: { 0x1e4c6260, 0x233b359e }, .Result: 0x1478f4afULL }, |
278 | { .Num: 0x1ce036ce0ULL, .Prob: { 0x29e3c8af, 0x5318dd4a }, .Result: 0xe8e76195ULL }, |
279 | { .Num: 0x1473ae2aULL, .Prob: { 0x29b897ba, 0x2be29378 }, .Result: 0x13718185ULL }, |
280 | { .Num: 0x1dd41aa68ULL, .Prob: { 0x3d0a4441, 0x5a0e8f12 }, .Result: 0x1437b6bbfULL }, |
281 | { .Num: 0x1b49e4a53ULL, .Prob: { 0x3430c1fe, 0x5a204aed }, .Result: 0xfcd6852fULL }, |
282 | { .Num: 0x217941b19ULL, .Prob: { 0x12ced2bd, 0x21b68310 }, .Result: 0x12aca65b1ULL }, |
283 | { .Num: 0xac6a4dc8ULL, .Prob: { 0x3ed68da8, 0x6fdca34c }, .Result: 0x60da926dULL }, |
284 | { .Num: 0x1c503a4e7ULL, .Prob: { 0xfcbbd32, 0x11e48d17 }, .Result: 0x18fec7d37ULL }, |
285 | { .Num: 0x1c885855ULL, .Prob: { 0x213e919d, 0x25941897 }, .Result: 0x193de742ULL }, |
286 | { .Num: 0x29b9c168eULL, .Prob: { 0x2b644aea, 0x45725ee7 }, .Result: 0x1a122e5d4ULL }, |
287 | { .Num: 0x806a33f2ULL, .Prob: { 0x30a80a23, 0x5063733a }, .Result: 0x4db9a264ULL }, |
288 | { .Num: 0x282afc96bULL, .Prob: { 0x143ae554, 0x1a9863ff }, .Result: 0x1e8de5204ULL }, |
289 | // Data for scaling that results in > 64 bit division. |
290 | { .Num: 0x23ca5f2f672ca41cULL, .Prob: { 0xecbc641, 0x111373f7 }, .Result: 0x1f0301e5c76869c6ULL }, |
291 | { .Num: 0x5e4f2468142265e3ULL, .Prob: { 0x1ddf5837, 0x32189233 }, .Result: 0x383ca7bad6053ac9ULL }, |
292 | { .Num: 0x277a1a6f6b266bf6ULL, .Prob: { 0x415d81a8, 0x61eb5e1e }, .Result: 0x1a5a3e1d1c9e8540ULL }, |
293 | { .Num: 0x1bdbb49a237035cbULL, .Prob: { 0xea5bf17, 0x1d25ffb3 }, .Result: 0xdffc51c5cb51cf1ULL }, |
294 | { .Num: 0x2bce6d29b64fb8ULL, .Prob: { 0x3bfd5631, 0x7525c9bb }, .Result: 0x166ebedd9581fdULL }, |
295 | { .Num: 0x3a02116103df5013ULL, .Prob: { 0x2ee18a83, 0x3299aea8 }, .Result: 0x35be89227276f105ULL }, |
296 | { .Num: 0x7b5762390799b18cULL, .Prob: { 0x12f8e5b9, 0x2563bcd4 }, .Result: 0x3e960077695655a3ULL }, |
297 | { .Num: 0x69cfd72537021579ULL, .Prob: { 0x4c35f468, 0x6a40feee }, .Result: 0x4be4cb38695a4f30ULL }, |
298 | { .Num: 0x49dfdf835120f1c1ULL, .Prob: { 0x8cb3759, 0x559eb891 }, .Result: 0x79663f6e3c8d8f6ULL }, |
299 | { .Num: 0x74b5be5c27676381ULL, .Prob: { 0x47e4c5e0, 0x7c7b19ff }, .Result: 0x4367d2dfb22b3265ULL }, |
300 | { .Num: 0x4f50f97075e7f431ULL, .Prob: { 0x9a50a17, 0x11cd1185 }, .Result: 0x2af952b30374f382ULL }, |
301 | { .Num: 0x2f8b0d712e393be4ULL, .Prob: { 0x1487e386, 0x15aa356e }, .Result: 0x2d0df3649b2b19fcULL }, |
302 | { .Num: 0x224c1c75999d3deULL, .Prob: { 0x3b2df0ea, 0x4523b100 }, .Result: 0x1d5b481d160dd8bULL }, |
303 | { .Num: 0x2bcbcea22a399a76ULL, .Prob: { 0x28b58212, 0x48dd013e }, .Result: 0x187814d0610c8a56ULL }, |
304 | { .Num: 0x1dbfca91257cb2d1ULL, .Prob: { 0x1a8c04d9, 0x5e92502c }, .Result: 0x859cf7d19e83ad0ULL }, |
305 | { .Num: 0x7f20039b57cda935ULL, .Prob: { 0xeccf651, 0x323f476e }, .Result: 0x25720cd9054634bdULL }, |
306 | { .Num: 0x40512c6a586aa087ULL, .Prob: { 0x113b0423, 0x398c9eab }, .Result: 0x1341c03dbb662054ULL }, |
307 | { .Num: 0x63d802693f050a11ULL, .Prob: { 0xf50cdd6, 0xfce2a44 }, .Result: 0x60c0177b667a4feaULL }, |
308 | { .Num: 0x2d956b422838de77ULL, .Prob: { 0xb2d345b, 0x1321e557 }, .Result: 0x1aa0ed16b094575cULL }, |
309 | { .Num: 0x5a1cdf0c1657bc91ULL, .Prob: { 0x1d77bb0c, 0x1f991ff1 }, .Result: 0x54097ee9907290eaULL }, |
310 | { .Num: 0x3801b26d7e00176bULL, .Prob: { 0xeed25da, 0x1a819d8b }, .Result: 0x1f89e96a616b9abeULL }, |
311 | { .Num: 0x37655e74338e1e45ULL, .Prob: { 0x300e170a, 0x5a1595fe }, .Result: 0x1d8cfb55ff6a6dbcULL }, |
312 | { .Num: 0x7b38703f2a84e6ULL, .Prob: { 0x66d9053, 0xc79b6b9 }, .Result: 0x3f7d4c91b9afb9ULL }, |
313 | { .Num: 0x2245063c0acb3215ULL, .Prob: { 0x30ce2f5b, 0x610e7271 }, .Result: 0x113b916455fe2560ULL }, |
314 | { .Num: 0x6bc195877b7b8a7eULL, .Prob: { 0x392004aa, 0x4a24e60c }, .Result: 0x530594fabfc81cc3ULL }, |
315 | { .Num: 0x40a3fde23c7b43dbULL, .Prob: { 0x4e712195, 0x6553e56e }, .Result: 0x320a799bc205c78dULL }, |
316 | { .Num: 0x1d3dfc2866fbccbaULL, .Prob: { 0x5075b517, 0x5fc42245 }, .Result: 0x18917f00745cb781ULL }, |
317 | { .Num: 0x19aeb14045a61121ULL, .Prob: { 0x1bf6edec, 0x707e2f4b }, .Result: 0x6626672aa2ba10aULL }, |
318 | { .Num: 0x44ff90486c531e9fULL, .Prob: { 0x66598a, 0x8a90dc }, .Result: 0x32f6f2b097001598ULL }, |
319 | { .Num: 0x3f3e7121092c5bcbULL, .Prob: { 0x1c754df7, 0x5951a1b9 }, .Result: 0x14267f50d4971583ULL }, |
320 | { .Num: 0x60e2dafb7e50a67eULL, .Prob: { 0x4d96c66e, 0x65bd878d }, .Result: 0x49e317155d75e883ULL }, |
321 | { .Num: 0x656286667e0e6e29ULL, .Prob: { 0x9d971a2, 0xacda23b }, .Result: 0x5c6ee3159e1deac3ULL }, |
322 | { .Num: 0x1114e0974255d507ULL, .Prob: { 0x1c693, 0x2d6ff }, .Result: 0xaae42e4be5f9f8dULL }, |
323 | { .Num: 0x508c8baf3a70ff5aULL, .Prob: { 0x3b26b779, 0x6ad78745 }, .Result: 0x2c983876178ed5b1ULL }, |
324 | { .Num: 0x5b47bc666bf1f9cfULL, .Prob: { 0x10a87ed6, 0x187d358a }, .Result: 0x3e1767153bea720aULL }, |
325 | { .Num: 0x50954e3744460395ULL, .Prob: { 0x7a42263, 0xcdaa048 }, .Result: 0x2fe739f0944a023cULL }, |
326 | { .Num: 0x20020b406550dd8fULL, .Prob: { 0x3318539, 0x42eead0 }, .Result: 0x186f326307c0d985ULL }, |
327 | { .Num: 0x5bcb0b872439ffd5ULL, .Prob: { 0x6f61fb2, 0x9af7344 }, .Result: 0x41fa1e3c47f0f80dULL }, |
328 | { .Num: 0x7a670f365db87a53ULL, .Prob: { 0x417e102, 0x3bb54c67 }, .Result: 0x8642a551d0f41b0ULL }, |
329 | { .Num: 0x1ef0db1e7bab1cd0ULL, .Prob: { 0x2b60cf38, 0x4188f78f }, .Result: 0x147ae0d63fc0575aULL } |
330 | }; |
331 | |
332 | for (const auto &T : Tests) { |
333 | EXPECT_EQ(T.Result, BP(T.Prob[0], T.Prob[1]).scale(T.Num)); |
334 | } |
335 | } |
336 | |
337 | TEST(BranchProbabilityTest, NormalizeProbabilities) { |
338 | const auto UnknownProb = BranchProbability::getUnknown(); |
339 | { |
340 | SmallVector<BranchProbability, 2> Probs{{0, 1}, {0, 1}}; |
341 | BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end()); |
342 | EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator()); |
343 | EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator()); |
344 | } |
345 | { |
346 | SmallVector<BranchProbability, 2> Probs{{0, 1}, {1, 1}}; |
347 | BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end()); |
348 | EXPECT_EQ(0u, Probs[0].getNumerator()); |
349 | EXPECT_EQ(BranchProbability::getDenominator(), Probs[1].getNumerator()); |
350 | } |
351 | { |
352 | SmallVector<BranchProbability, 2> Probs{{1, 100}, {1, 100}}; |
353 | BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end()); |
354 | EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator()); |
355 | EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator()); |
356 | } |
357 | { |
358 | SmallVector<BranchProbability, 2> Probs{{1, 1}, {1, 1}}; |
359 | BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end()); |
360 | EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator()); |
361 | EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator()); |
362 | } |
363 | { |
364 | SmallVector<BranchProbability, 3> Probs{{1, 1}, {1, 1}, {1, 1}}; |
365 | BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end()); |
366 | EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
367 | Probs[0].getNumerator()); |
368 | EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
369 | Probs[1].getNumerator()); |
370 | EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
371 | Probs[2].getNumerator()); |
372 | } |
373 | { |
374 | SmallVector<BranchProbability, 2> Probs{{0, 1}, UnknownProb}; |
375 | BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end()); |
376 | EXPECT_EQ(0U, Probs[0].getNumerator()); |
377 | EXPECT_EQ(BranchProbability::getDenominator(), Probs[1].getNumerator()); |
378 | } |
379 | { |
380 | SmallVector<BranchProbability, 2> Probs{{1, 1}, UnknownProb}; |
381 | BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end()); |
382 | EXPECT_EQ(BranchProbability::getDenominator(), Probs[0].getNumerator()); |
383 | EXPECT_EQ(0U, Probs[1].getNumerator()); |
384 | } |
385 | { |
386 | SmallVector<BranchProbability, 2> Probs{{1, 2}, UnknownProb}; |
387 | BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end()); |
388 | EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[0].getNumerator()); |
389 | EXPECT_EQ(BranchProbability::getDenominator() / 2, Probs[1].getNumerator()); |
390 | } |
391 | { |
392 | SmallVector<BranchProbability, 4> Probs{ |
393 | {1, 2}, {1, 2}, {1, 2}, UnknownProb}; |
394 | BranchProbability::normalizeProbabilities(Begin: Probs.begin(), End: Probs.end()); |
395 | EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
396 | Probs[0].getNumerator()); |
397 | EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
398 | Probs[1].getNumerator()); |
399 | EXPECT_EQ(BranchProbability::getDenominator() / 3 + 1, |
400 | Probs[2].getNumerator()); |
401 | EXPECT_EQ(0U, Probs[3].getNumerator()); |
402 | } |
403 | } |
404 | |
405 | } |
406 | |