[PATCH] Fix PR55833 + cheaper checking

[PATCH] Fix PR55833 + cheaper checking

[Marek Polacek]

The following patch fixes (?) PR55833 by recomputing irreducible loops
after every unswitch-transformation.  With this testcase, when we perform
loop unswitching on the RTL level, we end up in situation where we have
a loop into which we get through loop exit of another loop which is
a part of an irreducible region.  Between those two loops is something like
preheader, which isn't marked as irreducible, nor its edges.  verify_loop_structure
then ICEs because of that.  Another hunk of this patch is just cheaper checking,
written by Richi.

Regtested/bootstrapped on x86_64-linux.

Zdenek, any thoughts on this?

2013-01-10  Richard Biener  <rguenther@suse.de>
	    Marek Polacek  <polacek@redhat.com>

	PR rtl-optimization/55833
	* loop-unswitch.c (unswitch_loops): Move loop verification...
	(unswitch_single_loop): ...here.  Call mark_irreducible_loops.

	* gcc.dg/pr55833.c: New test.

--- gcc/loop-unswitch.c.mp	2013-01-10 16:50:28.899559875 +0100
+++ gcc/loop-unswitch.c	2013-01-10 16:50:34.203575403 +0100
@@ -145,12 +145,7 @@ unswitch_loops (void)
   /* Go through inner loops (only original ones).  */
 
   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
-    {
-      unswitch_single_loop (loop, NULL_RTX, 0);
-#ifdef ENABLE_CHECKING
-      verify_loop_structure ();
-#endif
-    }
+    unswitch_single_loop (loop, NULL_RTX, 0);
 
   iv_analysis_done ();
 }
@@ -370,6 +365,13 @@ unswitch_single_loop (struct loop *loop,
   nloop = unswitch_loop (loop, bbs[i], copy_rtx_if_shared (cond), cinsn);
   gcc_assert (nloop);
 
+  /* We changed the CFG.  Recompute irreducible BBs and edges.  */
+  mark_irreducible_loops ();
+
+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+#endif
+
   /* Invoke itself on modified loops.  */
   unswitch_single_loop (nloop, rconds, num + 1);
   unswitch_single_loop (loop, conds, num + 1);
--- gcc/testsuite/gcc.dg/pr55833.c.mp	2013-01-10 17:23:26.016102692 +0100
+++ gcc/testsuite/gcc.dg/pr55833.c	2013-01-10 17:23:15.898073384 +0100
@@ -0,0 +1,28 @@
+/* PR rtl-optimization/55833 */
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+
+int a, b, c;
+
+void foo()
+{
+    unsigned d, l, *p, k = 1;
+
+    if(bar())
+    {
+label:
+      	if((a = a <= 0))
+        {
+            if(c)
+                d = b;
+
+            if (b || d ? l : k ? : 0)
+                a = d = 0;
+
+            goto label;
+       	}
+    }
+
+    while(*p++)
+        goto label;
+}

	Marek

Re: [PATCH] Fix PR55833 + cheaper checking

[Steven Bosscher]

On Thu, Jan 10, 2013 at 6:31 PM, Marek Polacek wrote:
> +  /* We changed the CFG.  Recompute irreducible BBs and edges.  */
> +  mark_irreducible_loops ();

This is a very expensive fix for a really unusual situation.

I don't think this is the right thing to do...

Ciao!
Steven

Re: [PATCH] Fix PR55833 + cheaper checking

[Zdenek Dvorak]

Hi,

> On Thu, Jan 10, 2013 at 6:31 PM, Marek Polacek wrote:
> > +  /* We changed the CFG.  Recompute irreducible BBs and edges.  */
> > +  mark_irreducible_loops ();
> 
> This is a very expensive fix for a really unusual situation.
> 
> I don't think this is the right thing to do...

I agree -- at the very least, unswitch_single_loop should check whether there
is any possiblity it could have affected irreducible loops information (this
should only be the case when some already existing irreducible loop is altered
in the progress).  Which is what it (or more precisely, remove_path function
used by it) tries to do -- so is should be sufficient to check why this fails
for the considered testcase, and make sure the situation is correctly detected,

Zdenek

Re: [PATCH] Fix PR55833 + cheaper checking

[Marek Polacek]

On Thu, Jan 10, 2013 at 11:19:43PM +0100, Zdenek Dvorak wrote:
> I agree -- at the very least, unswitch_single_loop should check whether there
> is any possiblity it could have affected irreducible loops information (this
> should only be the case when some already existing irreducible loop is altered
> in the progress).  Which is what it (or more precisely, remove_path function
> used by it) tries to do -- so is should be sufficient to check why this fails
> for the considered testcase, and make sure the situation is correctly detected,

Actually, in this case, we don't call remove_path from unswitch_single_loop
at all.  So, here's another stab at it.  In this version, we will call
mark_irreducible_loops only in case where we're removing a loop
from loop hierarchy tree.  Because when we do that (and we're in some
irreducible region), the edge that connects those two loops
should be marked as EDGE_IRREDUCIBLE_LOOP.  And the preheader BB
eventually as BB_IRREDUCIBLE_LOOP.  Does this look any better?
I'm not actually checking whether we really are in a irreducible
region, should that be done (how?)?  Thanks.

Bootstrap and regtest pending on x86_64-unknown-linux-gnu.

2013-01-14  Richard Biener  <rguenther@suse.de>
	    Marek Polacek  <polacek@redhat.com>

	PR rtl-optimization/55833
	* loop-unswitch.c (unswitch_loops): Move loop verification...
	(unswitch_single_loop): ...here.  Call mark_irreducible_loops.
	* cfgloopmanip.c (fix_loop_placement): Add IRRED_INVALIDATED parameter.
	Set it to true when we're removing a loop from hierarchy tree.
	(fix_bb_placements): Adjust caller.
	(fix_loop_placements): Likewise.

	* gcc.dg/pr55833.c: New test.

--- gcc/loop-unswitch.c.mp	2013-01-10 16:50:28.899559875 +0100
+++ gcc/loop-unswitch.c	2013-01-14 15:44:30.574158810 +0100
@@ -145,12 +144,7 @@ unswitch_loops (void)
   /* Go through inner loops (only original ones).  */
 
   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
-    {
-      unswitch_single_loop (loop, NULL_RTX, 0);
-#ifdef ENABLE_CHECKING
-      verify_loop_structure ();
-#endif
-    }
+    unswitch_single_loop (loop, NULL_RTX, 0);
 
   iv_analysis_done ();
 }
