Adding __popcountsi2 and __popcountdi2
Hi Linus,
Since I ran into problems at pull request time previously, I figured I would save myself some trouble and gauge your opinion up front. How palatable would the diff at the end of the thread be for the kernel? Clang would like to start emitting calls to __popcountsi2 and __popcountdi2 [1] for certain architectures (ARM and RISC-V), which would normally be a part of the compiler runtime but obviously the kernel does not link against it so it breaks the build. I figured added these may not be as bad as the wcslen() case because most architectures generally have an optimized popcount implementation and I am not sure compiler builtins are banned entirely from the kernel but I can understand if it is still contentious. It sounds like GCC has previously wanted to something similar [2] and it was somewhat brought up on the mailing lists [3] but never persued further it seems. Since this is a compiler runtime function, '-fno-builtin' would not work to avoid this.
Cheers,
Nathan
[1]: https://github.com/llvm/llvm-project/pull/101786
[2]: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105253#c10
[3]: https://lore.kernel.org/YlSb5D3rDTyCWpay@tucnak/
lib/Makefile +1 -1
@@ -52,7 +52,7 @@ obj-y += lockref.o obj-y += bcd.o sort.o parser.o debug_locks.o random32.o \ bust_spinlocks.o kasprintf.o bitmap.o scatterlist.o \ - list_sort.o uuid.o iov_iter.o clz_ctz.o \ + list_sort.o uuid.o iov_iter.o clz_ctz.o popcount.o \ bsearch.o find_bit.o llist.o lwq.o memweight.o kfifo.o \ percpu-refcount.o rhashtable.o base64.o \ once.o refcount.o rcuref.o usercopy.o errseq.o bucket_locks.o \
lib/popcount.c new file +22 -0
@@ -0,0 +1,22 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* +* The functions in this file aren't called directly, but may be emitted +* by the compiler. +*/ + +#include <linux/bitops.h> +#include <linux/export.h> + +int __popcountsi2 (unsigned int val); +int __popcountsi2 (unsigned int val) +{ +return __arch_hweight32 (val); +} +EXPORT_SYMBOL (__popcountsi2); + +int __popcountdi2 (unsigned long long val); +int __popcountdi2 (unsigned long long val) +{ +return __arch_hweight64 (val); +} +EXPORT_SYMBOL (__popcountdi2);
Quoted 6 lines · Nathan Chancellor
I figured added
these may not be as bad as thewcslen()case because most architectures generally have an optimized popcount implementation and I am not sure compiler builtins are banned entirely from the kernel but I can understand if it is still contentious.
Why does the compiler even bother to do this if the architecture doesn't have the popcount instruction? The function call is quite possibly more expensive than just doing it the stupid way.
But if you want to do this, put the damn thing as an alias on the code that actually *does* the SW fallback in lib/hweight.c.
Because the way your patch does it now, it takes "I'm doing stupid things" to the next level by turning that function call into *two* function calls - first calling __popcountsi2, which then calls __sw_hweight32.
Let's not do stupid things, ok?
Linus
Quoted 11 lines · Linus Torvalds
Quoted 6 lines · Nathan Chancellor
I figured added
these may not be as bad as thewcslen()case because most architectures generally have an optimized popcount implementation and I am not sure compiler builtins are banned entirely from the kernel but I can understand if it is still contentious.Why does the compiler even bother to do this if the architecture doesn't have the popcount instruction? The function call is quite possibly more expensive than just doing it the stupid way.
Not entirely sure what the motivation is from the compiler side but I cannot immagine that they would be doing this if it was not more efficient in some way.
Quoted 9 lines
But if you want to do this, put the damn thing as an alias on the code that actually *does* the SW fallback in
lib/hweight.c.Because the way your patch does it now, it takes "I'm doing stupid things" to the next level by turning that function call into *two* function calls - first calling
__popcountsi2, which then calls__sw_hweight32.Let's not do stupid things, ok?
I will test declaring __popcount{s,d}i2() as aliases of __sw_hweight{32,64}() to see what effect that has but I figured that calling the __arch_hweight variants was more correct because some architectures (at least RISC-V and x86 when I looked) use alternatives in that path to use hardware instructions and avoid the software path altogether. While there would still be the overhead from the function call, I figured not using the software fallback would at least soften that blow.
Cheers,
Nathan
Quoted 9 lines · Nathan Chancellor
I will test declaring __popcount{s,d}i2() as aliases of __sw_hweight{32,64}() to see what effect that has but I figured that calling the
__arch_hweightvariants was more correct because some architectures (at least RISC-V and x86 when I looked) use alternatives in that path to use hardware instructions and avoid the software path altogether. While there would still be the overhead from the function call, I figured not using the software fallback would at least soften that blow.
Once you have the overhead of a function call - and all the register games etc that involves, you're almost certainly better off with the simple unconditional bitwise games.
Linus
Quoted 16 lines · On Thu, 24 Apr 2025 17:33:42 -0700 Nathan Chancellor <[email protected]> wrote:
Hi Linus,
Since I ran into problems at pull request time previously, I figured I would save myself some trouble and gauge your opinion up front. How palatable would the diff at the end of the thread be for the kernel? Clang would like to start emitting calls to
__popcountsi2and__popcountdi2[1] for certain architectures (ARM and RISC-V), which would normally be a part of the compiler runtime but obviously the kernel does not link against it so it breaks the build. I figured added these may not be as bad as thewcslen()case because most architectures generally have an optimized popcount implementation and I am not sure compiler builtins are banned entirely from the kernel but I can understand if it is still contentious. It sounds like GCC has previously wanted to something similar [2] and it was somewhat brought up on the mailing lists [3] but never persued further it seems. Since this is a compiler runtime function, '-fno-builtin' would not work to avoid this.
Is this the compiler converting a call to __builtin_popcount() into a function call - which the kernel can arrange to never do.
Or the compiler detecting a code pattern that looks like an open-coded 'popcount' function and deciding to convert it to a call to the builtin? (which is a translation the kernel pretty much never wants for any such code pattern - including memcpy()).
In either case the link failure is exactly what you want.
David
Quoted 9 lines · Linus Torvalds
Quoted 8 lines
I will test declaring __popcount{s,d}i2() as aliases of __sw_hweight{32,64}() to see what effect that has but I figured that calling the
__arch_hweightvariants was more correct because some architectures (at least RISC-V and x86 when I looked) use alternatives in that path to use hardware instructions and avoid the software path altogether. While there would still be the overhead from the function call, I figured not using the software fallback would at least soften that blow.
Quoted 3 lines
Once you have the overhead of a function call - and all the register games etc that involves, you're almost certainly better off with the simple unconditional bitwise games.
Unless optimising for size, which we do support.
Adding another function call to a non-leaf function is usually cheap on
RISC platforms as a stack frame must have been created already, so the instructions required have taken their space anyway. For a leaf function -- it depends, but in the cheapest case it's 5 instructions total: 2 pairs to adjust SP both ways and to save/restore the link register respectively, plus one for the actual call. The result may still be smaller than an open-coded variant.
I have no opinion though on providing libgcc replacement functions to
satisfy libcalls for -Os builds.
Maciej
Quoted 12 lines · Maciej W. Rozycki
Quoted 9 lines · Linus Torvalds
Quoted 8 lines
I will test declaring __popcount{s,d}i2() as aliases of __sw_hweight{32,64}() to see what effect that has but I figured that calling the
__arch_hweightvariants was more correct because some architectures (at least RISC-V and x86 when I looked) use alternatives in that path to use hardware instructions and avoid the software path altogether. While there would still be the overhead from the function call, I figured not using the software fallback would at least soften that blow.
Quoted 5 lines
Quoted 3 lines
Once you have the overhead of a function call - and all the register games etc that involves, you're almost certainly better off with the simple unconditional bitwise games.
Unless optimising for size, which we do support.
I think you missed the part where I said
"But if you want to do this, put the damn thing as an alias on the code
that actually *does* the SW fallback in lib/hweight.c."
IOW, what I object to is being *stupid* and doing *two* function calls. It sure as hell doesn't optimize for size.
If you want to optimize for size, just call the existing SW fallback in lib/hweight.c.
Don't call a *new* function that then calls the existing SW fallback as another fallback level.
Because that just makes me go "Eww".
Honestly, from a performance standpoint absolutely none of this matters. Unless you *inline* the bit scanning as a single instruction
- which this is *NOT* about - you have already lost.
So at that point, it's a question of just how pointless you want the code to be.
Linus
Quoted 6 lines · Linus Torvalds
Quoted 5 lines
Quoted 3 lines
Once you have the overhead of a function call - and all the register games etc that involves, you're almost certainly better off with the simple unconditional bitwise games.
Unless optimising for size, which we do support.
Quoted 7 lines
I think you missed the part where I said
"But if you want to do this, put the damn thing as an alias on the code
that actually *does* the SW fallback inlib/hweight.c."IOW, what I object to is being *stupid* and doing *two* function calls. It sure as hell doesn't optimize for size.
Sure, I only commented on whether or not to have entry points defined in
the link for libcalls that GCC emits whenever it produces a `popcount' operation it cannot find a machine description pattern for (IOW a machine instruction or a favourable sequence of).
They need to have specific names a per the subject and it's up to us to
implement them one way or another should we choose to; and as I say it seems not unreasonable to me for GCC to emit these libcalls at least when optimising for size.
Traditionally we have chosen not to implement double-precision division
libcalls so as to trap expensive usage. For `popcount' I have no opinion offhand.
Maciej