[Bug c/101950] New: __builtin_clrsb is never inlined

[Bug c/101950] New: __builtin_clrsb is never inlined

[sven.koehler at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101950

            Bug ID: 101950
           Summary: __builtin_clrsb is never inlined
           Product: gcc
           Version: 11.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: sven.koehler at gmail dot com
  Target Milestone: ---

With gcc 11.1 on ARM 32-bit and Intel, I don't see that __builtin_clrsb is
inlined. On AARCH64 it is inlined and the cls instruction is used, as expected.
I use the C-code below to compare the assembly generated. For ARM, I use -O3
-mcpu=cortex-a53 -marm and for Intel I just use -O3.


On ARM 32-bit, clrsb1 seems to be the fastest code (see below for the assembly
code) since clz handles zero correctly. On Intel, bsr does not handle zero,
hence the workaround of setting the lsb before calling __builtin_clzl (see
below for the assembly code). On Intel, clrsb1 is slighly longer and uses a
jump to handle the zero case. clang apparently uses variant clrsb1 on ARM and
Intel, and it's inlined on both architectures when using -O3.





#define SHIFT (sizeof(x)*8-1)

int clz(unsigned long x) {
    if (x == 0) {
        return sizeof(x)*8;
    }
    return __builtin_clzl(x);
}

int clsb(long x) {
    return clz(x ^ (x >> SHIFT));
}

int clrsb1(long x) {
    return clsb(x)-1;
}

int clrsb2(long x) {
    x = ((x << 1) ^ (x >> SHIFT)) | 1;
    return __builtin_clzl(x);
}

int clrsb3(long x) {
    return __builtin_clrsbl(x);
}



on ARM 32-bit:
clrsb1:
        eor     x0, x0, x0, asr 63
        clz     x0, x0
        sub     w0, w0, #1
        ret

on Intel:
clrsb2:
        lea     rax, [rdi+rdi]
        sar     rdi, 63
        xor     rax, rdi
        or      rax, 1
        bsr     rax, rax
        xor     eax, 63
        ret

[Bug c/101950] __builtin_clrsb is never inlined

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101950

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2021-08-17

[Bug middle-end/101950] __builtin_clrsb is never inlined

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101950

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 51318
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51318&action=edit
gcc12-pr101950.patch

Untested fix.

[Bug middle-end/101950] __builtin_clrsb is never inlined

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101950

--- Comment #2 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:301dc6011cbceb7ea9debd86aaec7cadb37213c8

commit r12-3017-g301dc6011cbceb7ea9debd86aaec7cadb37213c8
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Aug 19 11:00:27 2021 +0200

    expand: Add new clrsb fallback expansion [PR101950]

    As suggested in the PR, the following patch adds two new clrsb
    expansion possibilities if target doesn't have clrsb_optab for the
    requested nor wider modes, but does have clz_optab for the requested
    mode.
    One expansion is
    clrsb (op0)
    expands as
    clz (op0 ^ (((stype)op0) >> (prec-1))) - 1
    which is usable if CLZ_DEFINED_VALUE_AT_ZERO is 2 with value
    of prec, because the clz argument can be 0 and clrsb should give
    prec-1 in that case.
    The other expansion is
    clz (((op0 << 1) ^ (((stype)op0) >> (prec-1))) | 1)
    where the clz argument is never 0, but it is one operation longer.
    E.g. on x86_64-linux with -O2 -mno-lzcnt, this results for
    int foo (int x) { return __builtin_clrsb (x); }
    in
    -       subq    $8, %rsp
    -       movslq  %edi, %rdi
    -       call    __clrsbdi2
    -       addq    $8, %rsp
    -       subl    $32, %eax
    +       leal    (%rdi,%rdi), %eax
    +       sarl    $31, %edi
    +       xorl    %edi, %eax
    +       orl     $1, %eax
    +       bsrl    %eax, %eax
    +       xorl    $31, %eax
    and with -O2 -mlzcnt:
    +       movl    %edi, %eax
    +       sarl    $31, %eax
    +       xorl    %edi, %eax
    +       lzcntl  %eax, %eax
    +       subl    $1, %eax
    On armv7hl-linux-gnueabi with -O2:
    -       push    {r4, lr}
    -       bl      __clrsbsi2
    -       pop     {r4, pc}
    +       @ link register save eliminated.
    +       eor     r0, r0, r0, asr #31
    +       clz     r0, r0
    +       sub     r0, r0, #1
    +       bx      lr
    As it (at least usually) will make code larger, it is
    disabled for -Os or cold instructions.

    2021-08-19  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/101950
            * optabs.c (expand_clrsb_using_clz): New function.
            (expand_unop): Use it as another clrsb expansion fallback.

            * gcc.target/i386/pr101950-1.c: New test.
            * gcc.target/i386/pr101950-2.c: New test.

[Bug middle-end/101950] __builtin_clrsb is never inlined

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101950

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed, thanks for the suggestion.

[Bug middle-end/101950] __builtin_clrsb is never inlined

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101950

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.0