Index: llvm/include/llvm/ADT/BitVector.h =================================================================== --- llvm/include/llvm/ADT/BitVector.h +++ llvm/include/llvm/ADT/BitVector.h @@ -82,6 +82,13 @@ MutableArrayRef Bits; // Actual bits. unsigned Size; // Size of bitvector in bits. + ArrayRef getActiveBits() const { + return Bits.take_front(NumBitWords(Size)); + } + MutableArrayRef getActiveBits() { + return Bits.take_front(NumBitWords(Size)); + } + public: typedef unsigned size_type; // Encapsulation of a single bit. @@ -532,24 +539,8 @@ // 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; + return size() == RHS.size() && + getActiveBits() == RHS.getActiveBits(); } bool operator!=(const BitVector &RHS) const { @@ -773,7 +764,7 @@ } bool isInvalid() const { return Size == (unsigned)-1; } - ArrayRef getData() const { return Bits; } + ArrayRef getData() const { return getActiveBits(); } //===--------------------------------------------------------------------===// // Portable bit mask operations. Index: llvm/include/llvm/ADT/SmallBitVector.h =================================================================== --- llvm/include/llvm/ADT/SmallBitVector.h +++ llvm/include/llvm/ADT/SmallBitVector.h @@ -668,8 +668,18 @@ } bool isInvalid() const { return X == (uintptr_t)-1; } - ArrayRef getData() const { - return isSmall() ? makeArrayRef(X) : getPointer()->getData(); + unsigned getDenseMapHashValue() const { + using BitWord = uintptr_t; + ArrayRef Data; + BitWord SmallData; + if (isSmall()) { + SmallData = getSmallBits(); + Data = SmallData; + } else { + Data = getPointer()->getData(); + } + return DenseMapInfo>>::getHashValue( + std::make_pair(size(), Data)); } private: @@ -717,8 +727,7 @@ return V; } 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()) 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; @@ -1186,4 +1288,34 @@ EXPECT_EQ(true, Set.erase(A)); 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