[Bug tree-optimization/106114] New: wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu

[Bug tree-optimization/106114] New: wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu

[zhendong.su at inf dot ethz.ch]

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

            Bug ID: 106114
           Summary: wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zhendong.su at inf dot ethz.ch
  Target Milestone: ---

This appears to be a recent regression from 12.*. 

[563] % gcctk -v
Using built-in specs.
COLLECT_GCC=gcctk
COLLECT_LTO_WRAPPER=/local/suz-local/software/local/gcc-trunk/libexec/gcc/x86_64-pc-linux-gnu/13.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-trunk/configure --disable-bootstrap
--prefix=/local/suz-local/software/local/gcc-trunk --enable-sanitizers
--enable-languages=c,c++ --disable-werror --enable-multilib --with-system-zlib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 13.0.0 20220628 (experimental) [master r13-1313-gf9764ea128c] (GCC) 
[564] % 
[564] % gcctk -O0 small.c; ./a.out
[565] % 
[565] % gcctk -O1 small.c
[566] % ./a.out
0
[567] % cat small.c
int printf(const char *, ...);
char a = 139, b;
int main() {
  char c = 173;
  b = a;
  while (c <= a || a < -117)
    c = printf("0\n");
  return 0;
}

[Bug tree-optimization/106114] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu

[zhendong.su at inf dot ethz.ch]

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

--- Comment #1 from Zhendong Su <zhendong.su at inf dot ethz.ch> ---
Compiler Explorer: https://godbolt.org/z/T38WEd376

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com,
                   |                            |marxin at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
            Summary|wrong code at -O1, -O2 and  |[13 Regression] wrong code
                   |-O3 on x86_64-linux-gnu     |at -O1, -O2 and -O3 on
                   |                            |x86_64-linux-gnu since
                   |                            |r13-1268-g8c99e307b20c502e
   Last reconfirmed|                            |2022-06-28

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r13-1268-g8c99e307b20c502e.

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[mpolacek at gcc dot gnu.org]

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

--- Comment #3 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
*** Bug 106115 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

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

--- Comment #4 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Another test (-O2):

int printf(const char *, ...);
int a, b = 1041281974;
unsigned short c;
int main()
{
  int d, e = b;
  b = ~-~a;
  a = c = -~b;
  if (c < 65529) {
    printf("%d\n", d);
    e = 0;
  }
  if (b)
    d = a;
  if (((e > 1041281974) && d) || e < 1041281974)
    printf("%d\n", c);
  return 0;
}

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |13.0
                 CC|                            |jakub at gcc dot gnu.org
   Target Milestone|---                         |13.0

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1
                 CC|                            |law at gcc dot gnu.org

--- Comment #5 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
I think this is fold_using_range getting confused with DOM changing the IL from
under it.

fold_using_range::relation_fold_and_or() is (incorrectly) folding the final
conditional as always true:

  <bb 2> [local count: 79134772]:
  a.0_1 = a;
  b = a.0_1;
  a.1_15 = a.0_1;
  _16 = a.0_1 < -117;
  _17 = a.0_1 >= -83;
  _18 = _16 | _17;
  if (_18 != 0)

But the IL on entry to DOM is actually:

  <bb 2> [local count: 79134772]:
  a.0_1 = a;
  b = a.0_1;
  a.1_15 = a;
  _16 = a.1_15 < -117;
  _17 = a.1_15 >= -83;
  _18 = _16 | _17;
  if (_18 != 0)

DOM replaced a.1_15=a with a.1_15=a.0_1:

Optimizing statement a.1_15 = a;
LKUP STMT a.1_15 = a with .MEM_7
FIND: a.0_1
  Replaced redundant expr 'a' with 'a.0_1'


...and then cproped the a.1_15 into the uses:

Optimizing statement _16 = a.1_15 < -117;
  Replaced 'a.1_15' with variable 'a.0_1'
Optimizing statement _17 = a.1_15 >= -83;
  Replaced 'a.1_15' with variable 'a.0_1'

By the time we get to the conditional, the ranger thinks it can fold the
conditional:

Optimizing statement if (_18 != 0)
  Relation adjustment: _16  and _17  combine to produce [irange] _Bool [1, 1]
  Replaced '_18' with constant '1'

Since the IL on entry to DOM is different than what evrp would see, I added an
evrp instance before DOM and ran it with -O2 -fno-tree-dominator-opts, but evrp
does not fold the conditional.  So this is something particular to what we're
doing in DOM.

In this hacked up evrp instance I see ssa1_dep2 and ssa2_dep2 are both NULL
when we query "_18 = _16 | _17", so we never fold the conditional:

  // Both names will need to have 2 direct dependencies.
  tree ssa1_dep2 = src.gori ()->depend2 (ssa1);
  tree ssa2_dep2 = src.gori ()->depend2 (ssa2);
  if (!ssa1_dep2 || !ssa2_dep2)
    return;

  (gdb) p ssa1_dep2
  $35 = <tree 0x0>
  (gdb) p ssa2_dep2
  $36 = <tree 0x0>

