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 }