Support: Add BranchProbability::scale() and ::scaleByInverse()
[oota-llvm.git] / unittests / Support / BranchProbabilityTest.cpp
1 //===- unittest/Support/BranchProbabilityTest.cpp - BranchProbability tests -=//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "llvm/Support/BranchProbability.h"
11 #include "llvm/Support/raw_ostream.h"
12 #include "gtest/gtest.h"
13
14 using namespace llvm;
15
16 namespace llvm {
17 void PrintTo(const BranchProbability &P, ::std::ostream *os) {
18   *os << P.getNumerator() << "/" << P.getDenominator();
19 }
20 }
21 namespace {
22
23 typedef BranchProbability BP;
24 TEST(BranchProbabilityTest, Accessors) {
25   EXPECT_EQ(1u, BP(1, 7).getNumerator());
26   EXPECT_EQ(7u, BP(1, 7).getDenominator());
27   EXPECT_EQ(0u, BP::getZero().getNumerator());
28   EXPECT_EQ(1u, BP::getZero().getDenominator());
29   EXPECT_EQ(1u, BP::getOne().getNumerator());
30   EXPECT_EQ(1u, BP::getOne().getDenominator());
31 }
32
33 TEST(BranchProbabilityTest, Operators) {
34   EXPECT_TRUE(BP(1, 7) < BP(2, 7));
35   EXPECT_TRUE(BP(1, 7) < BP(1, 4));
36   EXPECT_TRUE(BP(5, 7) < BP(3, 4));
37   EXPECT_FALSE(BP(1, 7) < BP(1, 7));
38   EXPECT_FALSE(BP(1, 7) < BP(2, 14));
39   EXPECT_FALSE(BP(4, 7) < BP(1, 2));
40   EXPECT_FALSE(BP(4, 7) < BP(3, 7));
41
42   EXPECT_FALSE(BP(1, 7) > BP(2, 7));
43   EXPECT_FALSE(BP(1, 7) > BP(1, 4));
44   EXPECT_FALSE(BP(5, 7) > BP(3, 4));
45   EXPECT_FALSE(BP(1, 7) > BP(1, 7));
46   EXPECT_FALSE(BP(1, 7) > BP(2, 14));
47   EXPECT_TRUE(BP(4, 7) > BP(1, 2));
48   EXPECT_TRUE(BP(4, 7) > BP(3, 7));
49
50   EXPECT_TRUE(BP(1, 7) <= BP(2, 7));
51   EXPECT_TRUE(BP(1, 7) <= BP(1, 4));
52   EXPECT_TRUE(BP(5, 7) <= BP(3, 4));
53   EXPECT_TRUE(BP(1, 7) <= BP(1, 7));
54   EXPECT_TRUE(BP(1, 7) <= BP(2, 14));
55   EXPECT_FALSE(BP(4, 7) <= BP(1, 2));
56   EXPECT_FALSE(BP(4, 7) <= BP(3, 7));
57
58   EXPECT_FALSE(BP(1, 7) >= BP(2, 7));
59   EXPECT_FALSE(BP(1, 7) >= BP(1, 4));
60   EXPECT_FALSE(BP(5, 7) >= BP(3, 4));
61   EXPECT_TRUE(BP(1, 7) >= BP(1, 7));
62   EXPECT_TRUE(BP(1, 7) >= BP(2, 14));
63   EXPECT_TRUE(BP(4, 7) >= BP(1, 2));
64   EXPECT_TRUE(BP(4, 7) >= BP(3, 7));
65
66   EXPECT_FALSE(BP(1, 7) == BP(2, 7));
67   EXPECT_FALSE(BP(1, 7) == BP(1, 4));
68   EXPECT_FALSE(BP(5, 7) == BP(3, 4));
69   EXPECT_TRUE(BP(1, 7) == BP(1, 7));
70   EXPECT_TRUE(BP(1, 7) == BP(2, 14));
71   EXPECT_FALSE(BP(4, 7) == BP(1, 2));
72   EXPECT_FALSE(BP(4, 7) == BP(3, 7));
73
74   EXPECT_TRUE(BP(1, 7) != BP(2, 7));
75   EXPECT_TRUE(BP(1, 7) != BP(1, 4));
76   EXPECT_TRUE(BP(5, 7) != BP(3, 4));
77   EXPECT_FALSE(BP(1, 7) != BP(1, 7));
78   EXPECT_FALSE(BP(1, 7) != BP(2, 14));
79   EXPECT_TRUE(BP(4, 7) != BP(1, 2));
80   EXPECT_TRUE(BP(4, 7) != BP(3, 7));
81 }
82
83 TEST(BranchProbabilityTest, getCompl) {
84   EXPECT_EQ(BP(5, 7), BP(2, 7).getCompl());
85   EXPECT_EQ(BP(2, 7), BP(5, 7).getCompl());
86   EXPECT_EQ(BP::getZero(), BP(7, 7).getCompl());
87   EXPECT_EQ(BP::getOne(), BP(0, 7).getCompl());
88 }
89
90 TEST(BranchProbabilityTest, scale) {
91   // Multiply by 1.0.
92   EXPECT_EQ(UINT64_MAX, BP(1, 1).scale(UINT64_MAX));
93   EXPECT_EQ(UINT64_MAX, BP(7, 7).scale(UINT64_MAX));
94   EXPECT_EQ(UINT32_MAX, BP(1, 1).scale(UINT32_MAX));
95   EXPECT_EQ(UINT32_MAX, BP(7, 7).scale(UINT32_MAX));
96   EXPECT_EQ(0u, BP(1, 1).scale(0));
97   EXPECT_EQ(0u, BP(7, 7).scale(0));
98
99   // Multiply by 0.0.
100   EXPECT_EQ(0u, BP(0, 1).scale(UINT64_MAX));
101   EXPECT_EQ(0u, BP(0, 1).scale(UINT64_MAX));
102   EXPECT_EQ(0u, BP(0, 1).scale(0));
103
104   auto Two63 = UINT64_C(1) << 63;
105   auto Two31 = UINT64_C(1) << 31;
106
107   // Multiply by 0.5.
108   EXPECT_EQ(Two63 - 1, BP(1, 2).scale(UINT64_MAX));
109
110   // Big fractions.
111   EXPECT_EQ(1u, BP(Two31, UINT32_MAX).scale(2));
112   EXPECT_EQ(Two31, BP(Two31, UINT32_MAX).scale(Two31 * 2));
113   EXPECT_EQ(Two63 + Two31, BP(Two31, UINT32_MAX).scale(UINT64_MAX));
114
115   // High precision.
116   EXPECT_EQ(UINT64_C(9223372047592194055),
117             BP(Two31 + 1, UINT32_MAX - 2).scale(UINT64_MAX));
118 }
119
120 TEST(BranchProbabilityTest, scaleByInverse) {
121   // Divide by 1.0.
122   EXPECT_EQ(UINT64_MAX, BP(1, 1).scaleByInverse(UINT64_MAX));
123   EXPECT_EQ(UINT64_MAX, BP(7, 7).scaleByInverse(UINT64_MAX));
124   EXPECT_EQ(UINT32_MAX, BP(1, 1).scaleByInverse(UINT32_MAX));
125   EXPECT_EQ(UINT32_MAX, BP(7, 7).scaleByInverse(UINT32_MAX));
126   EXPECT_EQ(0u, BP(1, 1).scaleByInverse(0));
127   EXPECT_EQ(0u, BP(7, 7).scaleByInverse(0));
128
129   // Divide by something very small.
130   EXPECT_EQ(UINT64_MAX, BP(1, UINT32_MAX).scaleByInverse(UINT64_MAX));
131   EXPECT_EQ(uint64_t(UINT32_MAX) * UINT32_MAX,
132             BP(1, UINT32_MAX).scaleByInverse(UINT32_MAX));
133   EXPECT_EQ(UINT32_MAX, BP(1, UINT32_MAX).scaleByInverse(1));
134
135   auto Two63 = UINT64_C(1) << 63;
136   auto Two31 = UINT64_C(1) << 31;
137
138   // Divide by 0.5.
139   EXPECT_EQ(UINT64_MAX - 1, BP(1, 2).scaleByInverse(Two63 - 1));
140   EXPECT_EQ(UINT64_MAX, BP(1, 2).scaleByInverse(Two63));
141
142   // Big fractions.
143   EXPECT_EQ(1u, BP(Two31, UINT32_MAX).scaleByInverse(1));
144   EXPECT_EQ(2u, BP(Two31 - 1, UINT32_MAX).scaleByInverse(1));
145   EXPECT_EQ(Two31 * 2 - 1, BP(Two31, UINT32_MAX).scaleByInverse(Two31));
146   EXPECT_EQ(Two31 * 2 + 1, BP(Two31 - 1, UINT32_MAX).scaleByInverse(Two31));
147   EXPECT_EQ(UINT64_MAX, BP(Two31, UINT32_MAX).scaleByInverse(Two63 + Two31));
148
149   // High precision.  The exact answers to these are close to the successors of
150   // the floor.  If we were rounding, these would round up.
151   EXPECT_EQ(UINT64_C(18446744065119617030),
152             BP(Two31 + 2, UINT32_MAX - 2)
153                 .scaleByInverse(UINT64_C(9223372047592194055)));
154   EXPECT_EQ(UINT64_C(18446744065119617026),
155             BP(Two31 + 1, UINT32_MAX).scaleByInverse(Two63 + Two31));
156 }
157
158 }