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

[Tzu-Ching Yang <shingekinocore@gmail.com>]

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.

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

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.

> On Fri, Oct 16, 2026, at 07:54, Arnd Bergmann wrote:
>> I don't understand what you are trying to do here, but I don't
>> think we want this change: I find the nested macros harder
>> to read than the open-coded version and your changelog text
>> fails to explain what the purpose is.

Sorry, the changelog buried the point. This is a cleanup of the
generic versions, which are still needed on targets without a suitable
instruction. generic_ffs(), generic___ffs(), generic_fls() and
generic___fls() each open-code the same binary search with their own
hand-written masks. The copies differ in the order of the two updates
in a step and in how the test is written, and the two unsigned long
ones need an #if around the extra step for 64-bit words. The patch
replaces the four copies with one shared step per direction, whose
shift and mask are computed from the step number and the type of the
word, so the literal masks and the #if go away (27 fewer lines
overall).

One detail that may look odd is that the patch uses UNROLL(20)
although a 64-bit word needs only six steps. The steps are not tied to
a particular width, so it expands all 20 that UNROLL() supports: once
the shift reaches 0, a step does nothing and the compiler drops it
when optimizing.

generic_ffs() and generic_fls() compile to the same code as before.
With GCC 16.2, the code in callers of generic___ffs() and
generic___fls() mostly differs only in the order of two independent
instructions, and vmlinux size is unchanged on most of the
architectures I built.

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.

>> If you have a specific problem with one of the platforms using
>> this, I would suggest you address that one but leave the
>> generic code unchanged.

No, the patch did not come from a problem on a specific platform; it
was meant purely as a cleanup.

A few minor notes, for completeness. Because the shifts and masks are
derived from the type of the word, the steps also work for wider words
(I checked unsigned __int128) and could be used to build ctz/clz-style
helpers for other unsigned types, though nothing needs that today. And
__fls_step as posted is only correct for unsigned words, which is what
both of its users pass; if there were a v2, it would make the steps
work in the unsigned type of the same width as the word. Separately
from this patch, generic_ffs() in mainline right-shifts its int
argument; for negative values that is implementation-defined, though
GCC and Clang shift arithmetically and the result is correct. If you
think it is worth fixing, I can send a small patch that copies the
argument to an unsigned int first.

Thanks,
Tzu-Ching