[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

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

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

[chandlerc]

llvm/include/llvm/ADT/BitVector.h

472

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

524

Same as above.

655–661

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

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

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

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

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

556

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

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 ↗

(On Diff #95967)

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/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);
+
+    unsigned WordDistance = N / BITWORD_SIZE;
+    unsigned BitDistance = N % BITWORD_SIZE;
+    assert(WordDistance > 0 || BitDistance > 0);
+
+    if (BitDistance > 0) {
+      // 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;
+      clear_unused_bits();
+    }
+
+    wordShr(WordDistance);
+
+    return *this;
+  }
+
+  BitVector &operator<<=(unsigned N) {
+    assert(N <= Size);
+    if (LLVM_UNLIKELY(empty() || N == 0))
+      return *this;
+
+    unsigned NumWords = NumBitWords(Size);
+    assert(NumWords >= 1);
+
+    unsigned WordDistance = N / BITWORD_SIZE;
+    unsigned BitDistance = N % BITWORD_SIZE;
+    assert(WordDistance > 0 || BitDistance > 0);
+
+    if (BitDistance > 0) {
+      // 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;
+
+      assert(NumWords >= 1);
+
+      for (int I = NumWords - 1; I > 0; --I) {
+        Bits[I] <<= BitDistance;
+        Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
+      }
+      Bits[0] <<= BitDistance;
+      clear_unused_bits();
+    }
+
+    wordShl(WordDistance);
+
+    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:
+  /// Shift the Words array right by WordDistance words and set the discarded
+  /// words to 0.
+  /// 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);
+
+    std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
+    std::memset(Bits, 0, Count * sizeof(BitWord));
+    clear_unused_bits();
+  }
+
+  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));
+    clear_unused_bits();
+  }
+
   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/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/include/llvm/Support/MathExtras.h

 }
 
 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
 /// value, 64 if the value is zero. (64 bit edition.)
 inline unsigned Log2_64_Ceil(uint64_t Value) {
   return 64 - countLeadingZeros(Value - 1);
 }
 
+template <class T>
+constexpr const T &clamp(const T &v, const T &lo, const T &hi) {
+  return clamp(v, lo, hi, std::less<>());
+}
+
+template <class T, class Compare>
+constexpr const T &clamp(const T &v, const T &lo, const T &hi, Compare comp) {
+  return assert(!comp(hi, lo)), comp(v, lo) ? lo : comp(hi, v) ? hi : v;
+}
+
 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
 /// values using Euclid's algorithm.
 inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
   while (B) {
     uint64_t T = B;
     B = A % B;
     A = T;
   }

llvm/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(4, 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(40, A.size());
+  EXPECT_EQ(22, 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));