Patchwork [v2] PR tree-optimization/55079: Don't remove all exits of a loop during loop unroll

login
register
mail settings
Submitter Siddhesh Poyarekar
Date Nov. 15, 2012, 1:35 p.m.
Message ID <20121115190538.2f2cf221@spoyarek>
Download mbox | patch
Permalink /patch/199281/
State New
Headers show

Comments

Siddhesh Poyarekar - Nov. 15, 2012, 1:35 p.m.
Hi,

Here's an updated version of the patch which warns the user if the
removing of redundant exits results in an infinite loop.  I have added
an additional flag in struct loop called external_exits to record if
an exit edge is moved outside the loop body.  This currently happens in
the loop-unswitch pass and was the root cause of the regression in
torture/pr49518.c that I talked about earlier.  The patch now passes all
regression tests except a mudflap case (fail37-frag).  The test is
already broken due to removal of all exits so I haven't attempted to
fix it as part of this patch.  How does this version look?

Regards,
Siddhesh

gcc/ChangeLog:

	* cfgloop.h (struct loop): New member EXTERNAL_EXITS.
	* tree-ssa-loop-ivcanon.c (remove_redundant_iv_tests) Warn when
	loop is left without any exits.
	* tree-ssa-loop-unswitch.c (tree_unswitch_single_loop): Set
	EXTERNAL_EXITS when moving a statement with an exit edge out of
	the loop body.
Siddhesh Poyarekar - Nov. 21, 2012, 7:12 a.m.
Hi,

Ping!


Siddhesh

On Thu, 15 Nov 2012 19:05:38 +0530, Siddhesh wrote:

> Hi,
> 
> Here's an updated version of the patch which warns the user if the
> removing of redundant exits results in an infinite loop.  I have added
> an additional flag in struct loop called external_exits to record if
> an exit edge is moved outside the loop body.  This currently happens
> in the loop-unswitch pass and was the root cause of the regression in
> torture/pr49518.c that I talked about earlier.  The patch now passes
> all regression tests except a mudflap case (fail37-frag).  The test is
> already broken due to removal of all exits so I haven't attempted to
> fix it as part of this patch.  How does this version look?
> 
> Regards,
> Siddhesh
> 
> gcc/ChangeLog:
> 
> 	* cfgloop.h (struct loop): New member EXTERNAL_EXITS.
> 	* tree-ssa-loop-ivcanon.c (remove_redundant_iv_tests) Warn
> when loop is left without any exits.
> 	* tree-ssa-loop-unswitch.c (tree_unswitch_single_loop): Set
> 	EXTERNAL_EXITS when moving a statement with an exit edge out
> of the loop body.
Siddhesh Poyarekar - Nov. 27, 2012, 10:02 a.m.
Ping!

Siddhesh

On Wed, Nov 21, 2012 at 12:42:13PM +0530, Siddhesh Poyarekar wrote:
> Hi,
> 
> Ping!
> 
> 
> Siddhesh
> 
> On Thu, 15 Nov 2012 19:05:38 +0530, Siddhesh wrote:
> 
> > Hi,
> > 
> > Here's an updated version of the patch which warns the user if the
> > removing of redundant exits results in an infinite loop.  I have added
> > an additional flag in struct loop called external_exits to record if
> > an exit edge is moved outside the loop body.  This currently happens
> > in the loop-unswitch pass and was the root cause of the regression in
> > torture/pr49518.c that I talked about earlier.  The patch now passes
> > all regression tests except a mudflap case (fail37-frag).  The test is
> > already broken due to removal of all exits so I haven't attempted to
> > fix it as part of this patch.  How does this version look?
> > 
> > Regards,
> > Siddhesh
> > 
> > gcc/ChangeLog:
> > 
> > 	* cfgloop.h (struct loop): New member EXTERNAL_EXITS.
> > 	* tree-ssa-loop-ivcanon.c (remove_redundant_iv_tests) Warn
> > when loop is left without any exits.
> > 	* tree-ssa-loop-unswitch.c (tree_unswitch_single_loop): Set
> > 	EXTERNAL_EXITS when moving a statement with an exit edge out
> > of the loop body.
>
Siddhesh Poyarekar - Dec. 7, 2012, 11:32 a.m.
Ping!