OTOH, in DOM we have:

(gdb) p debug(ssa1_dep2)
a.0_1
$33 = void
(gdb) p debug(ssa2_dep2)
a.0_1
$34 = void
(gdb) 

So the dependencies in DOM's use of ranger in flight are different than what
evrp would see.

Andrew, would the changed IL cause the folding problem above?

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[zhendong.su at inf dot ethz.ch]

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

--- Comment #6 from Zhendong Su <zhendong.su at inf dot ethz.ch> ---
Two additional recent miscompiles that are likedly related:

(1)

[638] % gcctk -O0 small.c; ./a.out
[639] % gcctk -O1 small.c
[640] % ./a.out
Aborted
[641] % cat small.c
int a, b;
int main() {
  int c = 0, d, e, f;
  for (e = 0; e < 3; e++) {
    f = a;
    if (!b)
      f = 1;
    d = f;
  }
  if (d > 1 || d <= c)
    __builtin_abort();
  return 0;
}


(2) 

[579] % gcctk -O1 small.c; ./a.out
[580] % gcctk -O2 small.c
[581] % timeout -s 9 5 ./a.out
Killed
[582] % cat small.c
int a, b, *c;
int f(int d, int e) { return !e || d && e == 1 ? 0 : d % e; }
int main() {
  int g = -4, h = -3;
  if (a)
    h = b;
  while (h <= g || h > -1)
    ;
  if (f(1, a) > 3)
    c = &h;
  return 0;
}

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[amacleod at redhat dot com]

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

--- Comment #7 from Andrew Macleod <amacleod at redhat dot com> ---
The routine which tries to fold relations in && or || statements is getting
stale information.

GORI maintains a dependency cache which is mostly use by the temporal mechanism
to decide when statements are out of date.  It is a shortcut that is used to
prevent constant re-scanning of statements to find any ssa-names in the operand
list.

AS its intended use is dependency tracking, it is allowed to get out of date if
statements are rewritten (additional dependencies may just result in missed
opportunities)

IN this case, _16 and _17 is dependent on a.0_1, and DOM rewrites them, and
eventually the new name a.1_15 is processed and that dependency is added.

relation_fold_and_or erroneously accesses these cache values thinking its a
shortcut to looking at the statements, and then things the 2 relations feeding 
_18 = _16 | _17
are  comparisons between a.0_1 and a.1_15, and with a < and >=,  decides the
condition can be folded.

Using the cache for this purpose is incorrect.  Instead, it should simply query
the operands and ensure they are both ssa-names, and proceed.

Patch in testing.

This is less likely to occur in GCC12 as less places rewrite the IL under the
covers, but it should still be applied ot that branch just in case.

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[amacleod at redhat dot com]

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

--- Comment #8 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 53226
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53226&action=edit
proposed patch

Patch in testing

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:918ccccbb0e78ae42bfcf808a1e93a8f6b9d02ea

commit r13-1356-g918ccccbb0e78ae42bfcf808a1e93a8f6b9d02ea
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Wed Jun 29 13:34:05 2022 -0400

    Don't use gori dependencies to optimize.

      The routine fold_using_range::relation_fold_and_or needs to veriyf that
both
    operands of 2 stmts are the same, and uses GORIs dependency cache for this.
    This cache cannot be counted on to reflect the current contents of a
    stmt, expecially in the presence of an IL changing pass.  Instead, look at
the
    statement operands.

            PR tree-optimization/106114
            gcc/
            * gimple-range-fold.cc (fold_using_range::relation_fold_and_or):
Check
            statement operands instead of GORI cache.
            gcc/testsuite/
            * gcc.dg/pr106114.c: New.

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

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

--- Comment #10 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
fixed in trunk

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[sam at gentoo dot org]

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

--- Comment #11 from Sam James <sam at gentoo dot org> ---
>This is less likely to occur in GCC12 as less places rewrite the IL under the covers, but it should still be applied ot that branch just in case.

Should the bug be reopened for now then?

[Bug tree-optimization/106114] [13 Regression] wrong code at -O1, -O2 and -O3 on x86_64-linux-gnu since r13-1268-g8c99e307b20c502e

[cvs-commit at gcc dot gnu.org]

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

--- Comment #12 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Andrew Macleod
<amacleod@gcc.gnu.org>:

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

commit r12-8549-gd4738cbb02e201c031a2a44d8bc10d3e17d987dc
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Jul 4 11:21:34 2022 -0400

    Don't use gori depedencies to optimize.

      The routine fold_using_range::relation_fold_and_or needs to verify that
both
    operands of 2 stmts are the same, and uses GORIs dependency cache for this.
    This cache cannot be counted on to reflect the current contents of a
    stmt, expecially in the presence of an IL changing pass.  Instead, look at
the
    statement operands.

            PR tree-optimization/106114
            gcc/
            * gimple-range-fold.cc (fold_using_range::relation_fold_and_or):
Check
            statement operands instead of GORI cache.
            gcc/testsuite/
            * gcc.dg/pr106114.c: New.