This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by baziotis on Jul 27 2020, 5:47 PM.

Details

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.

Diff Detail

Event Timeline

baziotis created this revision.Jul 27 2020, 5:47 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 27 2020, 5:47 PM

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 updated this revision to Diff 281141.Jul 28 2020, 1:50 AM

Addressed comments.

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?

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

baziotis retitled this revision from [ADT][BitVector] Merge find_first_in() / find_first_unset_in() to [ADT][BitVector][NFC] Merge find_first_in() / find_first_unset_in().Jul 28 2020, 3:35 AM

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?

lattner resigned from this revision.Jul 28 2020, 9:45 AM
Meinersbur accepted this revision.Jul 28 2020, 10:13 AM

LGTM

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
275

set -> Set

This revision is now accepted and ready to land.Jul 28 2020, 10:13 AM

LGTM

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 updated this revision to Diff 281449.Jul 28 2020, 6:42 PM
baziotis edited the summary of this revision. (Show Details)
  • Added doc.