[Bug c/110243] New: Wrong code at -O3 on x86_64-linux-gnu

[Bug c/110243] New: Wrong code at -O3 on x86_64-linux-gnu

[shaohua.li at inf dot ethz.ch]

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

            Bug ID: 110243
           Summary: Wrong code at -O3 on x86_64-linux-gnu
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: shaohua.li at inf dot ethz.ch
  Target Milestone: ---

Since GCC-13, gcc at -O3 produces wrong code.

Compiler explorer: https://godbolt.org/z/jnroxhddY

$ cat a.c
#define X 1100000000
char a;
long b = X;
int c[9][1];
unsigned d;
static long *e = &b, *f = &b;
int g() {
  if (a && a <= '9')
    return '0';
  if (a)
    return 10;
  return -1;
}
int main() {
  d = 0;
  for (; (int)*f -(X-1) + d < 9; d++)
    c[g() + (int)*f + ((int)*e - X) -(X-1) + d]
     [0] = 0;
}
$
$ gcc-tk -O3 a.c &&./a.out
Segmentation fault
$
$ gcc-tk -O0 a.c &&./a.out
$
$ gcc-tk -fsanitize=address,undefined a.c &&./a.out
$
$ gcc-tk -v
Using built-in specs.
COLLECT_GCC=gcc-tk
COLLECT_LTO_WRAPPER=/zdata/shaoli/compilers/ccbuilder-compilers/gcc-bf470895905e9152424076d1630a9d2c60de023b/libexec/gcc/x86_64-pc-linux-gnu/14.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../configure --disable-multilib --disable-bootstrap
--enable-languages=c,c++
--prefix=/zdata/shaoli/compilers/ccbuilder-compilers/gcc-bf470895905e9152424076d1630a9d2c60de023b
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 14.0.0 20230612 (experimental) (GCC)
$

[Bug tree-optimization/110243] [13/14 Regression] Wrong code at -O3 on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Wrong code at -O3 on        |[13/14 Regression] Wrong
                   |x86_64-linux-gnu            |code at -O3 on
                   |                            |x86_64-linux-gnu
      Known to fail|                            |13.1.0
   Last reconfirmed|                            |2023-06-13
   Target Milestone|---                         |13.2
             Status|UNCONFIRMED                 |NEW
          Component|middle-end                  |tree-optimization
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed. I don't know if this is an IV-OPTs issue but turning off iv-opts
fixes the issue ...

[Bug tree-optimization/110243] [13/14 Regression] Wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug tree-optimization/110243] [13/14 Regression] Wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
   <bb 26> [local count: 5636687]:
+  _141 = (int) _5;
+  _144 = _141 * 2;
+  ivtmp.22_136 = (unsigned int) _144;
...

   <bb 19> [local count: 51242611]:
-  # d.7_1 = PHI <0(26), _48(23)>
+  # ivtmp.22_17 = PHI <ivtmp.22_136(26), ivtmp.22_16(23)>
...
-  _45 = d.7_1 + 3194967297;
-  _46 = _44 + _45;
+  _46 = ivtmp.22_17 + 2094967296;

that signed multiplication by two smells like it could be an issue.

Keeping IVOPTs enabled works when disabling the followup DOM and VRP passes
who eventually produce range info.

IV struct:
  SSA_NAME:     _46
  Type: unsigned int
  Base: (unsigned int) (((int) _5 + -1) + ((int) _5 + -1100000000)) +
3194967297
  Step: 1
  Biv:  N

Candidate 5:
  Var befor: ivtmp.22
  Var after: ivtmp.22
  Incr POS: before exit test
  IV struct:
    Type:       unsigned int
    Base:       (unsigned int) ((int) _5 * 2) 
    Step:       1
    Biv:        N
    Overflowness wrto loop niter:       Overflow

and indeed (int) _5 * 2 will overflow as _5 is 'X'.

This multiplication is built via

#0  0x00000000010eaa2a in fold_build2_loc (loc=0, code=MULT_EXPR, 
    type=<integer_type 0x7ffff6e515e8 int>, op0=<nop_expr 0x7ffff6c303a0>, 
    op1=<integer_cst 0x7ffff6e554e0>)
    at /home/rguenther/src/trunk/gcc/fold-const.cc:13781
