Re: [PATCH] arm64: enable GENERIC_FIND_FIRST_BIT

[Alexander Lobakin]

From: Yury Norov <yury.norov@xxxxxxxxx>
Date: Wed, 24 Feb 2021 07:44:16 -0800

> On Wed, Feb 24, 2021 at 11:52:55AM +0000, Alexander Lobakin wrote:
> > From: Yury Norov <yury.norov@xxxxxxxxx>
> > Date: Sat, 5 Dec 2020 08:54:06 -0800
> >
> > Hi,
> >
> > > ARM64 doesn't implement find_first_{zero}_bit in arch code and doesn't
> > > enable it in config. It leads to using find_next_bit() which is less
> > > efficient:
> > >
> > > 0000000000000000 <find_first_bit>:
> > >    0:	aa0003e4 	mov	x4, x0
> > >    4:	aa0103e0 	mov	x0, x1
> > >    8:	b4000181 	cbz	x1, 38 <find_first_bit+0x38>
> > >    c:	f9400083 	ldr	x3, [x4]
> > >   10:	d2800802 	mov	x2, #0x40                  	// #64
> > >   14:	91002084 	add	x4, x4, #0x8
> > >   18:	b40000c3 	cbz	x3, 30 <find_first_bit+0x30>
> > >   1c:	14000008 	b	3c <find_first_bit+0x3c>
> > >   20:	f8408483 	ldr	x3, [x4], #8
> > >   24:	91010045 	add	x5, x2, #0x40
> > >   28:	b50000c3 	cbnz	x3, 40 <find_first_bit+0x40>
> > >   2c:	aa0503e2 	mov	x2, x5
> > >   30:	eb02001f 	cmp	x0, x2
> > >   34:	54ffff68 	b.hi	20 <find_first_bit+0x20>  // b.pmore
> > >   38:	d65f03c0 	ret
> > >   3c:	d2800002 	mov	x2, #0x0                   	// #0
> > >   40:	dac00063 	rbit	x3, x3
> > >   44:	dac01063 	clz	x3, x3
> > >   48:	8b020062 	add	x2, x3, x2
> > >   4c:	eb02001f 	cmp	x0, x2
> > >   50:	9a829000 	csel	x0, x0, x2, ls  // ls = plast
> > >   54:	d65f03c0 	ret
> > >
> > >   ...
> > >
> > > 0000000000000118 <_find_next_bit.constprop.1>:
> > >  118:	eb02007f 	cmp	x3, x2
> > >  11c:	540002e2 	b.cs	178 <_find_next_bit.constprop.1+0x60>  // b.hs, b.nlast
> > >  120:	d346fc66 	lsr	x6, x3, #6
> > >  124:	f8667805 	ldr	x5, [x0, x6, lsl #3]
> > >  128:	b4000061 	cbz	x1, 134 <_find_next_bit.constprop.1+0x1c>
> > >  12c:	f8667826 	ldr	x6, [x1, x6, lsl #3]
> > >  130:	8a0600a5 	and	x5, x5, x6
> > >  134:	ca0400a6 	eor	x6, x5, x4
> > >  138:	92800005 	mov	x5, #0xffffffffffffffff    	// #-1
> > >  13c:	9ac320a5 	lsl	x5, x5, x3
> > >  140:	927ae463 	and	x3, x3, #0xffffffffffffffc0
> > >  144:	ea0600a5 	ands	x5, x5, x6
> > >  148:	54000120 	b.eq	16c <_find_next_bit.constprop.1+0x54>  // b.none
> > >  14c:	1400000e 	b	184 <_find_next_bit.constprop.1+0x6c>
> > >  150:	d346fc66 	lsr	x6, x3, #6
> > >  154:	f8667805 	ldr	x5, [x0, x6, lsl #3]
> > >  158:	b4000061 	cbz	x1, 164 <_find_next_bit.constprop.1+0x4c>
> > >  15c:	f8667826 	ldr	x6, [x1, x6, lsl #3]
> > >  160:	8a0600a5 	and	x5, x5, x6
> > >  164:	eb05009f 	cmp	x4, x5
> > >  168:	540000c1 	b.ne	180 <_find_next_bit.constprop.1+0x68>  // b.any
> > >  16c:	91010063 	add	x3, x3, #0x40
> > >  170:	eb03005f 	cmp	x2, x3
> > >  174:	54fffee8 	b.hi	150 <_find_next_bit.constprop.1+0x38>  // b.pmore
> > >  178:	aa0203e0 	mov	x0, x2
> > >  17c:	d65f03c0 	ret
> > >  180:	ca050085 	eor	x5, x4, x5
> > >  184:	dac000a5 	rbit	x5, x5
> > >  188:	dac010a5 	clz	x5, x5
> > >  18c:	8b0300a3 	add	x3, x5, x3
> > >  190:	eb03005f 	cmp	x2, x3
> > >  194:	9a839042 	csel	x2, x2, x3, ls  // ls = plast
> > >  198:	aa0203e0 	mov	x0, x2
> > >  19c:	d65f03c0 	ret
> > >
> > >  ...
> > >
> > > 0000000000000238 <find_next_bit>:
> > >  238:	a9bf7bfd 	stp	x29, x30, [sp, #-16]!
> > >  23c:	aa0203e3 	mov	x3, x2
> > >  240:	d2800004 	mov	x4, #0x0                   	// #0
> > >  244:	aa0103e2 	mov	x2, x1
> > >  248:	910003fd 	mov	x29, sp
> > >  24c:	d2800001 	mov	x1, #0x0                   	// #0
> > >  250:	97ffffb2 	bl	118 <_find_next_bit.constprop.1>
> > >  254:	a8c17bfd 	ldp	x29, x30, [sp], #16
> > >  258:	d65f03c0 	ret
> > >
> > > Enabling this functions would also benefit for_each_{set,clear}_bit().
> > > Would it make sense to enable this config for all such architectures by
> > > default?
> >
> > I confirm that GENERIC_FIND_FIRST_BIT also produces more optimized and
> > fast code on MIPS (32 R2) where there is also no architecture-specific
> > bitsearching routines.
> > So, if it's okay for other folks, I'd suggest to go for it and enable
> > for all similar arches.
>
> As far as I understand the idea of GENERIC_FIND_FIRST_BIT=n, it's
> intended to save some space in .text. But in fact it bloats the
> kernel:
>
>         yury:linux$ scripts/bloat-o-meter vmlinux vmlinux.ffb
>         add/remove: 4/1 grow/shrink: 19/251 up/down: 564/-1692 (-1128)
>         ...

Same for MIPS, enabling GENERIC_FIND_FIRST_BIT saves a bunch of .text
memory despite that it introduces new entries.

> For the next cycle, I'm going to submit a patch that removes the
> GENERIC_FIND_FIRST_BIT completely and forces all architectures to
> use find_first{_zero}_bit()

I like that idea. I'm almost sure there'll be no arch that benefits
from CONFIG_GENERIC_FIND_FIRST_BIT=n (and has no arch-optimized
versions).

> > (otherwise, I'll publish a separate entry for mips-next after 5.12-rc1
> >  release and mention you in "Suggested-by:")
>
> I think it worth to enable GENERIC_FIND_FIRST_BIT for mips and arm now
> and see how it works for people. If there'll be no complains I'll remove
> the config entirely. I'm OK if you submit the patch for mips now, or we
> can make a series and submit together. Works either way.

Lez make a series and see how it goes. I'll send you MIPS part soon.

Al