Use a byte array as an internal buffer of BitVector.

[ruiu]

Summary

Previously, BitVector was using an array of unsigned long as an
internal buffer. That design choice was not desirable if we want to
allow exporting bitmaps or importing existing bitmaps, because the
internal buffer's contents are different on machines with different
endianness.

In PDB file processing, we create bitmaps and then write it to a file.
We also read a bitmap from disk and convert it to BitVector.
All these operations involve for-loop for each bit and data copying
because we cannot map existing bitmaps to BitVector.

This patch solves the problem. Now the internal buffer is represented
as a byte array. So, two BitVectors having the identical bits are now
represented in the same way both on the LE and BE machines. The
endianness problem is gone.

In this patch, we are still doing word-size operations instead of
byte-size operations where possible. Changing the internal format
shouldn't degrade the performance.

[bryant]

include/llvm/ADT/BitVector.h

480

Would this violate strict aliasing rules?

[ruiu]

• Upload the correct patch. I split the patch locally, so the previous patch didn't include all changes.

[ruiu]

include/llvm/ADT/BitVector.h

480

I think it is, but we are doing this at so many places to read and convert values in different endianness.

[zturner]

include/llvm/ADT/BitVector.h

44

Since words are always little endian, why not make the type of Word be support::ulittle32_t

480

If the type of Word is support::ulittle32_t, then you don't have to worry about this, as you can just delete this entire function.

[ruiu]

include/llvm/ADT/BitVector.h

44

But in many cases you don't actually care about endianness. For example, for count(), only the number of 1s matters. You don't need to swap bytes. So I think using ulittle32_t is inefficient.

[bryant]

include/llvm/ADT/BitVector.h

480

not sure if ub is good, regardless. maybe return WordLE(WW); and let packed_endian_specific_integral::operator value_type do the potential conversion for you through void *, which is one of two exceptions to strict aliasing.

[zturner]

include/llvm/ADT/BitVector.h

44

But if you don't care about endianness, then it doesn't matter what you pass to popcnt either, so long as it contains the same number of 1s. So you could write it like this:

size_type count() const {
  unsigned NumBits = 0;
  for (unsigned i = 0; i < Bytes.size(); i += WORD_SIZE)
    NumBits += countPopulation(*reinterpret_cast<uint32_t*>(&Bytes[i]));
  return NumBits;
}

Maybe it's better to delete the Words array entirely and just do word-sized operations by casting the underlying byte vector.

[ruiu]

include/llvm/ADT/BitVector.h

44

I tried to remove Words, but the result did not look great. Casting to Word everywhere makes code longer and error-prone. As an example, current count() is this, which is much easier to understand than yours.

size_type count() const {
  unsigned N = 0;
  for (Word W : Words)
    N += countPopulation(W);
  return N;
}

[ruiu]

• Use getSwappedBytes instead of packed_endian_specific_integral.

[ruiu]

include/llvm/ADT/BitVector.h

480

I used getSwappedBytes instead.

[zturner]

include/llvm/ADT/BitVector.h

478

I don't think it's a good idea to check system endianness. This would be the only place in the entire codebase we checked it aside from something in libfuzzer. What about the alternative that bryant proposed earlier?

[ruiu]

include/llvm/ADT/BitVector.h

480

How does it work? What is WW?

[bryant]

include/llvm/ADT/BitVector.h

480

typo. i meant W. as for how it works:

explicit packed_endian_specific_integral(value_type val) { *this = val; }

operator value_type() const {
  return endian::read<value_type, endian, alignment>(
    (const void*)Value.buffer);
}

[ruiu]

include/llvm/ADT/BitVector.h

480

Is it different from

return *(WordLE *)((void *)&W)

?

[bryant]

include/llvm/ADT/BitVector.h

480

unfortunately, that would also be ub.

[majnemer]

