[Bug tree-optimization/94801] New: Failure to optimize narrowed __builtin_clz

[Bug tree-optimization/94801] New: Failure to optimize narrowed __builtin_clz

[gabravier at gmail dot com]

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

            Bug ID: 94801
           Summary: Failure to optimize narrowed __builtin_clz
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

int f(int a)
{
    return __builtin_clz(a) >> 5;
}

Can be optimized to `return 0;`. This transformation is done by LLVM, but not
by GCC.

Comparison here : https://godbolt.org/z/jhqQ2u

[Bug tree-optimization/94801] Failure to optimize narrowed __builtin_clz

[glisse at gcc dot gnu.org]

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

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Gcc considers that clz might return 32 on some platforms, it does not currently
use target-specific information to restrict the range of clz output.

[Bug tree-optimization/94801] Failure to optimize narrowed __builtin_clz

[glisse at gcc dot gnu.org]

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

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
  if(a==0)__builtin_unreachable();

lets gcc optimize the code.

[Bug tree-optimization/94801] Failure to optimize narrowed __builtin_clz

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Yeah.  Or using >> 6.

[Bug tree-optimization/94801] Failure to optimize narrowed __builtin_clz

[gabravier at gmail dot com]

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

--- Comment #4 from Gabriel Ravier <gabravier at gmail dot com> ---
Isn't `__builtin_clz(0)` undefined ?

[Bug tree-optimization/94801] Failure to optimize narrowed __builtin_clz

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
In the source yes, but by the time the optimizer sees it on some targets x == 0
? 32 : __builtin_clz (x) could have been already optimized into just
__builtin_clz (x) depending on what the target macros say.
          /* __builtin_c[lt]z* return [0, prec-1], except for
             when the argument is 0, but that is undefined behavior.
             On many targets where the CLZ RTL or optab value is defined
             for 0 the value is prec, so include that in the range
             by default.  */

[Bug tree-optimization/94801] Failure to optimize narrowed __builtin_clz

[gabravier at gmail dot com]

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

--- Comment #6 from Gabriel Ravier <gabravier at gmail dot com> ---
*** Bug 95532 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/94801] Failure to optimize narrowed __builtin_clz

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 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:781634daea8cb788efb33994f4a19df76598542e

commit r11-3744-g781634daea8cb788efb33994f4a19df76598542e
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Fri Oct 9 10:19:16 2020 +0200

    vrp: Fix up gcc.target/aarch64/pr90838.c [PR97312, PR94801]

    > Perhaps another way out of this would be document and enforce that
    > __builtin_c[lt]z{,l,ll} etc calls are undefined at zero, but C[TL]Z ifn
    > calls are defined there based on *_DEFINED_VALUE_AT_ZERO (*) == 2

    The following patch implements that, i.e. __builtin_c?z* now take full
    advantage of them being UB at zero, while the ifns are well defined at zero
    if *_DEFINED_VALUE_AT_ZERO (*) == 2.  That is what fixes PR94801.

    Furthermore, to fix PR97312, if it is well defined at zero and the value at
    zero is prec, we don't lower the maximum unless the argument is known to be
    non-zero.
    For gimple-range.cc I guess we could improve it if needed e.g. by returning
    a [0,7][32,32] range for .CTZ of e.g. [0,137], but for now it (roughly)
    matches what vr-values.c does.

    2020-10-09  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/94801
            PR target/97312
            * vr-values.c (vr_values::extract_range_basic) <CASE_CFN_CLZ,
            CASE_CFN_CTZ>: When stmt is not an internal-fn call or
            C?Z_DEFINED_VALUE_AT_ZERO is not 2, assume argument is not zero
            and thus use [0, prec-1] range unless it can be further improved.
            For CTZ, don't update maxi from upper bound if it was previously
prec.
            * gimple-range.cc (gimple_ranger::range_of_builtin_call)
<CASE_CFN_CLZ,
            CASE_CFN_CTZ>: Likewise.

            * gcc.dg/tree-ssa/pr94801.c: New test.

[Bug tree-optimization/94801] Failure to optimize narrowed __builtin_clz

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed on the trunk now.

[Bug tree-optimization/94801] Failure to optimize narrowed __builtin_clz

[dragan.mladjenovic at syrmia dot com]

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

dragan.mladjenovic at syrmia dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dragan.mladjenovic at syrmia dot c
                   |                            |om

--- Comment #9 from dragan.mladjenovic at syrmia dot com ---
Note that the transformation that the clang does seems to be target specific,
so it won't trigger for example on Aarch64. It does so on x86 irrespective of
the availability of lzcnt instruction.