[Bug tree-optimization/104543] New: wrong code at -O3 on x86_64-linux-gnu

[Bug tree-optimization/104543] New: wrong code at -O3 on x86_64-linux-gnu

[zhendong.su at inf dot ethz.ch]

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

            Bug ID: 104543
           Summary: wrong code at -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.

[588] % 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.1/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.1 20220215 (experimental) [master r12-7236-g2c3309e3d0f] (GCC) 
[589] % 
[589] % gcctk -O2 small.c; ./a.out
[590] % 
[590] % gcctk -O3 small.c
[591] % ./a.out
Aborted
[592] % 
[592] % cat small.c
int a[3], b, c;
int e() {
  if (!c) {
    for (b = 0; b < 3; b++)
      for (c = 0; c < 3; c++)
        a[c] ^= 1;
    return -1;
  }
  return 0;
}
int main() {
  e();
  if (a[1] != 1)
    __builtin_abort();
  return 0;
}

[Bug tree-optimization/104543] wrong code at -O3 on x86_64-linux-gnu

[zhendong.su at inf dot ethz.ch]

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

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

[Bug tree-optimization/104543] [12 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=104543

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.0
           Keywords|                            |wrong-code
            Summary|wrong code at -O3 on        |[12 Regression] wrong code
                   |x86_64-linux-gnu            |at -O3 on x86_64-linux-gnu

[Bug tree-optimization/104543] [12 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=104543

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-02-15
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.
>From what I could tell it is the unroll and jam pass which is messing up.


-fno-loop-unroll-and-jam

  <bb 5> [local count: 542102826]:
  # c.4_21 = PHI <0(7), _9(23)>
  _7 = a[c.4_21];
  _8 = _7 ^ 1;
  a[c.4_21] = _8;
  _9 = c.4_21 + 1;
  _11 = b_lsm.13_13 + 1;
  if (_11 <= 2)
    goto <bb 22>; [83.33%]
  else
    goto <bb 8>; [16.67%]

  <bb 22> [local count: 451752355]:
  a[c.4_21] = _7;

[Bug tree-optimization/104543] [12 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=104543

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

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
We might have a duplicate somewhere.

[Bug tree-optimization/104543] [12 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=104543

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> ---
The issue is that we call do_rpo_vn without having SSA form updated and thus
we see

<bb 5> [local count: 90350471]:
# c.4_22 = PHI <0(4), _40(24)>
_8 = a[c.4_22];
_9 = _8 ^ 1;
a[c.4_22] = _9;
_10 = c.4_22 + 1;

<bb 6> [local count: 11166912]:
_16 = 3;
_12 = b.6_23 + 1;

<bb 22> [local count: 11166912]:
# b.6_33 = PHI <_12(20)>

<bb 23> [local count: 90350471]:
# c.4_35 = PHI <c.4_22(22)>
_37 = a[c.4_35];
_38 = _37 ^ 1;
a[c.4_35] = _38;
_40 = c.4_35 + 1;
if (_40 <= 2)
  goto <bb 24>; [89.00%]
else
  goto <bb 25>; [11.00%]

but I think the PHI use in bb 23 will be _10 after updating SSA.  Though
need_ssa_update_p is false - tree_unroll_loop will call update SSA.

Ah, after unroll but before fuse we have

<bb 5> [local count: 90350471]:
# c.4_22 = PHI <_10(10), 0(4)>

and

<bb 23> [local count: 90350471]:
# c.4_35 = PHI <0(22), _40(24)>

we've changed how CFG copying may alter PHI args.  fuse_loops does

      /* The PHI nodes of the second body (single-argument now)
         need adjustments to use the right values: either directly
         the value of the corresponding PHI in the first copy or
         the one leaving the first body which unrolling did for us.

         See also unroll_jam_possible_p() for further possibilities.  */
      gphi_iterator psi_first, psi_second;
      e = single_pred_edge (next->header);
      for (psi_first = gsi_start_phis (loop->header),
           psi_second = gsi_start_phis (next->header);
           !gsi_end_p (psi_first);
           gsi_next (&psi_first), gsi_next (&psi_second))
        {

that we can iterate PHI args in lock-step this way is not guaranteed.

[Bug tree-optimization/104543] [12 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=104543

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

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hmm, no.  The issue seems to be that the outer loop is head-controlled which
means unrolling duplicates the exit check in the middle of the fused loop.
I think we miss a check for an empty header of the outer loop, the
perfect nest check is too simplistic here.  We have

  b = 0;
  do
    {
       if (b > 2)
         break;
       c = 0;
       do
         {
           a[c] ^= 1;
           ++c
         }
       while (c <= 2);
       ++b;
    }
  while (1);

and fusing ends up with something like

  b = 0;
  do
    {
       c = 0;
       do
         {
           a[c] ^= 1;
           if (b > 2)
             break;
           a[c] ^= 1;
         }
       while (c <= 2);
       b+=2;
    }
  while (1);

in particular the comment in bb_prevents_fusion_p saying

  /* BB is duplicated by outer unrolling and then all N-1 first copies
     move into the body of the fused inner loop.  If BB exits the outer loop
     the last copy still does so, and the first N-1 copies are cancelled
     by loop unrolling, so also after fusion it's the exit block.

looks wrong.  Yes, the first is cancelled but the remaining is not the
exit block.

[Bug tree-optimization/104543] [12 Regression] wrong code at -O3 on x86_64-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 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:d03a67dc69251dc86c0772a432380a6e9bcb8617

commit r12-7243-gd03a67dc69251dc86c0772a432380a6e9bcb8617
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Feb 15 12:27:14 2022 +0100

    tree-optimization/104543 - fix unroll-and-jam precondition

    We have to make sure that outer loop exits come after the inner
    loop since we otherwise will put it into the fused loop body.

    2022-02-15  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/104543
            * gimple-loop-jam.cc (unroll_jam_possible_p): Check outer loop
exits
            come after the inner loop.

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

[Bug tree-optimization/104543] [12 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=104543

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

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

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

[Bug tree-optimization/104543] [9/10/11 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=104543

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.0                        |9.5
           Priority|P3                          |P2
             Status|RESOLVED                    |NEW
      Known to work|                            |12.0
         Resolution|FIXED                       |---
            Summary|[12 Regression] wrong code  |[9/10/11 Regression] wrong
                   |at -O3 on x86_64-linux-gnu  |code at -O3 on
                   |                            |x86_64-linux-gnu

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hmm, the issue is probably latent.

[Bug tree-optimization/104543] [9/10/11 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=104543

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

[Bug tree-optimization/104543] [9/10/11 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=104543

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

[Bug tree-optimization/104543] [9/10/11 Regression] wrong code at -O3 on x86_64-linux-gnu

[matz at gcc dot gnu.org]

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

--- Comment #11 from Michael Matz <matz at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #5)
> in particular the comment in bb_prevents_fusion_p saying
> 
>   /* BB is duplicated by outer unrolling and then all N-1 first copies
>      move into the body of the fused inner loop.  If BB exits the outer loop
>      the last copy still does so, and the first N-1 copies are cancelled
>      by loop unrolling, so also after fusion it's the exit block.
> 
> looks wrong.  Yes, the first is cancelled but the remaining is not the
> exit block.

I think your patch is fine and fixes the bug.  We can possibly do better also
for head-controlled loops by just reversing the above: the _first_ of the N
exit-bb copies needs to remain (and stay in front of the inner loop), and
the last N-1 copies need to be cancelled.  Needs to be carefully thought
through,
but something like that should be possible.

[Bug tree-optimization/104543] [10/11 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=104543

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.5                         |10.4

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9 branch is being closed

[Bug tree-optimization/104543] [10/11 Regression] wrong code at -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.4                        |10.5

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 10.4 is being released, retargeting bugs to GCC 10.5.

[Bug tree-optimization/104543] [10/11 Regression] wrong code at -O3 on x86_64-linux-gnu

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |marxin at gcc dot gnu.org

--- Comment #14 from Martin Liška <marxin at gcc dot gnu.org> ---
Btw. started in r12-4526-gd8edfadfc7a9795b.

[Bug tree-optimization/104543] [11 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=104543

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.5                        |11.5

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 10 branch is being closed.

[Bug tree-optimization/104543] [11 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=104543

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.5                        |12.0
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed in GCC 12.