Failure to spot `popcount` idiom

[Kmeakin]

LLVM does a valiant effort of unrolling and vectorizing these loops, but they're really just popcount and it should recognize them as such

godbolt
alive proof

#include <stdint.h>

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;

template <typename T>
auto src(T x) -> u64 {
    u64 count = 0;
    for (u64 i = 0; i < sizeof(T) * 8; i++) {
        if (x & ((u64)1 << i)) {
            count++;
        }
    }
    return count;
}

template <typename T>
auto tgt(T x) -> u64 {
    return __builtin_popcountg(x);
}

extern "C" {
auto src8(u8 x) -> u64 { return src(x); }
auto src16(u16 x) -> u64 { return src(x); }
auto src32(u32 x) -> u64 { return src(x); }
auto src64(u64 x) -> u64 { return src(x); }

auto tgt8(u8 x) -> u64 { return tgt(x); }
auto tgt16(u16 x) -> u64 { return tgt(x); }
auto tgt32(u32 x) -> u64 { return tgt(x); }
auto tgt64(u64 x) -> u64 { return tgt(x); }
}

[Kmeakin]

Another variant not recognized is
godbolt
alive proof

template <typename T>
auto src(T x) -> u64 {
    u64 count = 0;
    for (; x > 0; x >>= 1) {
        if (x & 1) {
            count++;
        }
    }
    return count;
}

[Kmeakin]

This variant is recognized, but LLVM generates an unecessary branch to skip over the popcount instruction if x is 0:

godbolt
alive proof

template <typename T>
auto src(T x) -> u64 {
    u64 count = 0;
    for (; x > 0; x &= (x - 1)) {
        count++;
    }
    return count;
}

[topperc]

There's some overlap with the discussion in #129218

[Explorer09]

Can we just tell the code writers to just adopt the __builtin_popcount() or one of the standard functions (stdc_count_ones() in C23 and std::popcount() in C++20)? Ultimately the compilers should not need to recognize various popcount idioms and instead let the standard functions do the thing.

The bad thing for transforming a popcount loop into a built-in is that programmers might also do something else within the loop and, in certain cases, they don't want these transformations (for example, in benchmarking code). When Clang does such transformations, it would be not trivial to write syntax that suppress them.

[Kmeakin]

Can we just tell the code writers to just adopt the __builtin_popcount() or one of the standard functions (stdc_count_ones() in C23 and std::popcount() in C++20)? Ultimately the compilers should not need to recognize various popcount idioms and instead let the standard functions do the thing.

The bad thing for transforming a popcount loop into a built-in is that programmers might also do something else within the loop and, in certain cases, they don't want these transformations (for example, in benchmarking code). When Clang does such transformations, it would be not trivial to write syntax that suppress them.

There is a lot of old code out there that cannot or will not be rewritten, or the programmer may not realise that the code they have written is equivalent to a popcount. Better to solve it in one place (the compiler)

[topperc]

Can we just tell the code writers to just adopt the __builtin_popcount() or one of the standard functions (stdc_count_ones() in C23 and std::popcount() in C++20)? Ultimately the compilers should not need to recognize various popcount idioms and instead let the standard functions do the thing.
The bad thing for transforming a popcount loop into a built-in is that programmers might also do something else within the loop and, in certain cases, they don't want these transformations (for example, in benchmarking code). When Clang does such transformations, it would be not trivial to write syntax that suppress them.

There is a lot of old code out there that cannot or will not be rewritten, or the programmer may not realise that the code they have written is equivalent to a popcount. Better to solve it in one place (the compiler)

There are a lot of different ways you could write a popcount. How many ways should the compiler support? We already support two of the faster methods here https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan and https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

[Explorer09]

@Kmeakin

There is a lot of old code out there that cannot or will not be rewritten, or the programmer may not realise that the code they have written is equivalent to a popcount. Better to solve it in one place (the compiler)

If the programmer can't realise what they have written is a popcount, then neither can the compiler, because someone has to recognise the pattern or else the compiler isn't magic AI that can do it for humans.

Besides, if you can't optimise old code, it's better to leave it alone. The old code will always work whether or not there is a transformation to a popcount operation.

On the other hand, if you know you can optimise it, you would patch it already before compiling and not complain here.

@topperc

There are a lot of different ways you could write a popcount. How many ways should the compiler support? We already support two of the faster methods here

A lot:
#79823 (comment)