Re: [PATCH] lib/clz_ctz.c: Fix __clzdi2() and __ctzdi2() for 32-bit kernels

[Nick Desaulniers]

On Fri, Aug 25, 2023 at 1:43 PM Linus Torvalds
<torvalds@xxxxxxxxxxxxxxxxxxxx> wrote:
>
> [ Unrelated to this patch, except it made me look, adding clang build
> people to cc ]
>
> On Fri, 25 Aug 2023 at 13:25, Linus Torvalds
> <torvalds@xxxxxxxxxxxxxxxxxxxx> wrote:
> >
> > On Fri, 25 Aug 2023 at 12:50, Helge Deller <deller@xxxxxx> wrote:
> > >
> > > This patch fixes the in-kernel functions __clzdi2() and __ctzdi2() [..]
> >
> > Applied,
>
> Bah. Still applied,  but actually building this (on 64-bit, so kind of
> pointless) I note that clang completely messes up this function on
> x86.
>
> Clang turns this:
>
>         return __ffs64(val);
>
> into this horror:
>
>         pushq   %rax
>         movq    %rdi, (%rsp)
>         #APP
>         rep
>         bsfq    (%rsp), %rax
>         #NO_APP
>         popq    %rcx
>
> which is just incredibly broken on so many levels. It *should* be a
> single instruction, like gcc does:
>
>         rep; bsf %rdi,%rax      # tmp87, word
>
> but clang decides that it really wants to put the argument on the
> stack, and apparently also wants to do that nonsensical stack
> alignment thing to make things even worse.
>
> We use this:
>
>   static __always_inline unsigned long variable__ffs(unsigned long word)
>   {
>         asm("rep; bsf %1,%0"
>                 : "=r" (word)
>                 : "rm" (word));
>         return word;
>   }
>
> for the definition, and it looks like clang royally just screws up
> here. Yes, "m" is _allowed_ in that input set, but it damn well
> shouldn't be used for something that is already in a register, since
> "r" is also allowed, and is the first choice.
>
> I think it's this clang bug:
>
>     https://github.com/llvm/llvm-project/issues/20571

^ yep, my comments at the end of that thread are the last time we've
had a chance to look into this.  Boy, it's been 9 months since the
last discussion of it.  I'm sorry for that.

The TL;DR of that thread is that when both "r" and "m" constraints are
present, LLVM is conservative and always chooses "m" because at that
point it's not able to express to later passes that "m" is still a
valid fallback if "r" was chosen.

Obviously "r" is preferable to "m" and we should fix that.  Seeing who
wants to roll up their sleeves and volunteer to understand LLVM's
register allocation code is like asking who wants to be the first to
jump into a black hole and see what happens.  I'm having a hard enough
time understanding the stack spilling code to better understand what
precisely exists in what stack slots in order to make progress on some
of our -Wframe-larger-than= warnings, but I need to suck it up and do
better.

This came up previously in our discussion about __builtin_ia32_readeflags_*.
https://lore.kernel.org/all/20211215211847.206208-1-morbo@xxxxxxxxxx/

>     https://github.com/llvm/llvm-project/issues/30873
>     https://github.com/llvm/llvm-project/issues/34837
>
> and it doesn't matter for *this* case (since I don't think this
> library function is ever used on x86), but it looks like a generic
> clang issue.
>
>                  Linus



-- 
Thanks,
~Nick Desaulniers