Have you actually measured this to be a major improvement? Are there so many bits that the old way is a major bottleneck?
The BitVector is used for the CodeGen and optimizer, I'm not entirely convinced it makes sense to modify this generic datastructure so drastically for PDBs...

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/Support/MathExtras.h"
+#include "llvm/Support/SwapByteOrder.h"
 #include <algorithm>
 #include <cassert>
 #include <climits>
 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
 
 namespace llvm {
 
 class BitVector {
-  typedef unsigned long BitWord;
+  typedef unsigned long Word;
 
-  enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
+  enum { WORD_SIZE = (unsigned)sizeof(Word) * CHAR_BIT };
 
-  static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
-                "Unsupported word size");
+  static_assert(WORD_SIZE == 64 || WORD_SIZE == 32, "Unsupported word size");
 
-  BitWord  *Bits;        // Actual bits.
-  unsigned Size;         // Size of bitvector in bits.
-  unsigned Capacity;     // Number of BitWords allocated in the Bits array.
+  // Actual bits. Must be a multiple of sizeof(Word).
+  std::vector<uint8_t> Bytes;
+
+  // A reference to Bytes. There are many operations that are
+  // faster to do word-by-word than byte-by-byte. This ArrayRef
+  // provides a word-size access to the buffer.
+  // Note that because the first bit is stored to the first byte,
+  // Words are in the little endian order on all platforms.
+  MutableArrayRef<Word> Words;
+
+  // Size of bitvector in bits.
+  unsigned Size = 0;
 
 public:
   typedef unsigned size_type;
   // Encapsulation of a single bit.
   class reference {
     friend class BitVector;
 
-    BitWord *WordRef;
+    uint8_t *ByteRef;
     unsigned BitPos;
 
     reference();  // Undefined
 
   public:
     reference(BitVector &b, unsigned Idx) {
-      WordRef = &b.Bits[Idx / BITWORD_SIZE];
-      BitPos = Idx % BITWORD_SIZE;
+      ByteRef = &b.Bytes[Idx / 8];
+      BitPos = Idx % 8;
     }
 
     reference(const reference&) = default;
 
     reference &operator=(reference t) {
       *this = bool(t);
       return *this;
     }
 
     reference& operator=(bool t) {
       if (t)
-        *WordRef |= BitWord(1) << BitPos;
+        *ByteRef |= uint8_t(1) << BitPos;
       else
-        *WordRef &= ~(BitWord(1) << BitPos);
+        *ByteRef &= ~(uint8_t(1) << BitPos);
       return *this;
     }
 
-    operator bool() const {
-      return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
-    }
+    operator bool() const { return (*ByteRef) & (uint8_t(1) << BitPos); }
   };
 
-
   /// BitVector default ctor - Creates an empty bitvector.
-  BitVector() : Size(0), Capacity(0) {
-    Bits = nullptr;
-  }
+  BitVector() {}
 
   /// 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) {
-    Capacity = NumBitWords(s);
-    Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
-    init_words(Bits, Capacity, t);
-    if (t)
-      clear_unused_bits();
+  explicit BitVector(unsigned Size, bool T = false)
+      : Bytes(numWords(Size) * sizeof(Word)), Words(toWords(Bytes)),
+        Size(Size) {
+    memset(&Bytes[0], 0 - T, Bytes.size());
+    if (T)
+      clearUnusedBits();
   }
 
   /// BitVector copy ctor.
-  BitVector(const BitVector &RHS) : Size(RHS.size()) {
-    if (Size == 0) {
-      Bits = nullptr;
-      Capacity = 0;
-      return;
-    }
-
-    Capacity = NumBitWords(RHS.size());
-    Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
-    std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord));
-  }
+  BitVector(const BitVector &RHS)
+      : Bytes(RHS.Bytes), Words(toWords(Bytes)), Size(RHS.Size) {}
 
   BitVector(BitVector &&RHS)
-    : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) {
-    RHS.Bits = nullptr;
-    RHS.Size = RHS.Capacity = 0;
-  }
-
-  ~BitVector() {
-    std::free(Bits);
-  }
+      : Bytes(std::move(RHS.Bytes)), Words(toWords(Bytes)), Size(RHS.Size) {}
 
   /// 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]);
