Make BitVector::operator== return false for different-sized vectors

[bmoody]

Summary

This behaviour is in line with SmallBitVector and other vector-like types.

[bmoody]

Run git-clang-format

[Meinersbur]

It's helpful to have one patch per issue (instead of three in a single patch). One of the reasons is that in the commit history, it's unambiguous what diff caused which change.

[bmoody]

Change this review to be only for the operator== fix

[nikic]

I'm wondering whether it would make more sense to make this an assertion instead. Comparing bit vectors of different size doesn't seem like a well-defined operation. (We do assert if you compare APInts of different sizes, for example).

Disclaimer: I don't have any particularly familiarity with this piece of code.

[Meinersbur]

Since BitVector is supposed to resemble a std::vector<bool>, this is the behavior I'd expect.

APInts can be interpreted as either signed or unsigned, making comparison of different lengths undefined.

LGTM, but please wait a bit for other opinions before committing.

[dblaikie]

Agree in theory - but given the behavior has been different for quite a while, I think it might be worth a bit of an inventory of uses of BitVector and of BitVector's op== existing behavior - and maybe a rough explanation for why it's not problematic to change it in this way.

[bmoody]

I've reviewed all the uses of BitVector::operator==/!= in llvm and clang by renaming the functions and checking all the code that failed to compile. As far as I can tell, all uses should be either unaffected by the change, or will be more correct with the change applied.

---

llvm/include/llvm/Analysis/TargetLibraryInfo.h:

bool areInlineCompatible(const TargetLibraryInfo &CalleeTLI,
                         bool AllowCallerSuperset) const {
  if (!AllowCallerSuperset)
    return OverrideAsUnavailable == CalleeTLI.OverrideAsUnavailable;
  BitVector B = OverrideAsUnavailable;
  B |= CalleeTLI.OverrideAsUnavailable;
  // We can inline if the union of the caller and callee's nobuiltin
  // attributes is no stricter than the caller's nobuiltin attributes.
  return B == OverrideAsUnavailable;
}

Not affected by the proposed change - all vectors have constant size NumLibFuncs.

---

llvm/lib/CodeGen/RegisterClassInfo.cpp:

const BitVector &RR = MF->getRegInfo().getReservedRegs();
if (Reserved.size() != RR.size() || RR != Reserved) {
  Update = true;
  Reserved = RR;
}

Not affected by the proposed change - code has an explicit size check.

---

llvm/lib/Transforms/Coroutines/CoroFrame.cpp:

Changed |= (S.Kills != SavedKills) || (S.Consumes != SavedConsumes);

if (S.Kills != SavedKills) {
  LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI->getName()
                    << "\n");
  LLVM_DEBUG(dump("S.Kills", S.Kills));
  LLVM_DEBUG(dump("SavedKills", SavedKills));
}
if (S.Consumes != SavedConsumes) {
  LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI << "\n");
  LLVM_DEBUG(dump("S.Consume", S.Consumes));
  LLVM_DEBUG(dump("SavedCons", SavedConsumes));
}

Not affected by the proposed change - all the vectors in this code have the same size. They're initialised above, in the same function:

// Initialize every block so that it consumes itself
for (size_t I = 0; I < N; ++I) {
  auto &B = Block[I];
  B.Consumes.resize(N);
  B.Kills.resize(N);
  B.Consumes.set(I);
}

---

llvm/tools/llvm-exegesis/lib/MCInstrDescView.cpp:

const BitVector *BitVectorCache::getUnique(BitVector &&BV) const {
  for (const auto &Entry : Cache)
    if (*Entry == BV)
      return Entry.get();
  Cache.push_back(std::make_unique<BitVector>());
  auto &Entry = Cache.back();
  Entry->swap(BV);
  return Entry.get();
}

Looks like the proposed change will fix a (probably latent) bug in this code. Currently it seems like this function could return a pointer to a BitVector with a different size than the one that was passed in, which would be surprising.

---

llvm/include/llvm/ADT/PackedVector.h:

bool operator==(const PackedVector &RHS) const {
  return Bits == RHS.Bits;
}

bool operator!=(const PackedVector &RHS) const {
  return Bits != RHS.Bits;
}

