[Bug tree-optimization/115337] New: wrong code with _BitInt() __builtin_stdc_first_leading_one() at -O2

[Bug tree-optimization/115337] New: wrong code with _BitInt() __builtin_stdc_first_leading_one() at -O2

[zsojka at seznam dot cz]

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

            Bug ID: 115337
           Summary: wrong code with _BitInt()
                    __builtin_stdc_first_leading_one() at -O2
           Product: gcc
           Version: 15.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zsojka at seznam dot cz
                CC: jakub at gcc dot gnu.org
  Target Milestone: ---
              Host: x86_64-pc-linux-gnu
            Target: x86_64-pc-linux-gnu

Created attachment 58338
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58338&action=edit
reduced testcase

Output:
$ x86_64-pc-linux-gnu-gcc -O2 testcase.c
$ ./a.out 
Aborted


$ x86_64-pc-linux-gnu-gcc -v
Using built-in specs.
COLLECT_GCC=/repo/gcc-trunk/binary-latest-amd64/bin/x86_64-pc-linux-gnu-gcc
COLLECT_LTO_WRAPPER=/repo/gcc-trunk/binary-trunk-r15-929-20240530161758-g46d931b3dd3-checking-yes-rtl-df-extra-nobootstrap-amd64/bin/../libexec/gcc/x86_64-pc-linux-gnu/15.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /repo/gcc-trunk//configure --enable-languages=c,c++
--enable-valgrind-annotations --disable-nls --enable-checking=yes,rtl,df,extra
--disable-bootstrap --with-cloog --with-ppl --with-isl
--build=x86_64-pc-linux-gnu --host=x86_64-pc-linux-gnu
--target=x86_64-pc-linux-gnu --with-ld=/usr/bin/x86_64-pc-linux-gnu-ld
--with-as=/usr/bin/x86_64-pc-linux-gnu-as --enable-libsanitizer
--disable-libstdcxx-pch
--prefix=/repo/gcc-trunk//binary-trunk-r15-929-20240530161758-g46d931b3dd3-checking-yes-rtl-df-extra-nobootstrap-amd64
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 15.0.0 20240530 (experimental) (GCC)

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one() at -O2

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |pinskia at gcc dot gnu.org
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2024-06-04

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.

  # RANGE [irange] int [0, +INF]
  _1 = .CLZ (_2, -1);

Is WRONG in evrp. The range is [-1, +INF].

Reduced testcase:
```
[[gnu::noinline]]
int
foo (unsigned _BitInt (129) z)
{
  int t = __builtin_stdc_first_leading_one (z);
  return t == 0;
}

int main()
{
  if (! foo(0))
    __builtin_abort();
}
```

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Looks like the code in `cfn_clz::fold_range` in gimple-range-op.cc assume that
the return value for defining of 0 should only be positive.

`cfn_ctz::fold_range` has a similar issue too.

As a seperate note I notice:
```
// Implement range operator for CFN_BUILT_IN_POPCOUNT.
class cfn_popcount : public cfn_ffs

```
That seems wrong, popcount is not related to ffs (ffs is more related to
clz/ctz).

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
cfn_clz::fold_range is actually correct (but given the use of -1 second
argument perhaps could special case that case too).
What is wrong is tree_call_nonnegative_warnv_p.

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[jakub at gcc dot gnu.org]

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

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

Untested fix.

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 58340
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58340&action=edit
gcc15-pr115337-2.patch

Fixes for some formatting issues I found during the debugging.

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 58341
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58341&action=edit
gcc15-pr115337-3.patch

Improve ranger handling of .CLZ (x, -1).  As the stdbit.h builtins now use
that value, it is worth special casing it in the CLZ handling, so that we get
e.g. [-1, 128] range rather than VARYING.

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[jakub at gcc dot gnu.org]

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 58342
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58342&action=edit
gcc15-pr115337-4.patch

And finally, I think tree_call_expr_nonzero can handle CTZ the same as CLZ now.

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from GCC 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:b82a816000791e7a286c7836b3a473ec0e2a577b

commit r15-1011-gb82a816000791e7a286c7836b3a473ec0e2a577b
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 15:49:41 2024 +0200

    fold-const: Fix up CLZ handling in tree_call_nonnegative_warnv_p [PR115337]

    The function currently incorrectly assumes all the __builtin_clz* and .CLZ
    calls have non-negative result.  That is the case of the former which is UB
    on zero and has [0, prec-1] return value otherwise, and is the case of the
    single argument .CLZ as well (again, UB on zero), but for two argument
    .CLZ is the case only if the second argument is also nonnegative (or if we
    know the argument can't be zero, but let's do that just in the ranger
IMHO).

    The following patch does that.

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/115337
            * fold-const.cc (tree_call_nonnegative_warnv_p) <CASE_CFN_CLZ>:
            If arg1 is non-NULL, RECURSE on it, otherwise return true.

            * gcc.dg/bitint-106.c: New test.

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from GCC 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:181861b072ff1ef650c1a9d0290a4a672b9e747c

commit r15-1013-g181861b072ff1ef650c1a9d0290a4a672b9e747c
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 15:52:09 2024 +0200

    fold-const: Handle CTZ like CLZ in tree_call_nonnegative_warnv_p [PR115337]

    I think we can handle CTZ exactly like CLZ in
tree_call_nonnegative_warnv_p.
    Like CLZ, if it is UB at zero, the result range is [0, prec-1] and if it is
    well defined at zero, the second argument provides the value at zero.

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/115337
            * fold-const.cc (tree_call_nonnegative_warnv_p): Handle
            CASE_CFN_CTZ like CASE_CFN_CLZ.

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from GCC 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:591d30c5c97e757f63ce0d99ae9a3dbe8c75a50a

