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

[purplesyringa]

Godbolt

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.

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:

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.)

[Explorer09]

There're infinitely many popcount idioms that the compiler could recognize. But you have to give a good reason for adding another recognition code in the compiler's side. Since C and C++ have standardised stdc_count_ones and std::popcount interfaces, future code should transition to those interfaces when possible instead of demanding the compiler to do the work (since this algorithm transformation is technically out of scope of compiler optimizers).

Related: #129805

[purplesyringa]

I agree that LLVM shouldn't support every idiom under the sun, and I wouldn't really expect it to recognize, say, popcount_divide_and_conquer. I filed this issues mostly due to popcount_naive exclusively, since it can be formulated as "sum of all bits" quite succinctly.

I came here from a post from a person learning Zig, where they tried to measure the performance of a naive implementation. I tried to compile it with various options and was very surprised when I found that with -march=skylake, the code is vectorized into 57-ish vector instructions (godbolt) with a ton of memory accesses.

I would be too worried if LLVM just kept this as a loop, I suppose, but the combination of questionable vectorization with variable-time performance and the fact that a smarter loop is optimized makes me think this would be a win for simple portable C or C-style code that doesn't know about any smart algorithms nor wants to use builtins.

[Explorer09]

I agree on one point: That the popcount_naive example generates larger code in -Os than in -O1 is a bug.

I didn't comment on the loop-to-vector-code transformations in -O2. My complaint is when the loop unrolling or transformations can make the code larger, it should not optimize in -Os. (Not sure why Clang disables this only in -Oz or -O1.)

https://godbolt.org/z/jh7sPh54c