Fix bugs in SmallBitVector

[bmoody]

Summary

Fixes:

• find_last/find_last_unset - off-by-one error
• Compound assignment ops and operator== when mixing big/small modes

[dexonsmith]

unittests/ADT/BitVectorTest.cpp

240

It's not locally obvious why this clear() is important. Is it cleaner to just split into a separate test? Is there also an ASSERT_* you can add to prove that it's in small mode?

[bmoody]

Reorganize tests for clarity.

Can't see any way to assert that the bit vector is in small mode.

[bmoody]

Probably should have tried to compile that last change before I uploaded it..

[dexonsmith]

In D54933#1309166, @bmoody wrote:

Can't see any way to assert that the bit vector is in small mode.

Since it's important for the test, it might be worth adding one.

[zturner]

Is this the same bug described here? https://bugs.llvm.org/show_bug.cgi?id=38996

Can you confirm that it fixes the test cases proposed in that patch?

[bmoody]

New diff that makes SmallBitVector::isSmall() public and adds asserts to the tests.

I don't really agree with this change because I don't think isSmall should be part of SmallBitVector's public interface and I think the test is explicit enough without the asserts. But it's here if you want it.

P.s. I don't have commit access, so you're welcome to make any final tweaks and commit on my behalf.

[bmoody]

Also, yes, can confirm this patch fixes the tests in that bug report.

[bmoody]

Any update on getting this committed? I don't have commit access.

include/llvm/ADT/SmallBitVector.h

int find_first() const {
     return getPointer()->find_first();
   }
 
   int find_last() const {
     if (isSmall()) {
       uintptr_t Bits = getSmallBits();
       if (Bits == 0)
         return -1;
-      return NumBaseBits - countLeadingZeros(Bits);
+      return NumBaseBits - countLeadingZeros(Bits) - 1;
     }
     return getPointer()->find_last();
   }
 
   /// Returns the index of the first unset bit, -1 if all of the bits are set.
   int find_first_unset() const {
     if (isSmall()) {
       if (count() == getSmallSize())
         return -1;
 
       uintptr_t Bits = getSmallBits();
       return countTrailingOnes(Bits);
     }
     return getPointer()->find_first_unset();
   }
 
   int find_last_unset() const {
     if (isSmall()) {
       if (count() == getSmallSize())
         return -1;
 
       uintptr_t Bits = getSmallBits();
-      return NumBaseBits - countLeadingOnes(Bits);
+      // Set unused bits.
+      Bits |= ~uintptr_t(0) << getSmallSize();
+      return NumBaseBits - countLeadingOnes(Bits) - 1;
     }
     return getPointer()->find_last_unset();
   }
 
   /// 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 {
     if (isSmall()) {
for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
         return true;
     return false;
   }
 
   // Comparison operators.
   bool operator==(const SmallBitVector &RHS) const {
     if (size() != RHS.size())
       return false;
-    if (isSmall())
+    if (isSmall() && RHS.isSmall())
       return getSmallBits() == RHS.getSmallBits();
-    else
+    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;
+    }
   }
 
   bool operator!=(const SmallBitVector &RHS) const {
     return !(*this == RHS);
   }
 
   // Intersection, union, disjoint union.
