From 4bf2830a0102e7accd195127b1d7bf9b4a364ab0 Mon Sep 17 00:00:00 2001 From: Craig Topper Date: Tue, 18 Apr 2017 04:39:48 +0000 Subject: [PATCH] [APInt] Make operator<<= shift in place. Improve the implementation of tcShiftLeft and use it to implement operator<<=. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@300526 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/APInt.h | 31 ++++++----- lib/Support/APInt.cpp | 102 +++++++++--------------------------- unittests/ADT/APIntTest.cpp | 33 ++++++++++++ 3 files changed, 74 insertions(+), 92 deletions(-) diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index 1838db458a2..de097811ceb 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -189,7 +189,7 @@ private: void initSlowCase(const APInt &that); /// out-of-line slow case for shl - APInt shlSlowCase(unsigned shiftAmt) const; + void shlSlowCase(unsigned ShiftAmt); /// out-of-line slow case for operator= APInt &AssignSlowCase(const APInt &RHS); @@ -842,9 +842,16 @@ public: /// /// Shifts *this left by shiftAmt and assigns the result to *this. /// - /// \returns *this after shifting left by shiftAmt - APInt &operator<<=(unsigned shiftAmt) { - *this = shl(shiftAmt); + /// \returns *this after shifting left by ShiftAmt + APInt &operator<<=(unsigned ShiftAmt) { + if (isSingleWord()) { + if (ShiftAmt >= BitWidth) + VAL = 0; + else + VAL <<= ShiftAmt; + return clearUnusedBits(); + } + shlSlowCase(ShiftAmt); return *this; } @@ -888,13 +895,9 @@ public: /// /// Left-shift this APInt by shiftAmt. APInt shl(unsigned shiftAmt) const { - assert(shiftAmt <= BitWidth && "Invalid shift amount"); - if (isSingleWord()) { - if (shiftAmt >= BitWidth) - return APInt(BitWidth, 0); // avoid undefined shift results - return APInt(BitWidth, VAL << shiftAmt); - } - return shlSlowCase(shiftAmt); + APInt R(*this); + R <<= shiftAmt; + return R; } /// \brief Rotate left by rotateAmt. @@ -1765,9 +1768,9 @@ public: WordType *remainder, WordType *scratch, unsigned parts); - /// Shift a bignum left COUNT bits. Shifted in bits are zero. There are no - /// restrictions on COUNT. - static void tcShiftLeft(WordType *, unsigned parts, unsigned count); + /// Shift a bignum left Count bits. Shifted in bits are zero. There are no + /// restrictions on Count. + static void tcShiftLeft(WordType *, unsigned Words, unsigned Count); /// Shift a bignum right Count bits. Shifted in bits are zero. There are no /// restrictions on Count. diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp index 1d04f3b1cf9..1094a61cf1c 100644 --- a/lib/Support/APInt.cpp +++ b/lib/Support/APInt.cpp @@ -1161,60 +1161,9 @@ APInt APInt::shl(const APInt &shiftAmt) const { return shl((unsigned)shiftAmt.getLimitedValue(BitWidth)); } -APInt APInt::shlSlowCase(unsigned shiftAmt) const { - // If all the bits were shifted out, the result is 0. This avoids issues - // with shifting by the size of the integer type, which produces undefined - // results. We define these "undefined results" to always be 0. - if (shiftAmt == BitWidth) - return APInt(BitWidth, 0); - - // If none of the bits are shifted out, the result is *this. This avoids a - // lshr by the words size in the loop below which can produce incorrect - // results. It also avoids the expensive computation below for a common case. - if (shiftAmt == 0) - return *this; - - // Create some space for the result. - uint64_t * val = new uint64_t[getNumWords()]; - - // If we are shifting less than a word, do it the easy way - if (shiftAmt < APINT_BITS_PER_WORD) { - uint64_t carry = 0; - for (unsigned i = 0; i < getNumWords(); i++) { - val[i] = pVal[i] << shiftAmt | carry; - carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt); - } - APInt Result(val, BitWidth); - Result.clearUnusedBits(); - return Result; - } - - // Compute some values needed by the remaining shift algorithms - unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; - unsigned offset = shiftAmt / APINT_BITS_PER_WORD; - - // If we are shifting whole words, just move whole words - if (wordShift == 0) { - for (unsigned i = 0; i < offset; i++) - val[i] = 0; - for (unsigned i = offset; i < getNumWords(); i++) - val[i] = pVal[i-offset]; - APInt Result(val, BitWidth); - Result.clearUnusedBits(); - return Result; - } - - // Copy whole words from this to Result. - unsigned i = getNumWords() - 1; - for (; i > offset; --i) - val[i] = pVal[i-offset] << wordShift | - pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift); - val[offset] = pVal[0] << wordShift; - for (i = 0; i < offset; ++i) - val[i] = 0; - APInt Result(val, BitWidth); - Result.clearUnusedBits(); - return Result; +void APInt::shlSlowCase(unsigned ShiftAmt) { + tcShiftLeft(pVal, getNumWords(), ShiftAmt); + clearUnusedBits(); } // Calculate the rotate amount modulo the bit width. @@ -2657,34 +2606,31 @@ int APInt::tcDivide(WordType *lhs, const WordType *rhs, return false; } -/* Shift a bignum left COUNT bits in-place. Shifted in bits are zero. - There are no restrictions on COUNT. */ -void APInt::tcShiftLeft(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; - - while (parts > jump) { - WordType part; - - parts--; +/// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are +/// no restrictions on Count. +void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) { + // Don't bother performing a no-op shift. + if (!Count) + return; - /* dst[i] comes from the two parts src[i - jump] and, if we have - an intra-part shift, src[i - jump - 1]. */ - part = dst[parts - jump]; - if (shift) { - part <<= shift; - if (parts >= jump + 1) - part |= dst[parts - 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[parts] = part; + // Fastpath for moving by whole words. + if (BitShift == 0) { + std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE); + } else { + while (Words-- > WordShift) { + Dst[Words] = Dst[Words - WordShift] << BitShift; + if (Words > WordShift) + Dst[Words] |= + Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift); } - - while (parts > 0) - dst[--parts] = 0; } + + // Fill in the remainder with 0s. + std::memset(Dst, 0, WordShift * APINT_WORD_SIZE); } /// Shift a bignum right Count bits in-place. Shifted in bits are zero. There diff --git a/unittests/ADT/APIntTest.cpp b/unittests/ADT/APIntTest.cpp index 0bd309dd087..0f1d2d6d8f9 100644 --- a/unittests/ADT/APIntTest.cpp +++ b/unittests/ADT/APIntTest.cpp @@ -2024,4 +2024,37 @@ TEST(APIntTest, LogicalRightShift) { EXPECT_EQ(0, neg_one.lshr(257)); } +TEST(APIntTest, LeftShift) { + APInt i256(APInt::getLowBitsSet(256, 2)); + + i256 <<= 1; + EXPECT_EQ(253U, i256.countLeadingZeros()); + EXPECT_EQ(1U, i256.countTrailingZeros()); + EXPECT_EQ(2U, i256.countPopulation()); + + i256 <<= 62; + EXPECT_EQ(191U, i256.countLeadingZeros()); + EXPECT_EQ(63U, i256.countTrailingZeros()); + EXPECT_EQ(2U, i256.countPopulation()); + + i256 <<= 65; + EXPECT_EQ(126U, i256.countLeadingZeros()); + EXPECT_EQ(128U, i256.countTrailingZeros()); + EXPECT_EQ(2U, i256.countPopulation()); + + i256 <<= 64; + EXPECT_EQ(62U, i256.countLeadingZeros()); + EXPECT_EQ(192U, i256.countTrailingZeros()); + EXPECT_EQ(2U, i256.countPopulation()); + + i256 <<= 63; + EXPECT_EQ(0U, i256.countLeadingZeros()); + EXPECT_EQ(255U, 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.shl(257)); +} + } // end anonymous namespace -- 2.50.1