commit r15-1014-g591d30c5c97e757f63ce0d99ae9a3dbe8c75a50a
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 16:16:49 2024 +0200

    ranger: Improve CLZ fold_range [PR115337]

    cfn_ctz::fold_range includes special cases for the case where .CTZ has
    two arguments and so is well defined at zero, and the second argument is
    equal to prec or -1, but cfn_clz::fold_range does that only for the prec
    case.  -1 is fairly common as well though, because the <stdbit.h> builtins
    do use it now, so I think it is worth special casing that.
    If we don't know anything about the argument, the difference for
    .CLZ (arg, -1) is that previously the result was varying, now it will be
    [-1, prec-1].  If we knew arg can't be zero, it used to be optimized before
    as well into e.g. [0, prec-1] or similar.

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/115337
            * gimple-range-op.cc (cfn_clz::fold_range): For
            m_gimple_call_internal_p handle as a special case also second
argument
            of -1 next to prec.

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-14 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:a88e13bd7e0f50011e7f7f6e05c6f5e2a031143c

commit r14-10280-ga88e13bd7e0f50011e7f7f6e05c6f5e2a031143c
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 15:49:41 2024 +0200

    fold-const: Fix up CLZ handling in tree_call_nonnegative_warnv_p [PR115337]

    The function currently incorrectly assumes all the __builtin_clz* and .CLZ
    calls have non-negative result.  That is the case of the former which is UB
    on zero and has [0, prec-1] return value otherwise, and is the case of the
    single argument .CLZ as well (again, UB on zero), but for two argument
    .CLZ is the case only if the second argument is also nonnegative (or if we
    know the argument can't be zero, but let's do that just in the ranger
IMHO).

    The following patch does that.

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/115337
            * fold-const.cc (tree_call_nonnegative_warnv_p) <CASE_CFN_CLZ>:
            If arg1 is non-NULL, RECURSE on it, otherwise return true.

            * gcc.dg/bitint-106.c: New test.

    (cherry picked from commit b82a816000791e7a286c7836b3a473ec0e2a577b)

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[jakub at gcc dot gnu.org]

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

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Should be fixed now.
I think we want to backport the fold-const.cc first patch to older branches
too, but it will be different there.

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
.

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[cvs-commit at gcc dot gnu.org]

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

--- Comment #14 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:865d60ab4edbdb10d13000af81f9168fd3816a86

commit r13-8837-g865d60ab4edbdb10d13000af81f9168fd3816a86
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 15:49:41 2024 +0200

    fold-const: Fix up CLZ handling in tree_call_nonnegative_warnv_p [PR115337]

    The function currently incorrectly assumes all the __builtin_clz* and .CLZ
    calls have non-negative result.  That is the case of the former which is UB
    on zero and has [0, prec-1] return value otherwise, and is the case of the
    single argument .CLZ as well (again, UB on zero), but for two argument
    .CLZ is the case only if the second argument is also nonnegative (or if we
    know the argument can't be zero, but let's do that just in the ranger
IMHO).

    The following patch does that.

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/115337
            * fold-const.cc (tree_call_nonnegative_warnv_p) <CASE_CFN_CLZ>:
            If fn is CFN_CLZ, use CLZ_DEFINED_VALUE_AT.

    (cherry picked from commit b82a816000791e7a286c7836b3a473ec0e2a577b)

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[cvs-commit at gcc dot gnu.org]

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

--- Comment #15 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:b065824e30e9168d33b56039e436c4b09078e260

commit r12-10533-gb065824e30e9168d33b56039e436c4b09078e260
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 15:49:41 2024 +0200

    fold-const: Fix up CLZ handling in tree_call_nonnegative_warnv_p [PR115337]

    The function currently incorrectly assumes all the __builtin_clz* and .CLZ
    calls have non-negative result.  That is the case of the former which is UB
    on zero and has [0, prec-1] return value otherwise, and is the case of the
    single argument .CLZ as well (again, UB on zero), but for two argument
    .CLZ is the case only if the second argument is also nonnegative (or if we
    know the argument can't be zero, but let's do that just in the ranger
IMHO).

    The following patch does that.

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/115337
            * fold-const.cc (tree_call_nonnegative_warnv_p) <CASE_CFN_CLZ>:
            If fn is CFN_CLZ, use CLZ_DEFINED_VALUE_AT.

    (cherry picked from commit b82a816000791e7a286c7836b3a473ec0e2a577b)

[Bug tree-optimization/115337] wrong code with _BitInt() __builtin_stdc_first_leading_one/__builtin_clzg (with -1 as second arg) at -O2

[cvs-commit at gcc dot gnu.org]

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

--- Comment #16 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:b724525c9779bbf93c4905dc3d54296f5e39e607

commit r11-11514-gb724525c9779bbf93c4905dc3d54296f5e39e607
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jun 4 15:49:41 2024 +0200

    fold-const: Fix up CLZ handling in tree_call_nonnegative_warnv_p [PR115337]

    The function currently incorrectly assumes all the __builtin_clz* and .CLZ
    calls have non-negative result.  That is the case of the former which is UB
    on zero and has [0, prec-1] return value otherwise, and is the case of the
    single argument .CLZ as well (again, UB on zero), but for two argument
    .CLZ is the case only if the second argument is also nonnegative (or if we
    know the argument can't be zero, but let's do that just in the ranger
IMHO).

    The following patch does that.

    2024-06-04  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/115337
            * fold-const.c (tree_call_nonnegative_warnv_p) <CASE_CFN_CLZ>:
            If fn is CFN_CLZ, use CLZ_DEFINED_VALUE_AT.

    (cherry picked from commit b82a816000791e7a286c7836b3a473ec0e2a577b)