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

login
register
mail settings
Submitter Siddhesh Poyarekar
Date Nov. 9, 2012, 1:11 p.m.
Message ID <20121109184142.597e9d2c@spoyarek>
Download mbox | patch
Permalink /patch/198050/
State New
Headers show

Comments

Siddhesh Poyarekar - Nov. 9, 2012, 1:11 p.m.
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.
Ian Taylor - Nov. 9, 2012, 3:26 p.m.
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
Jan Hubicka - Nov. 9, 2012, 4:34 p.m.
> 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
Siddhesh Poyarekar - Nov. 9, 2012, 5:21 p.m.
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
Siddhesh Poyarekar - Nov. 10, 2012, 3:21 p.m.
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

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