Support: Move class ScaledNumber

ScaledNumber has been cleaned up enough to pull out of BFI now.  Still
work to do there (tests for shifting, bloated printing code, etc.), but
it seems clean enough for its new home.

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

2 files changed, 480 insertions, 483 deletions

diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
index 519d01342d..73408016e0 100644
--- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h
+++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
@@ -33,489 +33,6 @@
 
 //===----------------------------------------------------------------------===//
 //
-// ScaledNumber definition.
-//
-// TODO: Move to include/llvm/Support/ScaledNumber.h
-//
-//===----------------------------------------------------------------------===//
-namespace llvm {
-
-class ScaledNumberBase {
-public:
-  static const int DefaultPrecision = 10;
-
-  static void dump(uint64_t D, int16_t E, int Width);
-  static raw_ostream &print(raw_ostream &OS, uint64_t D, int16_t E, int Width,
-                            unsigned Precision);
-  static std::string toString(uint64_t D, int16_t E, int Width,
-                              unsigned Precision);
-  static int countLeadingZeros32(uint32_t N) { return countLeadingZeros(N); }
-  static int countLeadingZeros64(uint64_t N) { return countLeadingZeros(N); }
-  static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
-
-  static std::pair<uint64_t, bool> splitSigned(int64_t N) {
-    if (N >= 0)
-      return std::make_pair(N, false);
-    uint64_t Unsigned = N == INT64_MIN ? UINT64_C(1) << 63 : uint64_t(-N);
-    return std::make_pair(Unsigned, true);
-  }
-  static int64_t joinSigned(uint64_t U, bool IsNeg) {
-    if (U > uint64_t(INT64_MAX))
-      return IsNeg ? INT64_MIN : INT64_MAX;
-    return IsNeg ? -int64_t(U) : int64_t(U);
-  }
-};
-
-/// \brief Simple representation of a scaled number.
-///
-/// ScaledNumber is a number represented by digits and a scale.  It uses simple
-/// saturation arithmetic and every operation is well-defined for every value.
-/// It's somewhat similar in behaviour to a soft-float, but is *not* a
-/// replacement for one.  If you're doing numerics, look at \a APFloat instead.
-/// Nevertheless, we've found these semantics useful for modelling certain cost
-/// metrics.
-///
-/// The number is split into a signed scale and unsigned digits.  The number
-/// represented is \c getDigits()*2^getScale().  In this way, the digits are
-/// much like the mantissa in the x87 long double, but there is no canonical
-/// form so the same number can be represented by many bit representations.
-///
-/// ScaledNumber is templated on the underlying integer type for digits, which
-/// is expected to be unsigned.
-///
-/// Unlike APFloat, ScaledNumber does not model architecture floating point
-/// behaviour -- while this might make it a little faster and easier to reason
-/// about, it certainly makes it more dangerous for general numerics.
-///
-/// ScaledNumber is totally ordered.  However, there is no canonical form, so
-/// there are multiple representations of most scalars.  E.g.:
-///
-///     ScaledNumber(8u, 0) == ScaledNumber(4u, 1)
-///     ScaledNumber(4u, 1) == ScaledNumber(2u, 2)
-///     ScaledNumber(2u, 2) == ScaledNumber(1u, 3)
-///
-/// ScaledNumber implements most arithmetic operations.  Precision is kept
-/// where possible.  Uses simple saturation arithmetic, so that operations
-/// saturate to 0.0 or getLargest() rather than under or overflowing.  It has
-/// some extra arithmetic for unit inversion.  0.0/0.0 is defined to be 0.0.
-/// Any other division by 0.0 is defined to be getLargest().
-///
-/// As a convenience for modifying the exponent, left and right shifting are
-/// both implemented, and both interpret negative shifts as positive shifts in
-/// the opposite direction.
-///
-/// Scales are limited to the range accepted by x87 long double.  This makes
-/// it trivial to add functionality to convert to APFloat (this is already
-/// relied on for the implementation of printing).
-///
-/// Possible (and conflicting) future directions:
-///
-///  1. Turn this into a wrapper around \a APFloat.
-///  2. Share the algorithm implementations with \a APFloat.
-///  3. Allow \a ScaledNumber to represent a signed number.
-template <class DigitsT> class ScaledNumber : ScaledNumberBase {
-public:
-  static_assert(!std::numeric_limits<DigitsT>::is_signed,
-                "only unsigned floats supported");
-
-  typedef DigitsT DigitsType;
-
-private:
-  typedef std::numeric_limits<DigitsType> DigitsLimits;
-
-  static const int Width = sizeof(DigitsType) * 8;
-  static_assert(Width <= 64, "invalid integer width for digits");
-
-private:
-  DigitsType Digits;
-  int16_t Scale;
-
-public:
-  ScaledNumber() : Digits(0), Scale(0) {}
-
-  ScaledNumber(DigitsType Digits, int16_t Scale)
-      : Digits(Digits), Scale(Scale) {}
-
-private:
-  ScaledNumber(const std::pair<uint64_t, int16_t> &X)
-      : Digits(X.first), Scale(X.second) {}
-
-public:
-  static ScaledNumber getZero() { return ScaledNumber(0, 0); }
-  static ScaledNumber getOne() { return ScaledNumber(1, 0); }
-  static ScaledNumber getLargest() {
-    return ScaledNumber(DigitsLimits::max(), ScaledNumbers::MaxScale);
-  }
-  static ScaledNumber get(uint64_t N) { return adjustToWidth(N, 0); }
-  static ScaledNumber getInverse(uint64_t N) {
-    return get(N).invert();
-  }
-  static ScaledNumber getFraction(DigitsType N, DigitsType D) {
-    return getQuotient(N, D);
-  }
-
-  int16_t getScale() const { return Scale; }
-  DigitsType getDigits() const { return Digits; }
-
-  /// \brief Convert to the given integer type.
-  ///
-  /// Convert to \c IntT using simple saturating arithmetic, truncating if
-  /// necessary.
-  template <class IntT> IntT toInt() const;
-
-  bool isZero() const { return !Digits; }
-  bool isLargest() const { return *this == getLargest(); }
-  bool isOne() const {
-    if (Scale > 0 || Scale <= -Width)
-      return false;
-    return Digits == DigitsType(1) << -Scale;
-  }
-
-  /// \brief The log base 2, rounded.
-  ///
-  /// Get the lg of the scalar.  lg 0 is defined to be INT32_MIN.
-  int32_t lg() const { return ScaledNumbers::getLg(Digits, Scale); }
-
-  /// \brief The log base 2, rounded towards INT32_MIN.
-  ///
-  /// Get the lg floor.  lg 0 is defined to be INT32_MIN.
-  int32_t lgFloor() const { return ScaledNumbers::getLgFloor(Digits, Scale); }
-
-  /// \brief The log base 2, rounded towards INT32_MAX.
-  ///
-  /// Get the lg ceiling.  lg 0 is defined to be INT32_MIN.
-  int32_t lgCeiling() const {
-    return ScaledNumbers::getLgCeiling(Digits, Scale);
-  }
-
-  bool operator==(const ScaledNumber &X) const { return compare(X) == 0; }
-  bool operator<(const ScaledNumber &X) const { return compare(X) < 0; }
-  bool operator!=(const ScaledNumber &X) const { return compare(X) != 0; }
-  bool operator>(const ScaledNumber &X) const { return compare(X) > 0; }
-  bool operator<=(const ScaledNumber &X) const { return compare(X) <= 0; }
-  bool operator>=(const ScaledNumber &X) const { return compare(X) >= 0; }
-
-  bool operator!() const { return isZero(); }
-
-  /// \brief Convert to a decimal representation in a string.
-  ///
-  /// Convert to a string.  Uses scientific notation for very large/small
-  /// numbers.  Scientific notation is used roughly for numbers outside of the
-  /// range 2^-64 through 2^64.
-  ///
-  /// \c Precision indicates the number of decimal digits of precision to use;
-  /// 0 requests the maximum available.
-  ///
-  /// As a special case to make debugging easier, if the number is small enough
-  /// to convert without scientific notation and has more than \c Precision
-  /// digits before the decimal place, it's printed accurately to the first
-  /// digit past zero.  E.g., assuming 10 digits of precision:
-  ///
-  ///     98765432198.7654... => 98765432198.8
-  ///      8765432198.7654... =>  8765432198.8
-  ///       765432198.7654... =>   765432198.8
-  ///        65432198.7654... =>    65432198.77
-  ///         5432198.7654... =>     5432198.765
-  std::string toString(unsigned Precision = DefaultPrecision) {
-    return ScaledNumberBase::toString(Digits, Scale, Width, Precision);
-  }
-
-  /// \brief Print a decimal representation.
-  ///
-  /// Print a string.  See toString for documentation.
-  raw_ostream &print(raw_ostream &OS,
-                     unsigned Precision = DefaultPrecision) const {
-    return ScaledNumberBase::print(OS, Digits, Scale, Width, Precision);
-  }
-  void dump() const { return ScaledNumberBase::dump(Digits, Scale, Width); }
-
-  ScaledNumber &operator+=(const ScaledNumber &X) {
-    std::tie(Digits, Scale) =
-        ScaledNumbers::getSum(Digits, Scale, X.Digits, X.Scale);
-    // Check for exponent past MaxScale.
-    if (Scale > ScaledNumbers::MaxScale)
-      *this = getLargest();
-    return *this;
-  }
-  ScaledNumber &operator-=(const ScaledNumber &X) {
-    std::tie(Digits, Scale) =
-        ScaledNumbers::getDifference(Digits, Scale, X.Digits, X.Scale);
-    return *this;
-  }
-  ScaledNumber &operator*=(const ScaledNumber &X);
-  ScaledNumber &operator/=(const ScaledNumber &X);
-  ScaledNumber &operator<<=(int16_t Shift) {
-    shiftLeft(Shift);
-    return *this;
-  }
-  ScaledNumber &operator>>=(int16_t Shift) {
-    shiftRight(Shift);
-    return *this;
-  }
-
-private:
-  void shiftLeft(int32_t Shift);
-  void shiftRight(int32_t Shift);
-
-  /// \brief Adjust two floats to have matching exponents.
-  ///
-  /// Adjust \c this and \c X to have matching exponents.  Returns the new \c X
-  /// by value.  Does nothing if \a isZero() for either.
-  ///
-  /// The value that compares smaller will lose precision, and possibly become
-  /// \a isZero().
-  ScaledNumber matchScales(ScaledNumber X) {
-    ScaledNumbers::matchScales(Digits, Scale, X.Digits, X.Scale);
-    return X;
-  }
-
-public:
-  /// \brief Scale a large number accurately.
-  ///
-  /// Scale N (multiply it by this).  Uses full precision multiplication, even
-  /// if Width is smaller than 64, so information is not lost.
-  uint64_t scale(uint64_t N) const;
-  uint64_t scaleByInverse(uint64_t N) const {
-    // TODO: implement directly, rather than relying on inverse.  Inverse is
-    // expensive.
-    return inverse().scale(N);
-  }
-  int64_t scale(int64_t N) const {
-    std::pair<uint64_t, bool> Unsigned = splitSigned(N);
-    return joinSigned(scale(Unsigned.first), Unsigned.second);
-  }
-  int64_t scaleByInverse(int64_t N) const {
-    std::pair<uint64_t, bool> Unsigned = splitSigned(N);
-    return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second);
-  }
-
-  int compare(const ScaledNumber &X) const {
-    return ScaledNumbers::compare(Digits, Scale, X.Digits, X.Scale);
-  }
-  int compareTo(uint64_t N) const {
-    ScaledNumber Scaled = get(N);
-    int Compare = compare(Scaled);
-    if (Width == 64 || Compare != 0)
-      return Compare;
-
-    // Check for precision loss.  We know *this == RoundTrip.
-    uint64_t RoundTrip = Scaled.template toInt<uint64_t>();
-    return N == RoundTrip ? 0 : RoundTrip < N ? -1 : 1;
-  }
-  int compareTo(int64_t N) const { return N < 0 ? 1 : compareTo(uint64_t(N)); }
-
-  ScaledNumber &invert() { return *this = ScaledNumber::get(1) / *this; }
-  ScaledNumber inverse() const { return ScaledNumber(*this).invert(); }
-
-private:
-  static ScaledNumber getProduct(DigitsType LHS, DigitsType RHS) {
-    return ScaledNumbers::getProduct(LHS, RHS);
-  }
-  static ScaledNumber getQuotient(DigitsType Dividend, DigitsType Divisor) {
-    return ScaledNumbers::getQuotient(Dividend, Divisor);
-  }
-
-  static int countLeadingZerosWidth(DigitsType Digits) {
-    if (Width == 64)
-      return countLeadingZeros64(Digits);
-    if (Width == 32)
-      return countLeadingZeros32(Digits);
-    return countLeadingZeros32(Digits) + Width - 32;
-  }
-
-  /// \brief Adjust a number to width, rounding up if necessary.
-  ///
-  /// Should only be called for \c Shift close to zero.
-  ///
-  /// \pre Shift >= MinScale && Shift + 64 <= MaxScale.
-  static ScaledNumber adjustToWidth(uint64_t N, int32_t Shift) {
-    assert(Shift >= ScaledNumbers::MinScale && "Shift should be close to 0");
-    assert(Shift <= ScaledNumbers::MaxScale - 64 &&
-           "Shift should be close to 0");
-    auto Adjusted = ScaledNumbers::getAdjusted<DigitsT>(N, Shift);
-    return Adjusted;
-  }
-
-  static ScaledNumber getRounded(ScaledNumber P, bool Round) {
-    // Saturate.
-    if (P.isLargest())
-      return P;
-
-    return ScaledNumbers::getRounded(P.Digits, P.Scale, Round);
-  }
-};
-
-#define SCALED_NUMBER_BOP(op, base)                                            \
-  template <class DigitsT>                                                     \
-  ScaledNumber<DigitsT> operator op(const ScaledNumber<DigitsT> &L,            \
-                                    const ScaledNumber<DigitsT> &R) {          \
-    return ScaledNumber<DigitsT>(L) base R;                                    \
-  }
-SCALED_NUMBER_BOP(+, += )
-SCALED_NUMBER_BOP(-, -= )
-SCALED_NUMBER_BOP(*, *= )
-SCALED_NUMBER_BOP(/, /= )
-SCALED_NUMBER_BOP(<<, <<= )
-SCALED_NUMBER_BOP(>>, >>= )
-#undef SCALED_NUMBER_BOP
-
-template <class DigitsT>
-raw_ostream &operator<<(raw_ostream &OS, const ScaledNumber<DigitsT> &X) {
-  return X.print(OS, 10);
-}
-
-#define SCALED_NUMBER_COMPARE_TO_TYPE(op, T1, T2)                              \
-  template <class DigitsT>                                                     \
-  bool operator op(const ScaledNumber<DigitsT> &L, T1 R) {                     \
-    return L.compareTo(T2(R)) op 0;                                            \
-  }                                                                            \
-  template <class DigitsT>                                                     \
-  bool operator op(T1 L, const ScaledNumber<DigitsT> &R) {                     \
-    return 0 op R.compareTo(T2(L));                                            \
-  }
-#define SCALED_NUMBER_COMPARE_TO(op)                                           \
-  SCALED_NUMBER_COMPARE_TO_TYPE(op, uint64_t, uint64_t)                        \
-  SCALED_NUMBER_COMPARE_TO_TYPE(op, uint32_t, uint64_t)                        \
-  SCALED_NUMBER_COMPARE_TO_TYPE(op, int64_t, int64_t)                          \
-  SCALED_NUMBER_COMPARE_TO_TYPE(op, int32_t, int64_t)
-SCALED_NUMBER_COMPARE_TO(< )
-SCALED_NUMBER_COMPARE_TO(> )
-SCALED_NUMBER_COMPARE_TO(== )
-SCALED_NUMBER_COMPARE_TO(!= )
-SCALED_NUMBER_COMPARE_TO(<= )
-SCALED_NUMBER_COMPARE_TO(>= )
-#undef SCALED_NUMBER_COMPARE_TO
-#undef SCALED_NUMBER_COMPARE_TO_TYPE
-
-template <class DigitsT>
-uint64_t ScaledNumber<DigitsT>::scale(uint64_t N) const {
-  if (Width == 64 || N <= DigitsLimits::max())
-    return (get(N) * *this).template toInt<uint64_t>();
-
-  // Defer to the 64-bit version.
-  return ScaledNumber<uint64_t>(Digits, Scale).scale(N);
-}
-
-template <class DigitsT>
-template <class IntT>
-IntT ScaledNumber<DigitsT>::toInt() const {
-  typedef std::numeric_limits<IntT> Limits;
-  if (*this < 1)
-    return 0;
-  if (*this >= Limits::max())
-    return Limits::max();
-
-  IntT N = Digits;
-  if (Scale > 0) {
-    assert(size_t(Scale) < sizeof(IntT) * 8);
-    return N << Scale;
-  }
-  if (Scale < 0) {
-    assert(size_t(-Scale) < sizeof(IntT) * 8);
-    return N >> -Scale;
-  }
-  return N;
-}
-
-template <class DigitsT>
-ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
-operator*=(const ScaledNumber &X) {
-  if (isZero())
-    return *this;
-  if (X.isZero())
-    return *this = X;
-
-  // Save the exponents.
-  int32_t Scales = int32_t(Scale) + int32_t(X.Scale);
-
-  // Get the raw product.
-  *this = getProduct(Digits, X.Digits);
-
-  // Combine with exponents.
-  return *this <<= Scales;
-}
-template <class DigitsT>
-ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
-operator/=(const ScaledNumber &X) {
-  if (isZero())
-    return *this;
-  if (X.isZero())
-    return *this = getLargest();
-
-  // Save the exponents.
-  int32_t Scales = int32_t(Scale) - int32_t(X.Scale);
-
-  // Get the raw quotient.
-  *this = getQuotient(Digits, X.Digits);
-
-  // Combine with exponents.
-  return *this <<= Scales;
-}
-template <class DigitsT> void ScaledNumber<DigitsT>::shiftLeft(int32_t Shift) {
-  if (!Shift || isZero())
-    return;
-  assert(Shift != INT32_MIN);
-  if (Shift < 0) {
-    shiftRight(-Shift);
-    return;
-  }
-
-  // Shift as much as we can in the exponent.
-  int32_t ScaleShift = std::min(Shift, ScaledNumbers::MaxScale - Scale);
-  Scale += ScaleShift;
-  if (ScaleShift == Shift)
-    return;
-
-  // Check this late, since it's rare.
-  if (isLargest())
-    return;
-
-  // Shift the digits themselves.
-  Shift -= ScaleShift;
-  if (Shift > countLeadingZerosWidth(Digits)) {
-    // Saturate.
-    *this = getLargest();
-    return;
-  }
-
-  Digits <<= Shift;
-  return;
-}
-
-template <class DigitsT> void ScaledNumber<DigitsT>::shiftRight(int32_t Shift) {
-  if (!Shift || isZero())
-    return;
-  assert(Shift != INT32_MIN);
-  if (Shift < 0) {
-    shiftLeft(-Shift);
-    return;
-  }
-
-  // Shift as much as we can in the exponent.
-  int32_t ScaleShift = std::min(Shift, Scale - ScaledNumbers::MinScale);
-  Scale -= ScaleShift;
-  if (ScaleShift == Shift)
-    return;
-
-  // Shift the digits themselves.
-  Shift -= ScaleShift;
-  if (Shift >= Width) {
-    // Saturate.
-    *this = getZero();
-    return;
-  }
-
-  Digits >>= Shift;
-  return;
-}
-
-template <class T> struct isPodLike<ScaledNumber<T>> {
-  static const bool value = true;
-};
-}
-
-//===----------------------------------------------------------------------===//
-//
 // BlockMass definition.
 //
 // TODO: Make this private to BlockFrequencyInfoImpl or delete.
