Re: [PATCH] bitops: Share the generic ffs()/fls() binary search via UNROLL()

["Arnd Bergmann" <arnd@arndb.de>]

On Fri, Oct 16, 2026, at 15:53, Tzu-Ching Yang wrote:
> On Fri, Oct 16, 2026, at 09:16, Arnd Bergmann wrote:
>> If you are interested in creating helpful patches in this area,
>> maybe you could work towards eliminating the generic versions
>> of these functions in favor of using the builtin ones on targets
>> where the compilers produce sensible code for them.
>
> Thanks, I looked into this. For each architecture variant, I put the
> kernel's current version of each function and the builtin one into a
> small userspace test file, each in a function of its own, compiled it
> at -O2 and -Os with every GCC major release from 8 to 16 and Clang 17
> to 23 that supports the target, and compared the instruction counts
> for a variable argument. Of the rows below, only hexagon (Clang only),
> powerpc and mips other than octeon could be built with Clang. A few
> GCC -Os builds did not inline the kernel's version, so those cells
> (arc ARCompact, ffs() and fls() on mips, and ffs() on microblaze) use
> -O2 only.
>
> Each cell below gives what the kernel uses today (G the generic
> version or a copy of it, A arch asm, B the builtin) and how the
> builtin compares with it:
>
>   +  inline and never more instructions, with every compiler
>   ~  as +, but only with some compilers (see below)
>   -  more instructions, with every compiler
>   x  the hardware has an instruction, but the compiler never emits it
>      (the builtin is a library call)
>
> In the "fls (clzg)" column, the code in parentheses is for fls()
> written as 32 - __builtin_clzg(x, 32), which needs GCC 14 or Clang 19
> or later, so it covers only those compilers.

Thanks for checking those!

                      | __ffs | ffs | __fls | fls (clzg)
> ---------------------+-------+-----+-------+-----------
> ColdFire ISA_A+/C    | A-    | A-  | G+    | G+  (G+)
> microblaze PCMP 8.10 | G+    | G+  | G+    | G+  (G+)
> microblaze PCMP 11.0 | G~    | G~  | G~    | G~  (G+)
> hexagon              | A+    | A+  | A+    | A+  (A+)
> mips32 r2/r6         | A~    | A+  | A+    | A~  (A+)
> mips64 r2            | A~    | A+  | A+    | A~  (A~)
> mips64 r6            | G+    | A+  | G+    | A~  (A~)
> mips octeon          | A+    | A+  | A+    | A-  (A+)
> xtensa NSA           | A+    | A+  | A+    | A-  (A-)
> arc ARCompact        | A+    | A-  | A+    | A-  (A-)
> m68k 68020+          | A+    | A-  | A+    | A-  (A-)
> arc HS               | A~    | A+  | A~    | A-  (A-)
> csky                 | Ax    | Ax  | A+    | A-  (A-)
> openrisc FF1/FL1     | Ax    | Ax  | Ax    | Ax  (Ax)
> powerpc              | B     | B   | B     | A~  (A+)
>
> The ~ cells depend on the compiler: microblaze 11.0 needs GCC 14
> (older GCC compares "v11.0" and "v8.10.a" as plain strings and emits a
> library call), arc HS needs GCC 12, mips __ffs() is + only with GCC,
> mips and powerpc fls() only with Clang, and on mips64 neither fls()
> nor clzg is + with Clang 19.
>
> Not listed are the targets without a suitable instruction, where GCC
> turns the builtins into library calls, so their current code has to
> stay: alpha ev56, arm v4/v4t, ColdFire ISA_A/ISA_B, m68000, microblaze
> without PCMP or before 8.10.a, mips R3000, nios2, openrisc without
> FF1/FL1, parisc, riscv without Zbb, loongarch la32r, sh and sparc32.

Right, that list is pretty much anyone using the generic helpers
today, so it does not sound like we can convert any of them to
the built-in version, only the architectures that currently use
a custom helper.

> The G cells are the clear candidates: microblaze with PCMP (8.10.a or
> later) uses the generic versions although GCC emits clz for the
> builtins, and ColdFire ISA_A+/C still uses them for __fls() and fls(),
> while __ffs() and ffs() there already use ff1 in asm. On mips64 r6,
> __ffs() and __fls() end up in the C fallback of __fls(), a copy of the
> generic version. I confirmed this in 64r6el_defconfig builds with GCC
> 16 and Clang 23: the dclz branch is used only if cpu_has_mips64 is a
> compile-time constant, and on r6 it is not, because cpu_has_mips64r6
> still tests a runtime flag. The builtins would cut both functions
> there from 34-64 instructions to 4-8; making cpu_has_mips64r6 constant
> on 64-bit r6 kernels would fix this as well.

> In the A cells, __ffs() and __fls() could mostly switch at no cost,
> which also lets the compiler fold constant arguments where the asm
> does not. fls() pays for the zero test that __builtin_clz() needs,
> unless the compiler knows what the instruction returns for 0: Clang
> does on hexagon, mips and powerpc, and GCC only with __builtin_clzg(),
> on mips and powerpc. That test is why powerpc keeps asm for fls() with
> non-constant arguments.
>
> If this is what you had in mind, I would send one patch per
> architecture to its maintainers, with you, Yury and Rasmus on Cc:
> first the G+ cells (microblaze, ColdFire and mips64 r6), then the A+
> cells (hexagon, mips, xtensa, arc, m68k 68020+ and csky), with fls()
> using __builtin_clzg() behind a __has_builtin() check where the table
> shows that it helps (mips and powerpc). The same change to
> builtin-fls.h would make fls() smaller with some compilers, and never
> larger, on arm, arm64, loongarch and s390 (on arm64 from 6 to 4
> instructions at -O2 with GCC 14 and later). The ~ cells would need a
> check for the compiler or its version, so I would only do those if the
> maintainers want it. Each patch would be tested with kernel builds and
> the ffs KUnit test.

I would focus on the ones where you can manage to reduce complexity
in the architecture specific code, i.e. replace a custom helper with
the builtin one, but skip the ones where you would need additional
conditionals on toolchain or target options.

On most of these architectures, adding performance or size
optimization is no longer a concern, but source code
simplification does help.

If you have cases where gcc-12 and above produce better code wiht
the built-in, it may still be worth doing that for all toolchains
even if the older compilers may be off slightly worse.

> I agree that each step is easier to check in the open-coded version.
> The trade-off is one place to check instead of four, but since you
> find the current code easier to read, I'm happy to drop this unless
> Yury sees it differently.

Ok.

     Arnd