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

[Siddhesh Poyarekar <siddhesh at redhat dot com>]

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.

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