diff options
| -rw-r--r-- | include/llvm/Analysis/BlockFrequencyInfoImpl.h | 74 | ||||
| -rw-r--r-- | include/llvm/Support/ScaledNumber.h | 87 | ||||
| -rw-r--r-- | unittests/Support/ScaledNumberTest.cpp | 150 |
3 files changed, 250 insertions, 61 deletions
diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h index b462474adf..faa86644a4 100644 --- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h +++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h @@ -229,8 +229,19 @@ public: } void dump() const { return UnsignedFloatBase::dump(Digits, Exponent, Width); } - UnsignedFloat &operator+=(const UnsignedFloat &X); - UnsignedFloat &operator-=(const UnsignedFloat &X); + UnsignedFloat &operator+=(const UnsignedFloat &X) { + std::tie(Digits, Exponent) = + ScaledNumbers::getSum(Digits, Exponent, X.Digits, X.Exponent); + // Check for exponent past MaxExponent. + if (Exponent > MaxExponent) + *this = getLargest(); + return *this; + } + UnsignedFloat &operator-=(const UnsignedFloat &X) { + std::tie(Digits, Exponent) = + ScaledNumbers::getDifference(Digits, Exponent, X.Digits, X.Exponent); + return *this; + } UnsignedFloat &operator*=(const UnsignedFloat &X); UnsignedFloat &operator/=(const UnsignedFloat &X); UnsignedFloat &operator<<=(int16_t Shift) { shiftLeft(Shift); return *this; } @@ -401,65 +412,6 @@ IntT UnsignedFloat<DigitsT>::toInt() const { template <class DigitsT> UnsignedFloat<DigitsT> &UnsignedFloat<DigitsT>:: -operator+=(const UnsignedFloat &X) { - if (isLargest() || X.isZero()) - return *this; - if (isZero() || X.isLargest()) - return *this = X; - - // Normalize exponents. - UnsignedFloat Scaled = matchExponents(X); - - // Check for zero again. - if (isZero()) - return *this = Scaled; - if (Scaled.isZero()) - return *this; - - // Compute sum. - DigitsType Sum = Digits + Scaled.Digits; - bool DidOverflow = Sum < Digits; - Digits = Sum; - if (!DidOverflow) - return *this; - - if (Exponent == MaxExponent) - return *this = getLargest(); - - ++Exponent; - Digits = UINT64_C(1) << (Width - 1) | Digits >> 1; - - return *this; -} -template <class DigitsT> -UnsignedFloat<DigitsT> &UnsignedFloat<DigitsT>:: -operator-=(const UnsignedFloat &X) { - if (X.isZero()) - return *this; - if (*this <= X) - return *this = getZero(); - - // Normalize exponents. - UnsignedFloat Scaled = matchExponents(X); - assert(Digits >= Scaled.Digits); - - // Compute difference. - if (!Scaled.isZero()) { - Digits -= Scaled.Digits; - return *this; - } - - // Check if X just barely lost its last bit. E.g., for 32-bit: - // - // 1*2^32 - 1*2^0 == 0xffffffff != 1*2^32 - if (*this == UnsignedFloat(1, X.lgFloor() + Width)) { - Digits = DigitsType(0) - 1; - --Exponent; - } - return *this; -} -template <class DigitsT> -UnsignedFloat<DigitsT> &UnsignedFloat<DigitsT>:: operator*=(const UnsignedFloat &X) { if (isZero()) return *this; diff --git a/include/llvm/Support/ScaledNumber.h b/include/llvm/Support/ScaledNumber.h index caca5f731d..e8563cdeab 100644 --- a/include/llvm/Support/ScaledNumber.h +++ b/include/llvm/Support/ScaledNumber.h @@ -317,6 +317,93 @@ int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits, return LScale; } +/// \brief Get the sum of two scaled numbers. +/// +/// Get the sum of two scaled numbers with as much precision as possible. +/// +/// \pre Adding 1 to \c LScale (or \c RScale) will not overflow INT16_MAX. +template <class DigitsT> +std::pair<DigitsT, int16_t> getSum(DigitsT LDigits, int16_t LScale, + 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 + // testing here should catch more bugs. + assert(LScale < INT16_MAX && "scale too large"); + assert(RScale < INT16_MAX && "scale too large"); + + // Normalize digits to match scales. + int16_t Scale = matchScales(LDigits, LScale, RDigits, RScale); + + // Compute sum. + DigitsT Sum = LDigits + RDigits; + if (Sum >= RDigits) + return std::make_pair(Sum, Scale); + + // Adjust sum after arithmetic overflow. + DigitsT HighBit = DigitsT(1) << (getWidth<DigitsT>() - 1); + return std::make_pair(HighBit | Sum >> 1, Scale + 1); +} + +/// \brief Convenience helper for 32-bit sum. +inline std::pair<uint32_t, int16_t> getSum32(uint32_t LDigits, int16_t LScale, + uint32_t RDigits, int16_t RScale) { + return getSum(LDigits, LScale, RDigits, RScale); +} + +/// \brief Convenience helper for 64-bit sum. +inline std::pair<uint64_t, int16_t> getSum64(uint64_t LDigits, int16_t LScale, + uint64_t RDigits, int16_t RScale) { + return getSum(LDigits, LScale, RDigits, RScale); +} + +/// \brief Get the difference of two scaled numbers. +/// +/// Get LHS minus RHS with as much precision as possible. +/// +/// Returns \c (0, 0) if the RHS is larger than the LHS. +template <class DigitsT> +std::pair<DigitsT, int16_t> getDifference(DigitsT LDigits, int16_t LScale, + DigitsT RDigits, int16_t RScale) { + static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned"); + + // Normalize digits to match scales. + const DigitsT SavedRDigits = RDigits; + const int16_t SavedRScale = RScale; + matchScales(LDigits, LScale, RDigits, RScale); + + // Compute difference. + if (LDigits <= RDigits) + return std::make_pair(0, 0); + if (RDigits || !SavedRDigits) + return std::make_pair(LDigits - RDigits, LScale); + + // Check if RDigits just barely lost its last bit. E.g., for 32-bit: + // + // 1*2^32 - 1*2^0 == 0xffffffff != 1*2^32 + const auto RLgFloor = getLgFloor(SavedRDigits, SavedRScale); + if (!compare(LDigits, LScale, DigitsT(1), RLgFloor + getWidth<DigitsT>())) + return std::make_pair(std::numeric_limits<DigitsT>::max(), RLgFloor); + + return std::make_pair(LDigits, LScale); +} + +/// \brief Convenience helper for 32-bit sum. +inline std::pair<uint32_t, int16_t> getDifference32(uint32_t LDigits, + int16_t LScale, + uint32_t RDigits, + int16_t RScale) { + return getDifference(LDigits, LScale, RDigits, RScale); +} + +/// \brief Convenience helper for 64-bit sum. +inline std::pair<uint64_t, int16_t> getDifference64(uint64_t LDigits, + int16_t LScale, + uint64_t RDigits, + int16_t RScale) { + return getDifference(LDigits, LScale, RDigits, RScale); +} + } // end namespace ScaledNumbers } // end namespace llvm diff --git a/unittests/Support/ScaledNumberTest.cpp b/unittests/Support/ScaledNumberTest.cpp index 08d6c68b0e..48527e5d1b 100644 --- a/unittests/Support/ScaledNumberTest.cpp +++ b/unittests/Support/ScaledNumberTest.cpp @@ -386,4 +386,154 @@ TEST(ScaledNumberHelpersTest, matchScales) { MATCH_SCALES(uint64_t, 9, 0, UINT64_C(1) << 59, 4, 9, UINT64_C(1) << 63, 0); } +TEST(ScaledNumberHelpersTest, getSum) { + // Zero. + EXPECT_EQ(SP32(1, 0), getSum32(0, 0, 1, 0)); + EXPECT_EQ(SP32(8, -3), getSum32(0, 0, 8, -3)); + EXPECT_EQ(SP32(UINT32_MAX, 0), getSum32(0, 0, UINT32_MAX, 0)); + + // Basic. + EXPECT_EQ(SP32(2, 0), getSum32(1, 0, 1, 0)); + EXPECT_EQ(SP32(3, 0), getSum32(1, 0, 2, 0)); + EXPECT_EQ(SP32(67, 0), getSum32(7, 0, 60, 0)); + + // Different scales. + EXPECT_EQ(SP32(3, 0), getSum32(1, 0, 1, 1)); + EXPECT_EQ(SP32(4, 0), getSum32(2, 0, 1, 1)); + + // Loss of precision. + EXPECT_EQ(SP32(UINT32_C(1) << 31, 1), getSum32(1, 32, 1, 0)); + EXPECT_EQ(SP32(UINT32_C(1) << 31, -31), getSum32(1, -32, 1, 0)); + + // Not quite loss of precision. + EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, 1), getSum32(1, 32, 1, 1)); + EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, -32), getSum32(1, -32, 1, -1)); + + // Overflow. + EXPECT_EQ(SP32(UINT32_C(1) << 31, 1), getSum32(1, 0, UINT32_MAX, 0)); + + // Reverse operand order. + EXPECT_EQ(SP32(1, 0), getSum32(1, 0, 0, 0)); + EXPECT_EQ(SP32(8, -3), getSum32(8, -3, 0, 0)); + EXPECT_EQ(SP32(UINT32_MAX, 0), getSum32(UINT32_MAX, 0, 0, 0)); + EXPECT_EQ(SP32(3, 0), getSum32(2, 0, 1, 0)); + EXPECT_EQ(SP32(67, 0), getSum32(60, 0, 7, 0)); + EXPECT_EQ(SP32(3, 0), getSum32(1, 1, 1, 0)); + EXPECT_EQ(SP32(4, 0), getSum32(1, 1, 2, 0)); + EXPECT_EQ(SP32(UINT32_C(1) << 31, 1), getSum32(1, 0, 1, 32)); + EXPECT_EQ(SP32(UINT32_C(1) << 31, -31), getSum32(1, 0, 1, -32)); + EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, 1), getSum32(1, 1, 1, 32)); + EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, -32), getSum32(1, -1, 1, -32)); + EXPECT_EQ(SP32(UINT32_C(1) << 31, 1), getSum32(UINT32_MAX, 0, 1, 0)); + + // Zero. + EXPECT_EQ(SP64(1, 0), getSum64(0, 0, 1, 0)); + EXPECT_EQ(SP64(8, -3), getSum64(0, 0, 8, -3)); + EXPECT_EQ(SP64(UINT64_MAX, 0), getSum64(0, 0, UINT64_MAX, 0)); + + // Basic. + EXPECT_EQ(SP64(2, 0), getSum64(1, 0, 1, 0)); + EXPECT_EQ(SP64(3, 0), getSum64(1, 0, 2, 0)); + EXPECT_EQ(SP64(67, 0), getSum64(7, 0, 60, 0)); + + // Different scales. + EXPECT_EQ(SP64(3, 0), getSum64(1, 0, 1, 1)); + EXPECT_EQ(SP64(4, 0), getSum64(2, 0, 1, 1)); + + // Loss of precision. + EXPECT_EQ(SP64(UINT64_C(1) << 63, 1), getSum64(1, 64, 1, 0)); + EXPECT_EQ(SP64(UINT64_C(1) << 63, -63), getSum64(1, -64, 1, 0)); + + // Not quite loss of precision. + EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, 1), getSum64(1, 64, 1, 1)); + EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, -64), getSum64(1, -64, 1, -1)); + + // Overflow. + EXPECT_EQ(SP64(UINT64_C(1) << 63, 1), getSum64(1, 0, UINT64_MAX, 0)); + + // Reverse operand order. + EXPECT_EQ(SP64(1, 0), getSum64(1, 0, 0, 0)); + EXPECT_EQ(SP64(8, -3), getSum64(8, -3, 0, 0)); + EXPECT_EQ(SP64(UINT64_MAX, 0), getSum64(UINT64_MAX, 0, 0, 0)); + EXPECT_EQ(SP64(3, 0), getSum64(2, 0, 1, 0)); + EXPECT_EQ(SP64(67, 0), getSum64(60, 0, 7, 0)); + EXPECT_EQ(SP64(3, 0), getSum64(1, 1, 1, 0)); + EXPECT_EQ(SP64(4, 0), getSum64(1, 1, 2, 0)); + EXPECT_EQ(SP64(UINT64_C(1) << 63, 1), getSum64(1, 0, 1, 64)); + EXPECT_EQ(SP64(UINT64_C(1) << 63, -63), getSum64(1, 0, 1, -64)); + EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, 1), getSum64(1, 1, 1, 64)); + EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, -64), getSum64(1, -1, 1, -64)); + EXPECT_EQ(SP64(UINT64_C(1) << 63, 1), getSum64(UINT64_MAX, 0, 1, 0)); +} + +TEST(ScaledNumberHelpersTest, getDifference) { + // Basic. + EXPECT_EQ(SP32(0, 0), getDifference32(1, 0, 1, 0)); + EXPECT_EQ(SP32(1, 0), getDifference32(2, 0, 1, 0)); + EXPECT_EQ(SP32(53, 0), getDifference32(60, 0, 7, 0)); + + // Equals "0", different scales. + EXPECT_EQ(SP32(0, 0), getDifference32(2, 0, 1, 1)); + + // Subtract "0". + EXPECT_EQ(SP32(1, 0), getDifference32(1, 0, 0, 0)); + EXPECT_EQ(SP32(8, -3), getDifference32(8, -3, 0, 0)); + EXPECT_EQ(SP32(UINT32_MAX, 0), getDifference32(UINT32_MAX, 0, 0, 0)); + + // Loss of precision. + EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, 1), + getDifference32((UINT32_C(1) << 31) + 1, 1, 1, 0)); + EXPECT_EQ(SP32((UINT32_C(1) << 31) + 1, -31), + getDifference32((UINT32_C(1) << 31) + 1, -31, 1, -32)); + + // Not quite loss of precision. + EXPECT_EQ(SP32(UINT32_MAX, 0), getDifference32(1, 32, 1, 0)); + EXPECT_EQ(SP32(UINT32_MAX, -32), getDifference32(1, 0, 1, -32)); + + // Saturate to "0". + EXPECT_EQ(SP32(0, 0), getDifference32(0, 0, 1, 0)); + EXPECT_EQ(SP32(0, 0), getDifference32(0, 0, 8, -3)); + EXPECT_EQ(SP32(0, 0), getDifference32(0, 0, UINT32_MAX, 0)); + EXPECT_EQ(SP32(0, 0), getDifference32(7, 0, 60, 0)); + EXPECT_EQ(SP32(0, 0), getDifference32(1, 0, 1, 1)); + EXPECT_EQ(SP32(0, 0), getDifference32(1, -32, 1, 0)); + EXPECT_EQ(SP32(0, 0), getDifference32(1, -32, 1, -1)); + + // Regression tests for cases that failed during bringup. + EXPECT_EQ(SP32(UINT32_C(1) << 26, -31), + getDifference32(1, 0, UINT32_C(31) << 27, -32)); + + // Basic. + EXPECT_EQ(SP64(0, 0), getDifference64(1, 0, 1, 0)); + EXPECT_EQ(SP64(1, 0), getDifference64(2, 0, 1, 0)); + EXPECT_EQ(SP64(53, 0), getDifference64(60, 0, 7, 0)); + + // Equals "0", different scales. + EXPECT_EQ(SP64(0, 0), getDifference64(2, 0, 1, 1)); + + // Subtract "0". + EXPECT_EQ(SP64(1, 0), getDifference64(1, 0, 0, 0)); + EXPECT_EQ(SP64(8, -3), getDifference64(8, -3, 0, 0)); + EXPECT_EQ(SP64(UINT64_MAX, 0), getDifference64(UINT64_MAX, 0, 0, 0)); + + // Loss of precision. + EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, 1), + getDifference64((UINT64_C(1) << 63) + 1, 1, 1, 0)); + EXPECT_EQ(SP64((UINT64_C(1) << 63) + 1, -63), + getDifference64((UINT64_C(1) << 63) + 1, -63, 1, -64)); + + // Not quite loss of precision. + EXPECT_EQ(SP64(UINT64_MAX, 0), getDifference64(1, 64, 1, 0)); + EXPECT_EQ(SP64(UINT64_MAX, -64), getDifference64(1, 0, 1, -64)); + + // Saturate to "0". + EXPECT_EQ(SP64(0, 0), getDifference64(0, 0, 1, 0)); + EXPECT_EQ(SP64(0, 0), getDifference64(0, 0, 8, -3)); + EXPECT_EQ(SP64(0, 0), getDifference64(0, 0, UINT64_MAX, 0)); + EXPECT_EQ(SP64(0, 0), getDifference64(7, 0, 60, 0)); + EXPECT_EQ(SP64(0, 0), getDifference64(1, 0, 1, 1)); + EXPECT_EQ(SP64(0, 0), getDifference64(1, -64, 1, 0)); + EXPECT_EQ(SP64(0, 0), getDifference64(1, -64, 1, -1)); +} + } // end namespace |