[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 ↗

(On Diff #95984)

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 ↗

(On Diff #95984)

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

175–179 ↗

(On Diff #96163)

I this can be written as:

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

213–218 ↗

(On Diff #96163)

I think this is the same as:

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

llvm/trunk/include/llvm/ADT/BitVector.h

 // This file implements the BitVector class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_BITVECTOR_H
 #define LLVM_ADT_BITVECTOR_H
 
 #include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <cassert>
 #include <climits>
 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
 #include <utility>
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 {
+    if (Size == 0)
+      return -1;
+
+    unsigned N = NumBitWords(size());
+    assert(N > 0);
+
+    unsigned i = N - 1;
+    while (i > 0 && Bits[i] == BitWord(0))
+      --i;
+
+    return int((i + 1) * BITWORD_SIZE - countLeadingZeros(Bits[i])) - 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 {
+    if (Size == 0)
+      return -1;
+
+    const unsigned N = NumBitWords(size());
+    assert(N > 0);
+
+    unsigned i = N - 1;
+    BitWord W = Bits[i];
+
+    // The last word in the BitVector has some unused bits, so we need to set
+    // them all to 1 first.  Set them all to 1 so they don't get treated as
+    // valid unset bits.
+    unsigned UnusedCount = BITWORD_SIZE - size() % BITWORD_SIZE;
+    W |= maskLeadingOnes<BitWord>(UnusedCount);
+
+    while (W == ~BitWord(0) && --i > 0)
+      W = Bits[i];
+
+    return int((i + 1) * BITWORD_SIZE - countLeadingOnes(W)) - 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/trunk/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/trunk/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);