Index: include/llvm/ADT/BitVector.h =================================================================== --- include/llvm/ADT/BitVector.h +++ include/llvm/ADT/BitVector.h @@ -14,7 +14,9 @@ #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 #include #include @@ -25,16 +27,24 @@ 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 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 Words; + + // Size of bitvector in bits. + unsigned Size = 0; public: typedef unsigned size_type; @@ -42,15 +52,15 @@ 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; @@ -62,55 +72,34 @@ 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; } @@ -120,30 +109,29 @@ /// 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; } @@ -155,9 +143,9 @@ /// 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; } @@ -168,63 +156,58 @@ 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); + + 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); } - // 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(); + 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; } @@ -235,35 +218,35 @@ 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; } @@ -274,50 +257,49 @@ 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 { @@ -326,31 +308,31 @@ /// 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; @@ -362,108 +344,88 @@ /// 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); } //===--------------------------------------------------------------------===// @@ -503,75 +465,70 @@ } 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 toWords(std::vector &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 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) { @@ -581,11 +538,8 @@ } // 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); - } +/// Implement std::swap in terms of BitVector swap. +inline void swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { LHS.swap(RHS); } } // end namespace std #endif // LLVM_ADT_BITVECTOR_H