Re: [PATCH 11/14] lib: add fast path for find_next_*_bit()

Andy Shevchenko
2021-02-18T18:03:07Z

On Wed, Feb 17, 2021 at 08:05:09PM -0800, Yury Norov wrote:
> Similarly to bitmap functions, find_next_*_bit() users will benefit
> if we'll handle a case of bitmaps that fit into a single word. In the
> very best case, the compiler may replace a function call with a few
> instructions.
>
> This is the quite typical find_next_bit() user:
>
> unsigned int cpumask_next(int n, const struct cpumask *srcp)
> {
> /* -1 is a legal arg here. */
> if (n != -1)
> cpumask_check(n);
> return find_next_bit(cpumask_bits(srcp), nr_cpumask_bits, n + 1);
> }
> EXPORT_SYMBOL(cpumask_next);
>
> On ARM64 if CONFIG_FAST_PATH is disabled it generates:

bloat-o-meter over specific module and/or vmlinux.o?

> 0000000000000000 <cpumask_next>:
> 0: a9bf7bfd stp x29, x30, [sp, #-16]!
> 4: 11000402 add w2, w0, #0x1
> 8: aa0103e0 mov x0, x1
> c: d2800401 mov x1, #0x40 // #64
> 10: 910003fd mov x29, sp
> 14: 93407c42 sxtw x2, w2
> 18: 94000000 bl 0 <find_next_bit>
> 1c: a8c17bfd ldp x29, x30, [sp], #16
> 20: d65f03c0 ret
> 24: d503201f nop
>
> If CONFIG_FAST_PATH is enabled:
> 0000000000000140 <cpumask_next>:
> 140: 11000400 add w0, w0, #0x1
> 144: 93407c00 sxtw x0, w0
> 148: f100fc1f cmp x0, #0x3f
> 14c: 54000168 b.hi 178 <cpumask_next+0x38> // b.pmore
> 150: f9400023 ldr x3, [x1]
> 154: 92800001 mov x1, #0xffffffffffffffff // #-1
> 158: 9ac02020 lsl x0, x1, x0
> 15c: 52800802 mov w2, #0x40 // #64
> 160: 8a030001 and x1, x0, x3
> 164: dac00020 rbit x0, x1
> 168: f100003f cmp x1, #0x0
> 16c: dac01000 clz x0, x0
> 170: 1a800040 csel w0, w2, w0, eq // eq = none
> 174: d65f03c0 ret
> 178: 52800800 mov w0, #0x40 // #64
> 17c: d65f03c0 ret
>
> find_next_bit() call is replaced with 6 instructions. (And I suspect
> we can improve the GENMASK() for better code generation.) find_next_bit()
> itself is 41 instructions.

...

> + if (SMALL_CONST(size - 1)) {
> + unsigned long val;
> +
> + if (unlikely(offset >= size))
> + return size;

> + val = *addr & GENMASK(size - 1, offset);

Yeah, GENMASK() basically for constant values or cases like (x,0). I think here
is something what has been done in BITMAP_FIRST/LAST_WORD_MASK will give better
results.

> + return val ? __ffs(val) : size;
> + }

--
With Best Regards,
Andy Shevchenko