4 ms·

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

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

nickysielicki 5y ago
Popcount is easily recognized by llvm (and it’s actually mentioned in the article...) 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.
- bsmith0 5y ago
  Yep my bad! I think flipping the order should work still though. The two links in the article: https://lemire.me/blog/2016/05/23/the-surprising-cleverness-of-modern-compilers/ 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.
  - nickysielicki 5y ago
    Flipping the order works, except if the LSB on x is set. https://godbolt.org/z/qdWhxMPsf 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).
    - tialaramex 5y ago
      > or equivalent in Rust https://doc.rust-lang.org/std/?search=count_ones 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.
    - vardump 5y ago
      While it seems to be true gcc and clang don't recognize this pattern even when implemented correctly, your program becomes an infinite loop if the highest bit is set (negative), because 'i' will never become 0. 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 One needs to be careful when using >> (shift right) with signed integers. So your program is not equivalent to popcount.
sumtechguy 5y ago
I came across this long ago. But it shows some very nice ways to fiddle bits. It has a few different ways to do it. Which would be handy on systems that do not have a popcount. https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html
deleted 5y ago
[deleted]
secondcoming 5y ago
Both clang and gcc have __builtin_popcnt variants.
- ncmncm 5y ago
  But both will issue actual popcount instructions only if they have been assured the program will be run on a machine that implements the instruction, which is not the default on, in particular, amd64/x86_64.

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

nickysielicki 5y ago

Popcount is easily recognized by llvm (and it’s actually mentioned in the article...) 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.

bsmith0 5y ago
Yep my bad! I think flipping the order should work still though. The two links in the article: https://lemire.me/blog/2016/05/23/the-surprising-cleverness-of-modern-compilers/ 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.
- nickysielicki 5y ago
  Flipping the order works, except if the LSB on x is set. https://godbolt.org/z/qdWhxMPsf 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).
  - tialaramex 5y ago
    > or equivalent in Rust https://doc.rust-lang.org/std/?search=count_ones 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.
  - vardump 5y ago
    While it seems to be true gcc and clang don't recognize this pattern even when implemented correctly, your program becomes an infinite loop if the highest bit is set (negative), because 'i' will never become 0. 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 One needs to be careful when using >> (shift right) with signed integers. So your program is not equivalent to popcount.

sumtechguy 5y ago

I came across this long ago. But it shows some very nice ways to fiddle bits. It has a few different ways to do it. Which would be handy on systems that do not have a popcount. https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html

deleted 5y ago

[deleted]

secondcoming 5y ago

Both clang and gcc have __builtin_popcnt variants.

ncmncm 5y ago
But both will issue actual popcount instructions only if they have been assured the program will be run on a machine that implements the instruction, which is not the default on, in particular, amd64/x86_64.