+  // FIXME BitVector::operator&= does not resize the LHS but this does
   SmallBitVector &operator&=(const SmallBitVector &RHS) {
     resize(std::max(size(), RHS.size()));
-    if (isSmall())
+    if (isSmall() && RHS.isSmall())
       setSmallBits(getSmallBits() & RHS.getSmallBits());
-    else if (!RHS.isSmall())
+    else if (!isSmall() && !RHS.isSmall())
       getPointer()->operator&=(*RHS.getPointer());
     else {
-      SmallBitVector Copy = RHS;
-      Copy.resize(size());
-      getPointer()->operator&=(*Copy.getPointer());
+      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);
     }
     return *this;
   }
 
   /// Reset bits that are set in RHS. Same as *this &= ~RHS.
   SmallBitVector &reset(const SmallBitVector &RHS) {
     if (isSmall() && RHS.isSmall())
       setSmallBits(getSmallBits() & ~RHS.getSmallBits());
for (e = size(); i != e; ++i)
       if (test(i))
         return true;
 
     return false;
   }
 
   SmallBitVector &operator|=(const SmallBitVector &RHS) {
     resize(std::max(size(), RHS.size()));
-    if (isSmall())
+    if (isSmall() && RHS.isSmall())
       setSmallBits(getSmallBits() | RHS.getSmallBits());
-    else if (!RHS.isSmall())
+    else if (!isSmall() && !RHS.isSmall())
       getPointer()->operator|=(*RHS.getPointer());
     else {
-      SmallBitVector Copy = RHS;
-      Copy.resize(size());
-      getPointer()->operator|=(*Copy.getPointer());
+      for (size_t i = 0, e = RHS.size(); i != e; ++i)
+        (*this)[i] = test(i) || RHS.test(i);
     }
     return *this;
   }
 
   SmallBitVector &operator^=(const SmallBitVector &RHS) {
     resize(std::max(size(), RHS.size()));
-    if (isSmall())
+    if (isSmall() && RHS.isSmall())
       setSmallBits(getSmallBits() ^ RHS.getSmallBits());
-    else if (!RHS.isSmall())
+    else if (!isSmall() && !RHS.isSmall())
       getPointer()->operator^=(*RHS.getPointer());
     else {
-      SmallBitVector Copy = RHS;
-      Copy.resize(size());
-      getPointer()->operator^=(*Copy.getPointer());
+      for (size_t i = 0, e = RHS.size(); i != e; ++i)
+        (*this)[i] = test(i) != RHS.test(i);
     }
     return *this;
   }
 
   SmallBitVector &operator<<=(unsigned N) {
     if (isSmall())
       setSmallBits(getSmallBits() << N);
     else

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, SimpleFindOps) {
-  // Test finding in an empty BitVector.
-  TypeParam A;
-  EXPECT_EQ(-1, A.find_first());
-  EXPECT_EQ(-1, A.find_last());
-  EXPECT_EQ(-1, A.find_first_unset());
-  EXPECT_EQ(-1, A.find_last_unset());
-
+TYPED_TEST(BitVectorTest, SimpleFindOpsMultiWord) {
   // 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);
 
   EXPECT_EQ(75, A.find_last());
   EXPECT_EQ(12, A.find_first());
TYPED_TEST(BitVectorTest, SimpleFindOpsMultiWord) {
 
   A.reset(0, 100);
   EXPECT_EQ(0U, A.count());
   EXPECT_EQ(-1, A.find_first());
   EXPECT_EQ(-1, A.find_last());
   EXPECT_EQ(0, A.find_first_unset());
   EXPECT_EQ(99, A.find_last_unset());
   EXPECT_EQ(99, A.find_next_unset(98));
+}
+
+// These tests are intended to exercise the single-word case of BitVector
+// and the small-mode case of SmallBitVector.
+TYPED_TEST(BitVectorTest, SimpleFindOpsSingleWord) {
+  // Test finding in an empty BitVector.
+  TypeParam A;
+  EXPECT_EQ(-1, A.find_first());
+  EXPECT_EQ(-1, A.find_last());
+  EXPECT_EQ(-1, A.find_first_unset());
+  EXPECT_EQ(-1, A.find_last_unset());
 
-  // Also test with a vector that is small enough to fit in 1 word.
   A.resize(20);
   A.set(3);
   A.set(4);
   A.set(16);
   EXPECT_EQ(16, A.find_last());
   EXPECT_EQ(3, A.find_first());
   EXPECT_EQ(3, A.find_next(1));
   EXPECT_EQ(4, A.find_next(3));
   EXPECT_EQ(16, A.find_next(4));
TYPED_TEST(BitVectorTest, CompoundAssignment) {
 
   B.resize(10);
   B.set();
   B.reset(2);
   B.reset(7);
   A &= B;
   EXPECT_FALSE(A.test(2));
   EXPECT_FALSE(A.test(7));
+  EXPECT_TRUE(A.test(4));
+  EXPECT_TRUE(A.test(5));
   EXPECT_EQ(2U, A.count());
   EXPECT_EQ(50U, A.size());
 
   B.resize(100);
   B.set();
 
   A ^= B;
   EXPECT_TRUE(A.test(2));
   EXPECT_TRUE(A.test(7));
   EXPECT_EQ(98U, A.count());
   EXPECT_EQ(100U, A.size());
 }
 
+// Test SmallBitVector operations with mixed big/small representations
+TYPED_TEST(BitVectorTest, MixedBigSmall) {
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Small &= Big;
+    EXPECT_TRUE(Small.test(0));
+    EXPECT_EQ(1u, Small.count());
+    // FIXME BitVector and SmallBitVector behave differently here.
+    // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size())
+    // but BitVector does not.
+    //EXPECT_EQ(20u, Small.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Big &= Small;
+    EXPECT_TRUE(Big.test(0));
+    EXPECT_EQ(1u, Big.count());
+    // FIXME BitVector and SmallBitVector behave differently here.
+    // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size())
+    // but BitVector does not.
+    //EXPECT_EQ(20u, Big.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Small |= Big;
+    EXPECT_TRUE(Small.test(0));
+    EXPECT_TRUE(Small.test(1));
+    EXPECT_TRUE(Small.test(2));
+    EXPECT_TRUE(Small.test(16));
+    EXPECT_EQ(4u, Small.count());
+    EXPECT_EQ(20u, Small.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Big |= Small;
+    EXPECT_TRUE(Big.test(0));
+    EXPECT_TRUE(Big.test(1));
+    EXPECT_TRUE(Big.test(2));
+    EXPECT_TRUE(Big.test(16));
+    EXPECT_EQ(4u, Big.count());
+    EXPECT_EQ(20u, Big.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Small ^= Big;
+    EXPECT_TRUE(Small.test(1));
+    EXPECT_TRUE(Small.test(2));
+    EXPECT_TRUE(Small.test(16));
+    EXPECT_EQ(3u, Small.count());
+    EXPECT_EQ(20u, Small.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Big ^= Small;
+    EXPECT_TRUE(Big.test(1));
+    EXPECT_TRUE(Big.test(2));
+    EXPECT_TRUE(Big.test(16));
+    EXPECT_EQ(3u, Big.count());
+    EXPECT_EQ(20u, Big.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Small.reset(Big);
+    EXPECT_TRUE(Small.test(1));
+    EXPECT_EQ(1u, Small.count());
+    EXPECT_EQ(10u, Small.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Big.reset(Small);
+    EXPECT_TRUE(Big.test(2));
+    EXPECT_TRUE(Big.test(16));
+    EXPECT_EQ(2u, Big.count());
+    EXPECT_EQ(20u, Big.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(10);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+
+    EXPECT_FALSE(Big == Small);
+    EXPECT_FALSE(Small == Big);
+    Big.set(1);
+    EXPECT_TRUE(Big == Small);
+    EXPECT_TRUE(Small == Big);
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Big.set(1);
+
+    EXPECT_FALSE(Small.anyCommon(Big));
+    EXPECT_FALSE(Big.anyCommon(Small));
+    Big.set(0);
+    EXPECT_TRUE(Small.anyCommon(Big));
+    EXPECT_TRUE(Big.anyCommon(Small));
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(10);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+
+    EXPECT_TRUE(Small.test(Big));
+    EXPECT_FALSE(Big.test(Small));
+    Big.set(1);
+    EXPECT_FALSE(Small.test(Big));
+    EXPECT_FALSE(Big.test(Small));
+  }
+}
+
 TYPED_TEST(BitVectorTest, ProxyIndex) {
   TypeParam Vec(3);
   EXPECT_TRUE(Vec.none());
   Vec[0] = Vec[1] = Vec[2] = true;
   EXPECT_EQ(Vec.size(), Vec.count());
   Vec[2] = Vec[1] = Vec[0] = false;
   EXPECT_TRUE(Vec.none());
 }