[Bug tree-optimization/102134] New: [12 Regression] wrong code at -O1

[Bug tree-optimization/102134] New: [12 Regression] wrong code at -O1

[zsojka at seznam dot cz]

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

            Bug ID: 102134
           Summary: [12 Regression] wrong code at -O1
           Product: gcc
           Version: 12.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
  Target Milestone: ---
              Host: x86_64-pc-linux-gnu

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

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

$ x86_64-pc-linux-gnu-gcc -v
Using built-in specs.
COLLECT_GCC=/repo/gcc-trunk/binary-latest/bin/x86_64-pc-linux-gnu-gcc
COLLECT_LTO_WRAPPER=/repo/gcc-trunk/binary-trunk-r12-3224-20210830105821-gd73c44800b5-checking-yes-rtl-df-extra-amd64/bin/../libexec/gcc/x86_64-pc-linux-gnu/12.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
--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 --disable-libstdcxx-pch
--prefix=/repo/gcc-trunk//binary-trunk-r12-3224-20210830105821-gd73c44800b5-checking-yes-rtl-df-extra-amd64
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.0.0 20210830 (experimental) (GCC)

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[pinskia at gcc dot gnu.org]

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

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

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

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
                 CC|                            |jakub at gcc dot gnu.org
           Priority|P3                          |P1
   Last reconfirmed|                            |2021-08-30

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r12-3164-gb2ef23239f245871e9b35b902391f2e94a041627

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Visiting statement:
Visiting statement:
b_13 = b_12(D) * b_12(D);
which is likely CONSTANT
Lattice value changed to CONSTANT 0x0
(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd).
 Adding SSA edges to worklist.
marking stmt to be not simulated again
...

_2 = _1 & 63;
which is likely CONSTANT
Lattice value changed to CONSTANT 0x0 (0x3f).  Adding SSA edges to worklist.
marking stmt to be not simulated again

Visiting statement:
_3 = b_13 >> _2;
which is likely CONSTANT
Lattice value changed to CONSTANT 0.  Adding SSA edges to worklist.
marking stmt to be not simulated again

In GCC 11 it was:
Visiting statement:
_2 = _1 & 63;
which is likely CONSTANT
Lattice value changed to CONSTANT 0x0 (0x3f).  Adding SSA edges to worklist.
marking stmt to be not simulated again

Visiting statement:
_3 = b_13 >> _2;
which is likely CONSTANT
Lattice value changed to VARYING.  Adding SSA edges to worklist.

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
This is triggering the:
          else if (!wi::neg_p (r1val | r1mask, sgn))
            {
              /* Logical right shift, or zero sign bit.  */
              widest_int arg = r1val | r1mask;
              int lzcount = wi::clz (arg);
              lzcount -= wi::get_precision (arg) - width;
              widest_int tmp = wi::mask <widest_int> (width, false);
              tmp = wi::lrshift (tmp, lzcount);
              tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
              *mask = wi::ext (tmp, width, sgn);
              *val = 0;
            }
sgn is UNSIGNED, so wi::neg_p is false even when r1val | r1mask is negative, so
wi::clz (arg) is 0, but wi::get_precision (arg) is 576 and width is 64, so
we end up with lzcount of -512 and I bet the code doesn't expect lzcount to be
negative.

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #3)
> This is triggering the:
>           else if (!wi::neg_p (r1val | r1mask, sgn))
>             {
>               /* Logical right shift, or zero sign bit.  */
>               widest_int arg = r1val | r1mask;
>               int lzcount = wi::clz (arg);
>               lzcount -= wi::get_precision (arg) - width;
>               widest_int tmp = wi::mask <widest_int> (width, false);
>               tmp = wi::lrshift (tmp, lzcount);
>               tmp = wi::lrshift (tmp, wi::bit_and_not (r2val, r2mask));
>               *mask = wi::ext (tmp, width, sgn);
>               *val = 0;
>             }
> sgn is UNSIGNED, so wi::neg_p is false even when r1val | r1mask is negative,
> so
> wi::clz (arg) is 0, but wi::get_precision (arg) is 576 and width is 64, so
> we end up with lzcount of -512 and I bet the code doesn't expect lzcount to
> be negative.

So perhaps either guard the subtraction on
  if (lzcount)
    lzcount -= wi::get_precision (arg) - width;
