Here's a dumb question. If someone asked me to do it I'd probably write code like:
while(x != 0) { c += x&1; x >>= 1; }
Is this something that should be added to LLVM?
Edit: flip the order
while(x != 0) { c += x&1; x >>= 1; }
Is this something that should be added to LLVM?
Edit: flip the order
In the case of the code you’ve posted, you’re shifting out the LSB before you check the bit, so it’s not quite right, but (in general) popcount is recognized and used when possible.
The two links in the article:
https://lemire.me/blog/2016/05/23/the-surprising-cleverness-...
And the LLVM source indicate to me it only picks up on x&(x-1) pattern, which would miss the popcount optimization on code like mine.
https://godbolt.org/z/qdWhxMPsf
Note the run output under clang.
edit:
> And the LLVM source indicate to me it only picks up on x&(x-1) pattern, which would miss the popcount optimization on code like mine.
Thanks for teaching me something this morning. That's annoying.
I think the portable solution is std::popcount in C++ (or equivalent in Rust).
https://doc.rust-lang.org/std/?search=count_ones
Internally Rust actually just staples LLVM's implementation into your code, via an intrinsic - but if that were ever to change the standard library count_ones() methods will do whatever happens instead so you should use that.
Example with int8_t:
int8_t i = -127; // 0b10000001
i >>= 1; // 0b11000000
i >>= 1; // 0b11100000
i >>= 1; // 0b11110000
i >>= 1; // 0b11111000
i >>= 1; // 0b11111100
i >>= 1; // 0b11111110
i >>= 1; // 0b11111111
i >>= 1; // 0b11111111 ad infinitum
So your program is not equivalent to popcount.