diff --git a/include/llvm/Support/ScaledNumber.h b/include/llvm/Support/ScaledNumber.h
index e7c329f7bf..c0818d9bf6 100644
--- a/include/llvm/Support/ScaledNumber.h
+++ b/include/llvm/Support/ScaledNumber.h
@@ -27,6 +27,7 @@
 #include <algorithm>
 #include <cstdint>
 #include <limits>
+#include <string>
 #include <utility>
 
 namespace llvm {
@@ -413,4 +414,483 @@ inline std::pair<uint64_t, int16_t> getDifference64(uint64_t LDigits,
 } // end namespace ScaledNumbers
 } // end namespace llvm
 
+namespace llvm {
+
+class raw_ostream;
+class ScaledNumberBase {
+public:
+  static const int DefaultPrecision = 10;
+
+  static void dump(uint64_t D, int16_t E, int Width);
+  static raw_ostream &print(raw_ostream &OS, uint64_t D, int16_t E, int Width,
+                            unsigned Precision);
+  static std::string toString(uint64_t D, int16_t E, int Width,
+                              unsigned Precision);
+  static int countLeadingZeros32(uint32_t N) { return countLeadingZeros(N); }
+  static int countLeadingZeros64(uint64_t N) { return countLeadingZeros(N); }
+  static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
+
+  static std::pair<uint64_t, bool> splitSigned(int64_t N) {
+    if (N >= 0)
+      return std::make_pair(N, false);
+    uint64_t Unsigned = N == INT64_MIN ? UINT64_C(1) << 63 : uint64_t(-N);
+    return std::make_pair(Unsigned, true);
+  }
+  static int64_t joinSigned(uint64_t U, bool IsNeg) {
+    if (U > uint64_t(INT64_MAX))
+      return IsNeg ? INT64_MIN : INT64_MAX;
+    return IsNeg ? -int64_t(U) : int64_t(U);
+  }
+};
+
+/// \brief Simple representation of a scaled number.
+///
+/// ScaledNumber is a number represented by digits and a scale.  It uses simple
+/// saturation arithmetic and every operation is well-defined for every value.
+/// It's somewhat similar in behaviour to a soft-float, but is *not* a
+/// replacement for one.  If you're doing numerics, look at \a APFloat instead.
+/// Nevertheless, we've found these semantics useful for modelling certain cost
+/// metrics.
+///
+/// The number is split into a signed scale and unsigned digits.  The number
+/// represented is \c getDigits()*2^getScale().  In this way, the digits are
+/// much like the mantissa in the x87 long double, but there is no canonical
+/// form so the same number can be represented by many bit representations.
+///
+/// ScaledNumber is templated on the underlying integer type for digits, which
+/// is expected to be unsigned.
+///
+/// Unlike APFloat, ScaledNumber does not model architecture floating point
+/// behaviour -- while this might make it a little faster and easier to reason
+/// about, it certainly makes it more dangerous for general numerics.
+///
+/// ScaledNumber is totally ordered.  However, there is no canonical form, so
+/// there are multiple representations of most scalars.  E.g.:
+///
+///     ScaledNumber(8u, 0) == ScaledNumber(4u, 1)
+///     ScaledNumber(4u, 1) == ScaledNumber(2u, 2)
+///     ScaledNumber(2u, 2) == ScaledNumber(1u, 3)
+///
+/// ScaledNumber implements most arithmetic operations.  Precision is kept
+/// where possible.  Uses simple saturation arithmetic, so that operations
+/// saturate to 0.0 or getLargest() rather than under or overflowing.  It has
+/// some extra arithmetic for unit inversion.  0.0/0.0 is defined to be 0.0.
+/// Any other division by 0.0 is defined to be getLargest().
+///
+/// As a convenience for modifying the exponent, left and right shifting are
+/// both implemented, and both interpret negative shifts as positive shifts in
+/// the opposite direction.
+///
+/// Scales are limited to the range accepted by x87 long double.  This makes
+/// it trivial to add functionality to convert to APFloat (this is already
+/// relied on for the implementation of printing).
+///
+/// Possible (and conflicting) future directions:
+///
+///  1. Turn this into a wrapper around \a APFloat.
+///  2. Share the algorithm implementations with \a APFloat.
+///  3. Allow \a ScaledNumber to represent a signed number.
+template <class DigitsT> class ScaledNumber : ScaledNumberBase {
+public:
+  static_assert(!std::numeric_limits<DigitsT>::is_signed,
+                "only unsigned floats supported");
+
+  typedef DigitsT DigitsType;
+
+private:
+  typedef std::numeric_limits<DigitsType> DigitsLimits;
+
+  static const int Width = sizeof(DigitsType) * 8;
+  static_assert(Width <= 64, "invalid integer width for digits");
+
+private:
+  DigitsType Digits;
+  int16_t Scale;
+
+public:
+  ScaledNumber() : Digits(0), Scale(0) {}
+
+  ScaledNumber(DigitsType Digits, int16_t Scale)
+      : Digits(Digits), Scale(Scale) {}
+
+private:
+  ScaledNumber(const std::pair<uint64_t, int16_t> &X)
+      : Digits(X.first), Scale(X.second) {}
+
+public:
+  static ScaledNumber getZero() { return ScaledNumber(0, 0); }
+  static ScaledNumber getOne() { return ScaledNumber(1, 0); }
+  static ScaledNumber getLargest() {
+    return ScaledNumber(DigitsLimits::max(), ScaledNumbers::MaxScale);
+  }
+  static ScaledNumber get(uint64_t N) { return adjustToWidth(N, 0); }
+  static ScaledNumber getInverse(uint64_t N) {
+    return get(N).invert();
+  }
+  static ScaledNumber getFraction(DigitsType N, DigitsType D) {
+    return getQuotient(N, D);
+  }
+
+  int16_t getScale() const { return Scale; }
+  DigitsType getDigits() const { return Digits; }
+
+  /// \brief Convert to the given integer type.
+  ///
+  /// Convert to \c IntT using simple saturating arithmetic, truncating if
+  /// necessary.
+  template <class IntT> IntT toInt() const;
+
+  bool isZero() const { return !Digits; }
+  bool isLargest() const { return *this == getLargest(); }
+  bool isOne() const {
+    if (Scale > 0 || Scale <= -Width)
+      return false;
+    return Digits == DigitsType(1) << -Scale;
+  }
+
+  /// \brief The log base 2, rounded.
+  ///
+  /// Get the lg of the scalar.  lg 0 is defined to be INT32_MIN.
+  int32_t lg() const { return ScaledNumbers::getLg(Digits, Scale); }
+
+  /// \brief The log base 2, rounded towards INT32_MIN.
+  ///
+  /// Get the lg floor.  lg 0 is defined to be INT32_MIN.
+  int32_t lgFloor() const { return ScaledNumbers::getLgFloor(Digits, Scale); }
+
+  /// \brief The log base 2, rounded towards INT32_MAX.
+  ///
+  /// Get the lg ceiling.  lg 0 is defined to be INT32_MIN.
+  int32_t lgCeiling() const {
+    return ScaledNumbers::getLgCeiling(Digits, Scale);
+  }
+
+  bool operator==(const ScaledNumber &X) const { return compare(X) == 0; }
+  bool operator<(const ScaledNumber &X) const { return compare(X) < 0; }
+  bool operator!=(const ScaledNumber &X) const { return compare(X) != 0; }
+  bool operator>(const ScaledNumber &X) const { return compare(X) > 0; }
+  bool operator<=(const ScaledNumber &X) const { return compare(X) <= 0; }
+  bool operator>=(const ScaledNumber &X) const { return compare(X) >= 0; }
+
+  bool operator!() const { return isZero(); }
+
+  /// \brief Convert to a decimal representation in a string.
+  ///
+  /// Convert to a string.  Uses scientific notation for very large/small
+  /// numbers.  Scientific notation is used roughly for numbers outside of the
+  /// range 2^-64 through 2^64.
+  ///
+  /// \c Precision indicates the number of decimal digits of precision to use;
+  /// 0 requests the maximum available.
+  ///
+  /// As a special case to make debugging easier, if the number is small enough
+  /// to convert without scientific notation and has more than \c Precision
+  /// digits before the decimal place, it's printed accurately to the first
+  /// digit past zero.  E.g., assuming 10 digits of precision:
+  ///
+  ///     98765432198.7654... => 98765432198.8
+  ///      8765432198.7654... =>  8765432198.8
+  ///       765432198.7654... =>   765432198.8
+  ///        65432198.7654... =>    65432198.77
+  ///         5432198.7654... =>     5432198.765
+  std::string toString(unsigned Precision = DefaultPrecision) {
+    return ScaledNumberBase::toString(Digits, Scale, Width, Precision);
+  }
+
+  /// \brief Print a decimal representation.
+  ///
+  /// Print a string.  See toString for documentation.
+  raw_ostream &print(raw_ostream &OS,
+                     unsigned Precision = DefaultPrecision) const {
+    return ScaledNumberBase::print(OS, Digits, Scale, Width, Precision);
+  }
+  void dump() const { return ScaledNumberBase::dump(Digits, Scale, Width); }
+
+  ScaledNumber &operator+=(const ScaledNumber &X) {
+    std::tie(Digits, Scale) =
+        ScaledNumbers::getSum(Digits, Scale, X.Digits, X.Scale);
+    // Check for exponent past MaxScale.
+    if (Scale > ScaledNumbers::MaxScale)
+      *this = getLargest();
+    return *this;
+  }
+  ScaledNumber &operator-=(const ScaledNumber &X) {
+    std::tie(Digits, Scale) =
+        ScaledNumbers::getDifference(Digits, Scale, X.Digits, X.Scale);
+    return *this;
+  }
+  ScaledNumber &operator*=(const ScaledNumber &X);
+  ScaledNumber &operator/=(const ScaledNumber &X);
+  ScaledNumber &operator<<=(int16_t Shift) {
+    shiftLeft(Shift);
+    return *this;
+  }
+  ScaledNumber &operator>>=(int16_t Shift) {
+    shiftRight(Shift);
+    return *this;
+  }
+
+private:
+  void shiftLeft(int32_t Shift);
+  void shiftRight(int32_t Shift);
+
+  /// \brief Adjust two floats to have matching exponents.
+  ///
+  /// Adjust \c this and \c X to have matching exponents.  Returns the new \c X
+  /// by value.  Does nothing if \a isZero() for either.
+  ///
+  /// The value that compares smaller will lose precision, and possibly become
+  /// \a isZero().
+  ScaledNumber matchScales(ScaledNumber X) {
+    ScaledNumbers::matchScales(Digits, Scale, X.Digits, X.Scale);
+    return X;
+  }
+
+public:
+  /// \brief Scale a large number accurately.
+  ///
+  /// Scale N (multiply it by this).  Uses full precision multiplication, even
+  /// if Width is smaller than 64, so information is not lost.
+  uint64_t scale(uint64_t N) const;
+  uint64_t scaleByInverse(uint64_t N) const {
+    // TODO: implement directly, rather than relying on inverse.  Inverse is
+    // expensive.
+    return inverse().scale(N);
+  }
+  int64_t scale(int64_t N) const {
+    std::pair<uint64_t, bool> Unsigned = splitSigned(N);
+    return joinSigned(scale(Unsigned.first), Unsigned.second);
+  }
+  int64_t scaleByInverse(int64_t N) const {
+    std::pair<uint64_t, bool> Unsigned = splitSigned(N);
+    return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second);
+  }
+
+  int compare(const ScaledNumber &X) const {
+    return ScaledNumbers::compare(Digits, Scale, X.Digits, X.Scale);
+  }
+  int compareTo(uint64_t N) const {
+    ScaledNumber Scaled = get(N);
+    int Compare = compare(Scaled);
+    if (Width == 64 || Compare != 0)
+      return Compare;
+
+    // Check for precision loss.  We know *this == RoundTrip.
+    uint64_t RoundTrip = Scaled.template toInt<uint64_t>();
+    return N == RoundTrip ? 0 : RoundTrip < N ? -1 : 1;
+  }
+  int compareTo(int64_t N) const { return N < 0 ? 1 : compareTo(uint64_t(N)); }
+
+  ScaledNumber &invert() { return *this = ScaledNumber::get(1) / *this; }
+  ScaledNumber inverse() const { return ScaledNumber(*this).invert(); }
+
+private:
+  static ScaledNumber getProduct(DigitsType LHS, DigitsType RHS) {
+    return ScaledNumbers::getProduct(LHS, RHS);
+  }
+  static ScaledNumber getQuotient(DigitsType Dividend, DigitsType Divisor) {
+    return ScaledNumbers::getQuotient(Dividend, Divisor);
+  }
+
+  static int countLeadingZerosWidth(DigitsType Digits) {
+    if (Width == 64)
+      return countLeadingZeros64(Digits);
+    if (Width == 32)
+      return countLeadingZeros32(Digits);
+    return countLeadingZeros32(Digits) + Width - 32;
+  }
+
+  /// \brief Adjust a number to width, rounding up if necessary.
+  ///
+  /// Should only be called for \c Shift close to zero.
+  ///
+  /// \pre Shift >= MinScale && Shift + 64 <= MaxScale.
+  static ScaledNumber adjustToWidth(uint64_t N, int32_t Shift) {
+    assert(Shift >= ScaledNumbers::MinScale && "Shift should be close to 0");
+    assert(Shift <= ScaledNumbers::MaxScale - 64 &&
+           "Shift should be close to 0");
+    auto Adjusted = ScaledNumbers::getAdjusted<DigitsT>(N, Shift);
+    return Adjusted;
+  }
+
+  static ScaledNumber getRounded(ScaledNumber P, bool Round) {
+    // Saturate.
+    if (P.isLargest())
+      return P;
+
+    return ScaledNumbers::getRounded(P.Digits, P.Scale, Round);
+  }
+};
+
+#define SCALED_NUMBER_BOP(op, base)                                            \
+  template <class DigitsT>                                                     \
+  ScaledNumber<DigitsT> operator op(const ScaledNumber<DigitsT> &L,            \
+                                    const ScaledNumber<DigitsT> &R) {          \
+    return ScaledNumber<DigitsT>(L) base R;                                    \
+  }
+SCALED_NUMBER_BOP(+, += )
+SCALED_NUMBER_BOP(-, -= )
+SCALED_NUMBER_BOP(*, *= )
+SCALED_NUMBER_BOP(/, /= )
+SCALED_NUMBER_BOP(<<, <<= )
+SCALED_NUMBER_BOP(>>, >>= )
+#undef SCALED_NUMBER_BOP
+
+template <class DigitsT>
+raw_ostream &operator<<(raw_ostream &OS, const ScaledNumber<DigitsT> &X) {
+  return X.print(OS, 10);
+}
+
+#define SCALED_NUMBER_COMPARE_TO_TYPE(op, T1, T2)                              \
+  template <class DigitsT>                                                     \
+  bool operator op(const ScaledNumber<DigitsT> &L, T1 R) {                     \
+    return L.compareTo(T2(R)) op 0;                                            \
+  }                                                                            \
+  template <class DigitsT>                                                     \
+  bool operator op(T1 L, const ScaledNumber<DigitsT> &R) {                     \
+    return 0 op R.compareTo(T2(L));                                            \
+  }
+#define SCALED_NUMBER_COMPARE_TO(op)                                           \
+  SCALED_NUMBER_COMPARE_TO_TYPE(op, uint64_t, uint64_t)                        \
+  SCALED_NUMBER_COMPARE_TO_TYPE(op, uint32_t, uint64_t)                        \
+  SCALED_NUMBER_COMPARE_TO_TYPE(op, int64_t, int64_t)                          \
+  SCALED_NUMBER_COMPARE_TO_TYPE(op, int32_t, int64_t)
+SCALED_NUMBER_COMPARE_TO(< )
+SCALED_NUMBER_COMPARE_TO(> )
+SCALED_NUMBER_COMPARE_TO(== )
+SCALED_NUMBER_COMPARE_TO(!= )
+SCALED_NUMBER_COMPARE_TO(<= )
+SCALED_NUMBER_COMPARE_TO(>= )
+#undef SCALED_NUMBER_COMPARE_TO
+#undef SCALED_NUMBER_COMPARE_TO_TYPE
+
+template <class DigitsT>
+uint64_t ScaledNumber<DigitsT>::scale(uint64_t N) const {
+  if (Width == 64 || N <= DigitsLimits::max())
+    return (get(N) * *this).template toInt<uint64_t>();
+
+  // Defer to the 64-bit version.
+  return ScaledNumber<uint64_t>(Digits, Scale).scale(N);
+}
+
+template <class DigitsT>
+template <class IntT>
+IntT ScaledNumber<DigitsT>::toInt() const {
+  typedef std::numeric_limits<IntT> Limits;
+  if (*this < 1)
+    return 0;
+  if (*this >= Limits::max())
+    return Limits::max();
+
+  IntT N = Digits;
+  if (Scale > 0) {
+    assert(size_t(Scale) < sizeof(IntT) * 8);
+    return N << Scale;
+  }
+  if (Scale < 0) {
+    assert(size_t(-Scale) < sizeof(IntT) * 8);
+    return N >> -Scale;
+  }
+  return N;
+}
+
+template <class DigitsT>
+ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
+operator*=(const ScaledNumber &X) {
+  if (isZero())
+    return *this;
+  if (X.isZero())
+    return *this = X;
+
+  // Save the exponents.
+  int32_t Scales = int32_t(Scale) + int32_t(X.Scale);
+
+  // Get the raw product.
+  *this = getProduct(Digits, X.Digits);
+
+  // Combine with exponents.
+  return *this <<= Scales;
+}
+template <class DigitsT>
+ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
+operator/=(const ScaledNumber &X) {
+  if (isZero())
+    return *this;
+  if (X.isZero())
+    return *this = getLargest();
+
+  // Save the exponents.
+  int32_t Scales = int32_t(Scale) - int32_t(X.Scale);
+
+  // Get the raw quotient.
+  *this = getQuotient(Digits, X.Digits);
+
+  // Combine with exponents.
+  return *this <<= Scales;
+}
+template <class DigitsT> void ScaledNumber<DigitsT>::shiftLeft(int32_t Shift) {
+  if (!Shift || isZero())
+    return;
+  assert(Shift != INT32_MIN);
+  if (Shift < 0) {
+    shiftRight(-Shift);
+    return;
+  }
+
+  // Shift as much as we can in the exponent.
+  int32_t ScaleShift = std::min(Shift, ScaledNumbers::MaxScale - Scale);
+  Scale += ScaleShift;
+  if (ScaleShift == Shift)
+    return;
+
+  // Check this late, since it's rare.
+  if (isLargest())
+    return;
+
+  // Shift the digits themselves.
+  Shift -= ScaleShift;
+  if (Shift > countLeadingZerosWidth(Digits)) {
+    // Saturate.
+    *this = getLargest();
+    return;
+  }
+
+  Digits <<= Shift;
+  return;
+}
+
+template <class DigitsT> void ScaledNumber<DigitsT>::shiftRight(int32_t Shift) {
+  if (!Shift || isZero())
+    return;
+  assert(Shift != INT32_MIN);
+  if (Shift < 0) {
+    shiftLeft(-Shift);
+    return;
+  }
+
+  // Shift as much as we can in the exponent.
+  int32_t ScaleShift = std::min(Shift, Scale - ScaledNumbers::MinScale);
+  Scale -= ScaleShift;
+  if (ScaleShift == Shift)
+    return;
+
+  // Shift the digits themselves.
+  Shift -= ScaleShift;
+  if (Shift >= Width) {
+    // Saturate.
+    *this = getZero();
+    return;
+  }
+
+  Digits >>= Shift;
+  return;
+}
+
+template <typename T> struct isPodLike;
+template <typename T> struct isPodLike<ScaledNumber<T>> {
+  static const bool value = true;
+};
+
+} // end namespace llvm
+
 #endif