I think this is another latent bug. PackedVector::operator== doesn't appear to be used anywhere.

[dblaikie]

Thanks for this!

In D77027#1966204, @bmoody wrote:

I've reviewed all the uses of BitVector::operator==/!= in llvm and clang by renaming the functions and checking all the code that failed to compile. As far as I can tell, all uses should be either unaffected by the change, or will be more correct with the change applied.

---

llvm/include/llvm/Analysis/TargetLibraryInfo.h:

bool areInlineCompatible(const TargetLibraryInfo &CalleeTLI,
                         bool AllowCallerSuperset) const {
  if (!AllowCallerSuperset)
    return OverrideAsUnavailable == CalleeTLI.OverrideAsUnavailable;
  BitVector B = OverrideAsUnavailable;
  B |= CalleeTLI.OverrideAsUnavailable;
  // We can inline if the union of the caller and callee's nobuiltin
  // attributes is no stricter than the caller's nobuiltin attributes.
  return B == OverrideAsUnavailable;
}

Not affected by the proposed change - all vectors have constant size NumLibFuncs.

---

llvm/lib/CodeGen/RegisterClassInfo.cpp:

const BitVector &RR = MF->getRegInfo().getReservedRegs();
if (Reserved.size() != RR.size() || RR != Reserved) {
  Update = true;
  Reserved = RR;
}

Not affected by the proposed change - code has an explicit size check.

Could you migrate this code to use just the operator in this change since the size check will now be redundant?

---

llvm/lib/Transforms/Coroutines/CoroFrame.cpp:

Changed |= (S.Kills != SavedKills) || (S.Consumes != SavedConsumes);

if (S.Kills != SavedKills) {
  LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI->getName()
                    << "\n");
  LLVM_DEBUG(dump("S.Kills", S.Kills));
  LLVM_DEBUG(dump("SavedKills", SavedKills));
}
if (S.Consumes != SavedConsumes) {
  LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI << "\n");
  LLVM_DEBUG(dump("S.Consume", S.Consumes));
  LLVM_DEBUG(dump("SavedCons", SavedConsumes));
}

Not affected by the proposed change - all the vectors in this code have the same size. They're initialised above, in the same function:

// Initialize every block so that it consumes itself
for (size_t I = 0; I < N; ++I) {
  auto &B = Block[I];
  B.Consumes.resize(N);
  B.Kills.resize(N);
  B.Consumes.set(I);
}

---

llvm/tools/llvm-exegesis/lib/MCInstrDescView.cpp:

const BitVector *BitVectorCache::getUnique(BitVector &&BV) const {
  for (const auto &Entry : Cache)
    if (*Entry == BV)
      return Entry.get();
  Cache.push_back(std::make_unique<BitVector>());
  auto &Entry = Cache.back();
  Entry->swap(BV);
  return Entry.get();
}

Looks like the proposed change will fix a (probably latent) bug in this code. Currently it seems like this function could return a pointer to a BitVector with a different size than the one that was passed in, which would be surprising.

I think this code is probably fine - all the BitVectors start by being initialized from "emptyRegisters" (pre-initialized with the necessary size) in exegesis::Instruction::create, I think.

---

llvm/include/llvm/ADT/PackedVector.h:

bool operator==(const PackedVector &RHS) const {
  return Bits == RHS.Bits;
}

bool operator!=(const PackedVector &RHS) const {
  return Bits != RHS.Bits;
}

I think this is another latent bug. PackedVector::operator== doesn't appear to be used anywhere.

Is it tested? Might be worth leaving a FIXME of "hey, this is untested code".

llvm/include/llvm/ADT/BitVector.h

542

