Re: [patch] Warn on undefined loop exit

[Andrew Stubbs <ams@codesourcery.com>]

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

On 13/11/14 21:35, Andrew Stubbs wrote:
> On 12/11/14 11:15, Richard Biener wrote:
>> Please find a better way to communicate possibly_undefined_stmt than
>> enlarging struct loop.  Like associating it with the niter bound
>> we record (so you can also have more than one).
>
> Unfortunately, the bounds get regenerated frequently, but the upper
> bound can only get reduced once, so the subsequent generations would
> lose the possibly_undefined_stmt.
>
> I did originally try warning at the point where the upper bound gets
> reduced, but there were too many false positives. The two part solution
> I found gives the result I was looking for, but maybe there is another way?

I've found a way to do this. There is no longer any need to store 
anything, but it did require duplicating a little code.

The new patch also reports if multiple undefined statements are 
detected, although the existing algorithm only finds one per basic 
block. (It also misses cases that occur after a loop-exit, but would be 
undefined in earlier passes through the loop, but that's another story; 
it catches all cases where a loop-exit can be eliminated.)

I've now got it emitting a warning for both the loop-exit and the 
problem statement. This makes sense to me (on the grounds that it is the 
removed loop-exit that prompted this whole exercise in the first place), 
but others may feel that a warning on the undefined statement itself is 
sufficient.

The new warning looks like this:

./undefined-loop-1.c: In function 'foo':
./undefined-loop-1.c:15:8: warning: Loop exit may only be reached after 
undefined behaviour. [-Waggressive-loop-optimizations]
         && i < 5;
         ^
./undefined-loop-1.c:14:13: note: possible undefined statement is here
         array[i]
              ^

OK to commit?

Andrew

[-- Attachment #2: undefined-loop.patch --]
[-- Type: text/x-patch, Size: 4588 bytes --]

2014-11-19  Andrew Stubbs  <ams@codesourcery.com>

	gcc/
	* tree-ssa-loop-niter.c (maybe_lower_iteration_bound): Warn if a loop
	condition would be removed due to undefined behaviour.

	gcc/testsuite/
	* gcc.dg/undefined-loop-1.c: New file.
	* gcc.dg/undefined-loop-2.c: New file.
---
 gcc/testsuite/gcc.dg/undefined-loop-1.c |   18 ++++++++++++
 gcc/testsuite/gcc.dg/undefined-loop-2.c |   22 +++++++++++++++
 gcc/tree-ssa-loop-niter.c               |   46 +++++++++++++++++++++++++++++++
 3 files changed, 86 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/undefined-loop-1.c
 create mode 100644 gcc/testsuite/gcc.dg/undefined-loop-2.c

diff --git a/gcc/testsuite/gcc.dg/undefined-loop-1.c b/gcc/testsuite/gcc.dg/undefined-loop-1.c
new file mode 100644
index 0000000..bcb16e9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/undefined-loop-1.c
@@ -0,0 +1,18 @@
+/* Check that loops whose final iteration is undefined are detected.  */
+/* { dg-do compile } */
+/* { dg-options "-O2 -Waggressive-loop-optimizations" } */
+
+void doSomething(char);
+
+char array[5];
+
+void
+foo (void)
+{
+  int i;
+  for (i = 0;
+       array[i]  /* { dg-message "note: possible undefined statement is here" } */
+       && i < 5; /* { dg-warning "Loop exit may only be reached after undefined behaviour." } */
+       i++)
+    doSomething(array[i]);
+}
diff --git a/gcc/testsuite/gcc.dg/undefined-loop-2.c b/gcc/testsuite/gcc.dg/undefined-loop-2.c
new file mode 100644
index 0000000..29bcae0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/undefined-loop-2.c
@@ -0,0 +1,22 @@
+/* Check that loops whose final iteration is undefined are detected.  */
+/* { dg-do compile } */
+/* { dg-options "-O2 -Waggressive-loop-optimizations" } */
+
+void doSomething(char);
+
+char array1[5];
+char array2[5];
+
+void
+foo (int p)
+{
+  int i;
+  for (i=0;
+       (p
+        ? array1[i]  /* { dg-message "note: possible undefined statement is here" } */
+        : array2[i]) /* { dg-message "note: possible undefined statement is here" } */
+       && i < 5      /* { dg-warning "Loop exit may only be reached after undefined behaviour." } */
+       && i < 100;   /* { dg-warning "Loop exit may only be reached after undefined behaviour." } */
+       i++)
+    doSomething(array1[i]);
+}
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index fd32d28..7594717 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -3289,6 +3289,7 @@ maybe_lower_iteration_bound (struct loop *loop)
   struct nb_iter_bound *elt;
   bool found_exit = false;
   vec<basic_block> queue = vNULL;
+  vec<gimple> problem_stmts = vNULL;
   bitmap visited;
 
   /* Collect all statements with interesting (i.e. lower than
@@ -3334,6 +3335,7 @@ maybe_lower_iteration_bound (struct loop *loop)
 	  if (not_executed_last_iteration->contains (stmt))
 	    {
 	      stmt_found = true;
+	      problem_stmts.safe_push (stmt);
 	      break;
 	    }
 	  if (gimple_has_side_effects (stmt))
@@ -3377,9 +3379,53 @@ maybe_lower_iteration_bound (struct loop *loop)
 		 "undefined statement must be executed at the last iteration.\n");
       record_niter_bound (loop, loop->nb_iterations_upper_bound - 1,
 			  false, true);
+
+      if (OPT_Waggressive_loop_optimizations)
+	{
+	  bool exit_warned = false;
+	  for (elt = loop->bounds; elt; elt = elt->next)
+	    {
+	      if (elt->is_exit
+		  && wi::gtu_p (elt->bound, loop->nb_iterations_upper_bound))
+		{
+		  basic_block bb = gimple_bb (elt->stmt);
+		  edge exit_edge = EDGE_SUCC (bb, 0);
+		  struct tree_niter_desc niter;
+
+		  if (!loop_exit_edge_p (loop, exit_edge))
+		    exit_edge = EDGE_SUCC (bb, 1);
+
+		  if(number_of_iterations_exit (loop, exit_edge,
+						&niter, false, false)
+		     && integer_onep (niter.assumptions)
+		     && integer_zerop (niter.may_be_zero)
+		     && niter.niter
+		     && TREE_CODE (niter.niter) == INTEGER_CST
+		     && wi::ltu_p (loop->nb_iterations_upper_bound,
+				   wi::to_widest (niter.niter)))
+		   {
+		     if (warning_at (gimple_location (elt->stmt),
+				     OPT_Waggressive_loop_optimizations,
+				     "Loop exit may only be reached after undefined behaviour."))
+		       exit_warned = true;
+		   }
+		}
+	    }
+
+	  if (exit_warned && problem_stmts != vNULL)
+	    {
+	      gimple stmt;
+	      int index;
+	      FOR_EACH_VEC_ELT (problem_stmts, index, stmt)
+		inform (gimple_location (stmt),
+			"possible undefined statement is here");
+	    }
+      }
     }
+
   BITMAP_FREE (visited);
   queue.release ();
+  problem_stmts.release ();
   delete not_executed_last_iteration;
 }