Fix PR56035

We ICEd on attached testcase because we didn't properly detected the
latch edge.  Furthermore, I think the code for re-computing latches
is somehow broken at the moment.  In fix_loop_structure we have
      /* If there was no latch, schedule the loop for removal.  */
      if (!first_latch)
	loop->header = NULL;
      /* If there was a single latch and it belongs to the loop of the
	 header, record it.  */
      else if (latch
	       && latch->src->loop_father == loop)
	loop->latch = latch->src;
      /* Otherwise there are multiple latches which are eventually
         disambiguated below.  */
      else
	loop->latch = NULL;
but I don't think we can use the ->loop_father info, because that is
already cleared by
  FOR_EACH_BB (bb)
    {
      if (changed_bbs)
	bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
      bb->loop_father = current_loops->tree_root;
    }
earlier on.  Thus we ended up in the last else branch and NULLed loop->latch,
which is clearly wrong.
This patch just moves the hunk above so that we
reset ->loop_father-s only after re-computing loop latches.

Regtested/bootstraped on x86_64-linux, ok for trunk?

2013-01-22  Marek Polacek  <polacek@redhat.com>

	* cfgloopmanip.c (fix_loop_structure): Move clearing bb-to-loop
	mapping after re-computing latches.

	* testsuite/gcc.dg/pr56035.c: New test.


	Marek

Marek Polacek <polacek@redhat.com> wrote:

>We ICEd on attached testcase because we didn't properly detected the
>latch edge.  Furthermore, I think the code for re-computing latches
>is somehow broken at the moment.  In fix_loop_structure we have
>      /* If there was no latch, schedule the loop for removal.  */
>      if (!first_latch)
>	loop->header = NULL;

Are you sure this works when we hit this, thus
Remove the loop? Otherwise you are right, the current place looks bogus.

Ok if you can convince yourself that this is
The case.

Thanks,
Richard.

>      /* If there was a single latch and it belongs to the loop of the
>	 header, record it.  */
>      else if (latch
>	       && latch->src->loop_father == loop)
>	loop->latch = latch->src;
>      /* Otherwise there are multiple latches which are eventually
>         disambiguated below.  */
>      else
>	loop->latch = NULL;
>but I don't think we can use the ->loop_father info, because that is
>already cleared by
>  FOR_EACH_BB (bb)
>    {
>      if (changed_bbs)
>	bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
>      bb->loop_father = current_loops->tree_root;
>    }
>earlier on.  Thus we ended up in the last else branch and NULLed
>loop->latch,
>which is clearly wrong.
>This patch just moves the hunk above so that we
>reset ->loop_father-s only after re-computing loop latches.
>
>Regtested/bootstraped on x86_64-linux, ok for trunk?
>
>2013-01-22  Marek Polacek  <polacek@redhat.com>
>
>	* cfgloopmanip.c (fix_loop_structure): Move clearing bb-to-loop
>	mapping after re-computing latches.
>
>	* testsuite/gcc.dg/pr56035.c: New test.
>
>--- gcc/cfgloopmanip.c.mp	2013-01-22 14:11:25.241233824 +0100
>+++ gcc/cfgloopmanip.c	2013-01-22 14:11:42.364285826 +0100
>@@ -1784,16 +1784,6 @@ fix_loop_structure (bitmap changed_bbs)
>   /* We need exact and fast dominance info to be available.  */
>   gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK);
> 
>-  /* Remove the old bb -> loop mapping.  Remember the depth of the
>blocks in
>-     the loop hierarchy, so that we can recognize blocks whose loop
>nesting
>-     relationship has changed.  */
>-  FOR_EACH_BB (bb)
>-    {
>-      if (changed_bbs)
>-	bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
>-      bb->loop_father = current_loops->tree_root;
>-    }
>-
>   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
>     {
>       release_recorded_exits ();
>@@ -1834,6 +1824,16 @@ fix_loop_structure (bitmap changed_bbs)
> 	loop->latch = NULL;
>     }
> 
>+  /* Remove the old bb -> loop mapping.  Remember the depth of the
>blocks in
>+     the loop hierarchy, so that we can recognize blocks whose loop
>nesting
>+     relationship has changed.  */
>+  FOR_EACH_BB (bb)
>+    {
>+      if (changed_bbs)
>+	bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
>+      bb->loop_father = current_loops->tree_root;
>+    }
>+
> /* Remove the dead loops from structures.  We start from the innermost
> loops, so that when we remove the loops, we know that the loops inside
>      are preserved, and do not waste time relinking loops that will be
>--- gcc/testsuite/gcc.dg/pr56035.c.mp	2013-01-22 14:27:21.104614758
>+0100
>+++ gcc/testsuite/gcc.dg/pr56035.c	2013-01-22 14:31:01.642266091 +0100
>@@ -0,0 +1,35 @@
>+/* PR tree-optimization/56035 */
>+/* { dg-do compile } */
>+/* { dg-options "-O1 -ftree-vectorize -fcse-follow-jumps
>-fstrict-overflow" } */
>+
>+short a, c, *p;
>+
>+void
>+f (void)
>+{
>+  int b;
>+
>+  if (c)
>+  lbl1:
>+    for (a = 0; a < 1; a++)
>+      {
>+	for (c = 0; c < 1; c++)
>+	  {
>+	    goto lbl1;
>+	    while (*p++)
>+	    lbl2:
>+	      ;
>+	  }
>+      }
>+
>+  for (;; b++)
>+    {
>+      if (c)
>+	goto lbl2;
>+    lbl3:
>+      for (c = 0; c < 9; c++)
>+	for (c = -17; c < 2; c++)
>+	  if (*p)
>+	    goto lbl3;
>+    }
>+}
>
>	Marek

