Fix bug in BitVector and SmallBitVector DenseMap hashing

[bmoody]

Summary

BitVectors and SmallBitVectors with equal contents but different capacities were getting different hashes.

[bmoody]

Include fix for SmallBitVector hashing

[aganea]

Thanks for fixing this!

llvm/include/llvm/ADT/SmallBitVector.h

671–675

I didn't want to be too intrusive when I did it. Do you think we could do:

ArrayRef<uintptr_t> getData(uintptr_t &Store) const {
  if (!isSmall())
    return getPointer()->getData();
  Store = getSmallBits();
  return makeArrayRef(Store);
}

721

..and only do V.getData(Store) here with a definition above.

llvm/unittests/ADT/BitVectorTest.cpp

1209

Can you possibly add a non-TYPED_TEST to compare a BitVector and a SmallBitVector, to ensure hashes are the same for a given content?

[bmoody]

Make suggested changes to SmallBitVector, un-deleting SmallBitVector::getData.

[bmoody]

I'm unsure about adding a test that BitVector and SmallBitVector hash exactly the same way, because in principle I think this is a consequence of implementation details and not a property that we actually want per se. In future the implementations might diverge such that they must hash differently (or at least, that it would be convenient for them to hash differently), and IMO that would be ok. But I'm willing to add the test if you disagree.

[aganea]

In my sense a hash is a function of the represented data, not of the implementation. I feel that they should both resolve to the same hash, but at the same time I don't have practical example for this. Let's leave this open, until there's a practical application.

Thanks again! LTGM.

[jdoerfert]

In D77038#1990099, @bmoody wrote:

I'm unsure about adding a test that BitVector and SmallBitVector hash exactly the same way, because in principle I think this is a consequence of implementation details and not a property that we actually want per se. In future the implementations might diverge such that they must hash differently (or at least, that it would be convenient for them to hash differently), and IMO that would be ok. But I'm willing to add the test if you disagree.

[Drive by and meant as a generic comment] If the test states this concern it is still valuable to have it. Once the implementations diverge the test fails, the concern is rediscovered, and the author can decide if the divergence was intentional/good or accidental/bad. In the former case the test might be removed but it at least protects against the accident case.

[bmoody]

Great! I don't have commit access so please commit this on my behalf. Thanks!

[Meinersbur]

D77027 made BitVector::operator== return false for BitVectors of different size, one of the argument being that the hashes of different sizes are different, the other being that a vector, like std::vector return false for containing a different number of elements.

With that change, the hash can be different and since its a SmallBitVector I'd suggest to do the same.

[bmoody]

@Meinersbur I think you may have misunderstood this change - this change is to make hashing insensitive to capacity, not size. Both were already sensitive to size and still are after this change (and I agree that this is the correct behaviour). Please correct me if I've misunderstood your comment.

[Meinersbur]

You are right, I missed it's to make it capacity-independent.

I am going to commit for you...

llvm/include/llvm/ADT/BitVector.h

public:
   }
 
   void invalid() {
     assert(!Size && Bits.empty());
     Size = (unsigned)-1;
   }
   bool isInvalid() const { return Size == (unsigned)-1; }
 
-  ArrayRef<BitWord> getData() const { return Bits; }
+  ArrayRef<BitWord> getData() const {
+    return Bits.take_front(NumBitWords(size()));
+  }
 
   //===--------------------------------------------------------------------===//
   // Portable bit mask operations.
   //===--------------------------------------------------------------------===//
   //
   // These methods all operate on arrays of uint32_t, each holding 32 bits. The
   // fixed word size makes it easier to work with literal bit vector constants
   // in portable code.

llvm/include/llvm/ADT/SmallBitVector.h

public:
   }
 
   void invalid() {
     assert(empty());
     X = (uintptr_t)-1;
   }
   bool isInvalid() const { return X == (uintptr_t)-1; }
 
-  ArrayRef<uintptr_t> getData() const {
-    return isSmall() ? makeArrayRef(X) : getPointer()->getData();
+  ArrayRef<uintptr_t> getData(uintptr_t &Store) const {
+    if (!isSmall())
+      return getPointer()->getData();
+    Store = getSmallBits();
+    return makeArrayRef(Store);
   }
 
 private:
   template <bool AddBits, bool InvertMask>
   void applyMask(const uint32_t *Mask, unsigned MaskWords) {
     assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
     uintptr_t M = Mask[0];
     if (NumBaseBits == 64)

 template <> struct DenseMapInfo<SmallBitVector> {
   static inline SmallBitVector getEmptyKey() { return SmallBitVector(); }
   static inline SmallBitVector getTombstoneKey() {
     SmallBitVector V;
     V.invalid();
     return V;
   }
   static unsigned getHashValue(const SmallBitVector &V) {
+    uintptr_t Store;
     return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue(
-        std::make_pair(V.size(), V.getData()));
+        std::make_pair(V.size(), V.getData(Store)));
   }
   static bool isEqual(const SmallBitVector &LHS, const SmallBitVector &RHS) {
     if (LHS.isInvalid() || RHS.isInvalid())
       return LHS.isInvalid() == RHS.isInvalid();
     return LHS == RHS;
   }
 };
 } // end namespace llvm

llvm/unittests/ADT/BitVectorTest.cpp

#endif
   EXPECT_EQ(2U, Set.size());
 
   EXPECT_EQ(true, Set.erase(C));
   EXPECT_EQ(1U, Set.size());
 
   EXPECT_EQ(true, Set.erase(A));
   EXPECT_EQ(0U, Set.size());
 }
+
+/// Test that capacity doesn't affect hashing.
+TYPED_TEST(BitVectorTest, DenseMapHashing) {
+  using DMI = DenseMapInfo<TypeParam>;
+  {
+    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