Index: include/llvm/ADT/BitVector.h =================================================================== --- include/llvm/ADT/BitVector.h +++ include/llvm/ADT/BitVector.h @@ -14,6 +14,8 @@ #ifndef LLVM_ADT_BITVECTOR_H #define LLVM_ADT_BITVECTOR_H +#include "llvm/ADT/ArrayRef.h" +#include "llvm/Support/Endian.h" #include "llvm/Support/MathExtras.h" #include #include @@ -32,8 +34,18 @@ static_assert(WORD_SIZE == 64 || WORD_SIZE == 32, "Unsupported word size"); - std::vector Words; - unsigned Size = 0; // Size of bitvector in bits. + // 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; @@ -41,15 +53,15 @@ class reference { friend class BitVector; - Word *WordRef; + uint8_t *ByteRef; unsigned BitPos; reference(); // Undefined public: reference(BitVector &b, unsigned Idx) { - WordRef = &b.Words[Idx / WORD_SIZE]; - BitPos = Idx % WORD_SIZE; + ByteRef = &b.Bytes[Idx / 8]; + BitPos = Idx % 8; } reference(const reference&) = default; @@ -61,14 +73,14 @@ reference& operator=(bool t) { if (t) - *WordRef |= Word(1) << BitPos; + *ByteRef |= uint8_t(1) << BitPos; else - *WordRef &= ~(Word(1) << BitPos); + *ByteRef &= ~(uint8_t(1) << BitPos); return *this; } operator bool() const { - return ((*WordRef) & (Word(1) << BitPos)) != 0; + return (*ByteRef) & (uint8_t(1) << BitPos); } }; @@ -79,15 +91,20 @@ /// BitVector ctor - Creates a bitvector of specified number of bits. All /// bits are initialized to the specified value. explicit BitVector(unsigned Size, bool T = false) - : Words(NumWords(Size)), Size(Size) { - init_words(&Words[0], Words.size(), T); + : Bytes(numWords(Size) * sizeof(Word)), Words(toWords(Bytes)), + Size(Size) { + memset(&Bytes[0], 0 - T, Bytes.size()); if (T) - clear_unused_bits(); + clearUnusedBits(); } /// BitVector copy ctor. - BitVector(const BitVector &RHS) : Words(RHS.Words), Size(RHS.Size) {} - BitVector(BitVector &&RHS) : Words(std::move(RHS.Words)), Size(RHS.Size) {} + BitVector(const BitVector &RHS) + : Bytes(RHS.Bytes), Words(toWords(Bytes)), Size(RHS.Size) {} + + BitVector(BitVector &&RHS) + : 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; } @@ -97,16 +114,16 @@ /// count - Returns the number of bits which are set. size_type count() const { - unsigned NumBits = 0; - for (unsigned I = 0; I < NumWords(Size); ++I) - NumBits += countPopulation(Words[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 < NumWords(Size); ++I) - if (Words[I] != 0) + for (Word W : Words) + if (W) return true; return false; } @@ -119,7 +136,7 @@ // If bits remain check that they are ones. The unused bits are always zero. if (unsigned Remainder = Size % WORD_SIZE) - return Words[Size / WORD_SIZE] == (1UL << Remainder) - 1; + return fromLE(Words.back()) == (1UL << Remainder) - 1; return true; } @@ -131,9 +148,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 < NumWords(Size); ++I) - if (Words[I] != 0) - return I * WORD_SIZE + countTrailingZeros(Words[I]); + for (unsigned I = 0; I < Words.size(); ++I) + if (Words[I]) + return I * WORD_SIZE + countTrailingZeros(fromLE(Words[I])); return -1; } @@ -146,56 +163,58 @@ unsigned WordPos = Prev / WORD_SIZE; unsigned BitPos = Prev % WORD_SIZE; - Word Copy = Words[WordPos]; - // Mask off previous bits. - Copy &= ~0UL << BitPos; + Word Copy = fromLE(Words[WordPos]); + Copy &= ~0UL << BitPos; // Mask off previous bits if (Copy != 0) return WordPos * WORD_SIZE + countTrailingZeros(Copy); // Check subsequent words. - for (unsigned I = WordPos + 1; I < NumWords(size()); ++I) + for (unsigned I = WordPos + 1; I < numWords(size()); ++I) if (Words[I] != 0) - return I * WORD_SIZE + countTrailingZeros(Words[I]); + return I * WORD_SIZE + countTrailingZeros(fromLE(Words[I])); return -1; } /// clear - Clear all bits. void clear() { - Words.clear(); + Bytes.clear(); + Words = {}; Size = 0; } /// resize - Grow or shrink the bitvector. void resize(unsigned N, bool T = false) { - set_unused_bits(T); + setUnusedBits(T); - if (NumWords(N) > Words.size()) { - unsigned Old = Words.size(); - Words.resize(NumWords(N)); - init_words(&Words[Old], (Words.size() - Old), 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. - Words.resize(NumWords(N)); + Bytes.resize(numWords(N) * sizeof(Word)); + Words = toWords(Bytes); } Size = N; - clear_unused_bits(); + clearUnusedBits(); } void reserve(unsigned N) { - Words.reserve(NumWords(N)); + Bytes.reserve(numWords(N) * sizeof(Word)); } // Set, reset, flip BitVector &set() { - init_words(&Words[0], Words.size(), true); - clear_unused_bits(); + memset(&Bytes[0], -1, Bytes.size()); + clearUnusedBits(); return *this; } BitVector &set(unsigned Idx) { - Words[Idx / WORD_SIZE] |= Word(1) << (Idx % WORD_SIZE); + Bytes[Idx / 8] |= uint8_t(1) << (Idx % 8); return *this; } @@ -206,30 +225,30 @@ if (I == E) return *this; - if (I / WORD_SIZE == E / WORD_SIZE) { - Word EMask = 1UL << (E % WORD_SIZE); - Word IMask = 1UL << (I % WORD_SIZE); - Word Mask = EMask - IMask; - Words[I / WORD_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; } - Word PrefixMask = ~0UL << (I % WORD_SIZE); - Words[I / WORD_SIZE] |= PrefixMask; - I = alignTo(I, WORD_SIZE); + uint8_t PrefixMask = -1 << (I % 8); + Bytes[I / 8] |= PrefixMask; + I = alignTo(I, 8); - for (; I + WORD_SIZE <= E; I += WORD_SIZE) - Words[I / WORD_SIZE] = ~0UL; + memset(&Bytes[I / 8], -1, E / 8 - I / 8); - Word PostfixMask = (1UL << (E % WORD_SIZE)) - 1; - if (I < E) - Words[I / WORD_SIZE] |= PostfixMask; + if (E % 8) { + uint8_t PostfixMask = (1 << (E % 8)) - 1; + Bytes[E / 8] |= PostfixMask; + } return *this; } BitVector &reset() { - init_words(&Words[0], Words.size(), false); + memset(&Bytes[0], 0, Bytes.size()); return *this; } @@ -245,24 +264,24 @@ if (I == E) return *this; - if (I / WORD_SIZE == E / WORD_SIZE) { - Word EMask = 1UL << (E % WORD_SIZE); - Word IMask = 1UL << (I % WORD_SIZE); - Word Mask = EMask - IMask; - Words[I / WORD_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; } - Word PrefixMask = ~0UL << (I % WORD_SIZE); - Words[I / WORD_SIZE] &= ~PrefixMask; - I = alignTo(I, WORD_SIZE); + uint8_t PrefixMask = -1 << (I % 8); + Bytes[I / 8] &= ~PrefixMask; + I = alignTo(I, 8); - for (; I + WORD_SIZE <= E; I += WORD_SIZE) - Words[I / WORD_SIZE] = 0UL; + memset(&Bytes[I / 8], 0, E / 8 - I / 8); - Word PostfixMask = (1UL << (E % WORD_SIZE)) - 1; - if (I < E) - Words[I / WORD_SIZE] &= ~PostfixMask; + if (E % 8) { + uint8_t PostfixMask = (1 << (E % 8)) - 1; + Bytes[E / 8] &= ~PostfixMask; + } return *this; } @@ -270,25 +289,24 @@ BitVector &flip() { for (unsigned I = 0; I < Words.size(); ++I) Words[I] = ~Words[I]; - clear_unused_bits(); + clearUnusedBits(); return *this; } BitVector &flip(unsigned Idx) { - Words[Idx / WORD_SIZE] ^= Word(1) << (Idx % WORD_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."); - Word Mask = Word(1) << (Idx % WORD_SIZE); - return (Words[Idx / WORD_SIZE] & Mask) != 0; + return Bytes[Idx / 8] & (1 << (Idx % 8)); } bool test(unsigned Idx) const { @@ -297,8 +315,8 @@ /// Test if any common bits are set. bool anyCommon(const BitVector &RHS) const { - unsigned ThisWords = NumWords(Size); - unsigned RHSWords = NumWords(RHS.Size); + 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; @@ -307,8 +325,8 @@ // Comparison operators. bool operator==(const BitVector &RHS) const { - unsigned ThisWords = NumWords(size()); - unsigned RHSWords = NumWords(RHS.size()); + 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]) @@ -333,8 +351,8 @@ /// Intersection, union, disjoint union. BitVector &operator&=(const BitVector &RHS) { - unsigned ThisWords = NumWords(Size); - unsigned RHSWords = NumWords(RHS.Size); + 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]; @@ -349,8 +367,8 @@ /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. BitVector &reset(const BitVector &RHS) { - unsigned ThisWords = NumWords(Size); - unsigned RHSWords = NumWords(RHS.Size); + 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]; @@ -360,8 +378,8 @@ /// test - Check if (This - RHS) is zero. /// This is the same as reset(RHS) and any(). bool test(const BitVector &RHS) const { - unsigned ThisWords = NumWords(Size); - unsigned RHSWords = NumWords(RHS.Size); + 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) @@ -377,7 +395,7 @@ BitVector &operator|=(const BitVector &RHS) { if (Size < RHS.Size) resize(RHS.Size); - for (size_t I = 0, E = NumWords(RHS.Size); I != E; ++I) + for (size_t I = 0, E = Words.size(); I != E; ++I) Words[I] |= RHS.Words[I]; return *this; } @@ -385,7 +403,7 @@ BitVector &operator^=(const BitVector &RHS) { if (Size < RHS.Size) resize(RHS.Size); - for (size_t I = 0, E = NumWords(RHS.Size); I != E; ++I) + for (size_t I = 0, E = Words.size(); I != E; ++I) Words[I] ^= RHS.Words[I]; return *this; } @@ -395,7 +413,8 @@ if (this == &RHS) return *this; - Words = RHS.Words; + Bytes = RHS.Bytes; + Words = toWords(Bytes); Size = RHS.Size; return *this; } @@ -404,12 +423,14 @@ if (this == &RHS) return *this; - Words = std::move(RHS.Words); + Bytes = std::move(RHS.Bytes); + Words = toWords(Bytes); Size = RHS.Size; return *this; } void swap(BitVector &RHS) { + std::swap(Bytes, RHS.Bytes); std::swap(Words, RHS.Words); std::swap(Size, RHS.Size); } @@ -451,12 +472,23 @@ } private: - unsigned NumWords(unsigned S) const { + unsigned numWords(unsigned S) const { return (S + WORD_SIZE - 1) / WORD_SIZE; } + MutableArrayRef toWords(std::vector &Bytes) { + assert(Bytes.size() % sizeof(Word) == 0); + return {(Word *)&Bytes[0], Bytes.size() / sizeof(Word)}; + } + + Word fromLE(Word W) const { + using WordLE = support::detail::packed_endian_specific_integral< + Word, support::little, false>; + return *(WordLE *)&W; + } + // Set any stray high bits of the last used word. - void set_unused_bits(bool T) { + void setUnusedBits(bool T) { if (unsigned ExtraBits = Size % WORD_SIZE) { Word ExtraBitMask = ~0UL << ExtraBits; if (T) @@ -467,12 +499,8 @@ } // Clear the unused bits in the high words. - void clear_unused_bits() { - set_unused_bits(false); - } - - void init_words(Word *B, unsigned NumWords, bool t) { - memset(B, 0 - (int)t, NumWords * sizeof(Word)); + void clearUnusedBits() { + setUnusedBits(false); } template @@ -499,12 +527,12 @@ 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 Words.capacity() * sizeof(Word); } + size_t getMemorySize() const { return Bytes.capacity(); } }; static inline size_t capacity_in_bytes(const BitVector &X) {