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

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

[Siddhesh Poyarekar]

[-- Attachment #1: Type: text/plain, Size: 1622 bytes --]

Hi,

r193098 introduced a change to the loop unroll behaviour, where exits
beyond nb_iterations_upper_bound were removed as being redundant.  This
assumption is not true for an undefined behaviour, which is when a loop
causes access beyond bounds of an array.  In such a case, all exits are
removed and the result is an infinite loop.  Essentially, the following
program results in an infinite loop with -O:

int d[16];

int
main (void)
{
  int k, satd = 0, dd;

  for (dd=d[k=0]; k<16;)
    {
      satd += (dd < 0 ? -dd : dd);
      ++k;
      dd=d[k];
    }

  return satd;
}

I understand that the behaviour is undefined, but this is easily
avoidable by skipping removal of the exits if it results in an infinite
loop.  Attached patch does exactly that.

I guess a further improvement to this (if the patch approach is valid)
would be to issue a warning to the user based on this analysis.  I am
trying to figure out a way to call the remove_redundant_iv_tests
function safely in tree-vrp so that even -O2 does not produce an
infinite loop for the above program (it has since r186592) and prints
the warning instead.  Simply calling it after max_loop_iterations
causes a regression in the testsuite that I haven't figured out yet.

I have tested the patch on x86_64 for C language and the testsuite
reports no regressions.  In fact, it seems to have fixed a previous
failure in gcc.dg/vect/slp-perm-9.c.

Regards,
Siddhesh

ChangeLog:

2012-11-09  Siddhesh Poyarekar  <siddhesh@redhat.com>

	PR tree-optimization/55079
	* gcc/tree-ssa-loop-ivcanon.c (remove_redundant_iv_tests):
	Avoid removing all exits of the loop.

[-- Attachment #2: w.patch --]
[-- Type: text/x-patch, Size: 2216 bytes --]

diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c
index 601223b..04bcd86 100644
--- a/gcc/tree-ssa-loop-ivcanon.c
+++ b/gcc/tree-ssa-loop-ivcanon.c
@@ -525,10 +525,22 @@ 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);
+  VEC(edge, stack) *exit_edges = VEC_alloc (edge, 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,21 +567,40 @@ 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);
+	  VEC_safe_push (edge, stack, exit_edges, exit_edge);
+	}
+    }
+
+  /* Don't remove the exits if it leaves us with an infinite loop.  */
+  if (exits_left > 0)
+    {
+      while (VEC_length (gimple, exit_stmts))
+        {
+	  gimple stmt = VEC_pop (gimple, exit_stmts);
+	  edge exit_edge = VEC_pop (edge, exit_edges);
+
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    {
 	      fprintf (dump_file, "Removed pointless exit: ");
-	      print_gimple_stmt (dump_file, elt->stmt, 0, 0);
+	      print_gimple_stmt (dump_file, stmt, 0, 0);
 	    }
 	  if (exit_edge->flags & EDGE_TRUE_VALUE)
-	    gimple_cond_make_false (elt->stmt);
+	    gimple_cond_make_false (stmt);
 	  else
-	    gimple_cond_make_true (elt->stmt);
-	  update_stmt (elt->stmt);
-	  changed = true;
+	    gimple_cond_make_true (stmt);
+	  update_stmt (stmt);
 	}
     }
-  return changed;
+
+out:
+  VEC_free (gimple, stack, exit_stmts);
+  VEC_free (edge, stack, exit_edges);
+
+  return (exits_left && exits_left < num_exits);
 }
 
 /* Stores loops that will be unlooped after we process whole loop tree. */

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

[Ian Lance Taylor]

On Fri, Nov 9, 2012 at 5:11 AM, Siddhesh Poyarekar <siddhesh@redhat.com> wrote:
>
> I understand that the behaviour is undefined, but this is easily
> avoidable by skipping removal of the exits if it results in an infinite
> loop.  Attached patch does exactly that.

I don't mind saying that GCC should define cases that the language
standards leave undefined.  But that does not seem to be what this
patch does.  I don't see why this is a good idea.  It seems to produce
a program that is unpredictable in a different way.  How does that
help the user?  If anything an infinite loop might be better, since it
is more obvious that something is wrong.  Unless I misunderstand.

