Simplify BitVector code

[serge-sans-paille]

Summary

Instead of managing memory by hand, delegate it to std::vector. This makes the
code much simpler, easier to reason on and also avoids repeatedly computing the storage size.

According to valgrind --tool=callgrind, this also slightly decreases the
instruction count, but by a small margin.

[nikic]

llvm/include/llvm/ADT/BitVector.h

82

Any thoughts on making this SmallVector<BitWord, 0> instead?

168

is preferable imho.

345

Missing NumBitWords?

349

You only call this API with Bits.begin() and it already accessed Bits.end() internally, which makes for a weirdly asymmetric API. Move the Bits.begin() inside the call?

[serge-sans-paille]

Take review into account.

[nikic]

LGTM

llvm/include/llvm/ADT/BitVector.h

667

I'd move these next to the copy/move constructors ... though actually, can we just drop all of these? I don't think the explicit defaulting is necessary in this instance.

[thakis]

This broke tests on the expensive checks bot: http://lab.llvm.org:8011/#/builders/16/builds/9331

[saugustine]

I have tracked the asan build bot breakage to this change. See below.

I would fix it forward, but the issue isn't obvious to me, and getting things fixed is higher value.

Therefore am reverting.

https://lab.llvm.org/buildbot/#/builders/99/builds/2835

[thakis]

About the actual change: LLVM code tries to be careful with allocations. std::vector is pretty allocation-heavy. Did you check that this doesn't increase malloc traffic?

[dexonsmith]

llvm/include/llvm/ADT/BitVector.h

82–85

BTW, SmallVector<BitWord, 0> should be the same size as MutableArrayRef on 64-bit platforms, whereas std::vector is an extra word. Might be nice to avoid making BitVector bigger.

[serge-sans-paille]

@saugustine thanks for the revert. I'll investigate that.
@thakis I checked the instruction count and overall execution time and didn't notice much change.
@dexonsmith Yeah that was the plan: switch to SmallVector once that one, hum, validates ;-)

llvm/include/llvm/ADT/BitVector.h

82

You read in my mind :-) That's the next step.

[MaskRay]

Might to good updating the revision before a reland next time :)
It highlights what has changed.

[wingrez]

This code snippet was normal before this version, but after this version it produced an assertion failure.