-    return NumBits;
+    unsigned N = 0;
+    for (Word W : Words)
+      N += countPopulation(W);
+    return N;
   }
 
   /// any - Returns true if any bit is set.
   bool any() const {
-    for (unsigned i = 0; i < NumBitWords(size()); ++i)
-      if (Bits[i] != 0)
+    for (Word W : Words)
+      if (W)
         return true;
     return false;
   }
 
   /// all - Returns true if all bits are set.
   bool all() const {
-    for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
-      if (Bits[i] != ~0UL)
+    for (unsigned I = 0; I < Size / WORD_SIZE; ++I)
+      if (Words[I] != ~0UL)
         return false;
 
     // If bits remain check that they are ones. The unused bits are always zero.
-    if (unsigned Remainder = Size % BITWORD_SIZE)
-      return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1;
-
+    if (unsigned Remainder = Size % WORD_SIZE)
+      return fromLE(Words.back()) == (1UL << Remainder) - 1;
     return true;
   }
 
   /// none - Returns true if none of the bits are set.
   bool none() const {
     return !any();
   }
 
   /// find_first - Returns the index of the first set bit, -1 if none
   /// of the bits are set.
   int find_first() const {
-    for (unsigned i = 0; i < NumBitWords(size()); ++i)
-      if (Bits[i] != 0)
-        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
+    for (unsigned I = 0; I < Words.size(); ++I)
+      if (Words[I])
+        return I * WORD_SIZE + countTrailingZeros(fromLE(Words[I]));
     return -1;
   }
 
   /// find_next - Returns the index of the next set bit following the
   /// "Prev" bit. Returns -1 if the next set bit is not found.
   int find_next(unsigned Prev) const {
     ++Prev;
     if (Prev >= Size)
       return -1;
 
-    unsigned WordPos = Prev / BITWORD_SIZE;
-    unsigned BitPos = Prev % BITWORD_SIZE;
-    BitWord Copy = Bits[WordPos];
-    // Mask off previous bits.
-    Copy &= ~0UL << BitPos;
+    unsigned WordPos = Prev / WORD_SIZE;
+    unsigned BitPos = Prev % WORD_SIZE;
+    Word Copy = fromLE(Words[WordPos]);
+    Copy &= ~0UL << BitPos; // Mask off previous bits
 
     if (Copy != 0)
-      return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
+      return WordPos * WORD_SIZE + countTrailingZeros(Copy);
 
     // Check subsequent words.
-    for (unsigned i = WordPos+1; i < NumBitWords(size()); ++i)
-      if (Bits[i] != 0)
-        return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
+    for (unsigned I = WordPos + 1; I < numWords(size()); ++I)
+      if (Words[I] != 0)
+        return I * WORD_SIZE + countTrailingZeros(fromLE(Words[I]));
     return -1;
   }
 
   /// clear - Clear all bits.
   void clear() {
+    Bytes.clear();
+    Words = {};
     Size = 0;
   }
 
   /// resize - Grow or shrink the bitvector.
-  void resize(unsigned N, bool t = false) {
-    if (N > Capacity * BITWORD_SIZE) {
-      unsigned OldCapacity = Capacity;
-      grow(N);
-      init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t);
-    }
+  void resize(unsigned N, bool T = false) {
+    setUnusedBits(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);
+    if (numWords(N) > Words.size()) {
+      unsigned Old = Bytes.size();
+      Bytes.resize(numWords(N) * sizeof(Word));
+      Words = toWords(Bytes);
+      memset(&Bytes[Old], 0 - T, Bytes.size() - Old);
+    } else {
+      // Update the size, and clear out any bits that are now unused.
+      Bytes.resize(numWords(N) * sizeof(Word));
+      Words = toWords(Bytes);
+    }
 
-    // Update the size, and clear out any bits that are now unused
-    unsigned OldSize = Size;
     Size = N;
-    if (t || N < OldSize)
-      clear_unused_bits();
+    clearUnusedBits();
   }
 
