From 18a301e5788cbc7f0e1bcc2567d3a1d76fb4bf2a Mon Sep 17 00:00:00 2001 From: "Duncan P. N. Exon Smith" Date: Mon, 23 Jun 2014 17:47:40 +0000 Subject: [PATCH] Support: Extract ScaledNumbers::compare() git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211507 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../llvm/Analysis/BlockFrequencyInfoImpl.h | 38 ++----------------- include/llvm/Support/ScaledNumber.h | 34 +++++++++++++++++ lib/Support/ScaledNumber.cpp | 13 +++++++ unittests/Support/ScaledNumberTest.cpp | 37 ++++++++++++++++++ 4 files changed, 87 insertions(+), 35 deletions(-) diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h index 7944af9533a..054f26b1824 100644 --- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h +++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h @@ -66,19 +66,6 @@ public: return IsNeg ? INT64_MIN : INT64_MAX; return IsNeg ? -int64_t(U) : int64_t(U); } - - static int compare(uint64_t L, uint64_t R, int Shift) { - assert(Shift >= 0); - assert(Shift < 64); - - uint64_t L_adjusted = L >> Shift; - if (L_adjusted < R) - return -1; - if (L_adjusted > R) - return 1; - - return L > L_adjusted << Shift ? 1 : 0; - } }; /// \brief Simple representation of an unsigned floating point. @@ -289,7 +276,9 @@ public: return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second); } - int compare(const UnsignedFloat &X) const; + int compare(const UnsignedFloat &X) const { + return ScaledNumbers::compare(Digits, Exponent, X.Digits, X.Exponent); + } int compareTo(uint64_t N) const { UnsignedFloat Float = getFloat(N); int Compare = compare(Float); @@ -605,27 +594,6 @@ void UnsignedFloat::shiftRight(int32_t Shift) { return; } -template -int UnsignedFloat::compare(const UnsignedFloat &X) const { - // Check for zero. - if (isZero()) - return X.isZero() ? 0 : -1; - if (X.isZero()) - return 1; - - // Check for the scale. Use lgFloor to be sure that the exponent difference - // is always lower than 64. - int32_t lgL = lgFloor(), lgR = X.lgFloor(); - if (lgL != lgR) - return lgL < lgR ? -1 : 1; - - // Compare digits. - if (Exponent < X.Exponent) - return UnsignedFloatBase::compare(Digits, X.Digits, X.Exponent - Exponent); - - return -UnsignedFloatBase::compare(X.Digits, Digits, Exponent - X.Exponent); -} - template struct isPodLike> { static const bool value = true; }; diff --git a/include/llvm/Support/ScaledNumber.h b/include/llvm/Support/ScaledNumber.h index 1acc4b1b163..6a93623a8e9 100644 --- a/include/llvm/Support/ScaledNumber.h +++ b/include/llvm/Support/ScaledNumber.h @@ -227,6 +227,40 @@ template int32_t getLgCeiling(DigitsT Digits, int16_t Scale) { return Lg.first + (Lg.second < 0); } +/// \brief Implementation for comparing scaled numbers. +/// +/// Compare two 64-bit numbers with different scales. Given that the scale of +/// \c L is higher than that of \c R by \c ScaleDiff, compare them. Return -1, +/// 1, and 0 for less than, greater than, and equal, respectively. +/// +/// \pre 0 <= ScaleDiff < 64. +int compareImpl(uint64_t L, uint64_t R, int ScaleDiff); + +/// \brief Compare two scaled numbers. +/// +/// Compare two scaled numbers. Returns 0 for equal, -1 for less than, and 1 +/// for greater than. +template +int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale) { + // Check for zero. + if (!LDigits) + return RDigits ? -1 : 0; + if (!RDigits) + return 1; + + // Check for the scale. Use getLgFloor to be sure that the scale difference + // is always lower than 64. + int32_t lgL = getLgFloor(LDigits, LScale), lgR = getLgFloor(RDigits, RScale); + if (lgL != lgR) + return lgL < lgR ? -1 : 1; + + // Compare digits. + if (LScale < RScale) + return compareImpl(LDigits, RDigits, RScale - LScale); + + return -compareImpl(RDigits, LDigits, LScale - RScale); +} + } // end namespace ScaledNumbers } // end namespace llvm diff --git a/lib/Support/ScaledNumber.cpp b/lib/Support/ScaledNumber.cpp index e7531744b67..10b23273d0f 100644 --- a/lib/Support/ScaledNumber.cpp +++ b/lib/Support/ScaledNumber.cpp @@ -117,3 +117,16 @@ std::pair ScaledNumbers::divide64(uint64_t Dividend, return getRounded(Quotient, Shift, Dividend >= getHalf(Divisor)); } + +int ScaledNumbers::compareImpl(uint64_t L, uint64_t R, int ScaleDiff) { + assert(ScaleDiff >= 0 && "wrong argument order"); + assert(ScaleDiff < 64 && "numbers too far apart"); + + uint64_t L_adjusted = L >> ScaleDiff; + if (L_adjusted < R) + return -1; + if (L_adjusted > R) + return 1; + + return L > L_adjusted << ScaleDiff ? 1 : 0; +} diff --git a/unittests/Support/ScaledNumberTest.cpp b/unittests/Support/ScaledNumberTest.cpp index cd3d6fa9c8c..f6d7a44754f 100644 --- a/unittests/Support/ScaledNumberTest.cpp +++ b/unittests/Support/ScaledNumberTest.cpp @@ -285,4 +285,41 @@ TEST(ScaledNumberHelpersTest, getLgCeiling) { EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), 1)); } +TEST(ScaledNumberHelpersTest, Compare) { + EXPECT_EQ(0, compare(UINT32_C(0), 0, UINT32_C(0), 1)); + EXPECT_EQ(0, compare(UINT32_C(0), 0, UINT32_C(0), -10)); + EXPECT_EQ(0, compare(UINT32_C(0), 0, UINT32_C(0), 20)); + EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(64), -3)); + EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(32), -2)); + EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(16), -1)); + EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(8), 0)); + EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(4), 1)); + EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(2), 2)); + EXPECT_EQ(0, compare(UINT32_C(8), 0, UINT32_C(1), 3)); + EXPECT_EQ(-1, compare(UINT32_C(0), 0, UINT32_C(1), 3)); + EXPECT_EQ(-1, compare(UINT32_C(7), 0, UINT32_C(1), 3)); + EXPECT_EQ(-1, compare(UINT32_C(7), 0, UINT32_C(64), -3)); + EXPECT_EQ(1, compare(UINT32_C(9), 0, UINT32_C(1), 3)); + EXPECT_EQ(1, compare(UINT32_C(9), 0, UINT32_C(64), -3)); + EXPECT_EQ(1, compare(UINT32_C(9), 0, UINT32_C(0), 0)); + + EXPECT_EQ(0, compare(UINT64_C(0), 0, UINT64_C(0), 1)); + EXPECT_EQ(0, compare(UINT64_C(0), 0, UINT64_C(0), -10)); + EXPECT_EQ(0, compare(UINT64_C(0), 0, UINT64_C(0), 20)); + EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(64), -3)); + EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(32), -2)); + EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(16), -1)); + EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(8), 0)); + EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(4), 1)); + EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(2), 2)); + EXPECT_EQ(0, compare(UINT64_C(8), 0, UINT64_C(1), 3)); + EXPECT_EQ(-1, compare(UINT64_C(0), 0, UINT64_C(1), 3)); + EXPECT_EQ(-1, compare(UINT64_C(7), 0, UINT64_C(1), 3)); + EXPECT_EQ(-1, compare(UINT64_C(7), 0, UINT64_C(64), -3)); + EXPECT_EQ(1, compare(UINT64_C(9), 0, UINT64_C(1), 3)); + EXPECT_EQ(1, compare(UINT64_C(9), 0, UINT64_C(64), -3)); + EXPECT_EQ(1, compare(UINT64_C(9), 0, UINT64_C(0), 0)); + EXPECT_EQ(-1, compare(UINT64_MAX, 0, UINT64_C(1), 64)); +} + } // end namespace -- 2.34.1