Index: llvm/trunk/include/llvm/ADT/BitVector.h =================================================================== --- llvm/trunk/include/llvm/ADT/BitVector.h +++ llvm/trunk/include/llvm/ADT/BitVector.h @@ -14,6 +14,8 @@ #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 @@ -455,6 +457,105 @@ 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; @@ -538,6 +639,54 @@ } 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; Index: llvm/trunk/include/llvm/ADT/SmallBitVector.h =================================================================== --- llvm/trunk/include/llvm/ADT/SmallBitVector.h +++ llvm/trunk/include/llvm/ADT/SmallBitVector.h @@ -508,6 +508,22 @@ 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()) { Index: llvm/trunk/unittests/ADT/BitVectorTest.cpp =================================================================== --- llvm/trunk/unittests/ADT/BitVectorTest.cpp +++ llvm/trunk/unittests/ADT/BitVectorTest.cpp @@ -345,6 +345,128 @@ 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);