[PATCH 1/3] riscv: word-at-a-time: improve find_zero() for !RISCV_ISA_ZBB

Jisheng Zhang
2026-01-13T12:43:16Z

Current find_zero() heavily depends on fls64() for calculation. This
bring non-optimal code when !RISCV_ISA_ZBB.

But in word-at-a-time case, we don't have to go with fls64() code path,
instead, we can fallback to the generic word-at-a-time implementaion.

What's more, the fls64() brings non-necessary zero bits couting for
RV32. In fact, fls() is enough.

Before the patch:

0000000000000000 <find_zero>:
0: c529 beqz a0,4a <.L1>
2: 577d li a4,-1
4: 9301 srli a4,a4,0x20
6: 03f00793 li a5,63
a: 00a76463 bltu a4,a0,12 <.L3>
e: 1502 slli a0,a0,0x20
10: 47fd li a5,31

0000000000000012 <.L3>:
12: 577d li a4,-1
14: 8341 srli a4,a4,0x10
16: 00a76463 bltu a4,a0,1e <.L4>
1a: 37c1 addiw a5,a5,-16
1c: 0542 slli a0,a0,0x10

000000000000001e <.L4>:
1e: 577d li a4,-1
20: 8321 srli a4,a4,0x8
22: 00a76463 bltu a4,a0,2a <.L5>
26: 37e1 addiw a5,a5,-8
28: 0522 slli a0,a0,0x8

000000000000002a <.L5>:
2a: 577d li a4,-1
2c: 8311 srli a4,a4,0x4
2e: 00a76463 bltu a4,a0,36 <.L6>
32: 37f1 addiw a5,a5,-4
34: 0512 slli a0,a0,0x4

0000000000000036 <.L6>:
36: 577d li a4,-1
38: 8309 srli a4,a4,0x2
3a: 00a76463 bltu a4,a0,42 <.L7>
3e: 37f9 addiw a5,a5,-2
40: 050a slli a0,a0,0x2

0000000000000042 <.L7>:
42: 00054563 bltz a0,4c <.L12>
46: 4037d51b sraiw a0,a5,0x3

000000000000004a <.L1>:
4a: 8082 ret

000000000000004c <.L12>:
4c: 2785 addiw a5,a5,1
4e: 4037d51b sraiw a0,a5,0x3
52: 8082 ret

After the patch:

0000000000000000 <find_zero>:
0: 102037b7 lui a5,0x10203
4: 0792 slli a5,a5,0x4
6: 40578793 addi a5,a5,1029 # 10203405 <.L4+0x102033c5>
a: 07c2 slli a5,a5,0x10
c: 60878793 addi a5,a5,1544
10: 02f50533 mul a0,a0,a5
14: 9161 srli a0,a0,0x38
16: 8082 ret

33 instructions vs 8 instructions!

And this kind of instructions reducing dramatically improves the
performance of below micro-benchmark:

$ cat tt.c
#inlcude <stdio.h>
#inlcude "word-at-a-time.h" // copy and modify, eg. remove other headers
int main()
{
int i;
unsigned long ret = 0;

for (i = 0; i < 100000000; i++)
ret |= find_zero(0xabcd123 + i);

printf("%ld\n", ret);
}
$ gcc -O tt.c
$ time ./a.out

Per my test, the above micro-benchmark is improved by about 1150%!

Signed-off-by: Jisheng Zhang <jszhang@kernel.org>
---
arch/riscv/include/asm/word-at-a-time.h | 5 +++++
1 file changed, 5 insertions(+)

diff --git a/arch/riscv/include/asm/word-at-a-time.h b/arch/riscv/include/asm/word-at-a-time.h
index 3802cda71ab7..0c8a9b337f93 100644
--- a/arch/riscv/include/asm/word-at-a-time.h
+++ b/arch/riscv/include/asm/word-at-a-time.h
@@ -13,6 +13,9 @@
#include <linux/bitops.h>
#include <linux/wordpart.h>

+#if !(defined(CONFIG_RISCV_ISA_ZBB) && defined(CONFIG_TOOLCHAIN_HAS_ZBB))
+#include <asm-generic/word-at-a-time.h>
+#else
struct word_at_a_time {
const unsigned long one_bits, high_bits;
};
@@ -47,6 +50,8 @@ static inline unsigned long find_zero(unsigned long mask)
/* The mask we created is directly usable as a bytemask */
#define zero_bytemask(mask) (mask)

+#endif /* !(defined(CONFIG_RISCV_ISA_ZBB) && defined(CONFIG_TOOLCHAIN_HAS_ZBB)) */
+
#ifdef CONFIG_DCACHE_WORD_ACCESS

/*
--
2.51.0