#define LLVM_SUPPORT_SCALEDNUMBER_H
#include "llvm/Support/MathExtras.h"
-
#include <algorithm>
#include <cstdint>
#include <limits>
+#include <string>
+#include <tuple>
#include <utility>
namespace llvm {
///
/// As a convenience, returns the matching scale. If the output value of one
/// number is zero, returns the scale of the other. If both are zero, which
-/// scale is returned is unspecifed.
+/// scale is returned is unspecified.
template <class DigitsT>
int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits,
int16_t &RScale) {
DigitsT RDigits, int16_t RScale) {
static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
- // Check inputs up front. This is only relevent if addition overflows, but
+ // Check inputs up front. This is only relevant if addition overflows, but
// testing here should catch more bugs.
assert(LScale < INT16_MAX && "scale too large");
assert(RScale < INT16_MAX && "scale too large");
} // 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<DigitsT, 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 {
+ return ScaledNumbers::compare<uint64_t>(Digits, Scale, N, 0);
+ }
+ 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(/, /= )
+#undef SCALED_NUMBER_BOP
+
+template <class DigitsT>
+ScaledNumber<DigitsT> operator<<(const ScaledNumber<DigitsT> &L,
+ int16_t Shift) {
+ return ScaledNumber<DigitsT>(L) <<= Shift;
+}
+
+template <class DigitsT>
+ScaledNumber<DigitsT> operator>>(const ScaledNumber<DigitsT> &L,
+ int16_t Shift) {
+ return ScaledNumber<DigitsT>(L) >>= Shift;
+}
+
+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