[ADT][BitVector][NFC] Merge find_first_in() / find_first_unset_in()

[baziotis]

Summary

We can implement find_first_unset_in() in the same function if every BitWord we use is first flipped.

Performance wise, it should be the same because the branch predictor will do a very good job
since Set stays the same in a single run of the function. Plus, this won't even be a real
branch in x86, it will be just a cmov.

[Meinersbur]

Could you add "NFC" in the title?

llvm/include/llvm/ADT/BitVector.h

209

[style] Parameter names start with a capital letter.

216

[style] Parentheses are redundant.

There only one call to it, why the lambda?

[baziotis]

Addressed comments.

[baziotis]

One proposal by a friend of mine, GeorgeLS, is that we can make a wrapper in which instead of passing a bool, we pass a BitWord.
And then we XOR with this BitWord every BitWord we read from Bits. So, the passed BitWord acts conditionally. If we want the "unset" version, we pass ~0.
If we want the "set" version, we pass 0.

In that way, we can make the code unconditional. What do you think?

[RKSimon]

Please can you add unit test coverage at llvm/unittest/ADT/BitVectorTest.cpp

[baziotis]

In D84717#2178123, @RKSimon wrote:

Please can you add unit test coverage at llvm/unittest/ADT/BitVectorTest.cpp

Why? I mean, this is NFC, there's no new functionality added. What was tested previously, is tested still (more specifically, there are already tests for these two functions). Do I miss something?

[Meinersbur]

LGTM

In D84717#2178016, @baziotis wrote:

One proposal by a friend of mine, GeorgeLS, is that we can make a wrapper in which instead of passing a bool, we pass a BitWord.
And then we XOR with this BitWord every BitWord we read from Bits. So, the passed BitWord acts conditionally. If we want the "unset" version, we pass ~0.
If we want the "set" version, we pass 0.

An optimizing compiler might already do this if it thinks it is profitable. That is, InstCombine

if (!Set)
  Copy = ~Copy;

to

Mask = Set ? 0 : -1;
Copy ^= Mask;

and hoist Mask out of the loop.

However, unless you show that there is a relevant performance difference, I don't have a preference for either version.

llvm/include/llvm/ADT/BitVector.h

276

set -> Set

[baziotis]

In D84717#2179172, @Meinersbur wrote:

LGTM

In D84717#2178016, @baziotis wrote:

One proposal by a friend of mine, GeorgeLS, is that we can make a wrapper in which instead of passing a bool, we pass a BitWord.
And then we XOR with this BitWord every BitWord we read from Bits. So, the passed BitWord acts conditionally. If we want the "unset" version, we pass ~0.
If we want the "set" version, we pass 0.

An optimizing compiler might already do this if it thinks it is profitable. That is, InstCombine

if (!Set)
  Copy = ~Copy;

to

Mask = Set ? 0 : -1;
Copy ^= Mask;

and hoist Mask out of the loop.

However, unless you show that there is a relevant performance difference, I don't have a preference for either version.

Oh well, indeed: https://godbolt.org/z/9KsYKa
Thanks, I didn't think about it.

[baziotis]

• Added doc.

llvm/include/llvm/ADT/BitVector.h

bool all() const {
     return true;
   }
 
   /// none - Returns true if none of the bits are set.
   bool none() const {
     return !any();
   }
 
-  /// find_first_in - Returns the index of the first set bit in the range
-  /// [Begin, End).  Returns -1 if all bits in the range are unset.
-  int find_first_in(unsigned Begin, unsigned End) const {
+  /// find_first_in - Returns the index of the first set / unset bit,
+  /// depending on \p Set, in the range [Begin, End).
+  /// Returns -1 if all bits in the range are unset / set.
+  int find_first_in(unsigned Begin, unsigned End, bool Set = true) const {
     assert(Begin <= End && End <= Size);
     if (Begin == End)
       return -1;
 
     unsigned FirstWord = Begin / BITWORD_SIZE;
     unsigned LastWord = (End - 1) / BITWORD_SIZE;
 
     // Check subsequent words.
+    // The code below is based on search for the first _set_ bit. If
+    // we're searching for the first _unset_, we just take the
+    // complement of each word before we use it and apply
+    // the same method.
     for (unsigned i = FirstWord; i <= LastWord; ++i) {
       BitWord Copy = Bits[i];
+      if (!Set)
+        Copy = ~Copy;
 
       if (i == FirstWord) {
         unsigned FirstBit = Begin % BITWORD_SIZE;
         Copy &= maskTrailingZeros<BitWord>(FirstBit);
       }
 
       if (i == LastWord) {
         unsigned LastBit = (End - 1) % BITWORD_SIZE;
int find_last_in(unsigned Begin, unsigned End) const {
     }
 
     return -1;
   }
 
   /// find_first_unset_in - Returns the index of the first unset bit in the
   /// range [Begin, End).  Returns -1 if all bits in the range are set.
   int find_first_unset_in(unsigned Begin, unsigned End) const {
-    assert(Begin <= End && End <= Size);
-    if (Begin == End)
-      return -1;
-
-    unsigned FirstWord = Begin / BITWORD_SIZE;
-    unsigned LastWord = (End - 1) / BITWORD_SIZE;
-
-    // Check subsequent words.
-    for (unsigned i = FirstWord; i <= LastWord; ++i) {
-      BitWord Copy = Bits[i];
-
-      if (i == FirstWord) {
-        unsigned FirstBit = Begin % BITWORD_SIZE;
-        Copy |= maskTrailingOnes<BitWord>(FirstBit);
-      }
-
-      if (i == LastWord) {
-        unsigned LastBit = (End - 1) % BITWORD_SIZE;
-        Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
-      }
-      if (Copy != ~BitWord(0)) {
-        unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Copy);
-        return Result < size() ? Result : -1;
-      }
-    }
-    return -1;
+    return find_first_in(Begin, End, /* Set = */ false);
   }
 
   /// find_last_unset_in - Returns the index of the last unset bit in the
   /// range [Begin, End).  Returns -1 if all bits in the range are set.
   int find_last_unset_in(unsigned Begin, unsigned End) const {
     assert(Begin <= End && End <= Size);
     if (Begin == End)
       return -1;