From 9575d8ff364e79200177fb7f9ee93325308a83e6 Mon Sep 17 00:00:00 2001 From: Craig Topper Date: Mon, 17 Apr 2017 21:43:43 +0000 Subject: [PATCH] [APInt] Merge the multiword code from lshrInPlace and tcShiftRight into a single implementation This merges the two different multiword shift right implementations into a single version located in tcShiftRight. lshrInPlace now calls tcShiftRight for the multiword case. I retained the memmove fast path from lshrInPlace and used a memset for the zeroing. The for loop is basically tcShiftRight's implementation with the zeroing and the intra-shift of 0 removed. Differential Revision: https://reviews.llvm.org/D32114 llvm-svn: 300503 --- llvm/include/llvm/ADT/APInt.h | 10 ++--- llvm/lib/Support/APInt.cpp | 93 +++++++++++----------------------------- llvm/unittests/ADT/APIntTest.cpp | 38 +++++++++++++--- 3 files changed, 63 insertions(+), 78 deletions(-) diff --git a/llvm/include/llvm/ADT/APInt.h b/llvm/include/llvm/ADT/APInt.h index 92aa08d..1838db4 100644 --- a/llvm/include/llvm/ADT/APInt.h +++ b/llvm/include/llvm/ADT/APInt.h @@ -881,8 +881,8 @@ public: return R; } - /// Logical right-shift this APInt by shiftAmt in place. - void lshrInPlace(unsigned shiftAmt); + /// Logical right-shift this APInt by ShiftAmt in place. + void lshrInPlace(unsigned ShiftAmt); /// \brief Left-shift function. /// @@ -1769,9 +1769,9 @@ public: /// restrictions on COUNT. static void tcShiftLeft(WordType *, unsigned parts, unsigned count); - /// Shift a bignum right COUNT bits. Shifted in bits are zero. There are no - /// restrictions on COUNT. - static void tcShiftRight(WordType *, unsigned parts, unsigned count); + /// Shift a bignum right Count bits. Shifted in bits are zero. There are no + /// restrictions on Count. + static void tcShiftRight(WordType *, unsigned Words, unsigned Count); /// The obvious AND, OR and XOR and complement operations. static void tcAnd(WordType *, const WordType *, unsigned); diff --git a/llvm/lib/Support/APInt.cpp b/llvm/lib/Support/APInt.cpp index 0c7da1d..1d04f3b 100644 --- a/llvm/lib/Support/APInt.cpp +++ b/llvm/lib/Support/APInt.cpp @@ -1140,59 +1140,18 @@ APInt APInt::lshr(const APInt &shiftAmt) const { return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth)); } -/// Perform a logical right-shift from Src to Dst of Words words, by Shift, -/// which must be less than 64. If the source and destination ranges overlap, -/// we require that Src >= Dst (put another way, we require that the overall -/// operation is a right shift on the combined range). -static void lshrWords(APInt::WordType *Dst, APInt::WordType *Src, - unsigned Words, unsigned Shift) { - assert(Shift < APInt::APINT_BITS_PER_WORD); - - if (!Words) - return; - - if (Shift == 0) { - std::memmove(Dst, Src, Words * APInt::APINT_WORD_SIZE); - return; - } - - uint64_t Low = Src[0]; - for (unsigned I = 1; I != Words; ++I) { - uint64_t High = Src[I]; - Dst[I - 1] = - (Low >> Shift) | (High << (APInt::APINT_BITS_PER_WORD - Shift)); - Low = High; - } - Dst[Words - 1] = Low >> Shift; -} - /// Logical right-shift this APInt by shiftAmt. /// @brief Logical right-shift function. -void APInt::lshrInPlace(unsigned shiftAmt) { +void APInt::lshrInPlace(unsigned ShiftAmt) { if (isSingleWord()) { - if (shiftAmt >= BitWidth) + if (ShiftAmt >= BitWidth) VAL = 0; else - VAL >>= shiftAmt; + VAL >>= ShiftAmt; return; } - // Don't bother performing a no-op shift. - if (!shiftAmt) - return; - - // Find number of complete words being shifted out and zeroed. - const unsigned Words = getNumWords(); - const unsigned ShiftFullWords = - std::min(shiftAmt / APINT_BITS_PER_WORD, Words); - - // Fill in first Words - ShiftFullWords by shifting. - lshrWords(pVal, pVal + ShiftFullWords, Words - ShiftFullWords, - shiftAmt % APINT_BITS_PER_WORD); - - // The remaining high words are all zero. - for (unsigned I = Words - ShiftFullWords; I != Words; ++I) - pVal[I] = 0; + return tcShiftRight(pVal, getNumWords(), ShiftAmt); } /// Left-shift this APInt by shiftAmt. @@ -2728,33 +2687,31 @@ void APInt::tcShiftLeft(WordType *dst, unsigned parts, unsigned count) { } } -/* Shift a bignum right COUNT bits in-place. Shifted in bits are - zero. There are no restrictions on COUNT. */ -void APInt::tcShiftRight(WordType *dst, unsigned parts, unsigned count) { - if (count) { - /* Jump is the inter-part jump; shift is is intra-part shift. */ - unsigned jump = count / APINT_BITS_PER_WORD; - unsigned shift = count % APINT_BITS_PER_WORD; - - /* Perform the shift. This leaves the most significant COUNT bits - of the result at zero. */ - for (unsigned i = 0; i < parts; i++) { - WordType part; +/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There +/// are no restrictions on Count. +void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) { + // Don't bother performing a no-op shift. + if (!Count) + return; - if (i + jump >= parts) { - part = 0; - } else { - part = dst[i + jump]; - if (shift) { - part >>= shift; - if (i + jump + 1 < parts) - part |= dst[i + jump + 1] << (APINT_BITS_PER_WORD - shift); - } - } + // WordShift is the inter-part shift; BitShift is is intra-part shift. + unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words); + unsigned BitShift = Count % APINT_BITS_PER_WORD; - dst[i] = part; + unsigned WordsToMove = Words - WordShift; + // Fastpath for moving by whole words. + if (BitShift == 0) { + std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE); + } else { + for (unsigned i = 0; i != WordsToMove; ++i) { + Dst[i] = Dst[i + WordShift] >> BitShift; + if (i + 1 != WordsToMove) + Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift); } } + + // Fill in the remainder with 0s. + std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE); } /* Bitwise and of two bignums. */ diff --git a/llvm/unittests/ADT/APIntTest.cpp b/llvm/unittests/ADT/APIntTest.cpp index d24d580..0bd309d 100644 --- a/llvm/unittests/ADT/APIntTest.cpp +++ b/llvm/unittests/ADT/APIntTest.cpp @@ -37,11 +37,6 @@ TEST(APIntTest, i64_ArithmeticRightShiftNegative) { EXPECT_EQ(neg_one, neg_one.ashr(7)); } -TEST(APIntTest, i64_LogicalRightShiftNegative) { - const APInt neg_one(128, static_cast(-1), true); - EXPECT_EQ(0, neg_one.lshr(257)); -} - TEST(APIntTest, i128_NegativeCount) { APInt Minus3(128, static_cast(-3), true); EXPECT_EQ(126u, Minus3.countLeadingOnes()); @@ -1996,4 +1991,37 @@ TEST(APIntTest, GCD) { EXPECT_EQ(C, HugePrime); } +TEST(APIntTest, LogicalRightShift) { + APInt i256(APInt::getHighBitsSet(256, 2)); + + i256.lshrInPlace(1); + EXPECT_EQ(1U, i256.countLeadingZeros()); + EXPECT_EQ(253U, i256.countTrailingZeros()); + EXPECT_EQ(2U, i256.countPopulation()); + + i256.lshrInPlace(62); + EXPECT_EQ(63U, i256.countLeadingZeros()); + EXPECT_EQ(191U, i256.countTrailingZeros()); + EXPECT_EQ(2U, i256.countPopulation()); + + i256.lshrInPlace(65); + EXPECT_EQ(128U, i256.countLeadingZeros()); + EXPECT_EQ(126U, i256.countTrailingZeros()); + EXPECT_EQ(2U, i256.countPopulation()); + + i256.lshrInPlace(64); + EXPECT_EQ(192U, i256.countLeadingZeros()); + EXPECT_EQ(62U, i256.countTrailingZeros()); + EXPECT_EQ(2U, i256.countPopulation()); + + i256.lshrInPlace(63); + EXPECT_EQ(255U, i256.countLeadingZeros()); + EXPECT_EQ(0U, i256.countTrailingZeros()); + EXPECT_EQ(1U, i256.countPopulation()); + + // Ensure we handle large shifts of multi-word. + const APInt neg_one(128, static_cast(-1), true); + EXPECT_EQ(0, neg_one.lshr(257)); +} + } // end anonymous namespace -- 2.7.4