[Bug tree-optimization/100492] New: wrong code at -O3 (generated code hangs)

[Bug tree-optimization/100492] New: wrong code at -O3 (generated code hangs)

[zhendong.su at inf dot ethz.ch]

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

            Bug ID: 100492
           Summary: wrong code at -O3 (generated code hangs)
           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: ---

It seems to be a recent regression.

[619] % 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/12.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-languages=c,c++
--disable-werror --enable-multilib --with-system-zlib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 12.0.0 20210509 (experimental) [master revision
56103737f17:37fd4fac862:5e0236d3b0e0d7ad98bcee36128433fa755b5558] (GCC) 
[620] % 
[620] % gcctk -O2 small.c; ./a.out
0
[621] % gcc110 -O3 small.c; ./a.out
0
[622] % 
[622] % gcctk -O3 small.c
[623] % timeout -s 9 10 ./a.out
Killed
[624] % 
[624] % cat small.c
int printf (const char *, ...);
char a, c;
int b, d, *e = &d, g;
static char f;
int main() {
  int h = 0;
  for (; a < 1; a++) {
    int *i[5], **j = &i[4], ***k[3][2] = {{&j}}, ****l = &k[2][1], *****m = &l;
    char *n = &c;
    f = *e = g = 0;
    for (; g < 2; g++) {
      for (b = 0; b < 3; b++)
        h = (h && (*n = 0)) == 0;
      if (g)
        break;
    }
  }
  printf("%d\n", f);
  return 0;
}

[Bug tree-optimization/100492] wrong code at -O3 (generated code hangs)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-05-10
            Version|unknown                     |12.0
     Ever confirmed|0                           |1
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
           Keywords|                            |wrong-code

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed but it happens for me on all active branches...

[Bug tree-optimization/100492] wrong code at -O3 (generated code hangs)

[rguenth at gcc dot gnu.org]

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> Confirmed but it happens for me on all active branches...

Eh, no - branches are fine.

[Bug tree-optimization/100492] [12 Regression] wrong code at -O3 (generated code hangs)

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.0
           Priority|P3                          |P1
            Summary|wrong code at -O3           |[12 Regression] wrong code
                   |(generated code hangs)      |at -O3 (generated code
                   |                            |hangs)

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r12-145-gd1d01a66012a93cc8cb7dafbe1b5ec453ec96b59

[Bug tree-optimization/100492] [12 Regression] wrong code at -O3 (generated code hangs)

[rguenth at gcc dot gnu.org]

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

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 #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Mine then.

[Bug tree-optimization/100492] [12 Regression] wrong code at -O3 (generated code hangs)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |10.3.1, 11.1.1, 12.0
      Known to work|                            |9.3.1

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
We manage to do one more CSE of 'a' which in turn triggers loop distribution
which, when I disable it, fixes the testcase.  The disambiguation in question
only triggers in FRE{1,3,5}, DOM2, PRE and CUNROLL.  That points to a
latent issue in loop distribution.

The following modified testcase also is miscompiled on the GCC 10 and 11
branch,
-O2 -ftree-loop-distribution is enough to trigger that.

int printf (const char *, ...);
char a, c;
int b, d, *e = &d, g;
static char f;
int main() {
  int h = 0;
  int a_ = a;
  for (; a_ < 1; a = ++a_) {
    int *i[5], **j = &i[4], ***k[3][2] = {{&j}}, ****l = &k[2][1], *****m = &l;
    char *n = &c;
    f = *e = g = 0;
    for (; g < 2; g++) {
      for (b = 0; b < 3; b++)
        h = (h && (*n = 0)) == 0;
      if (g)
        break;
    }
  }
  printf("%d\n", f);
  return 0;
}

Specifically we distribute f = 0 from the rest.

What is odd is that we have a loop with multiple latches at the start of loop
distribution.

in .optimized we have

  <bb 9> [local count: 955630225]:
  goto <bb 9>; [100.00%]

which results from the tail partition which ends up "canonicalizing" not
included GIMPLE_CONDs in a way that forms the endless loop.

