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

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

2 files changed, 82 insertions, 45 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