On Tue, Nov 27, 2012 at 03:32:46PM +0530, Siddhesh Poyarekar wrote:
> Ping!
> 
> Siddhesh
> 
> On Wed, Nov 21, 2012 at 12:42:13PM +0530, Siddhesh Poyarekar wrote:
> > Hi,
> > 
> > Ping!
> > 
> > 
> > Siddhesh
> > 
> > On Thu, 15 Nov 2012 19:05:38 +0530, Siddhesh wrote:
> > 
> > > Hi,
> > > 
> > > Here's an updated version of the patch which warns the user if the
> > > removing of redundant exits results in an infinite loop.  I have added
> > > an additional flag in struct loop called external_exits to record if
> > > an exit edge is moved outside the loop body.  This currently happens
> > > in the loop-unswitch pass and was the root cause of the regression in
> > > torture/pr49518.c that I talked about earlier.  The patch now passes
> > > all regression tests except a mudflap case (fail37-frag).  The test is
> > > already broken due to removal of all exits so I haven't attempted to
> > > fix it as part of this patch.  How does this version look?
> > > 
> > > Regards,
> > > Siddhesh
> > > 
> > > gcc/ChangeLog:
> > > 
> > > 	* cfgloop.h (struct loop): New member EXTERNAL_EXITS.
> > > 	* tree-ssa-loop-ivcanon.c (remove_redundant_iv_tests) Warn
> > > when loop is left without any exits.
> > > 	* tree-ssa-loop-unswitch.c (tree_unswitch_single_loop): Set
> > > 	EXTERNAL_EXITS when moving a statement with an exit edge out
> > > of the loop body.
> >

Patch

diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index 5cd62b3..dab3565 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -173,6 +173,9 @@  struct GTY ((chain_next ("%h.next"))) loop {
 
   /* Head of the cyclic list of the exits of the loop.  */
   struct loop_exit *exits;
+
+  /* True if an exit branch was moved out of the loop.  */
+  bool external_exits;
 };
 
 /* Flags for state of loop structure.  */
diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c
index 601223b..8448234 100644
--- a/gcc/tree-ssa-loop-ivcanon.c
+++ b/gcc/tree-ssa-loop-ivcanon.c
@@ -50,6 +50,8 @@  along with GCC; see the file COPYING3.  If not see
 #include "flags.h"
 #include "tree-inline.h"
 #include "target.h"
+#include "diagnostic.h"
+#include "intl.h"
 
 /* Specifies types of loops that may be unrolled.  */
 
@@ -525,10 +527,21 @@  static bool
 remove_redundant_iv_tests (struct loop *loop)
 {
   struct nb_iter_bound *elt;
-  bool changed = false;
+  loop_exit *exit;
+  VEC(gimple, stack) *exit_stmts = VEC_alloc (gimple, stack, 16);
+  int exits_left = 0, num_exits = 0;
 
   if (!loop->any_upper_bound)
-    return false;
+    goto out;
+
+  /* Count our exits.  */
+  for (exit = loop->exits->next; exit->e; exit = exit->next)
+    num_exits++;
+
+  if (num_exits == 0)
+    goto out;
+
+  exits_left = num_exits;
   for (elt = loop->bounds; elt; elt = elt->next)
     {
       /* Exit is pointless if it won't be taken before loop reaches
@@ -555,7 +568,11 @@  remove_redundant_iv_tests (struct loop *loop)
 	      || !loop->nb_iterations_upper_bound.ult
 		   (tree_to_double_int (niter.niter)))
 	    continue;
-	  
+
+	  exits_left--;
+
+	  VEC_safe_push (gimple, stack, exit_stmts, elt->stmt);
+
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    {
 	      fprintf (dump_file, "Removed pointless exit: ");
@@ -566,10 +583,31 @@  remove_redundant_iv_tests (struct loop *loop)
 	  else
 	    gimple_cond_make_true (elt->stmt);
 	  update_stmt (elt->stmt);
-	  changed = true;
 	}
     }
-  return changed;
+
+  /* We removed all exit points, so tell the user.  */
+  if (exits_left == 0 && !loop->external_exits)
+    {
+      gimple stmt;
+      const char *wording;
+      unsigned i;
+      location_t loc;
+
+      FOR_EACH_VEC_ELT (gimple, exit_stmts, i, stmt)
+	{
+	  loc = gimple_location (stmt);
+	  wording = N_("Loop behavior is undefined before exit condition; "
+		       "turned into infinite loop");
+	  warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location, 0,
+		      gettext (wording));
+	}
+    }
+
+out:
+  VEC_free (gimple, stack, exit_stmts);
+
+  return exits_left < num_exits;
 }
 
 /* Stores loops that will be unlooped after we process whole loop tree. */
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index b24f3d7..fb95ab7 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -234,6 +234,14 @@  tree_unswitch_single_loop (struct loop *loop, int num)
 
       cond = simplify_using_entry_checks (loop, cond);
       stmt = last_stmt (bbs[i]);
+
+      /* We're switching out an exit point, so note that the loop has exits
+         outside its body.  */
+      if (loop_exit_edge_p (loop, EDGE_SUCC (bbs[i], 0))
+	  || loop_exit_edge_p (loop, EDGE_SUCC (bbs[i], 1)))
+	loop->external_exits = true;
+
+      /* TODO If this is a loop exit statement then note it.  */
       if (integer_nonzerop (cond))
 	{
 	  /* Remove false path.  */