Index: llvm/include/llvm/ADT/BitVector.h =================================================================== --- llvm/include/llvm/ADT/BitVector.h +++ llvm/include/llvm/ADT/BitVector.h @@ -71,7 +71,8 @@ } }; -class BitVector { +class BitVectorBase { +protected: typedef uintptr_t BitWord; enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; @@ -79,11 +80,13 @@ static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32, "Unsupported word size"); - MutableArrayRef Bits; // Actual bits. - unsigned Size; // Size of bitvector in bits. + static unsigned NumBitWords(unsigned S) { + return (S + BITWORD_SIZE - 1) / BITWORD_SIZE; + } public: typedef unsigned size_type; + // Encapsulation of a single bit. class reference { friend class BitVector; @@ -92,8 +95,8 @@ unsigned BitPos; public: - reference(BitVector &b, unsigned Idx) { - WordRef = &b.Bits[Idx / BITWORD_SIZE]; + reference(BitWord *Bits, unsigned Idx) { + WordRef = Bits + (Idx / BITWORD_SIZE); BitPos = Idx % BITWORD_SIZE; } @@ -117,76 +120,80 @@ return ((*WordRef) & (BitWord(1) << BitPos)) != 0; } }; +}; - typedef const_set_bits_iterator_impl const_set_bits_iterator; +/// A CRTP base class for logic and interface shared by BitVector and the +/// large-mode of SmallBitVector. +/// +/// The derived class should define the following interface: +/// +/// class DerivedExample : BitVectorImpl { +/// size_type getSize() const; +/// void setSize(size_type N); +/// size_type getCapacity() const; +/// BitWord *getBitsPtr(); +/// const BitWord *getBitsPtr() const; +/// void growImpl(size_type NewCapacity); +/// }; +template class BitVectorImpl : public BitVectorBase { + template friend class BitVectorImpl; + + Derived &self() { return static_cast(*this); } + const Derived &self() const { return static_cast(*this); } + +protected: + MutableArrayRef getBits() { + return MutableArrayRef(self().getBitsPtr(), self().getCapacity()); + } + ArrayRef getActiveBits() const { + return ArrayRef(self().getBitsPtr(), + NumBitWords(self().getSize())); + } + MutableArrayRef getActiveBits() { + return MutableArrayRef(self().getBitsPtr(), + NumBitWords(self().getSize())); + } + +public: + typedef const_set_bits_iterator_impl const_set_bits_iterator; typedef const_set_bits_iterator set_iterator; const_set_bits_iterator set_bits_begin() const { - return const_set_bits_iterator(*this); + return const_set_bits_iterator(self()); } const_set_bits_iterator set_bits_end() const { - return const_set_bits_iterator(*this, -1); + return const_set_bits_iterator(self(), -1); } iterator_range 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); - if (t) - clear_unused_bits(); - } - - /// BitVector copy ctor. - BitVector(const BitVector &RHS) : Size(RHS.size()) { - if (Size == 0) { - Bits = MutableArrayRef(); - return; - } - - size_t Capacity = NumBitWords(RHS.size()); - Bits = allocate(Capacity); - std::memcpy(Bits.data(), RHS.Bits.data(), Capacity * sizeof(BitWord)); - } - - BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size) { - RHS.Bits = MutableArrayRef(); - RHS.Size = 0; - } - - ~BitVector() { std::free(Bits.data()); } - /// empty - Tests whether there are no bits in this bitvector. - bool empty() const { return Size == 0; } + bool empty() const { return size() == 0; } /// size - Returns the number of bits in this bitvector. - size_type size() const { return Size; } + size_type size() const { return self().getSize(); } /// 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 (BitWord Word : getActiveBits()) + NumBits += countPopulation(Word); 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) + for (BitWord Word : getActiveBits()) + if (Word != 0) return true; return false; } /// all - Returns true if all bits are set. bool all() const { + ArrayRef Bits = getActiveBits(); + unsigned Size = size(); for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i) if (Bits[i] != ~BitWord(0)) return false; @@ -199,14 +206,13 @@ } /// none - Returns true if none of the bits are set. - bool none() const { - return !any(); - } + bool none() const { return !any(); } /// find_first_in - Returns the index of the first set bit in the range /// [Begin, End). Returns -1 if all bits in the range are unset. int find_first_in(unsigned Begin, unsigned End) const { - assert(Begin <= End && End <= Size); + ArrayRef Bits = getActiveBits(); + assert(Begin <= End && End <= size()); if (Begin == End) return -1; @@ -235,7 +241,8 @@ /// find_last_in - Returns the index of the last set bit in the range /// [Begin, End). Returns -1 if all bits in the range are unset. int find_last_in(unsigned Begin, unsigned End) const { - assert(Begin <= End && End <= Size); + ArrayRef Bits = getActiveBits(); + assert(Begin <= End && End <= size()); if (Begin == End) return -1; @@ -266,6 +273,8 @@ /// find_first_unset_in - Returns the index of the first unset bit in the /// range [Begin, End). Returns -1 if all bits in the range are set. int find_first_unset_in(unsigned Begin, unsigned End) const { + size_type Size = size(); + ArrayRef Bits = getActiveBits(); assert(Begin <= End && End <= Size); if (Begin == End) return -1; @@ -288,7 +297,7 @@ } if (Copy != ~BitWord(0)) { unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Copy); - return Result < size() ? Result : -1; + return Result < Size ? Result : -1; } } return -1; @@ -297,6 +306,8 @@ /// find_last_unset_in - Returns the index of the last unset bit in the /// range [Begin, End). Returns -1 if all bits in the range are set. int find_last_unset_in(unsigned Begin, unsigned End) const { + size_type Size = size(); + ArrayRef Bits = getActiveBits(); assert(Begin <= End && End <= Size); if (Begin == End) return -1; @@ -329,15 +340,17 @@ /// find_first - Returns the index of the first set bit, -1 if none /// of the bits are set. - int find_first() const { return find_first_in(0, Size); } + int find_first() const { return find_first_in(0, size()); } /// find_last - Returns the index of the last set bit, -1 if none of the bits /// are set. - int find_last() const { return find_last_in(0, Size); } + int find_last() const { return find_last_in(0, size()); } /// 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 { return find_first_in(Prev + 1, Size); } + int find_next(unsigned Prev) const { + return find_first_in(Prev + 1, size()); + } /// find_prev - Returns the index of the first set bit that precedes the /// the bit at \p PriorTo. Returns -1 if all previous bits are unset. @@ -345,17 +358,17 @@ /// find_first_unset - Returns the index of the first unset bit, -1 if all /// of the bits are set. - int find_first_unset() const { return find_first_unset_in(0, Size); } + int find_first_unset() const { return find_first_unset_in(0, size()); } /// find_next_unset - Returns the index of the next unset bit following the /// "Prev" bit. Returns -1 if all remaining bits are set. int find_next_unset(unsigned Prev) const { - return find_first_unset_in(Prev + 1, Size); + return find_first_unset_in(Prev + 1, size()); } /// find_last_unset - Returns the index of the last unset bit, -1 if all of /// the bits are set. - int find_last_unset() const { return find_last_unset_in(0, Size); } + int find_last_unset() const { return find_last_unset_in(0, size()); } /// find_prev_unset - Returns the index of the first unset bit that precedes /// the bit at \p PriorTo. Returns -1 if all previous bits are set. @@ -364,62 +377,64 @@ } /// clear - Removes all bits from the bitvector. Does not change capacity. - void clear() { - Size = 0; - } + void clear() { self().setSize(0); } /// resize - Grow or shrink the bitvector. - void resize(unsigned N, bool t = false) { - if (N > getBitCapacity()) { - unsigned OldCapacity = Bits.size(); + void resize(size_type N, bool t = false) { + size_type OldSize = size(); + if (N > getBitCapacity()) 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) + if (N > OldSize) { + size_type OldActiveWords = NumBitWords(OldSize); + size_type NewlyActiveWords = NumBitWords(N) - OldActiveWords; set_unused_bits(t); + init_words(getBits().slice(OldActiveWords, NewlyActiveWords), t); + } // Update the size, and clear out any bits that are now unused - unsigned OldSize = Size; - Size = N; + self().setSize(N); if (t || N < OldSize) clear_unused_bits(); } void reserve(unsigned N) { if (N > getBitCapacity()) - grow(N); + self().grow(N); } // Set, reset, flip - BitVector &set() { - init_words(Bits, true); + Derived &set() { + init_words(getActiveBits(), true); clear_unused_bits(); - return *this; + return self(); } - BitVector &set(unsigned Idx) { - assert(Bits.data() && "Bits never allocated"); + Derived &set(unsigned Idx) { + MutableArrayRef Bits = getActiveBits(); Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE); - return *this; + return self(); } /// set - Efficiently set a range of bits in [I, E) - BitVector &set(unsigned I, unsigned E) { + Derived &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 == E) + return self(); + + MutableArrayRef Bits = getActiveBits(); if (I / BITWORD_SIZE == E / BITWORD_SIZE) { BitWord EMask = BitWord(1) << (E % BITWORD_SIZE); BitWord IMask = BitWord(1) << (I % BITWORD_SIZE); BitWord Mask = EMask - IMask; Bits[I / BITWORD_SIZE] |= Mask; - return *this; + return self(); } BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE); @@ -433,32 +448,36 @@ if (I < E) Bits[I / BITWORD_SIZE] |= PostfixMask; - return *this; + return self(); } - BitVector &reset() { - init_words(Bits, false); - return *this; + Derived &reset() { + init_words(getActiveBits(), false); + return self(); } - BitVector &reset(unsigned Idx) { - Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE)); - return *this; + Derived &reset(unsigned Idx) { + getActiveBits()[Idx / BITWORD_SIZE] &= + ~(BitWord(1) << (Idx % BITWORD_SIZE)); + return self(); } /// reset - Efficiently reset a range of bits in [I, E) - BitVector &reset(unsigned I, unsigned E) { + Derived &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 == E) + return self(); + + MutableArrayRef Bits = getActiveBits(); if (I / BITWORD_SIZE == E / BITWORD_SIZE) { BitWord EMask = BitWord(1) << (E % BITWORD_SIZE); BitWord IMask = BitWord(1) << (I % BITWORD_SIZE); BitWord Mask = EMask - IMask; Bits[I / BITWORD_SIZE] &= ~Mask; - return *this; + return self(); } BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE); @@ -472,31 +491,32 @@ if (I < E) Bits[I / BITWORD_SIZE] &= ~PostfixMask; - return *this; + return self(); } - BitVector &flip() { - for (unsigned i = 0; i < NumBitWords(size()); ++i) - Bits[i] = ~Bits[i]; + Derived &flip() { + for (BitWord &Word : getActiveBits()) { + Word = ~Word; + } clear_unused_bits(); - return *this; + return self(); } - BitVector &flip(unsigned Idx) { - Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE); - return *this; + Derived &flip(unsigned Idx) { + getActiveBits()[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE); + return self(); } // Indexing. reference operator[](unsigned Idx) { - assert (Idx < Size && "Out-of-bounds Bit access."); - return reference(*this, Idx); + assert(Idx < size() && "Out-of-bounds Bit access."); + return reference(self().getBitsPtr(), Idx); } bool operator[](unsigned Idx) const { - assert (Idx < Size && "Out-of-bounds Bit access."); + assert(Idx < size() && "Out-of-bounds Bit access."); BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE); - return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; + return (getActiveBits()[Idx / BITWORD_SIZE] & Mask) != 0; } bool test(unsigned Idx) const { @@ -504,131 +524,112 @@ } // Push single bit to end of vector. - void push_back(bool Val) { - unsigned OldSize = Size; - unsigned NewSize = Size + 1; - - // Resize, which will insert zeros. - // If we already fit then the unused bits will be already zero. - if (NewSize > getBitCapacity()) - resize(NewSize, false); - else - Size = NewSize; - - // If true, set single bit. - if (Val) - set(OldSize); - } + void push_back(bool Val) { resize(size() + 1, Val); } /// Test if any common bits are set. - bool anyCommon(const BitVector &RHS) const { - unsigned ThisWords = NumBitWords(size()); - unsigned RHSWords = NumBitWords(RHS.size()); + bool anyCommon(const Derived &RHS) const { + ArrayRef ThisBits = getActiveBits(); + ArrayRef RHSBits = RHS.getActiveBits(); + unsigned ThisWords = ThisBits.size(); + unsigned RHSWords = RHSBits.size(); for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i) - if (Bits[i] & RHS.Bits[i]) + if (ThisBits[i] & RHSBits[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]) - return false; - - // Verify that any extra words are all zeros. - if (i != ThisWords) { - for (; i != ThisWords; ++i) - if (Bits[i]) - return false; - } else if (i != RHSWords) { - for (; i != RHSWords; ++i) - if (RHS.Bits[i]) - return false; - } - return true; + bool operator==(const Derived &RHS) const { + return size() == RHS.size() && + getActiveBits() == RHS.getActiveBits(); } - bool operator!=(const BitVector &RHS) const { - return !(*this == RHS); - } + bool operator!=(const Derived &RHS) const { return !(*this == RHS); } /// Intersection, union, disjoint union. - BitVector &operator&=(const BitVector &RHS) { - unsigned ThisWords = NumBitWords(size()); - unsigned RHSWords = NumBitWords(RHS.size()); + Derived &operator&=(const Derived &RHS) { + MutableArrayRef ThisBits = getActiveBits(); + ArrayRef RHSBits = RHS.getActiveBits(); + unsigned ThisWords = ThisBits.size(); + unsigned RHSWords = RHSBits.size(); unsigned i; for (i = 0; i != std::min(ThisWords, RHSWords); ++i) - Bits[i] &= RHS.Bits[i]; + ThisBits[i] &= RHSBits[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; + ThisBits[i] = 0; - return *this; + return self(); } /// 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()); + Derived &reset(const Derived &RHS) { + MutableArrayRef ThisBits = getActiveBits(); + ArrayRef RHSBits = RHS.getActiveBits(); + unsigned ThisWords = ThisBits.size(); + unsigned RHSWords = RHSBits.size(); unsigned i; for (i = 0; i != std::min(ThisWords, RHSWords); ++i) - Bits[i] &= ~RHS.Bits[i]; - return *this; + ThisBits[i] &= ~RHSBits[i]; + return self(); } /// 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()); + bool test(const Derived &RHS) const { + ArrayRef ThisBits = getActiveBits(); + ArrayRef RHSBits = RHS.getActiveBits(); + unsigned ThisWords = ThisBits.size(); + unsigned RHSWords = RHSBits.size(); unsigned i; for (i = 0; i != std::min(ThisWords, RHSWords); ++i) - if ((Bits[i] & ~RHS.Bits[i]) != 0) + if ((ThisBits[i] & ~RHSBits[i]) != 0) return true; - for (; i != ThisWords ; ++i) - if (Bits[i] != 0) + for (; i != ThisWords; ++i) + if (ThisBits[i] != 0) return true; return false; } - BitVector &operator|=(const BitVector &RHS) { + Derived &operator|=(const Derived &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; + MutableArrayRef ThisBits = getActiveBits(); + ArrayRef RHSBits = RHS.getActiveBits(); + for (size_t i = 0, e = RHSBits.size(); i != e; ++i) + ThisBits[i] |= RHSBits[i]; + return self(); } - BitVector &operator^=(const BitVector &RHS) { + Derived &operator^=(const Derived &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; + MutableArrayRef ThisBits = getActiveBits(); + ArrayRef RHSBits = RHS.getActiveBits(); + for (size_t i = 0, e = RHSBits.size(); i != e; ++i) + ThisBits[i] ^= RHSBits[i]; + return self(); } - BitVector &operator>>=(unsigned N) { - assert(N <= Size); + Derived &operator>>=(unsigned N) { + assert(N <= size()); if (LLVM_UNLIKELY(empty() || N == 0)) - return *this; + return self(); - unsigned NumWords = NumBitWords(Size); + MutableArrayRef Bits = getActiveBits(); + unsigned NumWords = Bits.size(); assert(NumWords >= 1); wordShr(N / BITWORD_SIZE); unsigned BitDistance = N % BITWORD_SIZE; if (BitDistance == 0) - return *this; + return self(); // 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 @@ -662,22 +663,23 @@ Bits[NumWords - 1] >>= BitDistance; - return *this; + return self(); } - BitVector &operator<<=(unsigned N) { - assert(N <= Size); + Derived &operator<<=(unsigned N) { + assert(N <= size()); if (LLVM_UNLIKELY(empty() || N == 0)) - return *this; + return self(); - unsigned NumWords = NumBitWords(Size); + MutableArrayRef Bits = getActiveBits(); + unsigned NumWords = Bits.size(); assert(NumWords >= 1); wordShl(N / BITWORD_SIZE); unsigned BitDistance = N % BITWORD_SIZE; if (BitDistance == 0) - return *this; + return self(); // 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 @@ -712,68 +714,10 @@ Bits[0] <<= BitDistance; clear_unused_bits(); - return *this; - } - - // Assignment operator. - const BitVector &operator=(const BitVector &RHS) { - if (this == &RHS) return *this; - - Size = RHS.size(); - - // 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(); - RHS.Size = 0; - - return *this; + return self(); } - 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 getData() const { return Bits; } + ArrayRef getData() const { return getActiveBits(); } //===--------------------------------------------------------------------===// // Portable bit mask operations. @@ -811,7 +755,7 @@ applyMask(Mask, MaskWords); } -private: +protected: /// Perform a logical left shift of \p Count words by moving everything /// \p Count words to the right in memory. /// @@ -830,10 +774,9 @@ 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); + MutableArrayRef Bits = getActiveBits(); + auto Src = Bits.drop_back(Count); + auto Dest = Bits.drop_front(Count); // 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 @@ -850,64 +793,43 @@ 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); + MutableArrayRef Bits = getActiveBits(); + auto Src = Bits.drop_front(Count); + auto Dest = Bits.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)); } - MutableArrayRef allocate(size_t NumWords) { - BitWord *RawBits = static_cast( - safe_malloc(NumWords * sizeof(BitWord))); - return MutableArrayRef(RawBits, NumWords); - } - - 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. + // Set the unused bits in the high word. 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; + getActiveBits().back() |= ExtraBitMask; else - Bits[UsedWords-1] &= ~ExtraBitMask; + getActiveBits().back() &= ~ExtraBitMask; } } - // Clear the unused bits in the high words. + // Clear the unused bits in the high word. void clear_unused_bits() { set_unused_bits(false); } + // Increase capacity. This leaves newly allocated data uninitialised. The + // caller is responsible for initialising the newly allocated memory as + // appropriate. void grow(unsigned NewSize) { - size_t NewCapacity = std::max(NumBitWords(NewSize), Bits.size() * 2); + size_type NewCapacity = + std::max(NumBitWords(NewSize), self().getCapacity() * 2); assert(NewCapacity > 0 && "realloc-ing zero space"); - BitWord *NewBits = static_cast( - safe_realloc(Bits.data(), NewCapacity * sizeof(BitWord))); - Bits = MutableArrayRef(NewBits, NewCapacity); - clear_unused_bits(); + // growImpl is required to also update the capacity. + self().growImpl(NewCapacity); } - void init_words(MutableArrayRef B, bool t) { + static void init_words(MutableArrayRef B, bool t) { if (B.size() > 0) memset(B.data(), 0 - (int)t, B.size() * sizeof(BitWord)); } @@ -917,6 +839,7 @@ static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size."); MaskWords = std::min(MaskWords, (size() + 31) / 32); const unsigned Scale = BITWORD_SIZE / 32; + MutableArrayRef Bits = getActiveBits(); unsigned i; for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) { BitWord BW = Bits[i]; @@ -941,8 +864,150 @@ public: /// Return the size (in bytes) of the bit vector. - size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); } - size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; } + size_t getMemorySize() const { + return self().getCapacity() * sizeof(BitWord); + } + size_t getBitCapacity() const { return self().getCapacity() * BITWORD_SIZE; } +}; + +class BitVector : public BitVectorImpl { + friend class BitVectorImpl; + + BitWord *BitsPtr; // Pointer to data array. + size_type Size; // Size of bitvector in bits. + size_type Capacity; // Capacity of data array in BitWords. + + // Methods required by BitVectorImpl + size_type getSize() const { return Size; } + void setSize(size_type N) { Size = N; } + + size_type getCapacity() const { return Capacity; } + + BitWord *getBitsPtr() { return BitsPtr; } + const BitWord *getBitsPtr() const { return BitsPtr; } + + void growImpl(size_type NewCapacity) { + + BitsPtr = static_cast( + safe_realloc(BitsPtr, NewCapacity * sizeof(BitWord))); + Capacity = NewCapacity; + } + +public: + /// BitVector default ctor - Creates an empty bitvector. + BitVector() : BitsPtr(nullptr), Size(0), Capacity(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), Capacity(NumBitWords(s)) { + if (Size == 0) { + BitsPtr = nullptr; + return; + } + BitsPtr = allocate(Capacity); + init_words(getBits(), t); + if (t) + clear_unused_bits(); + } + + /// BitVector copy ctor. + BitVector(const BitVector &RHS) + : Size(RHS.size()), Capacity(NumBitWords(Size)) { + if (Size == 0) { + BitsPtr = nullptr; + return; + } + + BitsPtr = allocate(Capacity); + std::memcpy(BitsPtr, RHS.BitsPtr, Capacity * sizeof(BitWord)); + } + + BitVector(BitVector &&RHS) + : BitsPtr(RHS.BitsPtr), Size(RHS.Size), Capacity(RHS.Capacity) { + RHS.BitsPtr = nullptr; + RHS.Size = 0; + RHS.Capacity = 0; + } + + ~BitVector() { std::free(BitsPtr); } + + /// size - Returns the number of bits in this bitvector. + size_type size() const { return Size; } + + // Assignment operator. + const BitVector &operator=(const BitVector &RHS) { + if (this == &RHS) + return *this; + + Size = RHS.size(); + + // Handle tombstone when the BitVector is a key of a DenseHash. + if (RHS.isInvalid()) { + std::free(BitsPtr); + BitsPtr = nullptr; + Capacity = 0; + return *this; + } + + unsigned RHSWords = NumBitWords(Size); + if (Size <= getBitCapacity()) { + if (Size) + std::memcpy(BitsPtr, RHS.BitsPtr, RHSWords * sizeof(BitWord)); + return *this; + } + + // Grow the bitvector to have enough elements. + unsigned NewCapacity = RHSWords; + assert(NewCapacity > 0 && "negative capacity?"); + BitWord *NewBits = allocate(NewCapacity); + std::memcpy(NewBits, RHS.BitsPtr, NewCapacity * sizeof(BitWord)); + + // Destroy the old bits. + std::free(BitsPtr); + BitsPtr = NewBits; + + return *this; + } + + const BitVector &operator=(BitVector &&RHS) { + if (this == &RHS) + return *this; + + std::free(BitsPtr); + BitsPtr = RHS.BitsPtr; + Size = RHS.Size; + Capacity = RHS.Capacity; + + RHS.BitsPtr = nullptr; + RHS.Size = 0; + RHS.Capacity = 0; + + return *this; + } + + void swap(BitVector &RHS) { + std::swap(BitsPtr, RHS.BitsPtr); + std::swap(Size, RHS.Size); + std::swap(Capacity, RHS.Capacity); + } + + static BitVector getDenseMapEmptyKey() { + BitVector K; + K.Size = size_type(-1); + return K; + } + static BitVector getDenseMapTombstoneKey() { + BitVector K; + K.Size = size_type(-2); + return K; + } + bool isInvalid() const { return Size >= size_type(-2); } + +private: + BitWord *allocate(size_t NumWords) { + return static_cast(safe_malloc(NumWords * sizeof(BitWord))); + } }; inline size_t capacity_in_bytes(const BitVector &X) { @@ -950,11 +1015,11 @@ } template <> struct DenseMapInfo { - static inline BitVector getEmptyKey() { return BitVector(); } + static inline BitVector getEmptyKey() { + return BitVector::getDenseMapEmptyKey(); + } static inline BitVector getTombstoneKey() { - BitVector V; - V.invalid(); - return V; + return BitVector::getDenseMapTombstoneKey(); } static unsigned getHashValue(const BitVector &V) { return DenseMapInfo>>::getHashValue( @@ -962,7 +1027,7 @@ } static bool isEqual(const BitVector &LHS, const BitVector &RHS) { if (LHS.isInvalid() || RHS.isInvalid()) - return LHS.isInvalid() == RHS.isInvalid(); + return LHS.size() == RHS.size(); return LHS == RHS; } }; Index: llvm/include/llvm/ADT/SmallBitVector.h =================================================================== --- llvm/include/llvm/ADT/SmallBitVector.h +++ llvm/include/llvm/ADT/SmallBitVector.h @@ -32,11 +32,6 @@ /// pointer to a larger heap-allocated array when necessary. This allows normal /// "small" cases to be fast without losing generality for large inputs. class SmallBitVector { - // TODO: In "large" mode, a pointer to a BitVector is used, leading to an - // unnecessary level of indirection. It would be more efficient to use a - // pointer to memory containing size, allocation size, and the array of bits. - uintptr_t X = 1; - enum { // The number of bits in this class. NumBaseBits = sizeof(uintptr_t) * CHAR_BIT, @@ -59,8 +54,95 @@ static_assert(NumBaseBits == 64 || NumBaseBits == 32, "Unsupported word size"); + class LargeImpl : public BitVectorImpl { + public: + friend class BitVectorImpl; + friend class SmallBitVector; + + static_assert((sizeof(size_type) * 2) % sizeof(BitWord) == 0, + "Data array must be correctly aligned"); + + // When the containing SmallBitVector is in large-mode, this is a pointer + // to the large-mode data, accessed via the methods below in this class. + // In small-mode this field contains the bit-packed data accessed by + // methods in the SmallBitVector class. + uintptr_t X; + + static size_t getAllocSize(size_type Capacity) { + return sizeof(size_type) * 2 + sizeof(BitWord) * Capacity; + } + + // Methods required by BitVectorImpl. + size_type getSize() const { return reinterpret_cast(X)[0]; } + void setSize(size_type N) { reinterpret_cast(X)[0] = N; } + + size_type getCapacity() const { + return reinterpret_cast(X)[1]; + } + + BitWord *getBitsPtr() { + return reinterpret_cast(reinterpret_cast(X) + 2); + } + const BitWord *getBitsPtr() const { + return const_cast(this)->getBitsPtr(); + } + + void growImpl(size_type NewCapacity) { + X = reinterpret_cast( + safe_realloc(reinterpret_cast(X), getAllocSize(NewCapacity))); + setCapacity(NewCapacity); + } + + void setCapacity(size_type C) { reinterpret_cast(X)[1] = C; } + + void allocate(size_type Size) { + size_type Capacity = NumBitWords(Size); + X = reinterpret_cast(safe_malloc(getAllocSize(Capacity))); + setCapacity(Capacity); + } + void init(size_type Size, bool t) { + allocate(Size); + setSize(Size); + init_words(getBits(), t); + } + void init(const LargeImpl &RHS) { + size_type Size = RHS.size(); + allocate(Size); + setSize(Size); + std::memcpy(getBitsPtr(), RHS.getBitsPtr(), + getCapacity() * sizeof(BitWord)); + } + void assign(const LargeImpl &RHS) { + size_type Size = RHS.size(); + unsigned RHSWords = NumBitWords(Size); + if (RHSWords <= getCapacity()) { + if (RHSWords) + std::memcpy(getBitsPtr(), RHS.getBitsPtr(), + RHSWords * sizeof(BitWord)); + setSize(Size); + setCapacity(RHSWords); + } else { + release(); + init(RHS); + } + } + void release() { std::free(reinterpret_cast(X)); } + + LargeImpl() = default; + LargeImpl(const LargeImpl &) = delete; + LargeImpl(LargeImpl &&) = delete; + LargeImpl &operator=(const LargeImpl &) = delete; + LargeImpl &operator=(LargeImpl &&) = delete; + }; + // We assume throughout the implementation of SmallBitVector small-mode data + // will always fit in a single BitWord. + static_assert(unsigned(SmallNumDataBits) <= unsigned(LargeImpl::BITWORD_SIZE), + "Unexpected SmallNumDataBits"); + + LargeImpl Data; + public: - using size_type = unsigned; + using size_type = LargeImpl::size_type; // Encapsulation of a single bit. class reference { @@ -91,44 +173,34 @@ }; private: - BitVector *getPointer() const { - assert(!isSmall()); - return reinterpret_cast(X); - } - void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { - X = 1; + Data.X = 1; setSmallSize(NewSize); setSmallBits(NewSmallBits); } - void switchToLarge(BitVector *BV) { - X = reinterpret_cast(BV); - assert(!isSmall() && "Tried to use an unaligned pointer"); - } - // Return all the bits used for the "small" representation; this includes // bits for the size as well as the element bits. uintptr_t getSmallRawBits() const { assert(isSmall()); - return X >> 1; + return Data.X >> 1; } void setSmallRawBits(uintptr_t NewRawBits) { assert(isSmall()); - X = (NewRawBits << 1) | uintptr_t(1); + Data.X = (NewRawBits << 1) | uintptr_t(1); } // Return the size. size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; } - void setSmallSize(size_t Size) { - setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); + void setSmallSize(size_type Size) { + setSmallRawBits(getSmallBits() | (uintptr_t(Size) << SmallNumDataBits)); } // Return the element bits. uintptr_t getSmallBits() const { - return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); + return getSmallRawBits() & ~(~uintptr_t(0) << SmallNumDataBits); } void setSmallBits(uintptr_t NewBits) { @@ -138,7 +210,7 @@ public: /// Creates an empty bitvector. - SmallBitVector() = default; + SmallBitVector() { Data.X = 1; } /// Creates a bitvector of specified number of bits. All bits are initialized /// to the specified value. @@ -146,24 +218,25 @@ if (s <= SmallNumDataBits) switchToSmall(t ? ~uintptr_t(0) : 0, s); else - switchToLarge(new BitVector(s, t)); + Data.init(s, t); } /// SmallBitVector copy ctor. SmallBitVector(const SmallBitVector &RHS) { if (RHS.isSmall()) - X = RHS.X; + Data.X = RHS.Data.X; else - switchToLarge(new BitVector(*RHS.getPointer())); + Data.init(RHS.Data); } - SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { - RHS.X = 1; + SmallBitVector(SmallBitVector &&RHS) { + Data.X = RHS.Data.X; + RHS.Data.X = 1; } ~SmallBitVector() { if (!isSmall()) - delete getPointer(); + Data.release(); } using const_set_bits_iterator = const_set_bits_iterator_impl; @@ -181,17 +254,13 @@ return make_range(set_bits_begin(), set_bits_end()); } - bool isSmall() const { return X & uintptr_t(1); } + bool isSmall() const { return Data.X & uintptr_t(1); } /// Tests whether there are no bits in this bitvector. - bool empty() const { - return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); - } + bool empty() const { return isSmall() ? getSmallSize() == 0 : Data.empty(); } /// Returns the number of bits in this bitvector. - size_t size() const { - return isSmall() ? getSmallSize() : getPointer()->size(); - } + size_t size() const { return isSmall() ? getSmallSize() : Data.size(); } /// Returns the number of bits which are set. size_type count() const { @@ -199,28 +268,28 @@ uintptr_t Bits = getSmallBits(); return countPopulation(Bits); } - return getPointer()->count(); + return Data.count(); } /// Returns true if any bit is set. bool any() const { if (isSmall()) return getSmallBits() != 0; - return getPointer()->any(); + return Data.any(); } /// Returns true if all bits are set. bool all() const { if (isSmall()) return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; - return getPointer()->all(); + return Data.all(); } /// Returns true if none of the bits are set. bool none() const { if (isSmall()) return getSmallBits() == 0; - return getPointer()->none(); + return Data.none(); } /// Returns the index of the first set bit, -1 if none of the bits are set. @@ -231,7 +300,7 @@ return -1; return countTrailingZeros(Bits); } - return getPointer()->find_first(); + return Data.find_first(); } int find_last() const { @@ -241,7 +310,7 @@ return -1; return NumBaseBits - countLeadingZeros(Bits) - 1; } - return getPointer()->find_last(); + return Data.find_last(); } /// Returns the index of the first unset bit, -1 if all of the bits are set. @@ -253,7 +322,7 @@ uintptr_t Bits = getSmallBits(); return countTrailingOnes(Bits); } - return getPointer()->find_first_unset(); + return Data.find_first_unset(); } int find_last_unset() const { @@ -266,7 +335,7 @@ Bits |= ~uintptr_t(0) << getSmallSize(); return NumBaseBits - countLeadingOnes(Bits) - 1; } - return getPointer()->find_last_unset(); + return Data.find_last_unset(); } /// Returns the index of the next set bit following the "Prev" bit. @@ -280,7 +349,7 @@ return -1; return countTrailingZeros(Bits); } - return getPointer()->find_next(Prev); + return Data.find_next(Prev); } /// Returns the index of the next unset bit following the "Prev" bit. @@ -297,7 +366,7 @@ return -1; return countTrailingOnes(Bits); } - return getPointer()->find_next_unset(Prev); + return Data.find_next_unset(Prev); } /// find_prev - Returns the index of the first set bit that precedes the @@ -315,47 +384,45 @@ return NumBaseBits - countLeadingZeros(Bits) - 1; } - return getPointer()->find_prev(PriorTo); + return Data.find_prev(PriorTo); } /// Clear all bits. void clear() { if (!isSmall()) - delete getPointer(); - switchToSmall(0, 0); + Data.release(); + Data.X = 1; } /// Grow or shrink the bitvector. - void resize(unsigned N, bool t = false) { + void resize(size_type N, bool t = false) { if (!isSmall()) { - getPointer()->resize(N, t); - } else if (SmallNumDataBits >= N) { + Data.resize(N, t); + } else if (N <= SmallNumDataBits) { uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; setSmallSize(N); setSmallBits(NewBits | getSmallBits()); } else { - BitVector *BV = new BitVector(N, t); uintptr_t OldBits = getSmallBits(); - for (size_t i = 0, e = getSmallSize(); i != e; ++i) - (*BV)[i] = (OldBits >> i) & 1; - switchToLarge(BV); + size_type OldSize = getSmallSize(); + Data.allocate(N); + Data.setSize(OldSize); + Data.getBitsPtr()[0] = OldBits; + Data.resize(N, t); } } - void reserve(unsigned N) { + void reserve(size_type N) { if (isSmall()) { if (N > SmallNumDataBits) { - uintptr_t OldBits = getSmallRawBits(); - size_t SmallSize = getSmallSize(); - BitVector *BV = new BitVector(SmallSize); - for (size_t i = 0; i < SmallSize; ++i) - if ((OldBits >> i) & 1) - BV->set(i); - BV->reserve(N); - switchToLarge(BV); + size_type Size = getSmallSize(); + uintptr_t OldBits = getSmallBits(); + Data.allocate(N); + Data.setSize(Size); + Data.getBitsPtr()[0] = OldBits; } } else { - getPointer()->reserve(N); + Data.reserve(N); } } @@ -364,19 +431,16 @@ if (isSmall()) setSmallBits(~uintptr_t(0)); else - getPointer()->set(); + Data.set(); return *this; } SmallBitVector &set(unsigned Idx) { if (isSmall()) { - assert(Idx <= static_cast( - std::numeric_limits::digits) && - "undefined behavior"); + assert(Idx < getSmallSize()); setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); - } - else - getPointer()->set(Idx); + } else + Data.set(Idx); return *this; } @@ -391,7 +455,7 @@ uintptr_t Mask = EMask - IMask; setSmallBits(getSmallBits() | Mask); } else - getPointer()->set(I, E); + Data.set(I, E); return *this; } @@ -399,15 +463,16 @@ if (isSmall()) setSmallBits(0); else - getPointer()->reset(); + Data.reset(); return *this; } SmallBitVector &reset(unsigned Idx) { - if (isSmall()) + if (isSmall()) { + assert(Idx < getSmallSize()); setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); - else - getPointer()->reset(Idx); + } else + Data.reset(Idx); return *this; } @@ -422,7 +487,7 @@ uintptr_t Mask = EMask - IMask; setSmallBits(getSmallBits() & ~Mask); } else - getPointer()->reset(I, E); + Data.reset(I, E); return *this; } @@ -430,15 +495,16 @@ if (isSmall()) setSmallBits(~getSmallBits()); else - getPointer()->flip(); + Data.flip(); return *this; } SmallBitVector &flip(unsigned Idx) { - if (isSmall()) + if (isSmall()) { + assert(Idx < getSmallSize()); setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); - else - getPointer()->flip(Idx); + } else + Data.flip(Idx); return *this; } @@ -457,7 +523,7 @@ assert(Idx < size() && "Out-of-bounds Bit access."); if (isSmall()) return ((getSmallBits() >> Idx) & 1) != 0; - return getPointer()->operator[](Idx); + return Data[Idx]; } bool test(unsigned Idx) const { @@ -465,38 +531,26 @@ } // Push single bit to end of vector. - void push_back(bool Val) { - resize(size() + 1, Val); - } + void push_back(bool Val) { resize(size() + 1, Val); } /// Test if any common bits are set. bool anyCommon(const SmallBitVector &RHS) const { if (isSmall() && RHS.isSmall()) return (getSmallBits() & RHS.getSmallBits()) != 0; if (!isSmall() && !RHS.isSmall()) - return getPointer()->anyCommon(*RHS.getPointer()); - - for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) - if (test(i) && RHS.test(i)) - return true; - return false; + return Data.anyCommon(RHS.Data); + return (getFirstWord() & RHS.getFirstWord()) != 0; } // Comparison operators. bool operator==(const SmallBitVector &RHS) const { - if (size() != RHS.size()) - return false; if (isSmall() && RHS.isSmall()) - return getSmallBits() == RHS.getSmallBits(); + return Data.X == RHS.Data.X; else if (!isSmall() && !RHS.isSmall()) - return *getPointer() == *RHS.getPointer(); - else { - for (size_t i = 0, e = size(); i != e; ++i) { - if ((*this)[i] != RHS[i]) - return false; - } - return true; - } + return Data == RHS.Data; + else if (size() == RHS.size()) + return getFirstWord() == RHS.getFirstWord(); + return false; } bool operator!=(const SmallBitVector &RHS) const { @@ -510,13 +564,10 @@ if (isSmall() && RHS.isSmall()) setSmallBits(getSmallBits() & RHS.getSmallBits()); else if (!isSmall() && !RHS.isSmall()) - getPointer()->operator&=(*RHS.getPointer()); + Data &= RHS.Data; else { - size_t i, e; - for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) - (*this)[i] = test(i) && RHS.test(i); - for (e = size(); i != e; ++i) - reset(i); + setFirstWord(getFirstWord() & RHS.getFirstWord()); + clearUpperWords(); } return *this; } @@ -526,12 +577,9 @@ if (isSmall() && RHS.isSmall()) setSmallBits(getSmallBits() & ~RHS.getSmallBits()); else if (!isSmall() && !RHS.isSmall()) - getPointer()->reset(*RHS.getPointer()); + Data.reset(RHS.Data); else - for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) - if (RHS.test(i)) - reset(i); - + setFirstWord(getFirstWord() & ~RHS.getFirstWord()); return *this; } @@ -540,17 +588,13 @@ if (isSmall() && RHS.isSmall()) return (getSmallBits() & ~RHS.getSmallBits()) != 0; if (!isSmall() && !RHS.isSmall()) - return getPointer()->test(*RHS.getPointer()); - - unsigned i, e; - for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) - if (test(i) && !RHS.test(i)) - return true; - - for (e = size(); i != e; ++i) - if (test(i)) + return Data.test(RHS.Data); + if ((getFirstWord() & ~RHS.getFirstWord()) != 0) + return true; + for (LargeImpl::BitWord Word : getUpperWords()) { + if (Word) return true; - + } return false; } @@ -559,11 +603,9 @@ if (isSmall() && RHS.isSmall()) setSmallBits(getSmallBits() | RHS.getSmallBits()); else if (!isSmall() && !RHS.isSmall()) - getPointer()->operator|=(*RHS.getPointer()); - else { - for (size_t i = 0, e = RHS.size(); i != e; ++i) - (*this)[i] = test(i) || RHS.test(i); - } + Data |= RHS.Data; + else + setFirstWord(getFirstWord() | RHS.getFirstWord()); return *this; } @@ -572,11 +614,9 @@ if (isSmall() && RHS.isSmall()) setSmallBits(getSmallBits() ^ RHS.getSmallBits()); else if (!isSmall() && !RHS.isSmall()) - getPointer()->operator^=(*RHS.getPointer()); - else { - for (size_t i = 0, e = RHS.size(); i != e; ++i) - (*this)[i] = test(i) != RHS.test(i); - } + Data ^= RHS.Data; + else + setFirstWord(getFirstWord() ^ RHS.getFirstWord()); return *this; } @@ -584,7 +624,7 @@ if (isSmall()) setSmallBits(getSmallBits() << N); else - getPointer()->operator<<=(N); + Data <<= N; return *this; } @@ -592,24 +632,25 @@ if (isSmall()) setSmallBits(getSmallBits() >> N); else - getPointer()->operator>>=(N); + Data >>= N; return *this; } // Assignment operator. const SmallBitVector &operator=(const SmallBitVector &RHS) { - if (isSmall()) { + if (this == &RHS) { + // Do nothing + } else if (isSmall()) { if (RHS.isSmall()) - X = RHS.X; + Data.X = RHS.Data.X; else - switchToLarge(new BitVector(*RHS.getPointer())); + Data.init(RHS.Data); } else { - if (!RHS.isSmall()) - *getPointer() = *RHS.getPointer(); - else { - delete getPointer(); - X = RHS.X; - } + if (RHS.isSmall()) { + Data.release(); + Data.X = RHS.Data.X; + } else + Data.assign(RHS.Data); } return *this; } @@ -623,7 +664,7 @@ } void swap(SmallBitVector &RHS) { - std::swap(X, RHS.X); + std::swap(Data.X, RHS.Data.X); } /// Add '1' bits from Mask to this vector. Don't resize. @@ -632,7 +673,7 @@ if (isSmall()) applyMask(Mask, MaskWords); else - getPointer()->setBitsInMask(Mask, MaskWords); + Data.setBitsInMask(Mask, MaskWords); } /// Clear any bits in this vector that are set in Mask. Don't resize. @@ -641,7 +682,7 @@ if (isSmall()) applyMask(Mask, MaskWords); else - getPointer()->clearBitsInMask(Mask, MaskWords); + Data.clearBitsInMask(Mask, MaskWords); } /// Add a bit to this vector for every '0' bit in Mask. Don't resize. @@ -650,7 +691,7 @@ if (isSmall()) applyMask(Mask, MaskWords); else - getPointer()->setBitsNotInMask(Mask, MaskWords); + Data.setBitsNotInMask(Mask, MaskWords); } /// Clear a bit in this vector for every '0' bit in Mask. Don't resize. @@ -659,20 +700,69 @@ if (isSmall()) applyMask(Mask, MaskWords); else - getPointer()->clearBitsNotInMask(Mask, MaskWords); + Data.clearBitsNotInMask(Mask, MaskWords); + } + + // These are invalid forms, because the maximum size value able to be + // represented in the small size is always more than number of data bits + // available. These forms are valid for =, == and != but nothing else. + static SmallBitVector getDenseMapEmptyKey() { + SmallBitVector K; + K.setSmallSize((1 << SmallNumSizeBits) - 1); + return K; + } + static SmallBitVector getDenseMapTombstoneKey() { + SmallBitVector K; + K.setSmallSize((1 << SmallNumSizeBits) - 2); + return K; + } + unsigned getDenseMapHashValue() const { + using HashType = std::pair>; + HashType H; + H.first = size(); + LargeImpl::BitWord Word; + if (isSmall()) { + Word = getSmallBits(); + H.second = ArrayRef(Word); + } else { + H.second = Data.getActiveBits(); + } + return DenseMapInfo::getHashValue(H); } - void invalid() { - assert(empty()); - X = (uintptr_t)-1; +private: + LargeImpl::BitWord getFirstWord() const { + if (isSmall()) + return getSmallBits(); + if (Data.empty()) + return 0; + return Data.getBitsPtr()[0]; } - bool isInvalid() const { return X == (uintptr_t)-1; } - - ArrayRef getData() const { - return isSmall() ? makeArrayRef(X) : getPointer()->getData(); + void setFirstWord(uintptr_t NewBits) { + if (isSmall()) { + setSmallBits(NewBits); + } else { + MutableArrayRef Bits = Data.getActiveBits(); + if (!Bits.empty()) + Bits[0] = NewBits; + } + } + void clearUpperWords() { + if (isSmall()) + return; + MutableArrayRef Bits = Data.getActiveBits(); + if (!Bits.empty()) + LargeImpl::init_words(Bits.drop_front(), false); + } + ArrayRef getUpperWords() const { + if (isSmall()) + return {}; + ArrayRef Bits = Data.getActiveBits(); + if (Bits.empty()) + return Bits; + return Bits.drop_front(); } -private: template void applyMask(const uint32_t *Mask, unsigned MaskWords) { assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!"); @@ -710,19 +800,16 @@ } template <> struct DenseMapInfo { - static inline SmallBitVector getEmptyKey() { return SmallBitVector(); } + static inline SmallBitVector getEmptyKey() { + return SmallBitVector::getDenseMapEmptyKey(); + } static inline SmallBitVector getTombstoneKey() { - SmallBitVector V; - V.invalid(); - return V; + return SmallBitVector::getDenseMapTombstoneKey(); } static unsigned getHashValue(const SmallBitVector &V) { - return DenseMapInfo>>::getHashValue( - std::make_pair(V.size(), V.getData())); + return V.getDenseMapHashValue(); } static bool isEqual(const SmallBitVector &LHS, const SmallBitVector &RHS) { - if (LHS.isInvalid() || RHS.isInvalid()) - return LHS.isInvalid() == RHS.isInvalid(); return LHS == RHS; } }; Index: llvm/lib/CodeGen/RegisterScavenging.cpp =================================================================== --- llvm/lib/CodeGen/RegisterScavenging.cpp +++ llvm/lib/CodeGen/RegisterScavenging.cpp @@ -119,7 +119,7 @@ DefRegUnits.reset(); for (const MachineOperand &MO : MI.operands()) { if (MO.isRegMask()) { - TmpRegUnits.clear(); + TmpRegUnits.reset(); for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; ++RU) { for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) { if (MO.clobbersPhysReg(*RURI)) { Index: llvm/unittests/ADT/BitVectorTest.cpp =================================================================== --- llvm/unittests/ADT/BitVectorTest.cpp +++ llvm/unittests/ADT/BitVectorTest.cpp @@ -179,6 +179,108 @@ EXPECT_TRUE(Vec.empty()); } +TYPED_TEST(BitVectorTest, Equality) { + TypeParam A; + TypeParam B; + EXPECT_TRUE(A == B); + A.resize(10); + EXPECT_FALSE(A == B); + B.resize(10); + EXPECT_TRUE(A == B); + A.set(5); + EXPECT_FALSE(A == B); + B.set(5); + EXPECT_TRUE(A == B); + A.resize(20); + EXPECT_FALSE(A == B); + B.resize(20); + EXPECT_TRUE(A == B); +} + +TYPED_TEST(BitVectorTest, Resize) { + // Increase size and capacity + { + TypeParam A; + A.resize(100); + A.set(12); + A.set(13); + A.set(75); + A.resize(400); + EXPECT_EQ(400U, A.size()); + EXPECT_EQ(3U, A.count()); + EXPECT_TRUE(A.test(12)); + EXPECT_TRUE(A.test(13)); + EXPECT_TRUE(A.test(75)); + } + { + TypeParam A; + A.resize(100); + A.set(12); + A.set(13); + A.set(75); + A.resize(400, true); + EXPECT_EQ(400U, A.size()); + EXPECT_EQ(303U, A.count()); + EXPECT_TRUE(A.test(12)); + EXPECT_TRUE(A.test(13)); + EXPECT_TRUE(A.test(75)); + } + // Increase size and but not capacity + { + TypeParam A; + A.reserve(600); + A.resize(100); + A.set(12); + A.set(13); + A.set(75); + A.resize(400); + EXPECT_EQ(400U, A.size()); + EXPECT_EQ(3U, A.count()); + EXPECT_TRUE(A.test(12)); + EXPECT_TRUE(A.test(13)); + EXPECT_TRUE(A.test(75)); + } + { + TypeParam A; + A.reserve(600); + A.resize(100); + A.set(12); + A.set(13); + A.set(75); + A.resize(400, true); + EXPECT_EQ(400U, A.size()); + EXPECT_EQ(303U, A.count()); + EXPECT_TRUE(A.test(12)); + EXPECT_TRUE(A.test(13)); + EXPECT_TRUE(A.test(75)); + } + // Reduce size + { + TypeParam A; + A.resize(100); + A.set(12); + A.set(13); + A.set(75); + A.resize(50); + EXPECT_EQ(50U, A.size()); + EXPECT_EQ(2U, A.count()); + EXPECT_TRUE(A.test(12)); + EXPECT_TRUE(A.test(13)); + } + { + TypeParam A; + A.resize(100); + A.set(12); + A.set(13); + A.set(75); + A.resize(50, true); + EXPECT_EQ(50U, A.size()); + EXPECT_EQ(2U, A.count()); + EXPECT_TRUE(A.test(12)); + EXPECT_TRUE(A.test(13)); + } +} + TYPED_TEST(BitVectorTest, SimpleFindOpsMultiWord) { TypeParam A; @@ -1166,24 +1268,56 @@ I = Set.insert(C); EXPECT_EQ(true, I.second); -#if LLVM_ENABLE_ABI_BREAKING_CHECKS TypeParam D; - EXPECT_DEATH(Set.insert(D), - "Empty/Tombstone value shouldn't be inserted into map!"); -#endif + I = Set.insert(D); + EXPECT_EQ(true, I.second); - EXPECT_EQ(3U, Set.size()); + EXPECT_EQ(4U, Set.size()); EXPECT_EQ(1U, Set.count(A)); EXPECT_EQ(1U, Set.count(B)); EXPECT_EQ(1U, Set.count(C)); + EXPECT_EQ(1U, Set.count(D)); EXPECT_EQ(true, Set.erase(B)); - EXPECT_EQ(2U, Set.size()); + EXPECT_EQ(3U, Set.size()); EXPECT_EQ(true, Set.erase(C)); - EXPECT_EQ(1U, Set.size()); + EXPECT_EQ(2U, Set.size()); EXPECT_EQ(true, Set.erase(A)); + EXPECT_EQ(1U, Set.size()); + + EXPECT_EQ(true, Set.erase(D)); EXPECT_EQ(0U, Set.size()); } + +/// Test that capacity and small/large mode don't affect hashing. +TYPED_TEST(BitVectorTest, DenseMapHashing) { + using DMI = DenseMapInfo; + { + TypeParam A; + A.resize(200); + A.set(100); + + TypeParam B; + B.resize(200); + B.set(100); + B.reserve(1000); + + EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B)); + } + { + TypeParam A; + A.resize(20); + A.set(10); + + TypeParam B; + B.resize(20); + B.set(10); + B.reserve(1000); + + EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B)); + } +} + } // namespace