llvm / llvm/llvm-project

[missed-opt] Naive per-bit loop not optimized to popcnt

Open
#172,193 3 comments 0 reactions 0 assignees View on GitHub
llvm:optimizations missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

[Godbolt](https://godbolt.org/z/P5roxr96j)

In this snippet, `popcount_naive` is lowered as an unrolled loop, while `popcount_bit_tricks` is optimized to a `popcnt` instruction. This seems kind of backwards -- I would've expected a simpler loop to get recognized as an idiom than the more complex one.

```cpp
int popcount_naive(unsigned long x) {
int result = 0;
for (int i = 0; i < 64; i++) {
result += (x >> i) & 1;
}
return result;
}

int popcount_bit_tricks(unsigned long x) {
int result = 0;
while (x) {
result++;
x &= x - 1;
}
return result;
}
```

Though I imagine improving this would be non-trivial, since you'd have to recognize this either before the loop is unrolled or somehow find all the accesses later...

Bonus:

```cpp
int popcount_divide_and_conquer(unsigned long x) {
x = (x & 0x5555555555555555) + ((x >> 1 ) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2 ) & 0x3333333333333333);
x = (x & 0x0f0f0f0f0f0f0f0f) + ((x >> 4 ) & 0x0f0f0f0f0f0f0f0f);
x = (x & 0x00ff00ff00ff00ff) + ((x >> 8 ) & 0x00ff00ff00ff00ff);
x = (x & 0x0000ffff0000ffff) + ((x >> 16) & 0x0000ffff0000ffff);
x = (x & 0x00000000ffffffff) + ((x >> 32) & 0x00000000ffffffff);
return x;
}
```

This is another popcount idiom, and it's always more performant to optimize it to `popcnt` if it's available.

It also seems reasonable to optimize `popcount_naive` to `popcount_divide_and_conquer` on targets without `popcnt`. (Optimizing `popcount_bit_tricks` to `popcount_divide_and_conquer` is more iffy, since the latter has worse performance on numbers with low popcount.)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.