@@ -370,6 +364,10 @@ unswitch_single_loop (struct loop *loop,
   nloop = unswitch_loop (loop, bbs[i], copy_rtx_if_shared (cond), cinsn);
   gcc_assert (nloop);
 
+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+#endif
+
   /* Invoke itself on modified loops.  */
   unswitch_single_loop (nloop, rconds, num + 1);
   unswitch_single_loop (loop, conds, num + 1);
--- gcc/cfgloopmanip.c.mp	2013-01-14 14:42:52.502002650 +0100
+++ gcc/cfgloopmanip.c	2013-01-14 16:48:40.693799547 +0100
@@ -111,10 +111,13 @@ fix_bb_placement (basic_block bb)
 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
    of LOOP to that leads at least one exit edge of LOOP, and set it
    as the immediate superloop of LOOP.  Return true if the immediate superloop
-   of LOOP changed.  */
+   of LOOP changed.
+
+   IRRED_INVALIDATED is set to true if a change in the loop structures might
+   invalidate the information about irreducible regions.  */
 
 static bool
-fix_loop_placement (struct loop *loop)
+fix_loop_placement (struct loop *loop, bool *irred_invalidated)
 {
   unsigned i;
   edge e;
@@ -136,6 +139,9 @@ fix_loop_placement (struct loop *loop)
       flow_loop_tree_node_remove (loop);
       flow_loop_tree_node_add (father, loop);
 
+      /* We may need to recompute irreducible loops.  */
+      *irred_invalidated = true;
+
       /* The exit edges of LOOP no longer exits its original immediate
 	 superloops; remove them from the appropriate exit lists.  */
       FOR_EACH_VEC_ELT (exits, i, e)
@@ -212,7 +218,7 @@ fix_bb_placements (basic_block from,
       if (from->loop_father->header == from)
 	{
 	  /* Subloop header, maybe move the loop upward.  */
-	  if (!fix_loop_placement (from->loop_father))
+	  if (!fix_loop_placement (from->loop_father, irred_invalidated))
 	    continue;
 	  target_loop = loop_outer (from->loop_father);
 	}
@@ -965,7 +971,7 @@ fix_loop_placements (struct loop *loop,
   while (loop_outer (loop))
     {
       outer = loop_outer (loop);
-      if (!fix_loop_placement (loop))
+      if (!fix_loop_placement (loop, irred_invalidated))
 	break;
 
       /* Changing the placement of a loop in the loop tree may alter the
--- gcc/testsuite/gcc.dg/pr55833.c.mp	2013-01-10 17:23:26.016102692 +0100
+++ gcc/testsuite/gcc.dg/pr55833.c	2013-01-10 17:23:15.898073384 +0100
@@ -0,0 +1,28 @@
+/* PR rtl-optimization/55833 */
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+
+int a, b, c;
+
+void foo()
+{
+    unsigned d, l, *p, k = 1;
+
+    if(bar())
+    {
+label:
+      	if((a = a <= 0))
+        {
+            if(c)
+                d = b;
+
+            if (b || d ? l : k ? : 0)
+                a = d = 0;
+
+            goto label;
+       	}
+    }
+
+    while(*p++)
+        goto label;
+}

	Marek

Re: [PATCH] Fix PR55833 + cheaper checking

[Zdenek Dvorak]

Hi,

> On Thu, Jan 10, 2013 at 11:19:43PM +0100, Zdenek Dvorak wrote:
> > I agree -- at the very least, unswitch_single_loop should check whether there
> > is any possiblity it could have affected irreducible loops information (this
> > should only be the case when some already existing irreducible loop is altered
> > in the progress).  Which is what it (or more precisely, remove_path function
> > used by it) tries to do -- so is should be sufficient to check why this fails
> > for the considered testcase, and make sure the situation is correctly detected,
> 
> Actually, in this case, we don't call remove_path from unswitch_single_loop
> at all.

I am not quite sure what you mean by that -- remove_path is called unconditionally
in unswitch_loop (and fix_loop_placement is only called through remove_path).

> So, here's another stab at it.  In this version, we will call
> mark_irreducible_loops only in case where we're removing a loop
> from loop hierarchy tree.  Because when we do that (and we're in some
> irreducible region), the edge that connects those two loops
> should be marked as EDGE_IRREDUCIBLE_LOOP.  And the preheader BB
> eventually as BB_IRREDUCIBLE_LOOP.  Does this look any better?
> I'm not actually checking whether we really are in a irreducible
> region, should that be done (how?)?

Yes, you should check whether you are in an irreducible loop.  This is done by
testing EDGE_IRREDUCIBLE_LOOP flag,

Zdenek

Re: [PATCH] Fix PR55833 + cheaper checking

[Marek Polacek]

On Mon, Jan 14, 2013 at 06:51:54PM +0100, Zdenek Dvorak wrote:
> Hi,
> 
> > On Thu, Jan 10, 2013 at 11:19:43PM +0100, Zdenek Dvorak wrote:
> > > I agree -- at the very least, unswitch_single_loop should check whether there
> > > is any possiblity it could have affected irreducible loops information (this
> > > should only be the case when some already existing irreducible loop is altered
> > > in the progress).  Which is what it (or more precisely, remove_path function
> > > used by it) tries to do -- so is should be sufficient to check why this fails
> > > for the considered testcase, and make sure the situation is correctly detected,
> > 
> > Actually, in this case, we don't call remove_path from unswitch_single_loop
> > at all.
> 
> I am not quite sure what you mean by that -- remove_path is called unconditionally
> in unswitch_loop (and fix_loop_placement is only called through remove_path).

Yeah, that's right, what I meant was that in unswitch_single_loop, we
call remove_path only conditionally (and for this particular TC that's
not the case).

> > So, here's another stab at it.  In this version, we will call
> > mark_irreducible_loops only in case where we're removing a loop
> > from loop hierarchy tree.  Because when we do that (and we're in some
> > irreducible region), the edge that connects those two loops
> > should be marked as EDGE_IRREDUCIBLE_LOOP.  And the preheader BB
> > eventually as BB_IRREDUCIBLE_LOOP.  Does this look any better?
> > I'm not actually checking whether we really are in a irreducible
> > region, should that be done (how?)?
> 
> Yes, you should check whether you are in an irreducible loop.  This is done by
> testing EDGE_IRREDUCIBLE_LOOP flag,

Alright, I was wondering whether there's any other way.  Unfortunately,
here I couldn't do something like

if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
  ...
because we're natural loop in a subloop, so I abused the loop exits of
this loop.  Hopefully I'm not doing something evil.

Updated patch attached.  Ok if testing passes?  Thanks,

2013-01-14  Richard Biener  <rguenther@suse.de>
	    Marek Polacek  <polacek@redhat.com>

	PR rtl-optimization/55833
	* loop-unswitch.c (unswitch_loops): Move loop verification...
	(unswitch_single_loop): ...here.  Call mark_irreducible_loops.
	* cfgloopmanip.c (fix_loop_placement): Add IRRED_INVALIDATED parameter.
	Set it to true when we're removing a loop from hierarchy tree in
	an irreducible region.
	(fix_bb_placements): Adjust caller.
	(fix_loop_placements): Likewise.

	* gcc.dg/pr55833.c: New test.

--- gcc/loop-unswitch.c.mp	2013-01-10 16:50:28.899559875 +0100
+++ gcc/loop-unswitch.c	2013-01-14 19:04:21.675418957 +0100
@@ -145,12 +144,7 @@ unswitch_loops (void)
   /* Go through inner loops (only original ones).  */
 
   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
-    {
-      unswitch_single_loop (loop, NULL_RTX, 0);
-#ifdef ENABLE_CHECKING
-      verify_loop_structure ();
-#endif
-    }
+    unswitch_single_loop (loop, NULL_RTX, 0);
 
   iv_analysis_done ();
 }
@@ -370,6 +364,10 @@ unswitch_single_loop (struct loop *loop,
   nloop = unswitch_loop (loop, bbs[i], copy_rtx_if_shared (cond), cinsn);
   gcc_assert (nloop);
 
+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+#endif
+
   /* Invoke itself on modified loops.  */
   unswitch_single_loop (nloop, rconds, num + 1);
   unswitch_single_loop (loop, conds, num + 1);
--- gcc/cfgloopmanip.c.mp	2013-01-14 14:42:52.502002650 +0100
+++ gcc/cfgloopmanip.c	2013-01-14 19:55:47.330356459 +0100
@@ -111,10 +111,13 @@ fix_bb_placement (basic_block bb)
 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
    of LOOP to that leads at least one exit edge of LOOP, and set it
    as the immediate superloop of LOOP.  Return true if the immediate superloop
-   of LOOP changed.  */
+   of LOOP changed.
+
+   IRRED_INVALIDATED is set to true if a change in the loop structures might
+   invalidate the information about irreducible regions.  */
 
 static bool
-fix_loop_placement (struct loop *loop)
+fix_loop_placement (struct loop *loop, bool *irred_invalidated)
 {
   unsigned i;
   edge e;
@@ -139,7 +142,12 @@ fix_loop_placement (struct loop *loop)
       /* The exit edges of LOOP no longer exits its original immediate
 	 superloops; remove them from the appropriate exit lists.  */
       FOR_EACH_VEC_ELT (exits, i, e)
-	rescan_loop_exit (e, false, false);
+	{
+	  /* We may need to recompute irreducible loops.  */
+	  if (e->flags & EDGE_IRREDUCIBLE_LOOP)
+	    *irred_invalidated = true;
+	  rescan_loop_exit (e, false, false);
+	}
 
       ret = true;
     }
@@ -212,7 +220,7 @@ fix_bb_placements (basic_block from,
       if (from->loop_father->header == from)
 	{
 	  /* Subloop header, maybe move the loop upward.  */
-	  if (!fix_loop_placement (from->loop_father))
+	  if (!fix_loop_placement (from->loop_father, irred_invalidated))
 	    continue;
 	  target_loop = loop_outer (from->loop_father);
 	}
@@ -965,7 +973,7 @@ fix_loop_placements (struct loop *loop,
   while (loop_outer (loop))
     {
       outer = loop_outer (loop);
-      if (!fix_loop_placement (loop))
+      if (!fix_loop_placement (loop, irred_invalidated))
 	break;
 
       /* Changing the placement of a loop in the loop tree may alter the
--- gcc/testsuite/gcc.dg/pr55833.c.mp	2013-01-10 17:23:26.016102692 +0100
+++ gcc/testsuite/gcc.dg/pr55833.c	2013-01-10 17:23:15.898073384 +0100
@@ -0,0 +1,28 @@
+/* PR rtl-optimization/55833 */
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+
+int a, b, c;
+
+void foo()
+{
+    unsigned d, l, *p, k = 1;
+
+    if(bar())
+    {
+label:
+      	if((a = a <= 0))
+        {
+            if(c)
+                d = b;
+
+            if (b || d ? l : k ? : 0)
+                a = d = 0;
+
+            goto label;
+       	}
+    }
+
+    while(*p++)
+        goto label;
+}

	Marek

Re: [PATCH] Fix PR55833 + cheaper checking

[Zdenek Dvorak]

Hi,

> > Yes, you should check whether you are in an irreducible loop.  This is done by
> > testing EDGE_IRREDUCIBLE_LOOP flag,
> 
> Alright, I was wondering whether there's any other way.  Unfortunately,
> here I couldn't do something like
> 
> if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
>   ...
> because we're natural loop in a subloop, so I abused the loop exits of
> this loop.  Hopefully I'm not doing something evil.
> 
> Updated patch attached.  Ok if testing passes?  Thanks,

yes, this is OK,

Zdenek

> 2013-01-14  Richard Biener  <rguenther@suse.de>
> 	    Marek Polacek  <polacek@redhat.com>
> 
> 	PR rtl-optimization/55833
> 	* loop-unswitch.c (unswitch_loops): Move loop verification...
> 	(unswitch_single_loop): ...here.  Call mark_irreducible_loops.
> 	* cfgloopmanip.c (fix_loop_placement): Add IRRED_INVALIDATED parameter.
> 	Set it to true when we're removing a loop from hierarchy tree in
> 	an irreducible region.
> 	(fix_bb_placements): Adjust caller.
> 	(fix_loop_placements): Likewise.
> 
> 	* gcc.dg/pr55833.c: New test.