unittests/Support/ScaledNumberTest.cpp

   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(ScaledNumberHelpersTest, 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(ScaledNumberHelpersTest, 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(ScaledNumberHelpersTest, getQuotient) {
 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 TEST(ScaledNumberHelpersTest, getLg) {
 195   EXPECT_EQ(0, getLg(UINT32_C(1), 0));
 196   EXPECT_EQ(1, getLg(UINT32_C(1), 1));
 197   EXPECT_EQ(1, getLg(UINT32_C(2), 0));
 198   EXPECT_EQ(3, getLg(UINT32_C(1), 3));
 199   EXPECT_EQ(3, getLg(UINT32_C(7), 0));
 200   EXPECT_EQ(3, getLg(UINT32_C(8), 0));
 201   EXPECT_EQ(3, getLg(UINT32_C(9), 0));
 202   EXPECT_EQ(3, getLg(UINT32_C(64), -3));
 203   EXPECT_EQ(31, getLg((UINT32_MAX >> 1) + 2, 0));
 204   EXPECT_EQ(32, getLg(UINT32_MAX, 0));
 205   EXPECT_EQ(-1, getLg(UINT32_C(1), -1));
 206   EXPECT_EQ(-1, getLg(UINT32_C(2), -2));
 207   EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), -1));
 208   EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), 0));
 209   EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), 1));
 210
 211   EXPECT_EQ(0, getLg(UINT64_C(1), 0));
 212   EXPECT_EQ(1, getLg(UINT64_C(1), 1));
 213   EXPECT_EQ(1, getLg(UINT64_C(2), 0));
 214   EXPECT_EQ(3, getLg(UINT64_C(1), 3));
 215   EXPECT_EQ(3, getLg(UINT64_C(7), 0));
 216   EXPECT_EQ(3, getLg(UINT64_C(8), 0));
 217   EXPECT_EQ(3, getLg(UINT64_C(9), 0));
 218   EXPECT_EQ(3, getLg(UINT64_C(64), -3));
 219   EXPECT_EQ(63, getLg((UINT64_MAX >> 1) + 2, 0));
 220   EXPECT_EQ(64, getLg(UINT64_MAX, 0));
 221   EXPECT_EQ(-1, getLg(UINT64_C(1), -1));
 222   EXPECT_EQ(-1, getLg(UINT64_C(2), -2));
 223   EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), -1));
 224   EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), 0));
 225   EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), 1));
 226 }
 227
 228 TEST(ScaledNumberHelpersTest, getLgFloor) {
 229   EXPECT_EQ(0, getLgFloor(UINT32_C(1), 0));
 230   EXPECT_EQ(1, getLgFloor(UINT32_C(1), 1));
 231   EXPECT_EQ(1, getLgFloor(UINT32_C(2), 0));
 232   EXPECT_EQ(2, getLgFloor(UINT32_C(7), 0));
 233   EXPECT_EQ(3, getLgFloor(UINT32_C(1), 3));
 234   EXPECT_EQ(3, getLgFloor(UINT32_C(8), 0));
 235   EXPECT_EQ(3, getLgFloor(UINT32_C(9), 0));
 236   EXPECT_EQ(3, getLgFloor(UINT32_C(64), -3));
 237   EXPECT_EQ(31, getLgFloor((UINT32_MAX >> 1) + 2, 0));
 238   EXPECT_EQ(31, getLgFloor(UINT32_MAX, 0));
 239   EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), -1));
 240   EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), 0));
 241   EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), 1));
 242
 243   EXPECT_EQ(0, getLgFloor(UINT64_C(1), 0));
 244   EXPECT_EQ(1, getLgFloor(UINT64_C(1), 1));
 245   EXPECT_EQ(1, getLgFloor(UINT64_C(2), 0));
 246   EXPECT_EQ(2, getLgFloor(UINT64_C(7), 0));
 247   EXPECT_EQ(3, getLgFloor(UINT64_C(1), 3));
 248   EXPECT_EQ(3, getLgFloor(UINT64_C(8), 0));
 249   EXPECT_EQ(3, getLgFloor(UINT64_C(9), 0));
 250   EXPECT_EQ(3, getLgFloor(UINT64_C(64), -3));
 251   EXPECT_EQ(63, getLgFloor((UINT64_MAX >> 1) + 2, 0));
 252   EXPECT_EQ(63, getLgFloor(UINT64_MAX, 0));
 253   EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), -1));
 254   EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), 0));
 255   EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), 1));
 256 }
 257
 258 TEST(ScaledNumberHelpersTest, getLgCeiling) {
 259   EXPECT_EQ(0, getLgCeiling(UINT32_C(1), 0));
 260   EXPECT_EQ(1, getLgCeiling(UINT32_C(1), 1));
 261   EXPECT_EQ(1, getLgCeiling(UINT32_C(2), 0));
 262   EXPECT_EQ(3, getLgCeiling(UINT32_C(1), 3));
 263   EXPECT_EQ(3, getLgCeiling(UINT32_C(7), 0));
 264   EXPECT_EQ(3, getLgCeiling(UINT32_C(8), 0));
 265   EXPECT_EQ(3, getLgCeiling(UINT32_C(64), -3));
 266   EXPECT_EQ(4, getLgCeiling(UINT32_C(9), 0));
 267   EXPECT_EQ(32, getLgCeiling(UINT32_MAX, 0));
 268   EXPECT_EQ(32, getLgCeiling((UINT32_MAX >> 1) + 2, 0));
 269   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), -1));
 270   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), 0));
 271   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), 1));
 272
 273   EXPECT_EQ(0, getLgCeiling(UINT64_C(1), 0));
 274   EXPECT_EQ(1, getLgCeiling(UINT64_C(1), 1));
 275   EXPECT_EQ(1, getLgCeiling(UINT64_C(2), 0));
 276   EXPECT_EQ(3, getLgCeiling(UINT64_C(1), 3));
 277   EXPECT_EQ(3, getLgCeiling(UINT64_C(7), 0));
 278   EXPECT_EQ(3, getLgCeiling(UINT64_C(8), 0));
 279   EXPECT_EQ(3, getLgCeiling(UINT64_C(64), -3));
 280   EXPECT_EQ(4, getLgCeiling(UINT64_C(9), 0));
 281   EXPECT_EQ(64, getLgCeiling((UINT64_MAX >> 1) + 2, 0));
 282   EXPECT_EQ(64, getLgCeiling(UINT64_MAX, 0));
 283   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), -1));
 284   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), 0));
 285   EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), 1));
 286 }
 287
 288 } // end namespace