[Bug middle-end/101973] New: subtraction of clz is not optimized

[Bug middle-end/101973] New: subtraction of clz is not optimized

[sven.koehler at gmail dot com]

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

            Bug ID: 101973
           Summary: subtraction of clz is not optimized
           Product: gcc
           Version: 11.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: sven.koehler at gmail dot com
  Target Milestone: ---

On Intel x86_64, the generated code for __builtin_clz(x) looks something like
this: clz(x) = 63 - bsr(x)

Since Intel does not seem to have a way to do 63-y in a single instruction, XOR
is used instead and the actual assembly code corresponds to clz(x) = 63 ^
bsr(x). Since bsr(x) is in the range 0 to 63, the XOR with 63 is equivalent to
63-y.

However, when we actually need the index of the most significant non-zero bit,
we have another 63-y, as in this function: 

int bsr(unsigned long x) {
    return sizeof(x)*8 - 1 - __builtin_clzl(x);
}


With -O3, GCC emits the following assembly code:

bsr:
        bsr     rdi, rdi
        mov     eax, 63
        xor     rdi, 63
        sub     eax, edi
        ret


The XOR with 63 and the subtraction from 63 cancel each other out in this
special case. LLVM/clang performs this optimization.

One might also consider the arbitrary case of z-clz(x) as a test case. On
Intel, this is equivalent to bsr(x)+(z-63).

[Bug middle-end/101973] subtraction of clz is not optimized

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This is fixed on the trunk.

[Bug middle-end/101973] subtraction of clz is not optimized

[sven.koehler at gmail dot com]

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

Sven <sven.koehler at gmail dot com> changed:

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

--- Comment #2 from Sven <sven.koehler at gmail dot com> ---
OK. Closing this myself.