Hmm - looking at this more closely (ie: I'm now actually looking at the code rather than just the commentary/discussion) this code makes me a bit uncomfortable - looks pretty intentionally designed to support potentially equal comparison of differently lengthed BitVectors. Is there any history of how/when this was added/potentially used?

[Meinersbur]

llvm/include/llvm/ADT/BitVector.h

542

It was introduced in 2007 by Chris Lattner in r42860 with the commit message "make bitvector &= do the right thing if vectors have mismatched length." and no other changes. Before that, it asserted on mismatching lengths.

By its name, it's a vector and a comparison that does something else than checking the same elements in the same order is confusing.

[Meinersbur]

llvm/include/llvm/ADT/BitVector.h

542

Sorry, looked at the wrong operator.

The commit was r42889 also by Chris Lattner in 2007. It's commit message is:

make operator== work with non-equal sized bitvectors, as long as the extra bits are all zeros. This allows "010" and "010000" to be treated as equal.

without any other changes or justifications. Before that, it returned false on different sizes.

Note that "010" and "010000" can be very different depending on its interpretation, e.g. the former represents the decimal number 2, the latter is 16.

[bmoody]

Regarding PackedVector::operator==, this code is covered by the PackedVector unit test but not thoroughly enough to catch the bug.

And I'd be happy to remove the redundant size check in RegisterClassInfo.cpp - would that go in as part of this change or in a follow-up change?

[Meinersbur]

Also note, that the implementation of BitVector's hash value is:

static unsigned getHashValue(const BitVector &V) {
  return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue(
      std::make_pair(V.size(), V.getData()));
}

that is the current implementation may have different hashes for 'equal' BitVectors.

[dblaikie]

In D77027#1969672, @Meinersbur wrote:

Also note, that the implementation of BitVector's hash value is:

static unsigned getHashValue(const BitVector &V) {
  return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue(
      std::make_pair(V.size(), V.getData()));
}

that is the current implementation may have different hashes for 'equal' BitVectors.

Good point!

Yeah, combination of factors makes me feel like this is the best direction. (@lattner in case he has some deep memories of this place - but happy to let that be post-commit review given the current state of BitVector and its usage)

[lattner]

I agree with this patch, we should definitely return non-equal for different length vectors! Thanks!

[bmoody]

Great! I don't have commit access so please commit this on my behalf :)

llvm/include/llvm/ADT/BitVector.h

class BitVector {
   enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
 
   static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
                 "Unsupported word size");
 
   MutableArrayRef<BitWord> Bits; // Actual bits.
   unsigned Size;                 // Size of bitvector in bits.
 
+  ArrayRef<BitWord> getActiveBits() const {
+    return Bits.take_front(NumBitWords(Size));
+  }
+  MutableArrayRef<BitWord> getActiveBits() {
+    return Bits.take_front(NumBitWords(Size));
+  }
+
 public:
   typedef unsigned size_type;
   // Encapsulation of a single bit.
   class reference {
     friend class BitVector;
 
     BitWord *WordRef;
     unsigned BitPos;
bool anyCommon(const BitVector &RHS) const {
     for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
       if (Bits[i] & RHS.Bits[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;
+    return size() == RHS.size() &&
+        getActiveBits() == RHS.getActiveBits();
   }
 
   bool operator!=(const BitVector &RHS) const {
     return !(*this == RHS);
   }
 
   /// Intersection, union, disjoint union.
   BitVector &operator&=(const BitVector &RHS) {
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 getActiveBits(); }
 
   //===--------------------------------------------------------------------===//
   // 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();
+  unsigned getDenseMapHashValue() const {
+    using BitWord = uintptr_t;
+    ArrayRef<BitWord> Data;
+    BitWord SmallData;
+    if (isSmall()) {
+      SmallData = getSmallBits();
+      Data = SmallData;
+    } else {
+      Data = getPointer()->getData();
+    }
+    return DenseMapInfo<std::pair<size_type, ArrayRef<BitWord>>>::getHashValue(
+        std::make_pair(size(), Data));
   }
 
 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) {
-    return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::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;
   }
 };
 } // end namespace llvm

llvm/unittests/ADT/BitVectorTest.cpp

TYPED_TEST(BitVectorTest, TrivialOperation) {
   EXPECT_EQ(0U, Vec.count());
   EXPECT_EQ(0U, Vec.size());
   EXPECT_FALSE(Vec.any());
   EXPECT_TRUE(Vec.all());
   EXPECT_TRUE(Vec.none());
   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;
 
   // Test finding next set and unset bits in a BitVector with multiple words
   A.resize(100);
   A.set(12);
   A.set(13);
   A.set(75);
#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 and small/large mode don'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