llvm/ADT/SmallVector.h:277: llvm::SmallVectorTemplateCommon::const_reference llvm::SmallVectorTemplateCommon<unsigned long>::operator[](llvm::SmallVectorTemplateCommon::size_type) const [T = unsigned long]: Assertion `idx < size()' failed.

BitVector bv;
auto k = bv.getData();
std::cout << k.size() << std::endl;

llvm/include/llvm/ADT/BitVector.h

 class BitVector {
   typedef uintptr_t BitWord;
 
   enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
 
   static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
                 "Unsupported word size");
 
-  MutableArrayRef<BitWord> Bits; // Actual bits.
-  unsigned Size;                 // Size of bitvector in bits.
+  using Storage = std::vector<BitWord>;
+
+  Storage Bits;  // Actual bits.
+  unsigned Size; // Size of bitvector in bits.
 
 public:
   typedef unsigned size_type;
+
   // Encapsulation of a single bit.
   class reference {
-    friend class BitVector;
 
     BitWord *WordRef;
     unsigned BitPos;
 
   public:
     reference(BitVector &b, unsigned Idx) {
       WordRef = &b.Bits[Idx / BITWORD_SIZE];
       BitPos = Idx % BITWORD_SIZE;
iterator_range<const_set_bits_iterator> set_bits() const {
     return make_range(set_bits_begin(), set_bits_end());
   }
 
   /// BitVector default ctor - Creates an empty bitvector.
   BitVector() : Size(0) {}
 
   /// BitVector ctor - Creates a bitvector of specified number of bits. All
   /// bits are initialized to the specified value.
-  explicit BitVector(unsigned s, bool t = false) : Size(s) {
-    size_t Capacity = NumBitWords(s);
-    Bits = allocate(Capacity);
-    init_words(Bits, t);
+  explicit BitVector(unsigned s, bool t = false)
+      : Bits(NumBitWords(s), 0 - (BitWord)t), Size(s) {
     if (t)
       clear_unused_bits();
   }
 
   /// BitVector copy ctor.
-  BitVector(const BitVector &RHS) : Size(RHS.size()) {
-    if (Size == 0) {
-      Bits = MutableArrayRef<BitWord>();
-      return;
-    }
-
-    size_t Capacity = NumBitWords(RHS.size());
-    Bits = allocate(Capacity);
-    std::memcpy(Bits.data(), RHS.Bits.data(), Capacity * sizeof(BitWord));
-  }
+  BitVector(const BitVector &RHS) = default;
 
-  BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size) {
-    RHS.Bits = MutableArrayRef<BitWord>();
-    RHS.Size = 0;
-  }
-
-  ~BitVector() { std::free(Bits.data()); }
+  BitVector(BitVector &&RHS) = default;
 
   /// empty - Tests whether there are no bits in this bitvector.
   bool empty() const { return Size == 0; }
 
   /// size - Returns the number of bits in this bitvector.
   size_type size() const { return Size; }
 
   /// count - Returns the number of bits which are set.
   size_type count() const {
     unsigned NumBits = 0;
-    for (unsigned i = 0; i < NumBitWords(size()); ++i)
-      NumBits += countPopulation(Bits[i]);
+    for (auto Bit : Bits)
+      NumBits += countPopulation(Bit);
     return NumBits;
   }
 
   /// any - Returns true if any bit is set.
   bool any() const {
-    for (unsigned i = 0; i < NumBitWords(size()); ++i)
-      if (Bits[i] != 0)
-        return true;
-    return false;
+    return any_of(Bits, [](BitWord Bit) -> bool { return Bit; });
   }
 
   /// all - Returns true if all bits are set.
   bool all() const {
     for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
       if (Bits[i] != ~BitWord(0))
         return false;
 
public:
   /// the bit at \p PriorTo.  Returns -1 if all previous bits are set.
   int find_prev_unset(unsigned PriorTo) {
     return find_last_unset_in(0, PriorTo);
   }
 
   /// clear - Removes all bits from the bitvector. Does not change capacity.
   void clear() {
     Size = 0;
+    Bits.clear();
   }
 
   /// resize - Grow or shrink the bitvector.
   void resize(unsigned N, bool t = false) {
-    if (N > getBitCapacity()) {
-      unsigned OldCapacity = Bits.size();
-      grow(N);
-      init_words(Bits.drop_front(OldCapacity), t);
-    }
-
-    // Set any old unused bits that are now included in the BitVector. This
-    // may set bits that are not included in the new vector, but we will clear
-    // them back out below.
-    if (N > Size)
-      set_unused_bits(t);
-
-    // Update the size, and clear out any bits that are now unused
-    unsigned OldSize = Size;
     Size = N;
-    if (t || N < OldSize)
-      clear_unused_bits();
+    Bits.resize(NumBitWords(N), 0 - BitWord(t));
   }
 
-  void reserve(unsigned N) {
-    if (N > getBitCapacity())
-      grow(N);
-  }
+  void reserve(unsigned N) { Bits.reserve(N); }
 
   // Set, reset, flip
   BitVector &set() {
-    init_words(Bits, true);
+    init_words(Bits.begin(), true);
     clear_unused_bits();
     return *this;
   }
 
   BitVector &set(unsigned Idx) {
-    assert(Bits.data() && "Bits never allocated");
     Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
     return *this;
   }
 
   /// set - Efficiently set a range of bits in [I, E)
   BitVector &set(unsigned I, unsigned E) {
     assert(I <= E && "Attempted to set backwards range!");
     assert(E <= size() && "Attempted to set out-of-bounds range!");
BitVector &set(unsigned I, unsigned E) {
     BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
     if (I < E)
       Bits[I / BITWORD_SIZE] |= PostfixMask;
 
     return *this;
   }
 
   BitVector &reset() {
-    init_words(Bits, false);
+    init_words(Bits.begin(), false);
     return *this;
   }
 
   BitVector &reset(unsigned Idx) {
     Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
     return *this;
   }
 
BitVector &reset(unsigned I, unsigned E) {
     BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
     if (I < E)
       Bits[I / BITWORD_SIZE] &= ~PostfixMask;
 
     return *this;
   }
 
   BitVector &flip() {
-    for (unsigned i = 0; i < NumBitWords(size()); ++i)
-      Bits[i] = ~Bits[i];
+    for (auto &Bit : Bits)
+      Bit = ~Bit;
     clear_unused_bits();
     return *this;
   }
 
   BitVector &flip(unsigned Idx) {
     Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
     return *this;
   }
void push_back(bool Val) {
 
     // If true, set single bit.
     if (Val)
       set(OldSize);
   }
 
   /// Test if any common bits are set.
   bool anyCommon(const BitVector &RHS) const {
-    unsigned ThisWords = NumBitWords(size());
-    unsigned RHSWords  = NumBitWords(RHS.size());
+    unsigned ThisWords = Bits.size();
+    unsigned RHSWords = RHS.Bits.size();
     for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
       if (Bits[i] & RHS.Bits[i])
         return true;
     return false;
   }
 
   // Comparison operators.
   bool operator==(const BitVector &RHS) const {
     if (size() != RHS.size())
       return false;
-    unsigned NumWords = NumBitWords(size());
-    return Bits.take_front(NumWords) == RHS.Bits.take_front(NumWords);
+    unsigned NumWords = Bits.size();
+    return std::equal(Bits.begin(), Bits.begin() + NumWords, RHS.Bits.begin());
   }
 
-  bool operator!=(const BitVector &RHS) const {
-    return !(*this == RHS);
-  }
+  bool operator!=(const BitVector &RHS) const { return !(*this == RHS); }
 
   /// Intersection, union, disjoint union.
   BitVector &operator&=(const BitVector &RHS) {
-    unsigned ThisWords = NumBitWords(size());
-    unsigned RHSWords  = NumBitWords(RHS.size());
+    unsigned ThisWords = Bits.size();
+    unsigned RHSWords = RHS.Bits.size();
     unsigned i;
     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
       Bits[i] &= RHS.Bits[i];
 
     // Any bits that are just in this bitvector become zero, because they aren't
     // in the RHS bit vector.  Any words only in RHS are ignored because they
     // are already zero in the LHS.
     for (; i != ThisWords; ++i)
       Bits[i] = 0;
 
     return *this;
   }
 
   /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
   BitVector &reset(const BitVector &RHS) {
-    unsigned ThisWords = NumBitWords(size());
-    unsigned RHSWords  = NumBitWords(RHS.size());
-    unsigned i;
-    for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
+    unsigned ThisWords = Bits.size();
+    unsigned RHSWords = RHS.Bits.size();
+    for (unsigned i = 0; i != std::min(ThisWords, RHSWords); ++i)
       Bits[i] &= ~RHS.Bits[i];
     return *this;
   }
 
   /// test - Check if (This - RHS) is zero.
   /// This is the same as reset(RHS) and any().
   bool test(const BitVector &RHS) const {
-    unsigned ThisWords = NumBitWords(size());
-    unsigned RHSWords  = NumBitWords(RHS.size());
+    unsigned ThisWords = Bits.size();
+    unsigned RHSWords = RHS.Bits.size();
     unsigned i;
     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
       if ((Bits[i] & ~RHS.Bits[i]) != 0)
         return true;
 
     for (; i != ThisWords ; ++i)
       if (Bits[i] != 0)
         return true;
 
     return false;
   }
 
   template <class F, class... ArgTys>
   static BitVector &apply(F &&f, BitVector &Out, BitVector const &Arg,
                           ArgTys const &...Args) {
     assert(llvm::all_of(
                std::initializer_list<unsigned>{Args.size()...},
                [&Arg](auto const &BV) { return Arg.size() == BV; }) &&
            "consistent sizes");
     Out.resize(Arg.size());
-    for (size_t i = 0, e = Out.NumBitWords(Arg.size()); i != e; ++i)
+    for (size_t i = 0, e = Arg.Bits.size(); i != e; ++i)
       Out.Bits[i] = f(Arg.Bits[i], Args.Bits[i]...);
     Out.clear_unused_bits();
     return Out;
   }
 
   BitVector &operator|=(const BitVector &RHS) {
     if (size() < RHS.size())
       resize(RHS.size());
-    for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
+    for (size_t i = 0, e = RHS.Bits.size(); i != e; ++i)
       Bits[i] |= RHS.Bits[i];
     return *this;
   }
 
   BitVector &operator^=(const BitVector &RHS) {
     if (size() < RHS.size())
       resize(RHS.size());
-    for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
+    for (size_t i = 0, e = RHS.Bits.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);
+    unsigned NumWords = Bits.size();
     assert(NumWords >= 1);
 
     wordShr(N / BITWORD_SIZE);
 
     unsigned BitDistance = N % BITWORD_SIZE;
     if (BitDistance == 0)
       return *this;
 
BitVector &operator>>=(unsigned N) {
     return *this;
   }
 
   BitVector &operator<<=(unsigned N) {
     assert(N <= Size);
     if (LLVM_UNLIKELY(empty() || N == 0))
       return *this;
 
-    unsigned NumWords = NumBitWords(Size);
+    unsigned NumWords = Bits.size();
     assert(NumWords >= 1);
 
     wordShl(N / BITWORD_SIZE);
 
     unsigned BitDistance = N % BITWORD_SIZE;
     if (BitDistance == 0)
       return *this;
 
BitVector &operator<<=(unsigned N) {
     }
     Bits[0] <<= BitDistance;
     clear_unused_bits();
 
     return *this;
   }
 
   // Assignment operator.
-  const BitVector &operator=(const BitVector &RHS) {
-    if (this == &RHS) return *this;
-
-    Size = RHS.size();
+  BitVector &operator=(const BitVector &RHS) = default;
 
-    // Handle tombstone when the BitVector is a key of a DenseHash.
-    if (RHS.isInvalid()) {
-      std::free(Bits.data());
-      Bits = None;
-      return *this;
-    }
-
-    unsigned RHSWords = NumBitWords(Size);
-    if (Size <= getBitCapacity()) {
-      if (Size)
-        std::memcpy(Bits.data(), RHS.Bits.data(), RHSWords * sizeof(BitWord));
-      clear_unused_bits();
-      return *this;
-    }
-
-    // Grow the bitvector to have enough elements.
-    unsigned NewCapacity = RHSWords;
-    assert(NewCapacity > 0 && "negative capacity?");
-    auto NewBits = allocate(NewCapacity);
-    std::memcpy(NewBits.data(), RHS.Bits.data(), NewCapacity * sizeof(BitWord));
-
-    // Destroy the old bits.
-    std::free(Bits.data());
-    Bits = NewBits;
-
-    return *this;
-  }
-
-  const BitVector &operator=(BitVector &&RHS) {
-    if (this == &RHS) return *this;
-
-    std::free(Bits.data());
-    Bits = RHS.Bits;
-    Size = RHS.Size;
-
-    RHS.Bits = MutableArrayRef<BitWord>();
-    RHS.Size = 0;
-
-    return *this;
-  }
+  BitVector &operator=(BitVector &&RHS) = default;
 
   void swap(BitVector &RHS) {
     std::swap(Bits, RHS.Bits);
     std::swap(Size, RHS.Size);
   }
 
   void invalid() {
     assert(!Size && Bits.empty());
     Size = (unsigned)-1;
   }
   bool isInvalid() const { return Size == (unsigned)-1; }
 
-  ArrayRef<BitWord> getData() const {
-    return Bits.take_front(NumBitWords(size()));
-  }
+  ArrayRef<BitWord> getData() const { return {&Bits[0], Bits.size()}; }
 
   //===--------------------------------------------------------------------===//
   // Portable bit mask operations.
   //===--------------------------------------------------------------------===//
   //
   // These methods all operate on arrays of uint32_t, each holding 32 bits. The
   // fixed word size makes it easier to work with literal bit vector constants
   // in portable code.
private:
   /// 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
+  /// 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 = Bits.take_front(NumWords).drop_back(Count);
-    auto Dest = Bits.take_front(NumWords).drop_front(Count);
+    uint32_t NumWords = Bits.size();
 
     // 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.data(), 0, Count * sizeof(BitWord));
+    std::copy(Bits.begin(), Bits.begin() + NumWords - Count,
+              Bits.begin() + Count);
+    std::fill(Bits.begin(), Bits.begin() + Count, 0);
     clear_unused_bits();
   }
 
   /// 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 = Bits.take_front(NumWords).drop_front(Count);
-    auto Dest = Bits.take_front(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));
-  }
+    uint32_t NumWords = Bits.size();
 
-  MutableArrayRef<BitWord> allocate(size_t NumWords) {
-    BitWord *RawBits = static_cast<BitWord *>(
-        safe_malloc(NumWords * sizeof(BitWord)));
-    return MutableArrayRef<BitWord>(RawBits, NumWords);
+    std::copy(Bits.begin() + Count, Bits.begin() + NumWords, Bits.begin());
+    std::fill(Bits.begin() + NumWords - Count, Bits.begin() + NumWords, 0);
   }
 
   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;
   }
 
   // Set the unused bits in the high words.
   void set_unused_bits(bool t = true) {
-    //  Set high words first.
-    unsigned UsedWords = NumBitWords(Size);
-    if (Bits.size() > UsedWords)
-      init_words(Bits.drop_front(UsedWords), t);
-
     //  Then set any stray high bits of the last used word.
-    unsigned ExtraBits = Size % BITWORD_SIZE;
-    if (ExtraBits) {
+    if (unsigned ExtraBits = Size % BITWORD_SIZE) {
       BitWord ExtraBitMask = ~BitWord(0) << ExtraBits;
       if (t)
-        Bits[UsedWords-1] |= ExtraBitMask;
+        Bits.back() |= ExtraBitMask;
       else
-        Bits[UsedWords-1] &= ~ExtraBitMask;
+        Bits.back() &= ~ExtraBitMask;
     }
   }
 
   // Clear the unused bits in the high words.
   void clear_unused_bits() {
     set_unused_bits(false);
   }
 
-  void grow(unsigned NewSize) {
-    size_t NewCapacity = std::max<size_t>(NumBitWords(NewSize), Bits.size() * 2);
-    assert(NewCapacity > 0 && "realloc-ing zero space");
-    BitWord *NewBits = static_cast<BitWord *>(
-        safe_realloc(Bits.data(), NewCapacity * sizeof(BitWord)));
-    Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity);
-    clear_unused_bits();
-  }
-
-  void init_words(MutableArrayRef<BitWord> B, bool t) {
-    if (B.size() > 0)
-      memset(B.data(), 0 - (int)t, B.size() * sizeof(BitWord));
+  template <class I> void init_words(I Iter, bool t) {
+    std::fill(Iter, Bits.end(), 0 - (BitWord)t);
   }
 
   template<bool AddBits, bool InvertMask>
   void applyMask(const uint32_t *Mask, unsigned MaskWords) {
     static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
     MaskWords = std::min(MaskWords, (size() + 31) / 32);
     const unsigned Scale = BITWORD_SIZE / 32;
     unsigned i;
public:
   size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
 };
 
 inline size_t capacity_in_bytes(const BitVector &X) {
   return X.getMemorySize();
 }
 
 template <> struct DenseMapInfo<BitVector> {
-  static inline BitVector getEmptyKey() { return BitVector(); }
+  static inline BitVector getEmptyKey() { return {}; }
   static inline BitVector getTombstoneKey() {
     BitVector V;
     V.invalid();
     return V;
   }
   static unsigned getHashValue(const BitVector &V) {
     return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue(
         std::make_pair(V.size(), V.getData()));
   }
   static bool isEqual(const BitVector &LHS, const BitVector &RHS) {
     if (LHS.isInvalid() || RHS.isInvalid())
       return LHS.isInvalid() == RHS.isInvalid();
     return LHS == RHS;
   }
 };
 } // end namespace llvm
 
 namespace std {
   /// Implement std::swap in terms of BitVector swap.
-  inline void
-  swap(llvm::BitVector &LHS, llvm::BitVector &RHS) {
-    LHS.swap(RHS);
-  }
+inline void swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { LHS.swap(RHS); }
 } // end namespace std
 
 #endif // LLVM_ADT_BITVECTOR_H