[BitVector] Add << and >> operators

[zturner]

Summary

BitVector does not currently provide any operators for shifting left and right by a specified amount. This patch adds them.

The logic here is surprisingly headache-inducing, but I believe I got it correct.

[craig.topper]

llvm/include/llvm/ADT/BitVector.h

504 ↗

(On Diff #95822)

I didn't look closely but why would there be non-zero values on a right shift that need to be cleared?

[zturner]

llvm/include/llvm/ADT/BitVector.h

504 ↗

(On Diff #95822)

I think I can get rid of that, thanks for noticing.

[chandlerc]

llvm/include/llvm/ADT/BitVector.h

472 ↗

(On Diff #95822)

Instead of this, test for 0 and do the word shift and return early? That will let the complex case be less indented.

524 ↗

(On Diff #95822)

Same as above.

655–661 ↗

(On Diff #95822)

Reality is worse than this. Using memmove operates on bytes, but the words might be in bigendian and thus the bytes *within* the words ordered differently. =[

I think you should either write a for loop that does the move a word at a time (and thus is obviously endian agnostic) or you'll need to do some endian dance here.. =[

[zturner]

llvm/include/llvm/ADT/BitVector.h

655–661 ↗

(On Diff #95822)

My brain already hurts from this, so I give the odds of me being completely wrong about 100%, but does this matter?

Although memmove moves bytes, the function itself moves a number of bytes that is always a multiple of the word size, and the move happens at a word-aligned boundary, so we should be guaranteed that we're just picking up a chunk of words in whatever endianness they may already be in, and moving that same chunk somewhere else in the same endianness.

shouldn't that work?

[craig.topper]

llvm/include/llvm/ADT/BitVector.h

655–661 ↗

(On Diff #95822)

Aren't we always moving a multiple of words with the memmove which should hide the endianess issue? Richard Smith just added a memmove to the equivalent shift code in APInt so I really hope memmove isn't an issue here.

[chandlerc]

llvm/include/llvm/ADT/BitVector.h

655–661 ↗

(On Diff #95822)

Sorry, I got confused by the predicate above that talks about BitDistance and thought this was the *byte* distance not *word* distance despite the number of times it says "word".

Maybe just an explicit comment here reminding the reader that this is safe because we move in increments of words.

[zturner]

Deleted some miscellaneous functions in MathExtras.h that I ended up not using, and added some comments to the implementation to clarify a few minor points.

[zturner]

Reduced indentation level a little bit.

[chandlerc]

Generally this looks pretty awesome. Thanks for all of this. Minor nitpicks inline. I'd let Craig have a look as well just in case I'm not seeing anything, but good to submit if he's happy as well.

llvm/include/llvm/ADT/BitVector.h

499 ↗

(On Diff #95847)

Nit picky detail: I would use 'i' for an integer and 'I' for an iterator.

556 ↗

(On Diff #95847)

Why is this needed here again? We have to have put zeros into the low bits here as well...

[zturner]

llvm/include/llvm/ADT/BitVector.h

556 ↗

(On Diff #95847)

Right, but it's actually the high order bits that we're concerned about. If your BitVector size is not a multiple of the word size, then the unused bits come from the most siginificant (i.e. leftmost) bits of the most significant word. And shifting left will write non-zero bits into those. Concrete example:

Suppose you've got this BitVector:

31--------------------------------0
XXXXXXXX XXXXXXXX XXXX0011 00001100

Where the X's represent unused bits. So here we've got a word size of 4 bytes, and a BitVector size of 12.

In memory this is going to be represented as

Bits[0] = 0b00000000000000000000001100001100

because the unused bits will be initialized to 0.

Now suppose we shift left by 10. You're going to end up with 0b00000000000011000011 | 000000000000 where I've used an | to indicate where the unused bits are supposed to be. Everything to the left of the | are unused bits and need to be cleared.

[hans]

llvm/trunk/include/llvm/ADT/BitVector.h

478

This sounds like exactly what APInt:tcShiftRight does. Would it be possible to reuse that code?

In general, it seems like a lot of what BitVector does is also implemented in APInt. Craig, what do you think?

[craig.topper]

BitVector's word size is dependent on target as it is using "unsigned long" not uint32_t/uint64_t. tcShiftRight is hardcoded to uint64_t though we could probably make it a template.

llvm/trunk/include/llvm/ADT/BitVector.h

 //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the BitVector class.
 //
 //===----------------------------------------------------------------------===//
 
 #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 <algorithm>
 #include <cassert>
 #include <climits>
 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
 #include <utility>
public:
   BitVector &operator^=(const BitVector &RHS) {
     if (size() < RHS.size())
       resize(RHS.size());
     for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
       Bits[i] ^= RHS.Bits[i];
     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<BitWord>(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<BitWord>(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;
 
     Size = RHS.size();
     unsigned RHSWords = NumBitWords(Size);
     if (Size <= Capacity * BITWORD_SIZE) {
       if (Size)
public:
 
   /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
   /// Don't resize.  This computes "*this &= Mask".
   void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
     applyMask<false, true>(Mask, MaskWords);
   }
 
 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<BitWord>(Bits, NumWords).drop_back(Count);
+    auto Dest = MutableArrayRef<BitWord>(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<BitWord>(Bits, NumWords).drop_front(Count);
+    auto Dest = MutableArrayRef<BitWord>(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;
   }
 
   unsigned NumBitWords(unsigned S) const {
     return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
   }

llvm/trunk/include/llvm/ADT/SmallBitVector.h

SmallBitVector &operator^=(const SmallBitVector &RHS) {
     else {
       SmallBitVector Copy = RHS;
       Copy.resize(size());
       getPointer()->operator^=(*Copy.getPointer());
     }
     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()) {
       if (RHS.isSmall())
         X = RHS.X;
       else
         switchToLarge(new BitVector(*RHS.getPointer()));
     } else {

llvm/trunk/unittests/ADT/BitVectorTest.cpp

TYPED_TEST(BitVectorTest, BinOps) {
   B.resize(70);
   B.set(64);
   B.reset(63);
   A.resize(64);
   EXPECT_FALSE(A.anyCommon(B));
   EXPECT_FALSE(B.anyCommon(A));
 }
 
+typedef std::vector<std::pair<int, int>> RangeList;
+
+template <typename VecType>
+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<TypeParam>(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<TypeParam>(12, {{1, 3}, {7, 9}}), A);
+
+  A <<= 1;
+  EXPECT_EQ(B, A);
+
+  A >>= 10;
+  EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
+
+  A = B;
+  A <<= 10;
+  EXPECT_EQ(createBitVector<TypeParam>(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<TypeParam>(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<TypeParam>(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<TypeParam>(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<TypeParam>(40, {{0, 5}, {18, 24}}), A);
+
+  // 3. Big test.
+  A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
+  A <<= 29;
+  EXPECT_EQ(createBitVector<TypeParam>(
+                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<TypeParam>(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<TypeParam>(
+      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<TypeParam>(
+                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<TypeParam>(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<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A);
+}
+
 TYPED_TEST(BitVectorTest, RangeOps) {
   TypeParam A;
   A.resize(256);
   A.reset();
   A.set(1, 255);
 
   EXPECT_FALSE(A.test(0));
   EXPECT_TRUE( A.test(1));