[Bug tree-optimization/114787] New: wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[Bug tree-optimization/114787] New: wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[zhendong.su at inf dot ethz.ch]

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

            Bug ID: 114787
           Summary: wrong code at -O1 on x86_64-linux-gnu (the 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 appears to be a recent regression and does not reproduce with 13.2 and
earlier. 

Compiler Explorer: https://godbolt.org/z/6sbh8Wr1e


[663] % 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/14.0.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-trunk/configure --disable-bootstrap
--enable-checking=yes --prefix=/local/suz-local/software/local/gcc-trunk
--enable-sanitizers --enable-languages=c,c++ --disable-werror --enable-multilib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 14.0.1 20240420 (experimental) (GCC) 
[664] % 
[664] % gcctk -O0 small.c; ./a.out
[665] % 
[665] % gcctk -O1 small.c
[666] % timeout -s 9 10 ./a.out
Killed
[667] % 
[667] % cat small.c
int a, b, c, d, e = -1, f, g, h, j, k, n, o, p;
int main() {
  int i, l = 2, m;
  for (b = 0; b < 1; b++)
    l = 0;
  for (; a >= 0; a--)
    for (m = 3; m; m--) {
      k = g;
      i = 0;
      for (; i < 1; i++)
        for (; f < 1; f++)
          h = g;
      n = 2 & ((e ^ d) | 1) * j;
      o = ~(e & n);
    q:
      if (c <= e)
        return 0;
      e = o;
    }
  p = l;
  l = 0;
  if (p)
    goto q;
  return 0;
}

[Bug tree-optimization/114787] [14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |14.0
   Last reconfirmed|                            |2024-04-20
                 CC|                            |hubicka at gcc dot gnu.org,
                   |                            |jakub at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
   Target Milestone|---                         |14.0
             Status|UNCONFIRMED                 |NEW
            Summary|wrong code at -O1 on        |[14 Regression] wrong code
                   |x86_64-linux-gnu (the       |at -O1 on x86_64-linux-gnu
                   |generated code hangs)       |(the generated code hangs)
     Ever confirmed|0                           |1

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r14-7138-g05e8ef2a05b477589cae25af3311bad0f68a90fe

[Bug tree-optimization/114787] [14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[law at gcc dot gnu.org]

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

Jeffrey A. Law <law at gcc dot gnu.org> changed:

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

[Bug target/114787] [14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |x86_64-linux-gnu
          Component|tree-optimization           |target

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The first difference besides prediction/counts on the BB is in the register
allocator.

The code for aarch64 looks ok too.

[Bug tree-optimization/114787] [14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|target                      |tree-optimization

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #2)
> The first difference besides prediction/counts on the BB is in the register
> allocator.
> 
> The code for aarch64 looks ok too.

So I was wrong (and now even more confused than before). In that sometimes even
GCC 13.2.0 code generation is broken. But I don't understand what the
conditions are which cause it (adding -fdump-tree-optimized-all or something
like that seems to cause different code generation).

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |needs-bisection
      Known to work|                            |12.1.0
   Target Milestone|14.0                        |13.3
      Known to fail|                            |13.1.0
            Summary|[14 Regression] wrong code  |[13/14 Regression] wrong
                   |at -O1 on x86_64-linux-gnu  |code at -O1 on
                   |(the generated code hangs)  |x86_64-linux-gnu (the
                   |                            |generated code hangs)

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So with GCC 13, with `-fdump-tree-all-all`, we get the same wrong code as on
the trunk.

This is why I was I misunderstood thinking it was a target issue as I was
comparing the dumps between GCC 13 and the trunk with -all enabled but it was
broken in GCC 13 too.

Anyways I tested GCC 12.3.0 and it looks to be working there.

It would be useful to get another bisect done this time with `-O1
-fdump-tree-all-all` .

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The first difference (in GCC 13) with/without -fdump-tree-all-all comes from
cunroll:



Broken:
```
Loop 3 iterates 2 times.
Loop 3 iterates at most 1 times.
Loop 3 likely iterates at most 1 times.
Analyzing # of iterations of loop 3
  exit condition [2, + , 4294967295] != 0
  bounds on difference of bases: -2 ... -2
  result:
    # of iterations 2, bounded by 2
Removed pointless exit: if (ivtmp_43 != 0)
```

Working:
```
Loop 3 iterates 2 times.
Loop 3 iterates at most 2 times.
Loop 3 likely iterates at most 2 times.
```

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #5)
> The first difference (in GCC 13) with/without -fdump-tree-all-all comes from
> cunroll:


I should note that -fdump-tree-cunroll-all still produces the correct code
generation for GCC 13 which makes this bug even odder.

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P1                          |P2
           Keywords|needs-bisection             |

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
With -fdump-tree-all-all it started with
r13-3898-gaf96500eea72c674a5686b35c66202ef2bd9688f
The assembly with r13-3897 is the same between -O1 and -O1 -fdump-tree-all-all,
while
with r13-3898 it is different and the testcase hangs.

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Seems it is -fdump-tree-profile_estimate-details that changes the code
generation.

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[jakub at gcc dot gnu.org]

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

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
It is the
      if (dump_file && (dump_flags & TDF_DETAILS)
          && max_loop_iterations_int (loop) >= 0)
        {
          fprintf (dump_file,
                   "Loop %d iterates at most %i times.\n", loop->num,
                   (int)max_loop_iterations_int (loop));
        }
      if (dump_file && (dump_flags & TDF_DETAILS)
          && likely_max_loop_iterations_int (loop) >= 0)
        {
          fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
                   loop->num, (int)likely_max_loop_iterations_int (loop));
        }
cases which trigger the different code generation with
-fdump-tree-profile_estimate-details -O1, either of them; guess
max_loop_iterations_int and likely_max_loop_iterations_int cache the results
and while it doesn't change the IL from the profile_estimate pass, it changes
the behavior of the cunroll pass later on.

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[pinskia at gcc dot gnu.org]

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I suspect there needs to be a call to free_numbers_of_iterations_estimates
somewhere. Maybe it is copyprop, maybe there are a few other missing ones.

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[jakub at gcc dot gnu.org]

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

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Seems it is {,likely_}max_loop_iterations_int on the for (; i < 1; i++) loop
which matters (aka loop 3).  Given the i = 0 right before it (guess csmith-ism,
don't see why it couldn't be in the for init expression) it estimates that it
loops once.
Then the copyprop2 pass removes the i++ latch and i <= 0 comparison in that
loop header, so from all I can see that loop disappears.
At profile_estimate time, we have loop 1 the b<=0 loop which iterates just once
and then loop 4 f<=0 nested in loop 3 i<=0 nested in loop 2 a>=0, the m loop
doesn't seem to be in loop structure maybe because of the goto into the loop.
After copyprop, the loop 1 b<=0 is gone and the i<=0 loop is as well, but not
in the loop structure, loop 3 in the loop structure (presumably with the cached
number of loop estimates) has the f<=0 header and loop 4 nested in it has a
header testing f<=0 too.

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P2                          |P1

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I think this should be still P1, while with -fdump-tree-all-all it miscompiled
the testcase already before, most users don't use those options, and on the
trunk it is a regression with just -O1.

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[hubicka at gcc dot gnu.org]

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

--- Comment #13 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
-fdump-tree-all-all  changing generated code is also bad.  We probably should
avoid dumping loop bounds then they are not recorded. I added dumping of loop
bounds and this may be unexpected side effect. WIll take a look.

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jan Hubicka from comment #13)
> -fdump-tree-all-all  changing generated code is also bad.  We probably
> should avoid dumping loop bounds then they are not recorded. I added dumping
> of loop bounds and this may be unexpected side effect. WIll take a look.

I think consistently estimating the number of iterations here is correct.

I don't think the bug should be P1, it's latent and exposed only with an
artificial testcase.  We've likely had similar bugs before where we end up
associating estimates with a wrong loop after some CFG transform.

In this case we end up with the i-loop header being associated with a former
irreducible region.  The fix in the past was to release estimates/niters
on problematic transforms.  Let me have a look.

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[rguenth at gcc dot gnu.org]

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

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 58023
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58023&action=edit
patch

I'm testing this.

[Bug tree-optimization/114787] [13/14 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[cvs-commit at gcc dot gnu.org]

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

--- Comment #16 from GCC 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:cc48418cfc2e555d837ae9138cbfac23acb3cdf9

commit r14-10106-gcc48418cfc2e555d837ae9138cbfac23acb3cdf9
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Apr 24 08:42:40 2024 +0200

    tree-optimization/114787 - more careful loop update with CFG cleanup

    When CFG cleanup removes a backedge we have to be more careful with
    loop update.  In particular we need to clear niter info and estimates
    and if we remove the last backedge of a loop we have to also mark
    it for removal to prevent a following basic block merging to associate
    loop info with an unrelated header.

            PR tree-optimization/114787
            * tree-cfg.cc (remove_edge_and_dominated_blocks): When
            removing a loop backedge clear niter info and when removing
            the last backedge of a loop mark that loop for removal.

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

[Bug tree-optimization/114787] [13 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |14.0
            Summary|[13/14 Regression] wrong    |[13 Regression] wrong code
                   |code at -O1 on              |at -O1 on x86_64-linux-gnu
                   |x86_64-linux-gnu (the       |(the generated code hangs)
                   |generated code hangs)       |
           Priority|P1                          |P2

--- Comment #17 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk (but not the -fdump-* side-effect - leaving that to Honza).  The
issue is latent on the branches.

[Bug tree-optimization/114787] [13 Regression] wrong code at -O1 on x86_64-linux-gnu (the generated code hangs)

[hubicka at gcc dot gnu.org]

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

--- Comment #18 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
predict.cc queries number of iterations using number_of_iterations_exit and
loop_niter_by_eval and finally using estimated_stmt_executions.

The first two queries are not updating the upper bounds datastructure so that
is why we get around without computing them in some cases.

I guess we can just drop dumping here. We now dump the recorded estimates
elsehwere, so this is somewhat redundant.