- when lzcount is 0, the sign bit is set and we shouldn't shift it right,
or do
  int lzcount;
  if (wi::neg_p (arg))
    lzcount = 0;
  else
    lzcount = wi::clz (arg) - (wi::get_precision (arg) - width);

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[jakub at gcc dot gnu.org]

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

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

I'll test this overnight.

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[roger at nextmovesoftware dot com]

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

Roger Sayle <roger at nextmovesoftware dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |roger at nextmovesoftware dot com

--- Comment #6 from Roger Sayle <roger at nextmovesoftware dot com> ---
Many thanks to Jakub for the speedy fix.  The diagnosis is quite right; I'd
assumed that if sgn is UNSIGNED, then arg would be zero extended.  Alas, that's
not quite how widest_int represents things internally, so Jakub's "if
(lzcount)" is, I think, the correct fix.  Sorry for the inconvenience.

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Roger Sayle from comment #6)
> Many thanks to Jakub for the speedy fix.  The diagnosis is quite right; I'd
> assumed that if sgn is UNSIGNED, then arg would be zero extended.  Alas,
> that's not quite how widest_int represents things internally, so Jakub's "if
> (lzcount)" is, I think, the correct fix.  Sorry for the inconvenience.

Yes, widest_ints are always signed (and sign-extended), you can view them as
arbitrary precision signed integers.

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[roger at nextmovesoftware dot com]

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

--- Comment #8 from Roger Sayle <roger at nextmovesoftware dot com> ---
It's even more complicated than that.  According to wi::clz, if the unsigned
value being stored has a precision that is a multiple of HOST_WIDE_INT it's
sign-extended, and for all other precisions they are zero extended.  The sign
bit is taken from the most significant word in the vector.

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 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:06ac981ffb3c0d6997f2e1c01ffaf6253b6a244f

commit r12-3246-g06ac981ffb3c0d6997f2e1c01ffaf6253b6a244f
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Aug 31 10:29:23 2021 +0200

    tree-ssa-ccp: Fix up bit_value_binop on RSHIFT_EXPR [PR102134]

    As mentioned in the PR, this hunk is guarded with !wi::neg_p (r1val |
r1mask, sgn)
    which means if sgn is UNSIGNED, it is always true, but r1val | r1mask in
    widest_int is still sign-extended.  That means wi::clz (arg) returns 0,
    wi::get_precision (arg) returns some very large number
    (WIDE_INT_MAX_PRECISION, on x86_64 576 bits) and width is 64, so we end up
    with lzcount of -512 where the code afterwards expects a non-negative
    lzcount.  For arg without the sign bit set the code works right, those
    numbers are zero extended and so wi::clz must return wi::get_precision
(arg) - width
    plus number of leading zero bits within the width precision.
    The patch fixes it by handling the sign-extension specially, either it
could
    be done through wi::neg_p (arg) check, but lzcount == 0 works identically.

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

            PR tree-optimization/102134
            * tree-ssa-ccp.c (bit_value_binop) <case RSHIFT_EXPR>: If sgn is
            UNSIGNED and r1val | r1mask has MSB set, ensure lzcount doesn't
            become negative.

            * gcc.c-torture/execute/pr102134.c: New test.

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Roger Sayle <sayle@gcc.gnu.org>:

https://gcc.gnu.org/g:74cb45e67d14624c3e2fafa99a8920d1866a5f0c

commit r12-3372-g74cb45e67d14624c3e2fafa99a8920d1866a5f0c
Author: Roger Sayle <roger@nextmovesoftware.com>
Date:   Mon Sep 6 22:48:53 2021 +0100

    Correct implementation of wi::clz

    As diagnosed with Jakub and Richard in the analysis of PR 102134, the
    current implementation of wi::clz has incorrect/inconsistent behaviour.
    As mentioned by Richard in comment #7, clz should (always) return zero
    for negative values, but the current implementation can only return 0
    when precision is a multiple of HOST_BITS_PER_WIDE_INT.  The fix is
    simply to reorder/shuffle the existing tests.

    2021-09-06  Roger Sayle  <roger@nextmovesoftware.com>

    gcc/ChangeLog
            * wide-int.cc (wi::clz): Reorder tests to ensure the result
            is zero for all negative values.

[Bug tree-optimization/102134] [12 Regression] wrong code at -O1

[jakub at gcc dot gnu.org]

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

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

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

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