1 //===- llvm/unittest/Support/ScaledNumberTest.cpp - ScaledPair 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/ScaledNumber.h" 11 12 #include "llvm/Support/DataTypes.h" 13 #include "gtest/gtest.h" 14 15 using namespace llvm; 16 using namespace llvm::ScaledNumbers; 17 18 namespace { 19 20 template <class UIntT> struct ScaledPair { 21 UIntT D; 22 int S; 23 ScaledPair(const std::pair<UIntT, int16_t> &F) : D(F.first), S(F.second) {} 24 ScaledPair(UIntT D, int S) : D(D), S(S) {} 25 26 bool operator==(const ScaledPair<UIntT> &X) const { 27 return D == X.D && S == X.S; 28 } 29 }; 30 template <class UIntT> 31 bool operator==(const std::pair<UIntT, int16_t> &L, 32 const ScaledPair<UIntT> &R) { 33 return ScaledPair<UIntT>(L) == R; 34 } 35 template <class UIntT> 36 void PrintTo(const ScaledPair<UIntT> &F, ::std::ostream *os) { 37 *os << F.D << "*2^" << F.S; 38 } 39 40 typedef ScaledPair<uint32_t> SP32; 41 typedef ScaledPair<uint64_t> SP64; 42 43 TEST(ScaledNumberHelpersTest, getRounded) { 44 EXPECT_EQ(getRounded32(0, 0, false), SP32(0, 0)); 45 EXPECT_EQ(getRounded32(0, 0, true), SP32(1, 0)); 46 EXPECT_EQ(getRounded32(20, 21, true), SP32(21, 21)); 47 EXPECT_EQ(getRounded32(UINT32_MAX, 0, false), SP32(UINT32_MAX, 0)); 48 EXPECT_EQ(getRounded32(UINT32_MAX, 0, true), SP32(1 << 31, 1)); 49 50 EXPECT_EQ(getRounded64(0, 0, false), SP64(0, 0)); 51 EXPECT_EQ(getRounded64(0, 0, true), SP64(1, 0)); 52 EXPECT_EQ(getRounded64(20, 21, true), SP64(21, 21)); 53 EXPECT_EQ(getRounded64(UINT32_MAX, 0, false), SP64(UINT32_MAX, 0)); 54 EXPECT_EQ(getRounded64(UINT32_MAX, 0, true), SP64(UINT64_C(1) << 32, 0)); 55 EXPECT_EQ(getRounded64(UINT64_MAX, 0, false), SP64(UINT64_MAX, 0)); 56 EXPECT_EQ(getRounded64(UINT64_MAX, 0, true), SP64(UINT64_C(1) << 63, 1)); 57 } 58 59 TEST(FloatsTest, getAdjusted) { 60 const uint64_t Max32In64 = UINT32_MAX; 61 EXPECT_EQ(getAdjusted32(0), SP32(0, 0)); 62 EXPECT_EQ(getAdjusted32(0, 5), SP32(0, 5)); 63 EXPECT_EQ(getAdjusted32(UINT32_MAX), SP32(UINT32_MAX, 0)); 64 EXPECT_EQ(getAdjusted32(Max32In64 << 1), SP32(UINT32_MAX, 1)); 65 EXPECT_EQ(getAdjusted32(Max32In64 << 1, 1), SP32(UINT32_MAX, 2)); 66 EXPECT_EQ(getAdjusted32(Max32In64 << 31), SP32(UINT32_MAX, 31)); 67 EXPECT_EQ(getAdjusted32(Max32In64 << 32), SP32(UINT32_MAX, 32)); 68 EXPECT_EQ(getAdjusted32(Max32In64 + 1), SP32(1u << 31, 1)); 69 EXPECT_EQ(getAdjusted32(UINT64_MAX), SP32(1u << 31, 33)); 70 71 EXPECT_EQ(getAdjusted64(0), SP64(0, 0)); 72 EXPECT_EQ(getAdjusted64(0, 5), SP64(0, 5)); 73 EXPECT_EQ(getAdjusted64(UINT32_MAX), SP64(UINT32_MAX, 0)); 74 EXPECT_EQ(getAdjusted64(Max32In64 << 1), SP64(Max32In64 << 1, 0)); 75 EXPECT_EQ(getAdjusted64(Max32In64 << 1, 1), SP64(Max32In64 << 1, 1)); 76 EXPECT_EQ(getAdjusted64(Max32In64 << 31), SP64(Max32In64 << 31, 0)); 77 EXPECT_EQ(getAdjusted64(Max32In64 << 32), SP64(Max32In64 << 32, 0)); 78 EXPECT_EQ(getAdjusted64(Max32In64 + 1), SP64(Max32In64 + 1, 0)); 79 EXPECT_EQ(getAdjusted64(UINT64_MAX), SP64(UINT64_MAX, 0)); 80 } 81 82 TEST(PositiveFloatTest, getProduct) { 83 // Zero. 84 EXPECT_EQ(SP32(0, 0), getProduct32(0, 0)); 85 EXPECT_EQ(SP32(0, 0), getProduct32(0, 1)); 86 EXPECT_EQ(SP32(0, 0), getProduct32(0, 33)); 87 88 // Basic. 89 EXPECT_EQ(SP32(6, 0), getProduct32(2, 3)); 90 EXPECT_EQ(SP32(UINT16_MAX / 3 * UINT16_MAX / 5 * 2, 0), 91 getProduct32(UINT16_MAX / 3, UINT16_MAX / 5 * 2)); 92 93 // Overflow, no loss of precision. 94 // ==> 0xf00010 * 0x1001 95 // ==> 0xf00f00000 + 0x10010 96 // ==> 0xf00f10010 97 // ==> 0xf00f1001 * 2^4 98 EXPECT_EQ(SP32(0xf00f1001, 4), getProduct32(0xf00010, 0x1001)); 99 100 // Overflow, loss of precision, rounds down. 101 // ==> 0xf000070 * 0x1001 102 // ==> 0xf00f000000 + 0x70070 103 // ==> 0xf00f070070 104 // ==> 0xf00f0700 * 2^8 105 EXPECT_EQ(SP32(0xf00f0700, 8), getProduct32(0xf000070, 0x1001)); 106 107 // Overflow, loss of precision, rounds up. 108 // ==> 0xf000080 * 0x1001 109 // ==> 0xf00f000000 + 0x80080 110 // ==> 0xf00f080080 111 // ==> 0xf00f0801 * 2^8 112 EXPECT_EQ(SP32(0xf00f0801, 8), getProduct32(0xf000080, 0x1001)); 113 114 // Reverse operand order. 115 EXPECT_EQ(SP32(0, 0), getProduct32(1, 0)); 116 EXPECT_EQ(SP32(0, 0), getProduct32(33, 0)); 117 EXPECT_EQ(SP32(6, 0), getProduct32(3, 2)); 118 EXPECT_EQ(SP32(UINT16_MAX / 3 * UINT16_MAX / 5 * 2, 0), 119 getProduct32(UINT16_MAX / 5 * 2, UINT16_MAX / 3)); 120 EXPECT_EQ(SP32(0xf00f1001, 4), getProduct32(0x1001, 0xf00010)); 121 EXPECT_EQ(SP32(0xf00f0700, 8), getProduct32(0x1001, 0xf000070)); 122 EXPECT_EQ(SP32(0xf00f0801, 8), getProduct32(0x1001, 0xf000080)); 123 124 // Round to overflow. 125 EXPECT_EQ(SP64(UINT64_C(1) << 63, 64), 126 getProduct64(UINT64_C(10376293541461622786), 127 UINT64_C(16397105843297379211))); 128 129 // Big number with rounding. 130 EXPECT_EQ(SP64(UINT64_C(9223372036854775810), 64), 131 getProduct64(UINT64_C(18446744073709551556), 132 UINT64_C(9223372036854775840))); 133 } 134 135 TEST(PositiveFloatTest, Divide) { 136 // Zero. 137 EXPECT_EQ(SP32(0, 0), getQuotient32(0, 0)); 138 EXPECT_EQ(SP32(0, 0), getQuotient32(0, 1)); 139 EXPECT_EQ(SP32(0, 0), getQuotient32(0, 73)); 140 EXPECT_EQ(SP32(UINT32_MAX, INT16_MAX), getQuotient32(1, 0)); 141 EXPECT_EQ(SP32(UINT32_MAX, INT16_MAX), getQuotient32(6, 0)); 142 143 // Powers of two. 144 EXPECT_EQ(SP32(1u << 31, -31), getQuotient32(1, 1)); 145 EXPECT_EQ(SP32(1u << 31, -30), getQuotient32(2, 1)); 146 EXPECT_EQ(SP32(1u << 31, -33), getQuotient32(4, 16)); 147 EXPECT_EQ(SP32(7u << 29, -29), getQuotient32(7, 1)); 148 EXPECT_EQ(SP32(7u << 29, -30), getQuotient32(7, 2)); 149 EXPECT_EQ(SP32(7u << 29, -33), getQuotient32(7, 16)); 150 151 // Divide evenly. 152 EXPECT_EQ(SP32(3u << 30, -30), getQuotient32(9, 3)); 153 EXPECT_EQ(SP32(9u << 28, -28), getQuotient32(63, 7)); 154 155 // Divide unevenly. 156 EXPECT_EQ(SP32(0xaaaaaaab, -33), getQuotient32(1, 3)); 157 EXPECT_EQ(SP32(0xd5555555, -31), getQuotient32(5, 3)); 158 159 // 64-bit division is hard to test, since divide64 doesn't canonicalized its 160 // output. However, this is the algorithm the implementation uses: 161 // 162 // - Shift divisor right. 163 // - If we have 1 (power of 2), return early -- not canonicalized. 164 // - Shift dividend left. 165 // - 64-bit integer divide. 166 // - If there's a remainder, continue with long division. 167 // 168 // TODO: require less knowledge about the implementation in the test. 169 170 // Zero. 171 EXPECT_EQ(SP64(0, 0), getQuotient64(0, 0)); 172 EXPECT_EQ(SP64(0, 0), getQuotient64(0, 1)); 173 EXPECT_EQ(SP64(0, 0), getQuotient64(0, 73)); 174 EXPECT_EQ(SP64(UINT64_MAX, INT16_MAX), getQuotient64(1, 0)); 175 EXPECT_EQ(SP64(UINT64_MAX, INT16_MAX), getQuotient64(6, 0)); 176 177 // Powers of two. 178 EXPECT_EQ(SP64(1, 0), getQuotient64(1, 1)); 179 EXPECT_EQ(SP64(2, 0), getQuotient64(2, 1)); 180 EXPECT_EQ(SP64(4, -4), getQuotient64(4, 16)); 181 EXPECT_EQ(SP64(7, 0), getQuotient64(7, 1)); 182 EXPECT_EQ(SP64(7, -1), getQuotient64(7, 2)); 183 EXPECT_EQ(SP64(7, -4), getQuotient64(7, 16)); 184 185 // Divide evenly. 186 EXPECT_EQ(SP64(UINT64_C(3) << 60, -60), getQuotient64(9, 3)); 187 EXPECT_EQ(SP64(UINT64_C(9) << 58, -58), getQuotient64(63, 7)); 188 189 // Divide unevenly. 190 EXPECT_EQ(SP64(0xaaaaaaaaaaaaaaab, -65), getQuotient64(1, 3)); 191 EXPECT_EQ(SP64(0xd555555555555555, -63), getQuotient64(5, 3)); 192 } 193 194 } // end namespace 195