#1  0x0000000002e41e72 in generic_simplify_PLUS_EXPR (loc=0, code=PLUS_EXPR, 
    type=<integer_type 0x7ffff6e515e8 int>, _p0=<nop_expr 0x7ffff6c303a0>, 
    _p1=<nop_expr 0x7ffff6c303c0>) at generic-match-2.cc:4924
#2  0x0000000001edc488 in generic_simplify (loc=0, code=PLUS_EXPR, 
    type=<integer_type 0x7ffff6e515e8 int>, _p0=<nop_expr 0x7ffff6c303a0>, 
    _p1=<nop_expr 0x7ffff6c303c0>) at generic-match-5.cc:8173
#3  0x00000000010dbf1a in fold_binary_loc (loc=0, code=PLUS_EXPR, 
    type=<integer_type 0x7ffff6e515e8 int>, op0=<nop_expr 0x7ffff6c303a0>, 
    op1=<nop_expr 0x7ffff6c303c0>)
    at /home/rguenther/src/trunk/gcc/fold-const.cc:10889
#4  0x00000000010eaa03 in fold_build2_loc (loc=0, code=PLUS_EXPR, 
    type=<integer_type 0x7ffff6e515e8 int>, op0=<nop_expr 0x7ffff6c303a0>, 
    op1=<nop_expr 0x7ffff6c303c0>)
    at /home/rguenther/src/trunk/gcc/fold-const.cc:13779
#5  0x000000000180266d in strip_offset_1 (expr=<plus_expr 0x7ffff6c2ea78>, 
    inside_addr=false, top_compref=false, offset=0x7fffffffd628)
    at /home/rguenther/src/trunk/gcc/tree-ssa-loop-ivopts.cc:2822
#6  0x00000000018024f7 in strip_offset_1 (expr=<plus_expr 0x7ffff6c2eac8>, 
    inside_addr=false, top_compref=false, offset=0x7fffffffd6d0)
    at /home/rguenther/src/trunk/gcc/tree-ssa-loop-ivopts.cc:2804
#7  0x0000000001802e70 in strip_offset (expr=<plus_expr 0x7ffff6c2eac8>, 
    offset=0x7fffffffd728)
    at /home/rguenther/src/trunk/gcc/tree-ssa-loop-ivopts.cc:2949
#8  0x0000000001804d7e in add_iv_candidate_for_use (data=0x7fffffffd990, 
    use=0x4207f60)
    at /home/rguenther/src/trunk/gcc/tree-ssa-loop-ivopts.cc:3566

where strip_offset simplifies (unsigned int) (((int) _5 + -1) + ((int) _5 +
-1100000000)) + 3194967297
to this expression and an offset.

I think IVOPTs strip_offset suffers from the same issues as tree-data-ref.cc
split_constant_offset did.  Using split_constant_offset instead does not
produce this candidate.  Instead we have

Candidate 4:
  Var befor: ivtmp.21
  Var after: ivtmp.21
  Incr POS: before exit test
  IV struct:
    Type:       unsigned int
    Base:       (unsigned int) (((int) _5 + -1) + ((int) _5 + -1100000000)) +
3194967297
    Step:       1
    Biv:        N
    Overflowness wrto loop niter:       Overflow
Candidate 5:
  Var befor: ivtmp.22
  Var after: ivtmp.22
  Incr POS: before exit test
  IV struct:
    Type:       unsigned int
    Base:       (unsigned int) _5 + 3194967298
    Step:       1
    Biv:        N
    Overflowness wrto loop niter:       Overflow

and

Selected IV set for loop 3 at t.c:16, 9 avg niters, 1 IVs:
Candidate 5:
  Var befor: ivtmp.22_17
  Var after: ivtmp.22_16
  Incr POS: before exit test
  IV struct:
    Type:       unsigned int
    Base:       (unsigned int) _5 + 3194967298
    Step:       1
    Biv:        N
    Overflowness wrto loop niter:       Overflow

[Bug tree-optimization/110243] [13/14 Regression] Wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I'm testing a fix.

[Bug tree-optimization/110243] [13/14 Regression] Wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
There's now a single strip_offset left in IVOPTs, the problematic one.  That
one
isn't trivial to convert to split_constant_offset since that only deals with
pointer or sizetype quantities in a way that's reasonable for this place.

