summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/BlockFrequencyInfoImpl.h40
-rw-r--r--include/llvm/Support/ScaledNumber.h56
-rw-r--r--unittests/Support/ScaledNumberTest.cpp94
3 files changed, 157 insertions, 33 deletions
diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
index df4ebcad33..7944af9533 100644
--- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h
+++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h
@@ -67,16 +67,6 @@ public:
return IsNeg ? -int64_t(U) : int64_t(U);
}
- static int32_t extractLg(const std::pair<int32_t, int> &Lg) {
- return Lg.first;
- }
- static int32_t extractLgFloor(const std::pair<int32_t, int> &Lg) {
- return Lg.first - (Lg.second > 0);
- }
- static int32_t extractLgCeiling(const std::pair<int32_t, int> &Lg) {
- return Lg.first + (Lg.second < 0);
- }
-
static int compare(uint64_t L, uint64_t R, int Shift) {
assert(Shift >= 0);
assert(Shift < 64);
@@ -195,17 +185,21 @@ public:
/// \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 extractLg(lgImpl()); }
+ int32_t lg() const { return ScaledNumbers::getLg(Digits, Exponent); }
/// \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 extractLgFloor(lgImpl()); }
+ int32_t lgFloor() const {
+ return ScaledNumbers::getLgFloor(Digits, Exponent);
+ }
/// \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 extractLgCeiling(lgImpl()); }
+ int32_t lgCeiling() const {
+ return ScaledNumbers::getLgCeiling(Digits, Exponent);
+ }
bool operator==(const UnsignedFloat &X) const { return compare(X) == 0; }
bool operator<(const UnsignedFloat &X) const { return compare(X) < 0; }
@@ -319,7 +313,6 @@ private:
return ScaledNumbers::getQuotient(Dividend, Divisor);
}
- std::pair<int32_t, int> lgImpl() const;
static int countLeadingZerosWidth(DigitsType Digits) {
if (Width == 64)
return countLeadingZeros64(Digits);
@@ -422,25 +415,6 @@ IntT UnsignedFloat<DigitsT>::toInt() const {
}
template <class DigitsT>
-std::pair<int32_t, int> UnsignedFloat<DigitsT>::lgImpl() const {
- if (isZero())
- return std::make_pair(INT32_MIN, 0);
-
- // Get the floor of the lg of Digits.
- int32_t LocalFloor = Width - countLeadingZerosWidth(Digits) - 1;
-
- // Get the floor of the lg of this.
- int32_t Floor = Exponent + LocalFloor;
- if (Digits == UINT64_C(1) << LocalFloor)
- return std::make_pair(Floor, 0);
-
- // Round based on the next digit.
- assert(LocalFloor >= 1);
- bool Round = Digits & UINT64_C(1) << (LocalFloor - 1);
- return std::make_pair(Floor + Round, Round ? 1 : -1);
-}
-
-template <class DigitsT>
UnsignedFloat<DigitsT> UnsignedFloat<DigitsT>::matchExponents(UnsignedFloat X) {
if (isZero() || X.isZero() || Exponent == X.Exponent)
return X;
diff --git a/include/llvm/Support/ScaledNumber.h b/include/llvm/Support/ScaledNumber.h
index 6789b89f7e..6d563fba1e 100644
--- a/include/llvm/Support/ScaledNumber.h
+++ b/include/llvm/Support/ScaledNumber.h
@@ -171,6 +171,62 @@ inline std::pair<uint64_t, int16_t> getQuotient64(uint64_t Dividend,
return getQuotient(Dividend, Divisor);
}
+/// \brief Implementation of getLg() and friends.
+///
+/// Returns the rounded lg of \c Digits*2^Scale and an int specifying whether
+/// this was rounded up (1), down (-1), or exact (0).
+///
+/// Returns \c INT32_MIN when \c Digits is zero.
+template <class DigitsT>
+inline std::pair<int32_t, int> getLgImpl(DigitsT Digits, int16_t Scale) {
+ static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
+
+ if (!Digits)
+ return std::make_pair(INT32_MIN, 0);
+
+ // Get the floor of the lg of Digits.
+ int32_t LocalFloor = sizeof(Digits) * 8 - countLeadingZeros(Digits) - 1;
+
+ // Get the actual floor.
+ int32_t Floor = Scale + LocalFloor;
+ if (Digits == UINT64_C(1) << LocalFloor)
+ return std::make_pair(Floor, 0);
+
+ // Round based on the next digit.
+ assert(LocalFloor >= 1);
+ bool Round = Digits & UINT64_C(1) << (LocalFloor - 1);
+ return std::make_pair(Floor + Round, Round ? 1 : -1);
+}
+
+/// \brief Get the lg (rounded) of a scaled number.
+///
+/// Get the lg of \c Digits*2^Scale.
+///
+/// Returns \c INT32_MIN when \c Digits is zero.
+template <class DigitsT> int32_t getLg(DigitsT Digits, int16_t Scale) {
+ return getLgImpl(Digits, Scale).first;
+}
+
+/// \brief Get the lg floor of a scaled number.
+///
+/// Get the floor of the lg of \c Digits*2^Scale.
+///
+/// Returns \c INT32_MIN when \c Digits is zero.
+template <class DigitsT> int32_t getLgFloor(DigitsT Digits, int16_t Scale) {
+ auto Lg = getLgImpl(Digits, Scale);
+ return Lg.first - (Lg.second > 0);
+}
+
+/// \brief Get the lg ceiling of a scaled number.
+///
+/// Get the ceiling of the lg of \c Digits*2^Scale.
+///
+/// Returns \c INT32_MIN when \c Digits is zero.
+template <class DigitsT> int32_t getLgCeiling(DigitsT Digits, int16_t Scale) {
+ auto Lg = getLgImpl(Digits, Scale);
+ return Lg.first + (Lg.second < 0);
+}
+
} // end namespace ScaledNumbers
} // end namespace llvm
diff --git a/unittests/Support/ScaledNumberTest.cpp b/unittests/Support/ScaledNumberTest.cpp
index 6f7cc2a14b..db8101cc26 100644
--- a/unittests/Support/ScaledNumberTest.cpp
+++ b/unittests/Support/ScaledNumberTest.cpp
@@ -191,4 +191,98 @@ TEST(PositiveFloatTest, Divide) {
EXPECT_EQ(SP64(0xd555555555555555, -63), getQuotient64(5, 3));
}
+TEST(ScaledNumbersHelpersTest, getLg) {
+ EXPECT_EQ(0, getLg(UINT32_C(1), 0));
+ EXPECT_EQ(1, getLg(UINT32_C(1), 1));
+ EXPECT_EQ(1, getLg(UINT32_C(2), 0));
+ EXPECT_EQ(3, getLg(UINT32_C(1), 3));
+ EXPECT_EQ(3, getLg(UINT32_C(7), 0));
+ EXPECT_EQ(3, getLg(UINT32_C(8), 0));
+ EXPECT_EQ(3, getLg(UINT32_C(9), 0));
+ EXPECT_EQ(3, getLg(UINT32_C(64), -3));
+ EXPECT_EQ(31, getLg((UINT32_MAX >> 1) + 2, 0));
+ EXPECT_EQ(32, getLg(UINT32_MAX, 0));
+ EXPECT_EQ(-1, getLg(UINT32_C(1), -1));
+ EXPECT_EQ(-1, getLg(UINT32_C(2), -2));
+ EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), -1));
+ EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), 0));
+ EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), 1));
+
+ EXPECT_EQ(0, getLg(UINT64_C(1), 0));
+ EXPECT_EQ(1, getLg(UINT64_C(1), 1));
+ EXPECT_EQ(1, getLg(UINT64_C(2), 0));
+ EXPECT_EQ(3, getLg(UINT64_C(1), 3));
+ EXPECT_EQ(3, getLg(UINT64_C(7), 0));
+ EXPECT_EQ(3, getLg(UINT64_C(8), 0));
+ EXPECT_EQ(3, getLg(UINT64_C(9), 0));
+ EXPECT_EQ(3, getLg(UINT64_C(64), -3));
+ EXPECT_EQ(63, getLg((UINT64_MAX >> 1) + 2, 0));
+ EXPECT_EQ(64, getLg(UINT64_MAX, 0));
+ EXPECT_EQ(-1, getLg(UINT64_C(1), -1));
+ EXPECT_EQ(-1, getLg(UINT64_C(2), -2));
+ EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), -1));
+ EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), 0));
+ EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), 1));
+}
+
+TEST(ScaledNumbersHelpersTest, getLgFloor) {
+ EXPECT_EQ(0, getLgFloor(UINT32_C(1), 0));
+ EXPECT_EQ(1, getLgFloor(UINT32_C(1), 1));
+ EXPECT_EQ(1, getLgFloor(UINT32_C(2), 0));
+ EXPECT_EQ(2, getLgFloor(UINT32_C(7), 0));
+ EXPECT_EQ(3, getLgFloor(UINT32_C(1), 3));
+ EXPECT_EQ(3, getLgFloor(UINT32_C(8), 0));
+ EXPECT_EQ(3, getLgFloor(UINT32_C(9), 0));
+ EXPECT_EQ(3, getLgFloor(UINT32_C(64), -3));
+ EXPECT_EQ(31, getLgFloor((UINT32_MAX >> 1) + 2, 0));
+ EXPECT_EQ(31, getLgFloor(UINT32_MAX, 0));
+ EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), -1));
+ EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), 0));
+ EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), 1));
+
+ EXPECT_EQ(0, getLgFloor(UINT64_C(1), 0));
+ EXPECT_EQ(1, getLgFloor(UINT64_C(1), 1));
+ EXPECT_EQ(1, getLgFloor(UINT64_C(2), 0));
+ EXPECT_EQ(2, getLgFloor(UINT64_C(7), 0));
+ EXPECT_EQ(3, getLgFloor(UINT64_C(1), 3));
+ EXPECT_EQ(3, getLgFloor(UINT64_C(8), 0));
+ EXPECT_EQ(3, getLgFloor(UINT64_C(9), 0));
+ EXPECT_EQ(3, getLgFloor(UINT64_C(64), -3));
+ EXPECT_EQ(63, getLgFloor((UINT64_MAX >> 1) + 2, 0));
+ EXPECT_EQ(63, getLgFloor(UINT64_MAX, 0));
+ EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), -1));
+ EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), 0));
+ EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), 1));
+}
+
+TEST(ScaledNumbersHelpersTest, getLgCeiling) {
+ EXPECT_EQ(0, getLgCeiling(UINT32_C(1), 0));
+ EXPECT_EQ(1, getLgCeiling(UINT32_C(1), 1));
+ EXPECT_EQ(1, getLgCeiling(UINT32_C(2), 0));
+ EXPECT_EQ(3, getLgCeiling(UINT32_C(1), 3));
+ EXPECT_EQ(3, getLgCeiling(UINT32_C(7), 0));
+ EXPECT_EQ(3, getLgCeiling(UINT32_C(8), 0));
+ EXPECT_EQ(3, getLgCeiling(UINT32_C(64), -3));
+ EXPECT_EQ(4, getLgCeiling(UINT32_C(9), 0));
+ EXPECT_EQ(32, getLgCeiling(UINT32_MAX, 0));
+ EXPECT_EQ(32, getLgCeiling((UINT32_MAX >> 1) + 2, 0));
+ EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), -1));
+ EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), 0));
+ EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), 1));
+
+ EXPECT_EQ(0, getLgCeiling(UINT64_C(1), 0));
+ EXPECT_EQ(1, getLgCeiling(UINT64_C(1), 1));
+ EXPECT_EQ(1, getLgCeiling(UINT64_C(2), 0));
+ EXPECT_EQ(3, getLgCeiling(UINT64_C(1), 3));
+ EXPECT_EQ(3, getLgCeiling(UINT64_C(7), 0));
+ EXPECT_EQ(3, getLgCeiling(UINT64_C(8), 0));
+ EXPECT_EQ(3, getLgCeiling(UINT64_C(64), -3));
+ EXPECT_EQ(4, getLgCeiling(UINT64_C(9), 0));
+ EXPECT_EQ(64, getLgCeiling((UINT64_MAX >> 1) + 2, 0));
+ EXPECT_EQ(64, getLgCeiling(UINT64_MAX, 0));
+ EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), -1));
+ EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), 0));
+ EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), 1));
+}
+
} // end namespace
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-27 07:28:08 +0000