From 154c0ad769da8ba8afe78e503596109b55fc8b8e Mon Sep 17 00:00:00 2001 From: Zachary Turner Date: Thu, 20 Apr 2017 16:35:22 +0000 Subject: [PATCH] Revert "[BitVector] Add operator<<= and operator>>=." This is causing test failures on Linux / BSD systems. Reverting while I investigate. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@300852 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/BitVector.h | 149 ------------------------------ include/llvm/ADT/SmallBitVector.h | 16 ---- unittests/ADT/BitVectorTest.cpp | 122 ------------------------ 3 files changed, 287 deletions(-) diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index 19abd4fa3e6..8240d01ae97 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -14,8 +14,6 @@ #ifndef LLVM_ADT_BITVECTOR_H #define LLVM_ADT_BITVECTOR_H -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/STLExtras.h" #include "llvm/Support/MathExtras.h" #include #include @@ -457,105 +455,6 @@ public: return *this; } - BitVector &operator>>=(unsigned N) { - assert(N <= Size); - if (LLVM_UNLIKELY(empty() || N == 0)) - return *this; - - unsigned NumWords = NumBitWords(Size); - assert(NumWords >= 1); - - wordShr(N / BITWORD_SIZE); - - unsigned BitDistance = N % BITWORD_SIZE; - if (BitDistance == 0) - return *this; - - // When the shift size is not a multiple of the word size, then we have - // a tricky situation where each word in succession needs to extract some - // of the bits from the next word and or them into this word while - // shifting this word to make room for the new bits. This has to be done - // for every word in the array. - - // Since we're shifting each word right, some bits will fall off the end - // of each word to the right, and empty space will be created on the left. - // The final word in the array will lose bits permanently, so starting at - // the beginning, work forwards shifting each word to the right, and - // OR'ing in the bits from the end of the next word to the beginning of - // the current word. - - // Example: - // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right - // by 4 bits. - // Step 1: Word[0] >>= 4 ; 0x0ABBCCDD - // Step 2: Word[0] |= 0x10000000 ; 0x1ABBCCDD - // Step 3: Word[1] >>= 4 ; 0x0EEFF001 - // Step 4: Word[1] |= 0x50000000 ; 0x5EEFF001 - // Step 5: Word[2] >>= 4 ; 0x02334455 - // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 } - const unsigned Mask = maskTrailingOnes(BitDistance); - const unsigned LSH = BITWORD_SIZE - BitDistance; - - for (unsigned I = 0; I < NumWords - 1; ++I) { - Bits[I] >>= BitDistance; - Bits[I] |= (Bits[I + 1] & Mask) << LSH; - } - - Bits[NumWords - 1] >>= BitDistance; - - return *this; - } - - BitVector &operator<<=(unsigned N) { - assert(N <= Size); - if (LLVM_UNLIKELY(empty() || N == 0)) - return *this; - - unsigned NumWords = NumBitWords(Size); - assert(NumWords >= 1); - - wordShl(N / BITWORD_SIZE); - - unsigned BitDistance = N % BITWORD_SIZE; - if (BitDistance == 0) - return *this; - - // When the shift size is not a multiple of the word size, then we have - // a tricky situation where each word in succession needs to extract some - // of the bits from the previous word and or them into this word while - // shifting this word to make room for the new bits. This has to be done - // for every word in the array. This is similar to the algorithm outlined - // in operator>>=, but backwards. - - // Since we're shifting each word left, some bits will fall off the end - // of each word to the left, and empty space will be created on the right. - // The first word in the array will lose bits permanently, so starting at - // the end, work backwards shifting each word to the left, and OR'ing - // in the bits from the end of the next word to the beginning of the - // current word. - - // Example: - // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left - // by 4 bits. - // Step 1: Word[2] <<= 4 ; 0x23344550 - // Step 2: Word[2] |= 0x0000000E ; 0x2334455E - // Step 3: Word[1] <<= 4 ; 0xEFF00110 - // Step 4: Word[1] |= 0x0000000A ; 0xEFF0011A - // Step 5: Word[0] <<= 4 ; 0xABBCCDD0 - // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E } - const unsigned Mask = maskLeadingOnes(BitDistance); - const unsigned RSH = BITWORD_SIZE - BitDistance; - - for (int I = NumWords - 1; I > 0; --I) { - Bits[I] <<= BitDistance; - Bits[I] |= (Bits[I - 1] & Mask) >> RSH; - } - Bits[0] <<= BitDistance; - clear_unused_bits(); - - return *this; - } - // Assignment operator. const BitVector &operator=(const BitVector &RHS) { if (this == &RHS) return *this; @@ -639,54 +538,6 @@ public: } private: - /// \brief Perform a logical left shift of \p Count words by moving everything - /// \p Count words to the right in memory. - /// - /// While confusing, words are stored from least significant at Bits[0] to - /// most significant at Bits[NumWords-1]. A logical shift left, however, - /// moves the current least significant bit to a higher logical index, and - /// fills the previous least significant bits with 0. Thus, we actually - /// need to move the bytes of the memory to the right, not to the left. - /// Example: - /// Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000] - /// represents a BitVector where 0xBBBBAAAA contain the least significant - /// bits. So if we want to shift the BitVector left by 2 words, we need to - /// turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a - /// memmove which moves right, not left. - void wordShl(uint32_t Count) { - if (Count == 0) - return; - - uint32_t NumWords = NumBitWords(Size); - - auto Src = ArrayRef(Bits, NumWords).drop_back(Count); - auto Dest = MutableArrayRef(Bits, NumWords).drop_front(Count); - - // Since we always move Word-sized chunks of data with src and dest both - // aligned to a word-boundary, we don't need to worry about endianness - // here. - std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord)); - std::memset(Bits, 0, Count * sizeof(BitWord)); - clear_unused_bits(); - } - - /// \brief Perform a logical right shift of \p Count words by moving those - /// words to the left in memory. See wordShl for more information. - /// - void wordShr(uint32_t Count) { - if (Count == 0) - return; - - uint32_t NumWords = NumBitWords(Size); - - auto Src = ArrayRef(Bits, NumWords).drop_front(Count); - auto Dest = MutableArrayRef(Bits, NumWords).drop_back(Count); - assert(Dest.size() == Src.size()); - - std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord)); - std::memset(Dest.end(), 0, Count * sizeof(BitWord)); - } - int next_unset_in_word(int WordIndex, BitWord Word) const { unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word); return Result < size() ? Result : -1; diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index 607e040a606..edb37da38da 100644 --- a/include/llvm/ADT/SmallBitVector.h +++ b/include/llvm/ADT/SmallBitVector.h @@ -508,22 +508,6 @@ public: return *this; } - SmallBitVector &operator<<=(unsigned N) { - if (isSmall()) - setSmallBits(getSmallBits() << N); - else - getPointer()->operator<<=(N); - return *this; - } - - SmallBitVector &operator>>=(unsigned N) { - if (isSmall()) - setSmallBits(getSmallBits() >> N); - else - getPointer()->operator>>=(N); - return *this; - } - // Assignment operator. const SmallBitVector &operator=(const SmallBitVector &RHS) { if (isSmall()) { diff --git a/unittests/ADT/BitVectorTest.cpp b/unittests/ADT/BitVectorTest.cpp index 71b6be36c3b..98ef66735ad 100644 --- a/unittests/ADT/BitVectorTest.cpp +++ b/unittests/ADT/BitVectorTest.cpp @@ -345,128 +345,6 @@ TYPED_TEST(BitVectorTest, BinOps) { EXPECT_FALSE(B.anyCommon(A)); } -typedef std::vector> RangeList; - -template -static inline VecType createBitVector(uint32_t Size, - const RangeList &setRanges) { - VecType V; - V.resize(Size); - for (auto &R : setRanges) - V.set(R.first, R.second); - return V; -} - -TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) { - // Test that shift ops work when the desired shift amount is less - // than one word. - - // 1. Case where the number of bits in the BitVector also fit into a single - // word. - TypeParam A = createBitVector(12, {{2, 4}, {8, 10}}); - TypeParam B = A; - - EXPECT_EQ(4U, A.count()); - EXPECT_TRUE(A.test(2)); - EXPECT_TRUE(A.test(3)); - EXPECT_TRUE(A.test(8)); - EXPECT_TRUE(A.test(9)); - - A >>= 1; - EXPECT_EQ(createBitVector(12, {{1, 3}, {7, 9}}), A); - - A <<= 1; - EXPECT_EQ(B, A); - - A >>= 10; - EXPECT_EQ(createBitVector(12, {}), A); - - A = B; - A <<= 10; - EXPECT_EQ(createBitVector(12, {}), A); - - // 2. Case where the number of bits in the BitVector do not fit into a single - // word. - - // 31----------------------------------------------------------------------0 - // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 - A = createBitVector(40, {{0, 12}, {25, 35}}); - EXPECT_EQ(40U, A.size()); - EXPECT_EQ(22U, A.count()); - - // 2a. Make sure that left shifting some 1 bits out of the vector works. - // 31----------------------------------------------------------------------0 - // Before: - // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 - // After: - // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 - A <<= 9; - EXPECT_EQ(createBitVector(40, {{9, 21}, {34, 40}}), A); - - // 2b. Make sure that keeping the number of one bits unchanged works. - // 31----------------------------------------------------------------------0 - // Before: - // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 - // After: - // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 - A >>= 6; - EXPECT_EQ(createBitVector(40, {{3, 15}, {28, 34}}), A); - - // 2c. Make sure that right shifting some 1 bits out of the vector works. - // 31----------------------------------------------------------------------0 - // Before: - // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 - // After: - // XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111 - A >>= 10; - EXPECT_EQ(createBitVector(40, {{0, 5}, {18, 24}}), A); - - // 3. Big test. - A = createBitVector(300, {{1, 30}, {60, 95}, {200, 275}}); - A <<= 29; - EXPECT_EQ(createBitVector( - 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}), - A); -} - -TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) { - // Test that shift ops work when the desired shift amount is greater than or - // equal to the size of a single word. - auto A = createBitVector(300, {{1, 30}, {60, 95}, {200, 275}}); - - // Make a copy so we can re-use it later. - auto B = A; - - // 1. Shift left by an exact multiple of the word size. This should invoke - // only a memmove and no per-word bit operations. - A <<= 64; - auto Expected = createBitVector( - 300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}}); - EXPECT_EQ(Expected, A); - - // 2. Shift left by a non multiple of the word size. This should invoke both - // a memmove and per-word bit operations. - A = B; - A <<= 93; - EXPECT_EQ(createBitVector( - 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}), - A); - - // 1. Shift right by an exact multiple of the word size. This should invoke - // only a memmove and no per-word bit operations. - A = B; - A >>= 64; - EXPECT_EQ( - createBitVector(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A); - - // 2. Shift left by a non multiple of the word size. This should invoke both - // a memmove and per-word bit operations. - A = B; - A >>= 93; - EXPECT_EQ( - createBitVector(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A); -} - TYPED_TEST(BitVectorTest, RangeOps) { TypeParam A; A.resize(256); -- 2.40.0