-  void reserve(unsigned N) {
-    if (N > Capacity * BITWORD_SIZE)
-      grow(N);
-  }
+  void reserve(unsigned N) { Bytes.reserve(numWords(N) * sizeof(Word)); }
 
   // Set, reset, flip
   BitVector &set() {
-    init_words(Bits, Capacity, true);
-    clear_unused_bits();
+    memset(&Bytes[0], -1, Bytes.size());
+    clearUnusedBits();
     return *this;
   }
 
   BitVector &set(unsigned Idx) {
-    assert(Bits && "Bits never allocated");
-    Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
+    Bytes[Idx / 8] |= uint8_t(1) << (Idx % 8);
     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!");
 
     if (I == E) return *this;
 
-    if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
-      BitWord EMask = 1UL << (E % BITWORD_SIZE);
-      BitWord IMask = 1UL << (I % BITWORD_SIZE);
-      BitWord Mask = EMask - IMask;
-      Bits[I / BITWORD_SIZE] |= Mask;
+    if (I / 8 == E / 8) {
+      uint8_t IMask = 1 << (I % 8);
+      uint8_t EMask = 1 << (E % 8);
+      uint8_t Mask = EMask - IMask;
+      Bytes[I / 8] |= Mask;
       return *this;
     }
 
-    BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
-    Bits[I / BITWORD_SIZE] |= PrefixMask;
-    I = alignTo(I, BITWORD_SIZE);
+    uint8_t PrefixMask = -1 << (I % 8);
+    Bytes[I / 8] |= PrefixMask;
+    I = alignTo(I, 8);
 
-    for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
-      Bits[I / BITWORD_SIZE] = ~0UL;
+    memset(&Bytes[I / 8], -1, E / 8 - I / 8);
 
-    BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
-    if (I < E)
-      Bits[I / BITWORD_SIZE] |= PostfixMask;
+    if (E % 8) {
+      uint8_t PostfixMask = (1 << (E % 8)) - 1;
+      Bytes[E / 8] |= PostfixMask;
+    }
 
     return *this;
   }
 
   BitVector &reset() {
-    init_words(Bits, Capacity, false);
+    memset(&Bytes[0], 0, Bytes.size());
     return *this;
   }
 
   BitVector &reset(unsigned Idx) {
-    Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
+    Bytes[Idx / 8] &= ~(1 << (Idx % 8));
     return *this;
   }
 
   /// reset - Efficiently reset a range of bits in [I, E)
   BitVector &reset(unsigned I, unsigned E) {
     assert(I <= E && "Attempted to reset backwards range!");
     assert(E <= size() && "Attempted to reset out-of-bounds range!");
 
     if (I == E) return *this;
 
-    if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
-      BitWord EMask = 1UL << (E % BITWORD_SIZE);
-      BitWord IMask = 1UL << (I % BITWORD_SIZE);
-      BitWord Mask = EMask - IMask;
-      Bits[I / BITWORD_SIZE] &= ~Mask;
+    if (I / 8 == E / 8) {
+      uint8_t IMask = 1 << (I % 8);
+      uint8_t EMask = 1 << (E % 8);
+      uint8_t Mask = EMask - IMask;
+      Words[I / 8] &= ~Mask;
       return *this;
     }
 
-    BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
-    Bits[I / BITWORD_SIZE] &= ~PrefixMask;
-    I = alignTo(I, BITWORD_SIZE);
+    uint8_t PrefixMask = -1 << (I % 8);
+    Bytes[I / 8] &= ~PrefixMask;
+    I = alignTo(I, 8);
 
-    for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
-      Bits[I / BITWORD_SIZE] = 0UL;
+    memset(&Bytes[I / 8], 0, E / 8 - I / 8);
 
-    BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
-    if (I < E)
-      Bits[I / BITWORD_SIZE] &= ~PostfixMask;
+    if (E % 8) {
+      uint8_t PostfixMask = (1 << (E % 8)) - 1;
+      Bytes[E / 8] &= ~PostfixMask;
+    }
 
     return *this;
   }
 
   BitVector &flip() {
-    for (unsigned i = 0; i < NumBitWords(size()); ++i)
-      Bits[i] = ~Bits[i];
-    clear_unused_bits();
+    for (unsigned I = 0; I < Words.size(); ++I)
+      Words[I] = ~Words[I];
+    clearUnusedBits();
     return *this;
   }
 
   BitVector &flip(unsigned Idx) {
-    Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
+    Bytes[Idx / 8] ^= 1 << (Idx % 8);
     return *this;
   }
 
   // Indexing.
   reference operator[](unsigned Idx) {
-    assert (Idx < Size && "Out-of-bounds Bit access.");
+    assert(Idx < Size && "Out-of-bounds Bit access.");
     return reference(*this, Idx);
   }
 
   bool operator[](unsigned Idx) const {
     assert (Idx < Size && "Out-of-bounds Bit access.");
-    BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
-    return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
+    return Bytes[Idx / 8] & (1 << (Idx % 8));
   }
 
   bool test(unsigned Idx) const {
     return (*this)[Idx];
   }
 
   /// Test if any common bits are set.
   bool anyCommon(const BitVector &RHS) const {
-    unsigned ThisWords = NumBitWords(size());
-    unsigned RHSWords  = NumBitWords(RHS.size());
-    for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
-      if (Bits[i] & RHS.Bits[i])
+    unsigned ThisWords = Words.size();
+    unsigned RHSWords = RHS.Words.size();
+    for (unsigned I = 0, E = std::min(ThisWords, RHSWords); I != E; ++I)
+      if (Words[I] & RHS.Words[I])
         return true;
     return false;
   }
 
   // Comparison operators.
   bool operator==(const BitVector &RHS) const {
-    unsigned ThisWords = NumBitWords(size());
-    unsigned RHSWords  = NumBitWords(RHS.size());
-    unsigned i;
-    for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
-      if (Bits[i] != RHS.Bits[i])
+    unsigned ThisWords = Words.size();
+    unsigned RHSWords = RHS.Words.size();
+    unsigned I;
+    for (I = 0; I != std::min(ThisWords, RHSWords); ++I)
+      if (Words[I] != RHS.Words[I])
         return false;
 
     // Verify that any extra words are all zeros.
-    if (i != ThisWords) {
-      for (; i != ThisWords; ++i)
-        if (Bits[i])
+    if (I != ThisWords) {
+      for (; I != ThisWords; ++I)
+        if (Words[I])
           return false;
-    } else if (i != RHSWords) {
-      for (; i != RHSWords; ++i)
-        if (RHS.Bits[i])
+    } else if (I != RHSWords) {
+      for (; I != RHSWords; ++I)
+        if (RHS.Words[I])
           return false;
     }
     return true;
   }
 
   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 i;
-    for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
-      Bits[i] &= RHS.Bits[i];
+    unsigned ThisWords = Words.size();
+    unsigned RHSWords = RHS.Words.size();
+    unsigned I;
+    for (I = 0; I != std::min(ThisWords, RHSWords); ++I)
+      Words[I] &= RHS.Words[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;
-
+    for (; I != ThisWords; ++I)
+      Words[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)
-      Bits[i] &= ~RHS.Bits[i];
+    unsigned ThisWords = Words.size();
+    unsigned RHSWords = RHS.Words.size();
+    unsigned I;
+    for (I = 0; I != std::min(ThisWords, RHSWords); ++I)
+      Words[I] &= ~RHS.Words[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 i;
-    for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
-      if ((Bits[i] & ~RHS.Bits[i]) != 0)
+    unsigned ThisWords = Words.size();
+    unsigned RHSWords = RHS.Words.size();
+    unsigned I;
+    for (I = 0; I != std::min(ThisWords, RHSWords); ++I)
+      if ((Words[I] & ~RHS.Words[I]) != 0)
         return true;
 
-    for (; i != ThisWords ; ++i)
-      if (Bits[i] != 0)
+    for (; I != ThisWords; ++I)
+      if (Words[I] != 0)
         return true;
 
     return false;
   }
 
   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];
+    if (Size < RHS.Size)
+      resize(RHS.Size);
+    for (size_t I = 0, E = RHS.Words.size(); I != E; ++I)
+      Words[I] |= RHS.Words[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)
-      Bits[i] ^= RHS.Bits[i];
+    if (Size < RHS.Size)
+      resize(RHS.Size);
+    for (size_t I = 0, E = RHS.Words.size(); I != E; ++I)
+      Words[I] ^= RHS.Words[I];
     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)