Hi,

> We ICEd on attached testcase because we didn't properly detected the
> latch edge.  Furthermore, I think the code for re-computing latches
> is somehow broken at the moment.  In fix_loop_structure we have
>       /* If there was no latch, schedule the loop for removal.  */
>       if (!first_latch)
> 	loop->header = NULL;
>       /* If there was a single latch and it belongs to the loop of the
> 	 header, record it.  */
>       else if (latch
> 	       && latch->src->loop_father == loop)
> 	loop->latch = latch->src;
>       /* Otherwise there are multiple latches which are eventually
>          disambiguated below.  */
>       else
> 	loop->latch = NULL;
> but I don't think we can use the ->loop_father info, because that is
> already cleared by
>   FOR_EACH_BB (bb)
>     {
>       if (changed_bbs)
> 	bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
>       bb->loop_father = current_loops->tree_root;
>     }
> earlier on.

I am not quite sure why we test "&& latch->src->loop_father == loop" in
the first place.  Would things work if that condition is removed?
I don't much like your proposed patch (as well as the current state),
as according to the specification of fix_loop_structure, we are not
allowed to assume anything about the bb --> loop mapping,

Zdenek

On Tue, Jan 22, 2013 at 05:26:02PM +0100, Zdenek Dvorak wrote:
> Hi,
> 
> > We ICEd on attached testcase because we didn't properly detected the
> > latch edge.  Furthermore, I think the code for re-computing latches
> > is somehow broken at the moment.  In fix_loop_structure we have
> >       /* If there was no latch, schedule the loop for removal.  */
> >       if (!first_latch)
> > 	loop->header = NULL;
> >       /* If there was a single latch and it belongs to the loop of the
> > 	 header, record it.  */
> >       else if (latch
> > 	       && latch->src->loop_father == loop)
> > 	loop->latch = latch->src;
> >       /* Otherwise there are multiple latches which are eventually
> >          disambiguated below.  */
> >       else
> > 	loop->latch = NULL;
> > but I don't think we can use the ->loop_father info, because that is
> > already cleared by
> >   FOR_EACH_BB (bb)
> >     {
> >       if (changed_bbs)
> > 	bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
> >       bb->loop_father = current_loops->tree_root;
> >     }
> > earlier on.
> 
> I am not quite sure why we test "&& latch->src->loop_father == loop" in
> the first place.  Would things work if that condition is removed?
> I don't much like your proposed patch (as well as the current state),
> as according to the specification of fix_loop_structure, we are not
> allowed to assume anything about the bb --> loop mapping,

I tried that approach, too, and it worked (even regtested that
successfully).  I was however worried that we might end up with an edge
coming out of BB
from different loop heading into the header.  In this case setting up
loop's latch as the source of the latch edge would be wrong.

	Marek

Hi,

> > > We ICEd on attached testcase because we didn't properly detected the
> > > latch edge.  Furthermore, I think the code for re-computing latches
> > > is somehow broken at the moment.  In fix_loop_structure we have
> > >       /* If there was no latch, schedule the loop for removal.  */
> > >       if (!first_latch)
> > > 	loop->header = NULL;
> > >       /* If there was a single latch and it belongs to the loop of the
> > > 	 header, record it.  */
> > >       else if (latch
> > > 	       && latch->src->loop_father == loop)
> > > 	loop->latch = latch->src;
> > >       /* Otherwise there are multiple latches which are eventually
> > >          disambiguated below.  */
> > >       else
> > > 	loop->latch = NULL;
> > > but I don't think we can use the ->loop_father info, because that is
> > > already cleared by
> > >   FOR_EACH_BB (bb)
> > >     {
> > >       if (changed_bbs)
> > > 	bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
> > >       bb->loop_father = current_loops->tree_root;
> > >     }
> > > earlier on.
> > 
> > I am not quite sure why we test "&& latch->src->loop_father == loop" in
> > the first place.  Would things work if that condition is removed?
> > I don't much like your proposed patch (as well as the current state),
> > as according to the specification of fix_loop_structure, we are not
> > allowed to assume anything about the bb --> loop mapping,
> 
> I tried that approach, too, and it worked (even regtested that
> successfully).

let's go with that, then (as well as updating the missleading comment before the test).

> I was however worried that we might end up with an edge
> coming out of BB
> from different loop heading into the header.  In this case setting up
> loop's latch as the source of the latch edge would be wrong.

Actually, the comment suggesting that possibility does not make much sense.
A latch (a predecessor of the header H that is dominated by H) belongs to
the loop headed by H by definition, so I am not quite sure what the test was supposed to do.

The latch block may of course belong to a subloop of the loop, but that is not
forbidden (and it is taken care of further in fix_loop_structure through force_single_succ_latches
in the situations where we want to avoid this possibility),

Zdenek

On Tue, Jan 22, 2013 at 03:30:06PM +0100, Richard Biener wrote:
> Marek Polacek <polacek@redhat.com> wrote:
> 
> >We ICEd on attached testcase because we didn't properly detected the
> >latch edge.  Furthermore, I think the code for re-computing latches
> >is somehow broken at the moment.  In fix_loop_structure we have
> >      /* If there was no latch, schedule the loop for removal.  */
> >      if (!first_latch)
> >	loop->header = NULL;
> 
> Are you sure this works when we hit this, thus
> Remove the loop? Otherwise you are right, the current place looks bogus.

I guess it should work--in the very next moment after zapping the
header we'd call delete_loop on that loop.   But...

> Ok if you can convince yourself that this is
> The case.

... I will prepare another fix which Zdenek likes more ;).  Thanks,

	Marek