[Bug tree-optimization/102542] New: [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[Bug tree-optimization/102542] New: [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[marxin at gcc dot gnu.org]

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

            Bug ID: 102542
           Summary: [12 Regression] ICE Segmentation fault since
                    r12-3876-g4a960d548b7d7d94
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: ice-on-valid-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: marxin at gcc dot gnu.org
                CC: aldyh at gcc dot gnu.org
  Target Milestone: ---

The following crashes:

$ cat block-5.c
int a[200][200];
int b_j;


void b() {
  int i;
  b_j = 1;
  for (; b_j < 200; b_j++) {
    i = 0;
    for (; i < 200; i++)
      a[i][b_j] = a[i][b_j - 1];
  }
}

$ gcc block-5.c -c -fno-tree-ch -O3 -c
during GIMPLE pass: unrolljam
block-5.c: In function ‘b’:
block-5.c:5:6: internal compiler error: Segmentation fault
    5 | void b() {
      |      ^
0xf053da crash_signal
        /home/marxin/Programming/gcc/gcc/toplev.c:328
0x7ffff789979f ???
       
/usr/src/debug/glibc-2.34-1.2.x86_64/signal/../sysdeps/unix/sysv/linux/x86_64/libc_sigaction.c:0
0x107a35c tree_transform_and_unroll_loop(loop*, unsigned int, edge_def*,
tree_niter_desc*, void (*)(loop*, void*), void*)
        /home/marxin/Programming/gcc/gcc/tree-ssa-loop-manip.c:1425
0x1b6324b tree_loop_unroll_and_jam
        /home/marxin/Programming/gcc/gcc/gimple-loop-jam.c:590
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.

[Bug tree-optimization/102542] [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-09-30
      Known to work|                            |11.2.0
      Known to fail|                            |12.0
     Ever confirmed|0                           |1
   Target Milestone|---                         |12.0

[Bug tree-optimization/102542] [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=102385

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Most likely the same bug as PR 102385 and its related ones.

[Bug tree-optimization/102542] [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[aldyh at gcc dot gnu.org]

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

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

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

--- Comment #2 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
A little -fdbg-cnt bisecting magic shows that the first jump thread causes some
sort of reaction downstream in unrolljam:

./cc1 a.c -quiet -O3 -fno-tree-ch -fdbg-cnt=registered_jump_thread:1-1
***dbgcnt: lower limit 1 reached for registered_jump_thread.***
***dbgcnt: upper limit 1 reached for registered_jump_thread.***
during GIMPLE pass: unrolljam
a.c: In function ‘b’:
a.c:5:6: internal compiler error: Segmentation fault

So it's the first threading path that is causing an issue.  Setting a
breakpoint at path registering yields this:

Breakpoint 5, jt_path_registry::register_jump_thread (this=0x391f150, Python
Exception <class 'gdb.error'> There is no member or method named m_vecpfx.: 
path=0x3a09430)
    at /home/aldyh/src/gcc/gcc/tree-ssa-threadupdate.c:2838
(gdb) p ::debug(path)
  [1] Registering jump thread: (8, 4) incoming edge;  (4, 3) normal; 

It's threading 8->4->3, which looks perfectly reasonable:

  <bb 4> [local count: 1073741824]:
  # i_5 = PHI <0(8), i_12(3)>
  if (i_5 != 200)
    goto <bb 3>; [99.00%]
  else
    goto <bb 5>; [1.00%]

Note that i_5 is known to be 0 on the 8->4 edge.

The loop info says that bb8 is the pre-header to loop 2 which starts at bb4. 
So this technically crosses loops into bb4, but is allowed as there's an
exception when the first BB is in another block:

      // The first entry represents the block with an outgoing edge
      // that we will redirect to the jump threading path.  Thus we
      // don't care about that block's loop father.

Similarly in the back threader profitability code:

 /* Remember, blocks in the path are stored in opposite order
         in the PATH array.  The last entry in the array represents
         the block with an outgoing edge that we will redirect to the
         jump threading path.  Thus we don't care about that block's
         loop father, nor how many statements are in that block because
         it will not be copied or whether or not it ends in a multiway
         branch.  */

For reference, here is the full IL:

  int i;
  int _1;
  int _2;
  int _3;
  int b_j.3_4;

  <bb 2> [local count: 1327096]:
  b_j = 1;
  goto <bb 6>; [100.00%]

  <bb 3> [local count: 1063004409]:
  _1 = b_j.3_4 + -1;
  _2 = a[i_5][_1];
  a[i_5][b_j.3_4] = _2;
  i_12 = i_5 + 1;

  <bb 4> [local count: 1073741824]:
  # i_5 = PHI <0(8), i_12(3)>
  if (i_5 != 200)
    goto <bb 3>; [99.00%]
  else
    goto <bb 5>; [1.00%]

  <bb 5> [local count: 10737416]:
  _3 = b_j.3_4 + 1;
  b_j = _3;

  <bb 6> [local count: 12064512]:
  b_j.3_4 = b_j;
  if (b_j.3_4 <= 199)
    goto <bb 8>; [89.00%]
  else
    goto <bb 7>; [11.00%]

  <bb 8> [local count: 10737416]:
  goto <bb 4>; [100.00%]

  <bb 7> [local count: 1327096]:
  return;

I think this is a problem elsewhere.

[Bug tree-optimization/102542] [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Aldy Hernandez from comment #2) 
> I think this is a problem elsewhere.

Right which is why I said this is most likely the same issue as reported on the
earlier bug 102385 (and its many dups).

[Bug tree-optimization/102542] [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[rguenther at suse dot de]

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

--- Comment #4 from rguenther at suse dot de <rguenther at suse dot de> ---
On Thu, 30 Sep 2021, aldyh at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102542
> 
> Aldy Hernandez <aldyh at gcc dot gnu.org> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |rguenth at gcc dot gnu.org
> 
> --- Comment #2 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
> A little -fdbg-cnt bisecting magic shows that the first jump thread causes some
> sort of reaction downstream in unrolljam:
> 
> ./cc1 a.c -quiet -O3 -fno-tree-ch -fdbg-cnt=registered_jump_thread:1-1
> ***dbgcnt: lower limit 1 reached for registered_jump_thread.***
> ***dbgcnt: upper limit 1 reached for registered_jump_thread.***
> during GIMPLE pass: unrolljam
> a.c: In function ‘b’:
> a.c:5:6: internal compiler error: Segmentation fault
> 
> So it's the first threading path that is causing an issue.  Setting a
> breakpoint at path registering yields this:
> 
> Breakpoint 5, jt_path_registry::register_jump_thread (this=0x391f150, Python
> Exception <class 'gdb.error'> There is no member or method named m_vecpfx.: 
> path=0x3a09430)
>     at /home/aldyh/src/gcc/gcc/tree-ssa-threadupdate.c:2838
> (gdb) p ::debug(path)
>   [1] Registering jump thread: (8, 4) incoming edge;  (4, 3) normal; 
> 
> It's threading 8->4->3, which looks perfectly reasonable:
> 
>   <bb 4> [local count: 1073741824]:
>   # i_5 = PHI <0(8), i_12(3)>
>   if (i_5 != 200)
>     goto <bb 3>; [99.00%]
>   else
>     goto <bb 5>; [1.00%]
> 
> Note that i_5 is known to be 0 on the 8->4 edge.
> 
> The loop info says that bb8 is the pre-header to loop 2 which starts at bb4. 
> So this technically crosses loops into bb4, but is allowed as there's an
> exception when the first BB is in another block:
> 
>       // The first entry represents the block with an outgoing edge
>       // that we will redirect to the jump threading path.  Thus we
>       // don't care about that block's loop father.

So the threading at hand rotates the loop (which is only so-so OK),
that might be problematic in case it creates a non-do-while loop
after loop header copying.

In this process it might also lose track of the loop, causing it to
be re-discovered as separate entity which has problems of its own.

IMHO we should avoid threadings through a loop header if the path
ends in the loop itself, even if it doesn't introduce a new entry but
just re-directs the existing one.

[Bug tree-optimization/102542] [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[aldyh at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jeffreyalaw at gmail dot com

--- Comment #5 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to rguenther@suse.de from comment #4)
> On Thu, 30 Sep 2021, aldyh at gcc dot gnu.org wrote:

Thanks for the loop explanation.  It's quite helpful.

> So the threading at hand rotates the loop (which is only so-so OK),
> that might be problematic in case it creates a non-do-while loop
> after loop header copying.
> 
> In this process it might also lose track of the loop, causing it to
> be re-discovered as separate entity which has problems of its own.
> 
> IMHO we should avoid threadings through a loop header if the path
> ends in the loop itself, even if it doesn't introduce a new entry but
> just re-directs the existing one.

It looks like Jeff and you have stumbled on various corner cases we must
address in cancel_invalid_paths().

Could I inconvenience you to tweak this function with your insight?  It's a
tiny function, and it seems you're much more qualified to add the restriction
code.  If not, I'm sure I can stumble around it and send it for review.

Orthogonal to this, it does look like the extra thread is causing an ICE in slp
which must be addressed??

Thanks.

[Bug tree-optimization/102542] [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Aldy Hernandez from comment #5)
> (In reply to rguenther@suse.de from comment #4)
> > On Thu, 30 Sep 2021, aldyh at gcc dot gnu.org wrote:
> 
> Thanks for the loop explanation.  It's quite helpful.
> 
> > So the threading at hand rotates the loop (which is only so-so OK),
> > that might be problematic in case it creates a non-do-while loop
> > after loop header copying.
> > 
> > In this process it might also lose track of the loop, causing it to
> > be re-discovered as separate entity which has problems of its own.
> > 
> > IMHO we should avoid threadings through a loop header if the path
> > ends in the loop itself, even if it doesn't introduce a new entry but
> > just re-directs the existing one.
> 
> It looks like Jeff and you have stumbled on various corner cases we must
> address in cancel_invalid_paths().
> 
> Could I inconvenience you to tweak this function with your insight?  It's a
> tiny function, and it seems you're much more qualified to add the
> restriction code.  If not, I'm sure I can stumble around it and send it for
> review.

Something like

diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index dcabfdb30d2..b1b77e91176 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2811,6 +2811,14 @@ jt_path_registry::cancel_invalid_paths
(vec<jump_thread_edge *> &path)
       cancel_thread (&path, "Path crosses loops");
       return true;
     }
+  edge entry = path[0]->e;
+  edge exit = path[path.length () - 1]->e;
+  if (entry->src->loop_father != exit->dest->loop_father
+      && !flow_loop_nested_p (exit->src->loop_father,
entry->dest->loop_father))
+    {
+      cancel_thread (&path, "Path rotates loop");
+      return true;
+    }
   return false;
 }

that is, the path should either start & end in the same loop or overall
exit the loop it starts in but never enter a loop (the above also catches
creating irreducible loops, not only rotation).

I find the

      // The first entry represents the block with an outgoing edge
      // that we will redirect to the jump threading path.  Thus we
      // don't care about that block's loop father.
      if ((i > 0 && e->src->loop_father != loop)
          || e->dest->loop_father != loop)
        path_crosses_loops = true;

mildly confusing and don't really understand what it is about.  What's
not present yet is avoiding to thread through the loop header.  For that
I'd add in the loop

       if (e->dest->loop_father->header == e->dest
           && !flow_loop_nested_p (exit->dest->loop_father,
e->dest->loop_father)
         cancel_thread ("Path crosses loop header but does not exit it");

such threadings tend to create sub-loops which _might_ be OK, not sure.
This is stricter than the above suggestion since it also covers paths
that remain in the same loop but it should cover the above cases as well.
Note it's difficult to tell whether the created sub-loop is irreducible.
This check should also prevent us from creating multiple latches.

> Orthogonal to this, it does look like the extra thread is causing an ICE in
> slp which must be addressed??

Yes, we have duplicates for this crash which is caused by some changes
Richard Sandiford did.

[Bug tree-optimization/102542] [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[aldyh at redhat dot com]

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

--- Comment #7 from Aldy Hernandez <aldyh at redhat dot com> ---
On Fri, Oct 1, 2021 at 1:46 PM rguenth at gcc dot gnu.org
<gcc-bugzilla@gcc.gnu.org> wrote:

> > Could I inconvenience you to tweak this function with your insight?  It's a
> > tiny function, and it seems you're much more qualified to add the
> > restriction code.  If not, I'm sure I can stumble around it and send it for
> > review.
>
> Something like
>
> diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
> index dcabfdb30d2..b1b77e91176 100644

Thanks so much for this.  I will test it, and incorporate it with some
ideas Jeff had suggested.  Then I'll post it upstream for
review/discussion.

BTW, it seems that the code restricting paths should actually live in
the loop world...since it's the loop experts who know what is allowed
and what is problematic ;-).

[Bug tree-optimization/102542] [12 Regression] ICE Segmentation fault since r12-3876-g4a960d548b7d7d94

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
No longer reproduces.