-        std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord));
-      clear_unused_bits();
+    if (this == &RHS)
       return *this;
-    }
-
-    // Grow the bitvector to have enough elements.
-    Capacity = RHSWords;
-    assert(Capacity > 0 && "negative capacity?");
-    BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
-    std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord));
-
-    // Destroy the old bits.
-    std::free(Bits);
-    Bits = NewBits;
 
+    Bytes = RHS.Bytes;
+    Words = toWords(Bytes);
+    Size = RHS.Size;
     return *this;
   }
 
   const BitVector &operator=(BitVector &&RHS) {
-    if (this == &RHS) return *this;
+    if (this == &RHS)
+      return *this;
 
-    std::free(Bits);
-    Bits = RHS.Bits;
+    Bytes = std::move(RHS.Bytes);
+    Words = toWords(Bytes);
     Size = RHS.Size;
-    Capacity = RHS.Capacity;
-
-    RHS.Bits = nullptr;
-    RHS.Size = RHS.Capacity = 0;
-
     return *this;
   }
 
   void swap(BitVector &RHS) {
-    std::swap(Bits, RHS.Bits);
+    std::swap(Bytes, RHS.Bytes);
+    std::swap(Words, RHS.Words);
     std::swap(Size, RHS.Size);
-    std::swap(Capacity, RHS.Capacity);
   }
 
   //===--------------------------------------------------------------------===//
   // 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
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:
-  unsigned NumBitWords(unsigned S) const {
-    return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
+  unsigned numWords(unsigned S) const {
+    return (S + WORD_SIZE - 1) / WORD_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 (Capacity > UsedWords)
-      init_words(&Bits[UsedWords], (Capacity-UsedWords), t);
-
-    //  Then set any stray high bits of the last used word.
-    unsigned ExtraBits = Size % BITWORD_SIZE;
-    if (ExtraBits) {
-      BitWord ExtraBitMask = ~0UL << ExtraBits;
-      if (t)
-        Bits[UsedWords-1] |= ExtraBitMask;
-      else
-        Bits[UsedWords-1] &= ~ExtraBitMask;
-    }
+  MutableArrayRef<Word> toWords(std::vector<uint8_t> &Bytes) {
+    assert(Bytes.size() % sizeof(Word) == 0);
+    return {(Word *)&Bytes[0], Bytes.size() / sizeof(Word)};
   }
 
-  // Clear the unused bits in the high words.
-  void clear_unused_bits() {
-    set_unused_bits(false);
+  Word fromLE(Word W) const {
+#ifdef __BIG_ENDIAN__
+    return sys::getSwappedBytes(W);
+#endif
+    return W;
   }
 
-  void grow(unsigned NewSize) {
-    Capacity = std::max(NumBitWords(NewSize), Capacity * 2);
-    assert(Capacity > 0 && "realloc-ing zero space");
-    Bits = (BitWord *)std::realloc(Bits, Capacity * sizeof(BitWord));
-
-    clear_unused_bits();
+  // Set any stray high bits of the last used word.
+  void setUnusedBits(bool T) {
+    if (unsigned ExtraBits = Size % WORD_SIZE) {
+      Word ExtraBitMask = ~0UL << ExtraBits;
+      if (T)
+        Words.back() |= ExtraBitMask;
+      else
+        Words.back() &= ~ExtraBitMask;
     }
-
-  void init_words(BitWord *B, unsigned NumWords, bool t) {
-    memset(B, 0 - (int)t, NumWords*sizeof(BitWord));
   }
 
+  // Clear the unused bits in the high words.
+  void clearUnusedBits() { setUnusedBits(false); }
+
   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;
+    static_assert(WORD_SIZE % 32 == 0, "Unsupported Word size.");
+    MaskWords = std::min(MaskWords, (Size + 31) / 32);
+    const unsigned Scale = WORD_SIZE / 32;
     unsigned i;
     for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) {
-      BitWord BW = Bits[i];
-      // This inner loop should unroll completely when BITWORD_SIZE > 32.
-      for (unsigned b = 0; b != BITWORD_SIZE; b += 32) {
+      Word BW = Words[i];
+      // This inner loop should unroll completely when WORD_SIZE > 32.
+      for (unsigned b = 0; b != WORD_SIZE; b += 32) {
         uint32_t M = *Mask++;
         if (InvertMask) M = ~M;
-        if (AddBits) BW |=   BitWord(M) << b;
-        else         BW &= ~(BitWord(M) << b);
+        if (AddBits)
+          BW |= Word(M) << b;
+        else
+          BW &= ~(Word(M) << b);
       }
-      Bits[i] = BW;
+      Words[i] = BW;
     }
     for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
       uint32_t M = *Mask++;
       if (InvertMask) M = ~M;
-      if (AddBits) Bits[i] |=   BitWord(M) << b;
-      else         Bits[i] &= ~(BitWord(M) << b);
+      if (AddBits)
+        Words[i] |= Word(M) << b;
+      else
+        Words[i] &= ~(Word(M) << b);
     }
     if (AddBits)
-      clear_unused_bits();
+      clearUnusedBits();
   }
 
 public:
   /// Return the size (in bytes) of the bit vector.
-  size_t getMemorySize() const { return Capacity * sizeof(BitWord); }
+  size_t getMemorySize() const { return Bytes.capacity(); }
 };
 
 static inline size_t capacity_in_bytes(const BitVector &X) {
   return X.getMemorySize();
 }
 
 } // 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