X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallBitVector.h;h=62620fa26782ff2aec25671912fbc7beab934bf2;hb=b02ed5b8eafd11500bbefb7206ecbf5bc3fc324a;hp=7563e81e1cef5e46c01234f08bca20f1f16b4d42;hpb=1e44aa0412473297994afb8b707d0326472fd2a4;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index 7563e81e1ce..62620fa2678 100644 --- a/include/llvm/ADT/SmallBitVector.h +++ b/include/llvm/ADT/SmallBitVector.h @@ -15,6 +15,7 @@ #define LLVM_ADT_SMALLBITVECTOR_H #include "llvm/ADT/BitVector.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" #include @@ -52,6 +53,34 @@ class SmallBitVector { SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits }; +public: + // Encapsulation of a single bit. + class reference { + SmallBitVector &TheVector; + unsigned BitPos; + + public: + reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} + + reference& operator=(reference t) { + *this = bool(t); + return *this; + } + + reference& operator=(bool t) { + if (t) + TheVector.set(BitPos); + else + TheVector.reset(BitPos); + return *this; + } + + operator bool() const { + return const_cast(TheVector).operator[](BitPos); + } + }; + +private: bool isSmall() const { return X & uintptr_t(1); } @@ -81,7 +110,7 @@ class SmallBitVector { void setSmallRawBits(uintptr_t NewRawBits) { assert(isSmall()); - X = NewRawBits << 1 | uintptr_t(1); + X = (NewRawBits << 1) | uintptr_t(1); } // Return the size. @@ -99,7 +128,7 @@ class SmallBitVector { } void setSmallBits(uintptr_t NewBits) { - setSmallRawBits(NewBits & ~(~uintptr_t(0) << getSmallSize()) | + setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | (getSmallSize() << SmallNumDataBits)); } @@ -124,6 +153,12 @@ public: switchToLarge(new BitVector(*RHS.getPointer())); } +#if LLVM_HAS_RVALUE_REFERENCES + SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { + RHS.X = 1; + } +#endif + ~SmallBitVector() { if (!isSmall()) delete getPointer(); @@ -147,7 +182,7 @@ public: return CountPopulation_32(Bits); if (sizeof(uintptr_t) * CHAR_BIT == 64) return CountPopulation_64(Bits); - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } return getPointer()->count(); } @@ -159,6 +194,13 @@ public: return getPointer()->any(); } + /// all - Returns true if all bits are set. + bool all() const { + if (isSmall()) + return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; + return getPointer()->all(); + } + /// none - Returns true if none of the bits are set. bool none() const { if (isSmall()) @@ -171,14 +213,13 @@ public: int find_first() const { if (isSmall()) { uintptr_t Bits = getSmallBits(); - if (sizeof(uintptr_t) * CHAR_BIT == 32) { - size_t FirstBit = CountTrailingZeros_32(Bits); - return FirstBit == 32 ? -1 : FirstBit; - } else if (sizeof(uintptr_t) * CHAR_BIT == 64) { - size_t FirstBit = CountTrailingZeros_64(Bits); - return FirstBit == 64 ? -1 : FirstBit; - } - assert(0 && "Unsupported!"); + if (Bits == 0) + return -1; + if (sizeof(uintptr_t) * CHAR_BIT == 32) + return CountTrailingZeros_32(Bits); + if (sizeof(uintptr_t) * CHAR_BIT == 64) + return CountTrailingZeros_64(Bits); + llvm_unreachable("Unsupported!"); } return getPointer()->find_first(); } @@ -190,14 +231,13 @@ public: uintptr_t Bits = getSmallBits(); // Mask off previous bits. Bits &= ~uintptr_t(0) << (Prev + 1); - if (sizeof(uintptr_t) * CHAR_BIT == 32) { - size_t FirstBit = CountTrailingZeros_32(Bits); - return FirstBit == 32 ? -1 : FirstBit; - } else if (sizeof(uintptr_t) * CHAR_BIT == 64) { - size_t FirstBit = CountTrailingZeros_64(Bits); - return FirstBit == 64 ? -1 : FirstBit; - } - assert(0 && "Unsupported!"); + if (Bits == 0 || Prev + 1 >= getSmallSize()) + return -1; + if (sizeof(uintptr_t) * CHAR_BIT == 32) + return CountTrailingZeros_32(Bits); + if (sizeof(uintptr_t) * CHAR_BIT == 64) + return CountTrailingZeros_64(Bits); + llvm_unreachable("Unsupported!"); } return getPointer()->find_next(Prev); } @@ -260,6 +300,21 @@ public: return *this; } + /// set - Efficiently set a range of bits in [I, E) + SmallBitVector &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 (isSmall()) { + uintptr_t EMask = ((uintptr_t)1) << E; + uintptr_t IMask = ((uintptr_t)1) << I; + uintptr_t Mask = EMask - IMask; + setSmallBits(getSmallBits() | Mask); + } else + getPointer()->set(I, E); + return *this; + } + SmallBitVector &reset() { if (isSmall()) setSmallBits(0); @@ -276,6 +331,21 @@ public: return *this; } + /// reset - Efficiently reset a range of bits in [I, E) + SmallBitVector &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 (isSmall()) { + uintptr_t EMask = ((uintptr_t)1) << E; + uintptr_t IMask = ((uintptr_t)1) << I; + uintptr_t Mask = EMask - IMask; + setSmallBits(getSmallBits() & ~Mask); + } else + getPointer()->reset(I, E); + return *this; + } + SmallBitVector &flip() { if (isSmall()) setSmallBits(~getSmallBits()); @@ -298,7 +368,11 @@ public: } // Indexing. - // TODO: Add an index operator which returns a "reference" (proxy class). + reference operator[](unsigned Idx) { + 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."); if (isSmall()) @@ -310,6 +384,19 @@ public: return (*this)[Idx]; } + /// 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; + } + // Comparison operators. bool operator==(const SmallBitVector &RHS) const { if (size() != RHS.size()) @@ -385,9 +472,72 @@ public: return *this; } +#if LLVM_HAS_RVALUE_REFERENCES + const SmallBitVector &operator=(SmallBitVector &&RHS) { + if (this != &RHS) { + clear(); + swap(RHS); + } + return *this; + } +#endif + void swap(SmallBitVector &RHS) { std::swap(X, RHS.X); } + + /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. + /// This computes "*this |= Mask". + void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { + if (isSmall()) + applyMask(Mask, MaskWords); + else + getPointer()->setBitsInMask(Mask, MaskWords); + } + + /// clearBitsInMask - Clear any bits in this vector that are set in Mask. + /// Don't resize. This computes "*this &= ~Mask". + void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { + if (isSmall()) + applyMask(Mask, MaskWords); + else + getPointer()->clearBitsInMask(Mask, MaskWords); + } + + /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. + /// Don't resize. This computes "*this |= ~Mask". + void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { + if (isSmall()) + applyMask(Mask, MaskWords); + else + getPointer()->setBitsNotInMask(Mask, MaskWords); + } + + /// 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) { + if (isSmall()) + applyMask(Mask, MaskWords); + else + getPointer()->clearBitsNotInMask(Mask, MaskWords); + } + +private: + template + void applyMask(const uint32_t *Mask, unsigned MaskWords) { + assert((NumBaseBits == 64 || NumBaseBits == 32) && "Unsupported word size"); + if (NumBaseBits == 64 && MaskWords >= 2) { + uint64_t M = Mask[0] | (uint64_t(Mask[1]) << 32); + if (InvertMask) M = ~M; + if (AddBits) setSmallBits(getSmallBits() | M); + else setSmallBits(getSmallBits() & ~M); + } else { + uint32_t M = Mask[0]; + if (InvertMask) M = ~M; + if (AddBits) setSmallBits(getSmallBits() | M); + else setSmallBits(getSmallBits() & ~M); + } + } }; inline SmallBitVector