Ian

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

[Jan Hubicka]

> On Fri, Nov 9, 2012 at 5:11 AM, Siddhesh Poyarekar <siddhesh@redhat.com> wrote:
> >
> > I understand that the behaviour is undefined, but this is easily
> > avoidable by skipping removal of the exits if it results in an infinite
> > loop.  Attached patch does exactly that.
> 
> I don't mind saying that GCC should define cases that the language
> standards leave undefined.  But that does not seem to be what this
> patch does.  I don't see why this is a good idea.  It seems to produce
> a program that is unpredictable in a different way.  How does that
> help the user?  If anything an infinite loop might be better, since it
> is more obvious that something is wrong.  Unless I misunderstand.

I think resonable thing to do is to output warning in this case
"Loop reaches undefined effect before any of the exit conditions are satisfied; turned into infinite loop"
or something along these lines?  We can probably even get the location info of
the statement that implied the loop bound.

This is particularly simple case where undefined code is now handled
differently.  What I am more worried about is the case where we wire in
__builtin_unreachable that will stay reachable and the resulting program will
die in difficult to debug way.  I was thinking about adding similar warning
when __builtin_unreachable starts to be unconditional.

Honza

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

[Siddhesh Poyarekar]

On Fri, 9 Nov 2012 17:34:26 +0100, Jan wrote:
> > I don't mind saying that GCC should define cases that the language
> > standards leave undefined.  But that does not seem to be what this
> > patch does.  I don't see why this is a good idea.  It seems to
> > produce a program that is unpredictable in a different way.  How
> > does that help the user?  If anything an infinite loop might be
> > better, since it is more obvious that something is wrong.  Unless I
> > misunderstand.
> 
> I think resonable thing to do is to output warning in this case
> "Loop reaches undefined effect before any of the exit conditions are
> satisfied; turned into infinite loop" or something along these
> lines?  We can probably even get the location info of the statement
> that implied the loop bound.

I had reckoned that the behaviour could be reverted to what was before
while I figure out a way to get the warning in place for both cases,
i.e. with tree-vrp (where max_loop_iterations now causes the loop to be
folded away in -O2) and this unroll case (in -O1).  I'll look at
getting a warning for the tree-vrp case separately if the infinite loop
behaviour needs to be retained.

An infinite loop without the warning breaks diagnostic apps like
valgrind since they are no longer in a position to detect this.  The
user would then have to somehow conclude that their loop loops
infinitely because they have a beyond-array-bounds access in it.
However, the infinite loop could be OK if there is an explicit warning
telling the user that it's going to happen.  I already have some rough
code in place to do the warning against the loop header, so I'll clean
it up to issue a warning for all exit points beyond the upper bound
when we see that no exits remain.  It will break a few existing test
cases though - I had posted a patch to fix those earlier today:

http://gcc.gnu.org/ml/gcc-patches/2012-11/msg00722.html

Thanks,
Siddhesh

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

[Siddhesh Poyarekar]

On Fri, 9 Nov 2012 22:51:45 +0530, Siddhesh wrote:
> I had reckoned that the behaviour could be reverted to what was before
> while I figure out a way to get the warning in place for both cases,
> i.e. with tree-vrp (where max_loop_iterations now causes the loop to
> be folded away in -O2) and this unroll case (in -O1).  I'll look at
> getting a warning for the tree-vrp case separately if the infinite
> loop behaviour needs to be retained.

I'm sorry, I won't be able to get this done today.  The patch causes a
regression with torture/pr49518.c where it gives out the warning when
it shouldn't.  I had seen this warning earlier (with the earlier
behaviour of not removing the exits) and fixed it, but it has reappeared
now, perhaps due to some recent patch that removes more exits or
something else.  I'll get back on this late next week since I'll be
offline for most of the week (it's holiday season here in India).


Siddhesh

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

[Siddhesh Poyarekar]

[-- Attachment #1: Type: text/plain, Size: 950 bytes --]

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.

[-- Attachment #2: w.patch --]
[-- Type: text/x-patch, Size: 3434 bytes --]

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.  */

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

[Siddhesh Poyarekar]

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.

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

[Siddhesh Poyarekar]

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.
> 

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

[Siddhesh Poyarekar]

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.
> >