diff options
| -rw-r--r-- | include/llvm/Analysis/BlockFrequencyInfoImpl.h | 483 | ||||
| -rw-r--r-- | include/llvm/Support/ScaledNumber.h | 480 | ||||
| -rw-r--r-- | lib/Analysis/BlockFrequencyInfoImpl.cpp | 190 | ||||
| -rw-r--r-- | lib/Support/ScaledNumber.cpp | 187 |
4 files changed, 667 insertions, 673 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 diff --git a/lib/Analysis/BlockFrequencyInfoImpl.cpp b/lib/Analysis/BlockFrequencyInfoImpl.cpp index d8e633c47c..4fd2c11131 100644 --- a/lib/Analysis/BlockFrequencyInfoImpl.cpp +++ b/lib/Analysis/BlockFrequencyInfoImpl.cpp @@ -12,7 +12,6 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/BlockFrequencyInfoImpl.h" -#include "llvm/ADT/APFloat.h" #include "llvm/ADT/SCCIterator.h" #include "llvm/Support/raw_ostream.h" #include <deque> @@ -24,195 +23,6 @@ using namespace llvm::bfi_detail; //===----------------------------------------------------------------------===// // -// ScaledNumber implementation. -// -//===----------------------------------------------------------------------===// -static void appendDigit(std::string &Str, unsigned D) { - assert(D < 10); - Str += '0' + D % 10; -} - -static void appendNumber(std::string &Str, uint64_t N) { - while (N) { - appendDigit(Str, N % 10); - N /= 10; - } -} - -static bool doesRoundUp(char Digit) { - switch (Digit) { - case '5': - case '6': - case '7': - case '8': - case '9': - return true; - default: - return false; - } -} - -static std::string toStringAPFloat(uint64_t D, int E, unsigned Precision) { - assert(E >= ScaledNumbers::MinScale); - assert(E <= ScaledNumbers::MaxScale); - - // Find a new E, but don't let it increase past MaxScale. - int LeadingZeros = ScaledNumberBase::countLeadingZeros64(D); - int NewE = std::min(ScaledNumbers::MaxScale, E + 63 - LeadingZeros); - int Shift = 63 - (NewE - E); - assert(Shift <= LeadingZeros); - assert(Shift == LeadingZeros || NewE == ScaledNumbers::MaxScale); - D <<= Shift; - E = NewE; - - // Check for a denormal. - unsigned AdjustedE = E + 16383; - if (!(D >> 63)) { - assert(E == ScaledNumbers::MaxScale); - AdjustedE = 0; - } - - // Build the float and print it. - uint64_t RawBits[2] = {D, AdjustedE}; - APFloat Float(APFloat::x87DoubleExtended, APInt(80, RawBits)); - SmallVector<char, 24> Chars; - Float.toString(Chars, Precision, 0); - return std::string(Chars.begin(), Chars.end()); -} - -static std::string stripTrailingZeros(const std::string &Float) { - size_t NonZero = Float.find_last_not_of('0'); - assert(NonZero != std::string::npos && "no . in floating point string"); - - if (Float[NonZero] == '.') - ++NonZero; - - return Float.substr(0, NonZero + 1); -} - -std::string ScaledNumberBase::toString(uint64_t D, int16_t E, int Width, - unsigned Precision) { - if (!D) - return "0.0"; - - // Canonicalize exponent and digits. - uint64_t Above0 = 0; - uint64_t Below0 = 0; - uint64_t Extra = 0; - int ExtraShift = 0; - if (E == 0) { - Above0 = D; - } else if (E > 0) { - if (int Shift = std::min(int16_t(countLeadingZeros64(D)), E)) { - D <<= Shift; - E -= Shift; - - if (!E) - Above0 = D; - } - } else if (E > -64) { - Above0 = D >> -E; - Below0 = D << (64 + E); - } else if (E > -120) { - Below0 = D >> (-E - 64); - Extra = D << (128 + E); - ExtraShift = -64 - E; - } - - // Fall back on APFloat for very small and very large numbers. - if (!Above0 && !Below0) - return toStringAPFloat(D, E, Precision); - - // Append the digits before the decimal. - std::string Str; - size_t DigitsOut = 0; - if (Above0) { - appendNumber(Str, Above0); - DigitsOut = Str.size(); - } else - appendDigit(Str, 0); - std::reverse(Str.begin(), Str.end()); - - // Return early if there's nothing after the decimal. - if (!Below0) - return Str + ".0"; - - // Append the decimal and beyond. - Str += '.'; - uint64_t Error = UINT64_C(1) << (64 - Width); - - // We need to shift Below0 to the right to make space for calculating - // digits. Save the precision we're losing in Extra. - Extra = (Below0 & 0xf) << 56 | (Extra >> 8); - Below0 >>= 4; - size_t SinceDot = 0; - size_t AfterDot = Str.size(); - do { - if (ExtraShift) { - --ExtraShift; - Error *= 5; - } else - Error *= 10; - - Below0 *= 10; - Extra *= 10; - Below0 += (Extra >> 60); - Extra = Extra & (UINT64_MAX >> 4); - appendDigit(Str, Below0 >> 60); - Below0 = Below0 & (UINT64_MAX >> 4); - if (DigitsOut || Str.back() != '0') - ++DigitsOut; - ++SinceDot; - } while (Error && (Below0 << 4 | Extra >> 60) >= Error / 2 && - (!Precision || DigitsOut <= Precision || SinceDot < 2)); - - // Return early for maximum precision. - if (!Precision || DigitsOut <= Precision) - return stripTrailingZeros(Str); - - // Find where to truncate. - size_t Truncate = - std::max(Str.size() - (DigitsOut - Precision), AfterDot + 1); - - // Check if there's anything to truncate. - if (Truncate >= Str.size()) - return stripTrailingZeros(Str); - - bool Carry = doesRoundUp(Str[Truncate]); - if (!Carry) - return stripTrailingZeros(Str.substr(0, Truncate)); - - // Round with the first truncated digit. - for (std::string::reverse_iterator I(Str.begin() + Truncate), E = Str.rend(); - I != E; ++I) { - if (*I == '.') - continue; - if (*I == '9') { - *I = '0'; - continue; - } - - ++*I; - Carry = false; - break; - } - - // Add "1" in front if we still need to carry. - return stripTrailingZeros(std::string(Carry, '1') + Str.substr(0, Truncate)); -} - -raw_ostream &ScaledNumberBase::print(raw_ostream &OS, uint64_t D, int16_t E, - int Width, unsigned Precision) { - return OS << toString(D, E, Width, Precision); -} - -void ScaledNumberBase::dump(uint64_t D, int16_t E, int Width) { - print(dbgs(), D, E, Width, 0) << "[" << Width << ":" << D << "*2^" << E - << "]"; -} - -//===----------------------------------------------------------------------===// -// // BlockMass implementation. // //===----------------------------------------------------------------------===// diff --git a/lib/Support/ScaledNumber.cpp b/lib/Support/ScaledNumber.cpp index 10b23273d0..3fe027ba33 100644 --- a/lib/Support/ScaledNumber.cpp +++ b/lib/Support/ScaledNumber.cpp @@ -13,6 +13,9 @@ #include "llvm/Support/ScaledNumber.h" +#include "llvm/ADT/APFloat.h" +#include "llvm/Support/Debug.h" + using namespace llvm; using namespace llvm::ScaledNumbers; @@ -130,3 +133,187 @@ int ScaledNumbers::compareImpl(uint64_t L, uint64_t R, int ScaleDiff) { return L > L_adjusted << ScaleDiff ? 1 : 0; } + +static void appendDigit(std::string &Str, unsigned D) { + assert(D < 10); + Str += '0' + D % 10; +} + +static void appendNumber(std::string &Str, uint64_t N) { + while (N) { + appendDigit(Str, N % 10); + N /= 10; + } +} + +static bool doesRoundUp(char Digit) { + switch (Digit) { + case '5': + case '6': + case '7': + case '8': + case '9': + return true; + default: + return false; + } +} + +static std::string toStringAPFloat(uint64_t D, int E, unsigned Precision) { + assert(E >= ScaledNumbers::MinScale); + assert(E <= ScaledNumbers::MaxScale); + + // Find a new E, but don't let it increase past MaxScale. + int LeadingZeros = ScaledNumberBase::countLeadingZeros64(D); + int NewE = std::min(ScaledNumbers::MaxScale, E + 63 - LeadingZeros); + int Shift = 63 - (NewE - E); + assert(Shift <= LeadingZeros); + assert(Shift == LeadingZeros || NewE == ScaledNumbers::MaxScale); + D <<= Shift; + E = NewE; + + // Check for a denormal. + unsigned AdjustedE = E + 16383; + if (!(D >> 63)) { + assert(E == ScaledNumbers::MaxScale); + AdjustedE = 0; + } + + // Build the float and print it. + uint64_t RawBits[2] = {D, AdjustedE}; + APFloat Float(APFloat::x87DoubleExtended, APInt(80, RawBits)); + SmallVector<char, 24> Chars; + Float.toString(Chars, Precision, 0); + return std::string(Chars.begin(), Chars.end()); +} + +static std::string stripTrailingZeros(const std::string &Float) { + size_t NonZero = Float.find_last_not_of('0'); + assert(NonZero != std::string::npos && "no . in floating point string"); + + if (Float[NonZero] == '.') + ++NonZero; + + return Float.substr(0, NonZero + 1); +} + +std::string ScaledNumberBase::toString(uint64_t D, int16_t E, int Width, + unsigned Precision) { + if (!D) + return "0.0"; + + // Canonicalize exponent and digits. + uint64_t Above0 = 0; + uint64_t Below0 = 0; + uint64_t Extra = 0; + int ExtraShift = 0; + if (E == 0) { + Above0 = D; + } else if (E > 0) { + if (int Shift = std::min(int16_t(countLeadingZeros64(D)), E)) { + D <<= Shift; + E -= Shift; + + if (!E) + Above0 = D; + } + } else if (E > -64) { + Above0 = D >> -E; + Below0 = D << (64 + E); + } else if (E > -120) { + Below0 = D >> (-E - 64); + Extra = D << (128 + E); + ExtraShift = -64 - E; + } + + // Fall back on APFloat for very small and very large numbers. + if (!Above0 && !Below0) + return toStringAPFloat(D, E, Precision); + + // Append the digits before the decimal. + std::string Str; + size_t DigitsOut = 0; + if (Above0) { + appendNumber(Str, Above0); + DigitsOut = Str.size(); + } else + appendDigit(Str, 0); + std::reverse(Str.begin(), Str.end()); + + // Return early if there's nothing after the decimal. + if (!Below0) + return Str + ".0"; + + // Append the decimal and beyond. + Str += '.'; + uint64_t Error = UINT64_C(1) << (64 - Width); + + // We need to shift Below0 to the right to make space for calculating + // digits. Save the precision we're losing in Extra. + Extra = (Below0 & 0xf) << 56 | (Extra >> 8); + Below0 >>= 4; + size_t SinceDot = 0; + size_t AfterDot = Str.size(); + do { + if (ExtraShift) { + --ExtraShift; + Error *= 5; + } else + Error *= 10; + + Below0 *= 10; + Extra *= 10; + Below0 += (Extra >> 60); + Extra = Extra & (UINT64_MAX >> 4); + appendDigit(Str, Below0 >> 60); + Below0 = Below0 & (UINT64_MAX >> 4); + if (DigitsOut || Str.back() != '0') + ++DigitsOut; + ++SinceDot; + } while (Error && (Below0 << 4 | Extra >> 60) >= Error / 2 && + (!Precision || DigitsOut <= Precision || SinceDot < 2)); + + // Return early for maximum precision. + if (!Precision || DigitsOut <= Precision) + return stripTrailingZeros(Str); + + // Find where to truncate. + size_t Truncate = + std::max(Str.size() - (DigitsOut - Precision), AfterDot + 1); + + // Check if there's anything to truncate. + if (Truncate >= Str.size()) + return stripTrailingZeros(Str); + + bool Carry = doesRoundUp(Str[Truncate]); + if (!Carry) + return stripTrailingZeros(Str.substr(0, Truncate)); + + // Round with the first truncated digit. + for (std::string::reverse_iterator I(Str.begin() + Truncate), E = Str.rend(); + I != E; ++I) { + if (*I == '.') + continue; + if (*I == '9') { + *I = '0'; + continue; + } + + ++*I; + Carry = false; + break; + } + + // Add "1" in front if we still need to carry. + return stripTrailingZeros(std::string(Carry, '1') + Str.substr(0, Truncate)); +} + +raw_ostream &ScaledNumberBase::print(raw_ostream &OS, uint64_t D, int16_t E, + int Width, unsigned Precision) { + return OS << toString(D, E, Width, Precision); +} + +void ScaledNumberBase::dump(uint64_t D, int16_t E, int Width) { + print(dbgs(), D, E, Width, 0) << "[" << Width << ":" << D << "*2^" << E + << "]"; +} |