[Bug tree-optimization/100492] [12 Regression] wrong code at -O3 (generated code hangs)

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Ah, no - there's an irreducible region inside the inner loop.  The logic

              /* In distribution of loop nest, if bb is inner loop's exit_bb,
                 we choose its exit edge/path in order to avoid generating
                 infinite loop.  For all other cases, we choose an arbitrary
                 path through the empty CFG part that this unnecessary
                 control stmt controls.  */
              if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
                {
                  if (inner_exit && inner_exit->flags & EDGE_TRUE_VALUE)
                    gimple_cond_make_true (cond_stmt);
                  else
                    gimple_cond_make_false (cond_stmt);
                  update_stmt (stmt);
                }

only works for conditions exiting the loop (where we asked for a single-exit
earlier) and for conditions not controlling a cycle (where it doesn't matter
which way we go).

There's no sweep over stmts qualifying a loop body, but
find_seed_stmts_for_distribution could be abused that way.  We could also
simply forcefully put this condition in all partitions or we could see
whether to use post-dominance we compute for control dependence can be
used to find the edge towards exit.

[Bug tree-optimization/100492] [10/11/12 Regression] wrong code at -O3 (generated code hangs)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.0                        |10.4
            Summary|[12 Regression] wrong code  |[10/11/12 Regression] wrong
                   |at -O3 (generated code      |code at -O3 (generated code
                   |hangs)                      |hangs)
           Priority|P1                          |P2

[Bug tree-optimization/100492] [10/11/12 Regression] wrong code at -O3 (generated code hangs)

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 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:60af2db18013a0339302928ba98fee893ccc1957

commit r12-661-g60af2db18013a0339302928ba98fee893ccc1957
Author: Richard Biener <rguenther@suse.de>
Date:   Mon May 10 11:37:27 2021 +0200

    tree-optimization/100492 - avoid irreducible regions in loop distribution

    When we distribute away a condition we rely on the ability to
    change it to either 1 != 0 or 0 != 0 depending on the direction
    of the exit branch in the respective loop.  But when the loop
    contains an irreducible sub-region then for the conditions inside
    this this fails and can lead to infinite loops being generated.

    Avoid distibuting loops with irreducible sub-regions.

    2021-05-10  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/100492
            * tree-loop-distribution.c (find_seed_stmts_for_distribution):
            Find nothing when the loop contains an irreducible region.

            * gcc.dg/torture/pr100492.c: New testcase.

[Bug tree-optimization/100492] [10/11 Regression] wrong code at -O3 (generated code hangs)

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:9b3852d998bd4ae68f51311441feea13103971e3

commit r11-8462-g9b3852d998bd4ae68f51311441feea13103971e3
Author: Richard Biener <rguenther@suse.de>
Date:   Mon May 10 11:37:27 2021 +0200

    tree-optimization/100492 - avoid irreducible regions in loop distribution

    When we distribute away a condition we rely on the ability to
    change it to either 1 != 0 or 0 != 0 depending on the direction
    of the exit branch in the respective loop.  But when the loop
    contains an irreducible sub-region then for the conditions inside
    this this fails and can lead to infinite loops being generated.

    Avoid distibuting loops with irreducible sub-regions.

    2021-05-10  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/100492
            * tree-loop-distribution.c (find_seed_stmts_for_distribution):
            Find nothing when the loop contains an irreducible region.

            * gcc.dg/torture/pr100492.c: New testcase.

    (cherry picked from commit 60af2db18013a0339302928ba98fee893ccc1957)

[Bug tree-optimization/100492] [10 Regression] wrong code at -O3 (generated code hangs)

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r10-9920-gcedce283c319103e039ae2659d0d7473dd8efeca
Author: Richard Biener <rguenther@suse.de>
Date:   Mon May 10 11:37:27 2021 +0200

    tree-optimization/100492 - avoid irreducible regions in loop distribution

    When we distribute away a condition we rely on the ability to
    change it to either 1 != 0 or 0 != 0 depending on the direction
    of the exit branch in the respective loop.  But when the loop
    contains an irreducible sub-region then for the conditions inside
    this this fails and can lead to infinite loops being generated.

    Avoid distibuting loops with irreducible sub-regions.

    2021-05-10  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/100492
            * tree-loop-distribution.c (find_seed_stmts_for_distribution):
            Find nothing when the loop contains an irreducible region.

            * gcc.dg/torture/pr100492.c: New testcase.

    (cherry picked from commit 60af2db18013a0339302928ba98fee893ccc1957)

[Bug tree-optimization/100492] [10 Regression] wrong code at -O3 (generated code hangs)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |10.3.1
      Known to fail|10.3.1                      |10.3.0
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

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