[BitVector] Add find_last() and find_last_unset()

[zturner]

Summary

BitVector currently provides find_first() and find_first_unset(), this adds methods to search in reverse.

[chandlerc]

llvm/include/llvm/ADT/BitVector.h

170–173

The for loop above seems simpler?

If you really want, you can use:

for (unsigned i : llvm::reverse(llvm::seq(0, NumBitWords(size())))

196–202

Rather than this, what about just handling the last word outside the loop?

[zturner]

Updated based on feedback from chandlerc.

[zturner]

Fix an inverted conditional / break statement.

[chandlerc]

LGTM with some loop simplifications.

llvm/include/llvm/ADT/BitVector.h

176–180

I this can be written as:

while (i > 0 && Bits[i] != Bitword(0))
  --i;

208–213

I think this is the same as:

while (W == ~BitWord(0) && --i > 0)
  W = Bits[i];

llvm/include/llvm/ADT/BitVector.h

public:
   /// of the bits are set.
   int find_first() const {
     for (unsigned i = 0; i < NumBitWords(size()); ++i)
       if (Bits[i] != 0)
         return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
     return -1;
   }
 
+  /// find_last - Returns the index of the last set bit, -1 if none of the bits
+  /// are set.
+  int find_last() const {
+    ArrayRef<BitWord> Words(Bits, NumBitWords(size()));
+    for (auto Word : enumerate(reverse(Words))) {
+      if (Word.value() == BitWord(0))
+        continue;
+      unsigned Idx = NumBitWords(size()) - Word.index();
+      return Idx * BITWORD_SIZE - countLeadingZeros(Word.value()) - 1;
+    }
+    return -1;
+  }
+
   /// find_first_unset - Returns the index of the first unset bit, -1 if all
   /// of the bits are set.
   int find_first_unset() const {
     for (unsigned i = 0; i < NumBitWords(size()); ++i)
       if (Bits[i] != ~0UL) {
         unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Bits[i]);
         return Result < size() ? Result : -1;
       }
     return -1;
   }
 
+  /// find_last_unset - Returns the index of the last unset bit, -1 if all of
+  /// the bits are set.
+  int find_last_unset() const {
+    ArrayRef<BitWord> Words(Bits, NumBitWords(size()));
+    for (auto Word : enumerate(reverse(Words))) {
+      BitWord Val = Word.value();
+      if (Word.index() == 0) {
+        // If this is the last word in the BitVector, it has some unused bits.
+        // Set them all to 1 so that the countLeadingOnes check works.
+        unsigned UnusedCount = BITWORD_SIZE - size() % BITWORD_SIZE;
+        BitWord Mask = maskLeadingOnes<BitWord>(UnusedCount);
+        Val |= Mask;
+      }
+
+      if (Val == ~BitWord(0))
+        continue;
+
+      unsigned Idx = NumBitWords(size()) - Word.index() - 1;
+      unsigned Result = (Idx + 1) * BITWORD_SIZE - countLeadingOnes(Val) - 1;
+      assert(Result < size());
+      return Result;
+    }
+    return -1;
+  }
+
   /// find_next - 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 {
     ++Prev;
     if (Prev >= Size)
       return -1;
 
     unsigned WordPos = Prev / BITWORD_SIZE;

llvm/include/llvm/ADT/SmallBitVector.h

private:
   }
 
   void setSmallRawBits(uintptr_t NewRawBits) {
     assert(isSmall());
     X = (NewRawBits << 1) | uintptr_t(1);
   }
 
   // Return the size.
-  size_t getSmallSize() const {
-    return getSmallRawBits() >> SmallNumDataBits;
-  }
+  size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
 
   void setSmallSize(size_t Size) {
     setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
   }
 
   // Return the element bits.
   uintptr_t getSmallBits() const {
     return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
if (isSmall()) {
       uintptr_t Bits = getSmallBits();
       if (Bits == 0)
         return -1;
       return countTrailingZeros(Bits);
     }
     return getPointer()->find_first();
   }
 
+  int find_last() const {
+    if (isSmall()) {
+      uintptr_t Bits = getSmallBits();
+      if (Bits == 0)
+        return -1;
+      return NumBaseBits - countLeadingZeros(Bits);
+    }
+    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);
+    }
+    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()) {
       uintptr_t Bits = getSmallBits();
       // Mask off previous bits.
       Bits &= ~uintptr_t(0) << (Prev + 1);
       if (Bits == 0 || Prev + 1 >= getSmallSize())

llvm/unittests/ADT/BitVectorTest.cpp

TYPED_TEST(BitVectorTest, TrivialOperation) {
   EXPECT_TRUE(Vec.none());
   EXPECT_TRUE(Vec.empty());
 }
 
 TYPED_TEST(BitVectorTest, FindOperations) {
   // 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());
   EXPECT_EQ(-1, A.find_next(0));
   EXPECT_EQ(-1, A.find_next_unset(0));
 
   // 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());
   EXPECT_EQ(13, A.find_next(12));
   EXPECT_EQ(75, A.find_next(13));
   EXPECT_EQ(-1, A.find_next(75));
 
   EXPECT_EQ(0, A.find_first_unset());
+  EXPECT_EQ(99, A.find_last_unset());
   EXPECT_EQ(14, A.find_next_unset(11));
   EXPECT_EQ(14, A.find_next_unset(12));
   EXPECT_EQ(14, A.find_next_unset(13));
   EXPECT_EQ(16, A.find_next_unset(15));
   EXPECT_EQ(76, A.find_next_unset(74));
   EXPECT_EQ(76, A.find_next_unset(75));
   EXPECT_EQ(-1, A.find_next_unset(99));
 
   A.set(0, 100);
   EXPECT_EQ(100U, A.count());
   EXPECT_EQ(0, A.find_first());
+  EXPECT_EQ(99, A.find_last());
   EXPECT_EQ(-1, A.find_first_unset());
+  EXPECT_EQ(-1, A.find_last_unset());
 
   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());
 }
 
 TYPED_TEST(BitVectorTest, CompoundAssignment) {
   TypeParam A;
   A.resize(10);
   A.set(4);
   A.set(7);