[PATCH] x86_64: Optimize ffsll function code size.

[Adhemerval Zanella Netto]

On 26/07/23 13:59, Noah Goldstein via Libc-alpha wrote:
> On Wed, Jul 26, 2023 at 11:52 AM Sunil Pandey via Libc-alpha
> <libc-alpha@sourceware.org> wrote:
>>
>> On Wed, Jul 26, 2023 at 9:38 AM Richard Henderson <
>> richard.henderson@linaro.org> wrote:
>>
>>> On 7/26/23 09:05, Sunil K Pandey via Libc-alpha wrote:
>>>> Ffsll function size is 17 byte, this patch optimizes size to 16 byte.
>>>> Currently ffsll function randomly regress by ~20%, depending on how
>>>> code get aligned.
>>>>
>>>> This patch fixes ffsll function random performance regression.
>>>> ---
>>>>   sysdeps/x86_64/ffsll.c | 2 +-
>>>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>>>
>>>> diff --git a/sysdeps/x86_64/ffsll.c b/sysdeps/x86_64/ffsll.c
>>>> index a1c13d4906..dbded6f0a1 100644
>>>> --- a/sysdeps/x86_64/ffsll.c
>>>> +++ b/sysdeps/x86_64/ffsll.c
>>>> @@ -29,7 +29,7 @@ ffsll (long long int x)
>>>>     long long int tmp;
>>>>
>>>>     asm ("bsfq %2,%0\n"               /* Count low bits in X and store
>>> in %1.  */
>>>> -       "cmoveq %1,%0\n"              /* If number was zero, use -1 as
>>> result.  */
>>>> +       "cmove %k1,%k0\n"     /* If number was zero, use -1 as result.
>>> */
>>>
>>> This no longer produces -1, but 0xffffffff in cnt.  However, since the
>>> return type is
>>> 'int', cnt need not be 'long long int' either.  I'm not sure why tmp
>>> exists at all, since
>>> cnt is the only register modified.
>>>
>>
>> Here is the exact assembly produced with this change.
>> ./build-x86_64-linux/string/ffsll.o:     file format elf64-x86-64
>>
>>
>> Disassembly of section .text:
>>
>> 0000000000000000 <ffsll>:
>>    0: ba ff ff ff ff       mov    $0xffffffff,%edx
>>    5: 48 0f bc c7           bsf    %rdi,%rax
>>    9: 0f 44 c2             cmove  %edx,%eax
>>    c: 83 c0 01             add    $0x1,%eax
>>    f: c3                   ret
>>
> 
> FWIW it should be:
> ```
> 0000000000000000 <.text>:
>    0: b8 ff ff ff ff        mov    $0xffffffff,%eax
>    5: 48 0f bc c7          bsf    %rdi,%rax
>    9: ff c0                inc    %eax
> ```
> 
> And since its in inline asm no reason not to get that.

Can't we just use compiler builtins instead and remove a bunch of asm?
GCC already optimizes ffsl/ffsll to builtin if the architecture allows it,
so I think microptimizing it on libc.so using arch-specific is really not
ideal.

With gcc 13 and my patch [1] I see:

$ objdump -d ./string/ffsll.os

./string/ffsll.os:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <__ffsll>:
   0:   48 0f bc ff             bsf    %rdi,%rdi
   4:   48 c7 c0 ff ff ff ff    mov    $0xffffffffffffffff,%rax
   b:   48 0f 44 f8             cmove  %rax,%rdi
   f:   8d 47 01                lea    0x1(%rdi),%eax
  12:   c3                      ret


[1] https://patchwork.sourceware.org/project/glibc/patch/20230717143431.2075924-1-adhemerval.zanella@linaro.org/