There's the opportunity to generalize split_constant_offset to work on
other (unsigned) "base" types.  I think that's the most reasonable thing to
do.

[Bug tree-optimization/110243] [13/14 Regression] Wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.2                        |13.3

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 13.2 is being released, retargeting bugs to GCC 13.3.

[Bug tree-optimization/110243] [13/14 Regression] Wrong code at -O3 on x86_64-linux-gnu

[shaohua.li at inf dot ethz.ch]

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

--- Comment #6 from Shaohua Li <shaohua.li at inf dot ethz.ch> ---
I tried to bisect it and it was bisected to r13-3875-g9e11ceef165

[Bug tree-optimization/110243] [13/14 Regression] Wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Thanks.  I still need to work on the patch fixing IVOPTs, I think what I have
will not work in some corner cases (not exercised by the testsuite
unfortunately).

[Bug tree-optimization/110243] [13/14 Regression] Wrong code at -O3 on x86_64-linux-gnu since r13-3875-g9e11ceef165

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
See https://gcc.gnu.org/pipermail/gcc-patches/2023-June/621989.html for the
prototype patch.  I still think it might be too aggressive, an alternative I
didn't yet implement is turning everything in split_offset to unsigned arith
as IVOPTs does elsewhere anyway.

[Bug tree-optimization/110243] [13/14 Regression] Wrong code at -O3 on x86_64-linux-gnu since r13-3875-g9e11ceef165

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:44e7e4498c3cdc27e087ab80aa76dac41819702f

commit r14-4789-g44e7e4498c3cdc27e087ab80aa76dac41819702f
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Oct 20 14:08:46 2023 +0200

    tree-optimization/110243 - IVOPTs introducing undefined overflow

    The following addresses IVOPTs rewriting expressions in its
    strip_offset without caring for definedness of overflow.  Rather
    than the earlier attempt of just using the proper
    split_constant_offset from data-ref analysis the following adjusts
    IVOPTs helper trying to minimize changes from this fix, possibly
    easing backports.

            PR tree-optimization/110243
            PR tree-optimization/111336
            * tree-ssa-loop-ivopts.cc (strip_offset_1): Rewrite
            operations with undefined behavior on overflow to
            unsigned arithmetic.

            * gcc.dg/torture/pr110243.c: New testcase.
            * gcc.dg/torture/pr111336.c: Likewise.

[Bug tree-optimization/110243] [13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r13-3875-g9e11ceef165

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[13/14 Regression] Wrong    |[13 Regression] Wrong code
                   |code at -O3 on              |at -O3 on x86_64-linux-gnu
                   |x86_64-linux-gnu since      |since r13-3875-g9e11ceef165
                   |r13-3875-g9e11ceef165       |
      Known to work|                            |14.0

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.

[Bug tree-optimization/110243] [13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r13-3875-g9e11ceef165

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 111383 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/110243] [13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r13-3875-g9e11ceef165

[cvs-commit at gcc dot gnu.org]

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

--- Comment #12 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

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

commit r14-4791-ga1fc2cc0a8a8b97dbc3dc6715fd4f384d9204845
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Oct 20 15:52:09 2023 +0200

    tree-optimization/111383 - testcase for fixed PR

            PR tree-optimization/111383
            PR tree-optimization/110243
    gcc/testsuite/
            * gcc.dg/torture/pr111383.c: New testcase.

[Bug tree-optimization/110243] [12/13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r13-3875-g9e11ceef165

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.3                        |12.4
            Summary|[13 Regression] Wrong code  |[12/13 Regression] Wrong
                   |at -O3 on x86_64-linux-gnu  |code at -O3 on
                   |since r13-3875-g9e11ceef165 |x86_64-linux-gnu since
                   |                            |r13-3875-g9e11ceef165

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
PR111383 also affects the GCC 12 branch.

[Bug tree-optimization/110243] [12/13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r13-3875-g9e11ceef165

[rguenth at gcc dot gnu.org]

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

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 110233 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/110243] [12/13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r13-3875-g9e11ceef165

[rguenth at gcc dot gnu.org]

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

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 111365 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/110243] [12/13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r13-3875-g9e11ceef165

[rguenth at gcc dot gnu.org]

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

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Backporting to GCC 13 causes gcc.dg/tree-ssa/ldist-17.c to FAIL.