On February 27, 2025 1:57:41 PM PST, David Laight <david.laight.linux@xxxxxxxxx> wrote:
>On Thu, 27 Feb 2025 13:05:29 -0500
>Yury Norov <yury.norov@xxxxxxxxx> wrote:
>
>> On Wed, Feb 26, 2025 at 10:29:11PM +0000, David Laight wrote:
>> > On Mon, 24 Feb 2025 14:27:03 -0500
>> > Yury Norov <yury.norov@xxxxxxxxx> wrote:
>> > ....
>> > > +#define parity(val) \
>> > > +({ \
>> > > + u64 __v = (val); \
>> > > + int __ret; \
>> > > + switch (BITS_PER_TYPE(val)) { \
>> > > + case 64: \
>> > > + __v ^= __v >> 32; \
>> > > + fallthrough; \
>> > > + case 32: \
>> > > + __v ^= __v >> 16; \
>> > > + fallthrough; \
>> > > + case 16: \
>> > > + __v ^= __v >> 8; \
>> > > + fallthrough; \
>> > > + case 8: \
>> > > + __v ^= __v >> 4; \
>> > > + __ret = (0x6996 >> (__v & 0xf)) & 1; \
>> > > + break; \
>> > > + default: \
>> > > + BUILD_BUG(); \
>> > > + } \
>> > > + __ret; \
>> > > +})
>> > > +
>> >
>> > You really don't want to do that!
>> > gcc makes a right hash of it for x86 (32bit).
>> > See https://www.godbolt.org/z/jG8dv3cvs
>>
>> GCC fails to even understand this. Of course, the __v should be an
>> __auto_type. But that way GCC fails to understand that case 64 is
>> a dead code for all smaller type and throws a false-positive
>> Wshift-count-overflow. This is a known issue, unfixed for 25 years!
>
>Just do __v ^= __v >> 16 >> 16
>
>>
>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=4210
>>
>> > You do better using a __v32 after the 64bit xor.
>>
>> It should be an __auto_type. I already mentioned. So because of that,
>> we can either do something like this:
>>
>> #define parity(val) \
>> ({ \
>> #ifdef CLANG \
>> __auto_type __v = (val); \
>> #else /* GCC; because of this and that */ \
>> u64 __v = (val); \
>> #endif \
>> int __ret; \
>>
>> Or simply disable Wshift-count-overflow for GCC.
>
>For 64bit values on 32bit it is probably better to do:
>int p32(unsigned long long x)
>{
> unsigned int lo = x;
> lo ^= x >> 32;
> lo ^= lo >> 16;
> lo ^= lo >> 8;
> lo ^= lo >> 4;
> return (0x6996 >> (lo & 0xf)) & 1;
>}
>That stops the compiler doing 64bit shifts (ok on x86, but probably not elsewhere).
>It is likely to be reasonably optimal for most 64bit cpu as well.
>(For x86-64 it probably removes a load of REX prefix.)
>(It adds an extra instruction to arm because if its barrel shifter.)
>
>
>>
>> > Even the 64bit version is probably sub-optimal (both gcc and clang).
>> > The whole lot ends up being a bit single register dependency chain.
>> > You want to do:
>>
>> No, I don't. I want to have a sane compiler that does it for me.
>>
>> > mov %eax, %edx
>> > shrl $n, %eax
>> > xor %edx, %eax
>> > so that the 'mov' and 'shrl' can happen in the same clock
>> > (without relying on the register-register move being optimised out).
>> >
>> > I dropped in the arm64 for an example of where the magic shift of 6996
>> > just adds an extra instruction.
>>
>> It's still unclear to me that this parity thing is used in hot paths.
>> If that holds, it's unclear that your hand-made version is better than
>> what's generated by GCC.
>
>I wasn't seriously considering doing that optimisation.
>Perhaps just hoping is might make a compiler person think :-)
>
> David
>
>>
>> Do you have any perf test?
>>
>> Thanks,
>> Yury
>
What the compiler people need to do is to not make __builtin_parity*() generate crap.
