Support: Write ScaledNumber::getQuotient() and getProduct()

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211409 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 314 insertions, 136 deletions

diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
index 264aff3725..df4ebcad33 100644
--- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h
+++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
@@ -77,9 +77,6 @@ public:
     return Lg.first + (Lg.second < 0);
   }
 
-  static std::pair<uint64_t, int16_t> divide64(uint64_t L, uint64_t R);
-  static std::pair<uint64_t, int16_t> multiply64(uint64_t L, uint64_t R);
-
   static int compare(uint64_t L, uint64_t R, int Shift) {
     assert(Shift >= 0);
     assert(Shift < 64);
@@ -315,8 +312,12 @@ public:
   UnsignedFloat inverse() const { return UnsignedFloat(*this).invert(); }
 
 private:
-  static UnsignedFloat getProduct(DigitsType L, DigitsType R);
-  static UnsignedFloat getQuotient(DigitsType Dividend, DigitsType Divisor);
+  static UnsignedFloat getProduct(DigitsType LHS, DigitsType RHS) {
+    return ScaledNumbers::getProduct(LHS, RHS);
+  }
+  static UnsignedFloat getQuotient(DigitsType Dividend, DigitsType Divisor) {
+    return ScaledNumbers::getQuotient(Dividend, Divisor);
+  }
 
   std::pair<int32_t, int> lgImpl() const;
   static int countLeadingZerosWidth(DigitsType Digits) {
@@ -400,46 +401,6 @@ uint64_t UnsignedFloat<DigitsT>::scale(uint64_t N) const {
 }
 
 template <class DigitsT>
-UnsignedFloat<DigitsT> UnsignedFloat<DigitsT>::getProduct(DigitsType L,
-                                                          DigitsType R) {
-  // Check for zero.
-  if (!L || !R)
-    return getZero();
-
-  // Check for numbers that we can compute with 64-bit math.
-  if (Width <= 32 || (L <= UINT32_MAX && R <= UINT32_MAX))
-    return adjustToWidth(uint64_t(L) * uint64_t(R), 0);
-
-  // Do the full thing.
-  return UnsignedFloat(multiply64(L, R));
-}
-template <class DigitsT>
-UnsignedFloat<DigitsT> UnsignedFloat<DigitsT>::getQuotient(DigitsType Dividend,
-                                                           DigitsType Divisor) {
-  // Check for zero.
-  if (!Dividend)
-    return getZero();
-  if (!Divisor)
-    return getLargest();
-
-  if (Width == 64)
-    return UnsignedFloat(divide64(Dividend, Divisor));
-
-  // We can compute this with 64-bit math.
-  int Shift = countLeadingZeros64(Dividend);
-  uint64_t Shifted = uint64_t(Dividend) << Shift;
-  uint64_t Quotient = Shifted / Divisor;
-
-  // If Quotient needs to be shifted, then adjustToWidth will round.
-  if (Quotient > DigitsLimits::max())
-    return adjustToWidth(Quotient, -Shift);
-
-  // Round based on the value of the next bit.
-  return getRounded(UnsignedFloat(Quotient, -Shift),
-                    Shifted % Divisor >= getHalf(Divisor));
-}
-
-template <class DigitsT>
 template <class IntT>
 IntT UnsignedFloat<DigitsT>::toInt() const {
   typedef std::numeric_limits<IntT> Limits;
diff --git a/include/llvm/Support/ScaledNumber.h b/include/llvm/Support/ScaledNumber.h
index 8b7c5d0c4a..6789b89f7e 100644
--- a/include/llvm/Support/ScaledNumber.h
+++ b/include/llvm/Support/ScaledNumber.h
@@ -95,6 +95,82 @@ inline std::pair<uint64_t, int16_t> getAdjusted64(uint64_t Digits,
   return getAdjusted<uint64_t>(Digits, Scale);
 }
 
+/// \brief Multiply two 64-bit integers to create a 64-bit scaled number.
+///
+/// Implemented with four 64-bit integer multiplies.
+std::pair<uint64_t, int16_t> multiply64(uint64_t LHS, uint64_t RHS);
+
+/// \brief Multiply two 32-bit integers to create a 32-bit scaled number.
+///
+/// Implemented with one 64-bit integer multiply.
+template <class DigitsT>
+inline std::pair<DigitsT, int16_t> getProduct(DigitsT LHS, DigitsT RHS) {
+  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
+
+  if (getWidth<DigitsT>() <= 32 || (LHS <= UINT32_MAX && RHS <= UINT32_MAX))
+    return getAdjusted<DigitsT>(uint64_t(LHS) * RHS);
+
+  return multiply64(LHS, RHS);
+}
+
+/// \brief Convenience helper for 32-bit product.
+inline std::pair<uint32_t, int16_t> getProduct32(uint32_t LHS, uint32_t RHS) {
+  return getProduct(LHS, RHS);
+}
+
+/// \brief Convenience helper for 64-bit product.
+inline std::pair<uint64_t, int16_t> getProduct64(uint64_t LHS, uint64_t RHS) {
+  return getProduct(LHS, RHS);
+}
+
+/// \brief Divide two 64-bit integers to create a 64-bit scaled number.
+///
+/// Implemented with long division.
+///
+/// \pre \c Dividend and \c Divisor are non-zero.
+std::pair<uint64_t, int16_t> divide64(uint64_t Dividend, uint64_t Divisor);
+
+/// \brief Divide two 32-bit integers to create a 32-bit scaled number.
+///
+/// Implemented with one 64-bit integer divide/remainder pair.
+///
+/// \pre \c Dividend and \c Divisor are non-zero.
+std::pair<uint32_t, int16_t> divide32(uint32_t Dividend, uint32_t Divisor);
+
+/// \brief Divide two 32-bit numbers to create a 32-bit scaled number.
+///
+/// Implemented with one 64-bit integer divide/remainder pair.
+///
+/// Returns \c (DigitsT_MAX, INT16_MAX) for divide-by-zero (0 for 0/0).
+template <class DigitsT>
+std::pair<DigitsT, int16_t> getQuotient(DigitsT Dividend, DigitsT Divisor) {
+  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
+  static_assert(sizeof(DigitsT) == 4 || sizeof(DigitsT) == 8,
+                "expected 32-bit or 64-bit digits");
+
+  // Check for zero.
+  if (!Dividend)
+    return std::make_pair(0, 0);
+  if (!Divisor)
+    return std::make_pair(std::numeric_limits<DigitsT>::max(), INT16_MAX);
+
+  if (getWidth<DigitsT>() == 64)
+    return divide64(Dividend, Divisor);
+  return divide32(Dividend, Divisor);
+}
+
+/// \brief Convenience helper for 32-bit quotient.
+inline std::pair<uint32_t, int16_t> getQuotient32(uint32_t Dividend,
+                                                  uint32_t Divisor) {
+  return getQuotient(Dividend, Divisor);
+}
+
+/// \brief Convenience helper for 64-bit quotient.
+inline std::pair<uint64_t, int16_t> getQuotient64(uint64_t Dividend,
+                                                  uint64_t Divisor) {
+  return getQuotient(Dividend, Divisor);
+}
+
 } // end namespace ScaledNumbers
 } // end namespace llvm
 
diff --git a/lib/Analysis/BlockFrequencyInfoImpl.cpp b/lib/Analysis/BlockFrequencyInfoImpl.cpp
index 87d93a4bd5..edf1eca45c 100644
--- a/lib/Analysis/BlockFrequencyInfoImpl.cpp
+++ b/lib/Analysis/BlockFrequencyInfoImpl.cpp
@@ -216,97 +216,6 @@ void UnsignedFloatBase::dump(uint64_t D, int16_t E, int Width) {
                                 << "]";
 }
 
-static std::pair<uint64_t, int16_t>
-getRoundedFloat(uint64_t N, bool ShouldRound, int64_t Shift) {
-  if (ShouldRound)
-    if (!++N)
-      // Rounding caused an overflow.
-      return std::make_pair(UINT64_C(1), Shift + 64);
-  return std::make_pair(N, Shift);
-}
-
-std::pair<uint64_t, int16_t> UnsignedFloatBase::divide64(uint64_t Dividend,
-                                                         uint64_t Divisor) {
-  // Input should be sanitized.
-  assert(Divisor);
-  assert(Dividend);
-
-  // Minimize size of divisor.
-  int16_t Shift = 0;
-  if (int Zeros = countTrailingZeros(Divisor)) {
-    Shift -= Zeros;
-    Divisor >>= Zeros;
-  }
-
-  // Check for powers of two.
-  if (Divisor == 1)
-    return std::make_pair(Dividend, Shift);
-
-  // Maximize size of dividend.
-  if (int Zeros = countLeadingZeros64(Dividend)) {
-    Shift -= Zeros;
-    Dividend <<= Zeros;
-  }
-
-  // Start with the result of a divide.
-  uint64_t Quotient = Dividend / Divisor;
-  Dividend %= Divisor;
-
-  // Continue building the quotient with long division.
-  //
-  // TODO: continue with largers digits.
-  while (!(Quotient >> 63) && Dividend) {
-    // Shift Dividend, and check for overflow.
-    bool IsOverflow = Dividend >> 63;
-    Dividend <<= 1;
-    --Shift;
-
-    // Divide.
-    bool DoesDivide = IsOverflow || Divisor <= Dividend;
-    Quotient = (Quotient << 1) | uint64_t(DoesDivide);
-    Dividend -= DoesDivide ? Divisor : 0;
-  }
-
-  // Round.
-  if (Dividend >= getHalf(Divisor))
-    if (!++Quotient)
-      // Rounding caused an overflow in Quotient.
-      return std::make_pair(UINT64_C(1), Shift + 64);
-
-  return getRoundedFloat(Quotient, Dividend >= getHalf(Divisor), Shift);
-}
-
-std::pair<uint64_t, int16_t> UnsignedFloatBase::multiply64(uint64_t L,
-                                                           uint64_t R) {
-  // Separate into two 32-bit digits (U.L).
-  uint64_t UL = L >> 32, LL = L & UINT32_MAX, UR = R >> 32, LR = R & UINT32_MAX;
-
-  // Compute cross products.
-  uint64_t P1 = UL * UR, P2 = UL * LR, P3 = LL * UR, P4 = LL * LR;
-
-  // Sum into two 64-bit digits.
-  uint64_t Upper = P1, Lower = P4;
-  auto addWithCarry = [&](uint64_t N) {
-    uint64_t NewLower = Lower + (N << 32);
-    Upper += (N >> 32) + (NewLower < Lower);
-    Lower = NewLower;
-  };
-  addWithCarry(P2);
-  addWithCarry(P3);
-
-  // Check whether the upper digit is empty.
-  if (!Upper)
-    return std::make_pair(Lower, 0);
-
-  // Shift as little as possible to maximize precision.
-  unsigned LeadingZeros = countLeadingZeros64(Upper);
-  int16_t Shift = 64 - LeadingZeros;
-  if (LeadingZeros)
-    Upper = Upper << LeadingZeros | Lower >> Shift;
-  bool ShouldRound = Shift && (Lower & UINT64_C(1) << (Shift - 1));
-  return getRoundedFloat(Upper, ShouldRound, Shift);
-}
-
 //===----------------------------------------------------------------------===//
 //
 // BlockMass implementation.
diff --git a/lib/Support/CMakeLists.txt b/lib/Support/CMakeLists.txt
index 2438d729d8..354e2003b5 100644
--- a/lib/Support/CMakeLists.txt
+++ b/lib/Support/CMakeLists.txt
@@ -42,6 +42,7 @@ add_llvm_library(LLVMSupport
   PluginLoader.cpp
   PrettyStackTrace.cpp
   Regex.cpp
+  ScaledNumber.cpp
   SmallPtrSet.cpp
   SmallVector.cpp
   SourceMgr.cpp
diff --git a/lib/Support/ScaledNumber.cpp b/lib/Support/ScaledNumber.cpp
new file mode 100644
index 0000000000..e7531744b6
--- /dev/null
+++ b/lib/Support/ScaledNumber.cpp
@@ -0,0 +1,119 @@
+//==- lib/Support/ScaledNumber.cpp - Support for scaled numbers -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of some scaled number algorithms.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/ScaledNumber.h"
+
+using namespace llvm;
+using namespace llvm::ScaledNumbers;
+
+std::pair<uint64_t, int16_t> ScaledNumbers::multiply64(uint64_t LHS,
+                                                       uint64_t RHS) {
+  // Separate into two 32-bit digits (U.L).
+  auto getU = [](uint64_t N) { return N >> 32; };
+  auto getL = [](uint64_t N) { return N & UINT32_MAX; };
+  uint64_t UL = getU(LHS), LL = getL(LHS), UR = getU(RHS), LR = getL(RHS);
+
+  // Compute cross products.
+  uint64_t P1 = UL * UR, P2 = UL * LR, P3 = LL * UR, P4 = LL * LR;
+
+  // Sum into two 64-bit digits.
+  uint64_t Upper = P1, Lower = P4;
+  auto addWithCarry = [&](uint64_t N) {
+    uint64_t NewLower = Lower + (getL(N) << 32);
+    Upper += getU(N) + (NewLower < Lower);
+    Lower = NewLower;
+  };
+  addWithCarry(P2);
+  addWithCarry(P3);
+
+  // Check whether the upper digit is empty.
+  if (!Upper)
+    return std::make_pair(Lower, 0);
+
+  // Shift as little as possible to maximize precision.
+  unsigned LeadingZeros = countLeadingZeros(Upper);
+  int Shift = 64 - LeadingZeros;
+  if (LeadingZeros)
+    Upper = Upper << LeadingZeros | Lower >> Shift;
+  return getRounded(Upper, Shift,
+                    Shift && (Lower & UINT64_C(1) << (Shift - 1)));
+}
+
+static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
+
+std::pair<uint32_t, int16_t> ScaledNumbers::divide32(uint32_t Dividend,
+                                                     uint32_t Divisor) {
+  assert(Dividend && "expected non-zero dividend");
+  assert(Divisor && "expected non-zero divisor");
+
+  // Use 64-bit math and canonicalize the dividend to gain precision.
+  uint64_t Dividend64 = Dividend;
+  int Shift = 0;
+  if (int Zeros = countLeadingZeros(Dividend64)) {
+    Shift -= Zeros;
+    Dividend64 <<= Zeros;
+  }
+  uint64_t Quotient = Dividend64 / Divisor;
+  uint64_t Remainder = Dividend64 % Divisor;
+
+  // If Quotient needs to be shifted, leave the rounding to getAdjusted().
+  if (Quotient > UINT32_MAX)
+    return getAdjusted<uint32_t>(Quotient, Shift);
+
+  // Round based on the value of the next bit.
+  return getRounded<uint32_t>(Quotient, Shift, Remainder >= getHalf(Divisor));
+}
+
+std::pair<uint64_t, int16_t> ScaledNumbers::divide64(uint64_t Dividend,
+                                                     uint64_t Divisor) {
+  assert(Dividend && "expected non-zero dividend");
+  assert(Divisor && "expected non-zero divisor");
+
+  // Minimize size of divisor.
+  int Shift = 0;
+  if (int Zeros = countTrailingZeros(Divisor)) {
+    Shift -= Zeros;
+    Divisor >>= Zeros;
+  }
+
+  // Check for powers of two.
+  if (Divisor == 1)
+    return std::make_pair(Dividend, Shift);
+
+  // Maximize size of dividend.
+  if (int Zeros = countLeadingZeros(Dividend)) {
+    Shift -= Zeros;
+    Dividend <<= Zeros;
+  }
+
+  // Start with the result of a divide.
+  uint64_t Quotient = Dividend / Divisor;
+  Dividend %= Divisor;
+
+  // Continue building the quotient with long division.
+  while (!(Quotient >> 63) && Dividend) {
+    // Shift Dividend and check for overflow.
+    bool IsOverflow = Dividend >> 63;
+    Dividend <<= 1;
+    --Shift;
+
+    // Get the next bit of Quotient.
+    Quotient <<= 1;
+    if (IsOverflow || Divisor <= Dividend) {
+      Quotient |= 1;
+      Dividend -= Divisor;
+    }
+  }
+
+  return getRounded(Quotient, Shift, Dividend >= getHalf(Divisor));
+}
diff --git a/unittests/Support/ScaledNumberTest.cpp b/unittests/Support/ScaledNumberTest.cpp
index e6d24d4512..6f7cc2a14b 100644
--- a/unittests/Support/ScaledNumberTest.cpp
+++ b/unittests/Support/ScaledNumberTest.cpp
@@ -79,4 +79,116 @@ TEST(FloatsTest, getAdjusted) {
   EXPECT_EQ(getAdjusted64(UINT64_MAX), SP64(UINT64_MAX, 0));
 }
 
+TEST(PositiveFloatTest, getProduct) {
+  // Zero.
+  EXPECT_EQ(SP32(0, 0), getProduct32(0, 0));
+  EXPECT_EQ(SP32(0, 0), getProduct32(0, 1));
+  EXPECT_EQ(SP32(0, 0), getProduct32(0, 33));
+
+  // Basic.
+  EXPECT_EQ(SP32(6, 0), getProduct32(2, 3));
+  EXPECT_EQ(SP32(UINT16_MAX / 3 * UINT16_MAX / 5 * 2, 0),
+            getProduct32(UINT16_MAX / 3, UINT16_MAX / 5 * 2));
+
+  // Overflow, no loss of precision.
+  // ==> 0xf00010 * 0x1001
+  // ==> 0xf00f00000 + 0x10010
+  // ==> 0xf00f10010
+  // ==> 0xf00f1001 * 2^4
+  EXPECT_EQ(SP32(0xf00f1001, 4), getProduct32(0xf00010, 0x1001));
+
+  // Overflow, loss of precision, rounds down.
+  // ==> 0xf000070 * 0x1001
+  // ==> 0xf00f000000 + 0x70070
+  // ==> 0xf00f070070
+  // ==> 0xf00f0700 * 2^8
+  EXPECT_EQ(SP32(0xf00f0700, 8), getProduct32(0xf000070, 0x1001));
+
+  // Overflow, loss of precision, rounds up.
+  // ==> 0xf000080 * 0x1001
+  // ==> 0xf00f000000 + 0x80080
+  // ==> 0xf00f080080
+  // ==> 0xf00f0801 * 2^8
+  EXPECT_EQ(SP32(0xf00f0801, 8), getProduct32(0xf000080, 0x1001));
+
+  // Reverse operand order.
+  EXPECT_EQ(SP32(0, 0), getProduct32(1, 0));
+  EXPECT_EQ(SP32(0, 0), getProduct32(33, 0));
+  EXPECT_EQ(SP32(6, 0), getProduct32(3, 2));
+  EXPECT_EQ(SP32(UINT16_MAX / 3 * UINT16_MAX / 5 * 2, 0),
+            getProduct32(UINT16_MAX / 5 * 2, UINT16_MAX / 3));
+  EXPECT_EQ(SP32(0xf00f1001, 4), getProduct32(0x1001, 0xf00010));
+  EXPECT_EQ(SP32(0xf00f0700, 8), getProduct32(0x1001, 0xf000070));
+  EXPECT_EQ(SP32(0xf00f0801, 8), getProduct32(0x1001, 0xf000080));
+
+  // Round to overflow.
+  EXPECT_EQ(SP64(UINT64_C(1) << 63, 64),
+            getProduct64(UINT64_C(10376293541461622786),
+                         UINT64_C(16397105843297379211)));
+
+  // Big number with rounding.
+  EXPECT_EQ(SP64(UINT64_C(9223372036854775810), 64),
+            getProduct64(UINT64_C(18446744073709551556),
+                         UINT64_C(9223372036854775840)));
+}
+
+TEST(PositiveFloatTest, Divide) {
+  // Zero.
+  EXPECT_EQ(SP32(0, 0), getQuotient32(0, 0));
+  EXPECT_EQ(SP32(0, 0), getQuotient32(0, 1));
+  EXPECT_EQ(SP32(0, 0), getQuotient32(0, 73));
+  EXPECT_EQ(SP32(UINT32_MAX, INT16_MAX), getQuotient32(1, 0));
+  EXPECT_EQ(SP32(UINT32_MAX, INT16_MAX), getQuotient32(6, 0));
+
+  // Powers of two.
+  EXPECT_EQ(SP32(1u << 31, -31), getQuotient32(1, 1));
+  EXPECT_EQ(SP32(1u << 31, -30), getQuotient32(2, 1));
+  EXPECT_EQ(SP32(1u << 31, -33), getQuotient32(4, 16));
+  EXPECT_EQ(SP32(7u << 29, -29), getQuotient32(7, 1));
+  EXPECT_EQ(SP32(7u << 29, -30), getQuotient32(7, 2));
+  EXPECT_EQ(SP32(7u << 29, -33), getQuotient32(7, 16));
+
+  // Divide evenly.
+  EXPECT_EQ(SP32(3u << 30, -30), getQuotient32(9, 3));
+  EXPECT_EQ(SP32(9u << 28, -28), getQuotient32(63, 7));
+
+  // Divide unevenly.
+  EXPECT_EQ(SP32(0xaaaaaaab, -33), getQuotient32(1, 3));
+  EXPECT_EQ(SP32(0xd5555555, -31), getQuotient32(5, 3));
+
+  // 64-bit division is hard to test, since divide64 doesn't canonicalized its
+  // output.  However, this is the algorithm the implementation uses:
+  //
+  // - Shift divisor right.
+  // - If we have 1 (power of 2), return early -- not canonicalized.
+  // - Shift dividend left.
+  // - 64-bit integer divide.
+  // - If there's a remainder, continue with long division.
+  //
+  // TODO: require less knowledge about the implementation in the test.
+
+  // Zero.
+  EXPECT_EQ(SP64(0, 0), getQuotient64(0, 0));
+  EXPECT_EQ(SP64(0, 0), getQuotient64(0, 1));
+  EXPECT_EQ(SP64(0, 0), getQuotient64(0, 73));
+  EXPECT_EQ(SP64(UINT64_MAX, INT16_MAX), getQuotient64(1, 0));
+  EXPECT_EQ(SP64(UINT64_MAX, INT16_MAX), getQuotient64(6, 0));
+
+  // Powers of two.
+  EXPECT_EQ(SP64(1, 0), getQuotient64(1, 1));
+  EXPECT_EQ(SP64(2, 0), getQuotient64(2, 1));
+  EXPECT_EQ(SP64(4, -4), getQuotient64(4, 16));
+  EXPECT_EQ(SP64(7, 0), getQuotient64(7, 1));
+  EXPECT_EQ(SP64(7, -1), getQuotient64(7, 2));
+  EXPECT_EQ(SP64(7, -4), getQuotient64(7, 16));
+
+  // Divide evenly.
+  EXPECT_EQ(SP64(UINT64_C(3) << 60, -60), getQuotient64(9, 3));
+  EXPECT_EQ(SP64(UINT64_C(9) << 58, -58), getQuotient64(63, 7));
+
+  // Divide unevenly.
+  EXPECT_EQ(SP64(0xaaaaaaaaaaaaaaab, -65), getQuotient64(1, 3));
+  EXPECT_EQ(SP64(0xd555555555555555, -63), getQuotient64(5, 3));
+}
+
 } // end namespace