[patch] Warn on undefined loop exit

[patch] Warn on undefined loop exit

[Andrew Stubbs]

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

This patch adds the following warning message:

undefined.c:9:20: warning: statement may be undefined in the final loop 
iteration. [-Waggressive-loop-optimizations]
    for (i = 0; array[i] && i < 5; i++)
                     ^

(Where the code ought to read "i < 5 && array[i]".)

The tree-ssa loop optimizations already eliminate useless loop-exit 
conditions (i.e. conditions that will never be true). Unfortunately, 
they also eliminate exit conditions that can be true, but only after 
undefined behaviour has occurred. Typically, that means that the 
undefined behaviour becomes an infinite loop (if it doesn't happen to 
crash, of course), and that's surprising. It also looks more like a 
compiler bug than a crash does.

The new warning should highlight these cases but does not actually 
change anything. I've included a comment where the compiler could be 
adjusted to avoid the surprising optimization. Would it be appropriate 
to do so?

OK to commit?

Andrew

[-- Attachment #2: undef-warning.patch --]
[-- Type: text/x-patch, Size: 3623 bytes --]

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

	gcc/
	* tree-ssa-loop-niter.c (maybe_lower_iteration_bound): Set
	loop->possibly_undefined_stmt appropriately.
	* tree-ssa-loop-ivcanon.c (remove_redundant_iv_tests): Warn if
	any tests have loop->possibly_undefined_stmt set.
	* cfgloop.h (struct loop): Add field "possibly_undefined_stmt".

	gcc/testsuite/
	* gcc.dg/undefined-loop.c: New file.

Index: gcc/tree-ssa-loop-niter.c
===================================================================
--- gcc/tree-ssa-loop-niter.c	(revision 217085)
+++ gcc/tree-ssa-loop-niter.c	(working copy)
@@ -3320,6 +3320,7 @@
   visited = BITMAP_ALLOC (NULL);
   bitmap_set_bit (visited, loop->header->index);
   found_exit = false;
+  gimple problem_stmt = NULL;
 
   do
     {
@@ -3334,6 +3335,8 @@
 	  if (not_executed_last_iteration->contains (stmt))
 	    {
 	      stmt_found = true;
+	      if (!problem_stmt)
+		problem_stmt = stmt;
 	      break;
 	    }
 	  if (gimple_has_side_effects (stmt))
@@ -3375,6 +3378,8 @@
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "Reducing loop iteration estimate by 1; "
 		 "undefined statement must be executed at the last iteration.\n");
+      if (!loop->possibly_undefined_stmt)
+	loop->possibly_undefined_stmt = problem_stmt;
       record_niter_bound (loop, loop->nb_iterations_upper_bound - 1,
 			  false, true);
     }
Index: gcc/testsuite/gcc.dg/undefined-loop.c
===================================================================
--- gcc/testsuite/gcc.dg/undefined-loop.c	(revision 0)
+++ gcc/testsuite/gcc.dg/undefined-loop.c	(revision 0)
@@ -0,0 +1,15 @@
+/* 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] && i < 5; i++) /* { dg-warning "statement may be undefined in the final loop iteration" } */
+    doSomething(array[i]);
+}
Index: gcc/tree-ssa-loop-ivcanon.c
===================================================================
--- gcc/tree-ssa-loop-ivcanon.c	(revision 217085)
+++ gcc/tree-ssa-loop-ivcanon.c	(working copy)
@@ -86,6 +86,7 @@
 #include "target.h"
 #include "tree-cfgcleanup.h"
 #include "builtins.h"
+#include "diagnostic-core.h"
 
 /* Specifies types of loops that may be unrolled.  */
 
@@ -586,6 +587,18 @@
 			     wi::to_widest (niter.niter)))
 	    continue;
 	  
+	  /* If another loop exit has previously been suspected of causing
+	     undefined behavior then removing other exit statements may be
+	     unsafe. */
+	  if (loop->possibly_undefined_stmt)
+	    {
+	      warning_at (gimple_location (loop->possibly_undefined_stmt),
+			  OPT_Waggressive_loop_optimizations,
+			  "statement may be undefined in the final loop iteration.");
+	      /* We could avoid the unsafe optimzation here:
+	         continue;  */
+	    }
+
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    {
 	      fprintf (dump_file, "Removed pointless exit: ");
Index: gcc/cfgloop.h
===================================================================
--- gcc/cfgloop.h	(revision 217085)
+++ gcc/cfgloop.h	(working copy)
@@ -179,6 +179,10 @@
      already.  */
   bool warned_aggressive_loop_optimizations;
 
+  /* Set if the loop count was reduced do to a statement that is undefined
+     in the final iteration.  */
+  gimple possibly_undefined_stmt;
+
   /* An integer estimation of the number of iterations.  Estimate_state
      describes what is the state of the estimation.  */
   enum loop_estimation estimate_state;

Re: [patch] Warn on undefined loop exit

[Andrew Stubbs]

Ping.

On 05/11/14 21:45, Andrew Stubbs wrote:
> This patch adds the following warning message:
>
> undefined.c:9:20: warning: statement may be undefined in the final loop
> iteration. [-Waggressive-loop-optimizations]
>     for (i = 0; array[i] && i < 5; i++)
>                      ^
>
> (Where the code ought to read "i < 5 && array[i]".)
>
> The tree-ssa loop optimizations already eliminate useless loop-exit
> conditions (i.e. conditions that will never be true). Unfortunately,
> they also eliminate exit conditions that can be true, but only after
> undefined behaviour has occurred. Typically, that means that the
> undefined behaviour becomes an infinite loop (if it doesn't happen to
> crash, of course), and that's surprising. It also looks more like a
> compiler bug than a crash does.
>
> The new warning should highlight these cases but does not actually
> change anything. I've included a comment where the compiler could be
> adjusted to avoid the surprising optimization. Would it be appropriate
> to do so?
>
> OK to commit?
>
> Andrew

Re: [patch] Warn on undefined loop exit

[Richard Biener]

On Wed, Nov 5, 2014 at 10:45 PM, Andrew Stubbs <ams@codesourcery.com> wrote:
> This patch adds the following warning message:
>
> undefined.c:9:20: warning: statement may be undefined in the final loop
> iteration. [-Waggressive-loop-optimizations]
>    for (i = 0; array[i] && i < 5; i++)
>                     ^
>
> (Where the code ought to read "i < 5 && array[i]".)
>
> The tree-ssa loop optimizations already eliminate useless loop-exit
> conditions (i.e. conditions that will never be true). Unfortunately, they
> also eliminate exit conditions that can be true, but only after undefined
> behaviour has occurred. Typically, that means that the undefined behaviour
> becomes an infinite loop (if it doesn't happen to crash, of course), and
> that's surprising. It also looks more like a compiler bug than a crash does.
>
> The new warning should highlight these cases but does not actually change
> anything. I've included a comment where the compiler could be adjusted to
> avoid the surprising optimization. Would it be appropriate to do so?
>
> OK to commit?

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

Thanks,
Richard.

> Andrew

Re: [patch] Warn on undefined loop exit

[Andrew Stubbs]

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'm going to keep looking, but any suggestions would be appreciated.

Andrew

Re: [patch] Warn on undefined loop exit

[Andrew Stubbs]

[-- 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;
 }
 

Re: [patch] Warn on undefined loop exit

[Marek Polacek]

On Wed, Nov 19, 2014 at 04:32:43PM +0000, Andrew Stubbs wrote:
> +		     if (warning_at (gimple_location (elt->stmt),
> +				     OPT_Waggressive_loop_optimizations,
> +				     "Loop exit may only be reached after undefined behaviour."))

Warnings should start with a lowercase and should be without
a fullstop at the end.

	Marek

Re: [patch] Warn on undefined loop exit

[Andrew Stubbs]

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

On 19/11/14 16:39, Marek Polacek wrote:
> On Wed, Nov 19, 2014 at 04:32:43PM +0000, Andrew Stubbs wrote:
>> +		     if (warning_at (gimple_location (elt->stmt),
>> +				     OPT_Waggressive_loop_optimizations,
>> +				     "Loop exit may only be reached after undefined behaviour."))
>
> Warnings should start with a lowercase and should be without
> a fullstop at the end.

Fixed, and I spotted a britishism too.

Andrew

[-- Attachment #2: undefined-loop.patch --]
[-- Type: text/x-patch, Size: 4580 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..80260cc
--- /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 behavior" } */
+       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..dbea62c
--- /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 behavior" } */
+       && i < 100;   /* { dg-warning "loop exit may only be reached after undefined behavior" } */
+       i++)
+    doSomething(array1[i]);
+}
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index fd32d28..0365505 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 behavior"))
+		       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;
 }
 

Re: [patch] Warn on undefined loop exit

[Richard Biener]

On Wed, Nov 19, 2014 at 9:19 PM, Andrew Stubbs <ams@codesourcery.com> wrote:
> On 19/11/14 16:39, Marek Polacek wrote:
>>
>> On Wed, Nov 19, 2014 at 04:32:43PM +0000, Andrew Stubbs wrote:
>>>
>>> +                    if (warning_at (gimple_location (elt->stmt),
>>> +                                    OPT_Waggressive_loop_optimizations,
>>> +                                    "Loop exit may only be reached after
>>> undefined behaviour."))
>>
>>
>> Warnings should start with a lowercase and should be without
>> a fullstop at the end.
>
>
> Fixed, and I spotted a britishism too.

If it's really duplicated code can you split it out to a function?

+      if (OPT_Waggressive_loop_optimizations)
+    {

this doesn't do what you think it does ;)  The variable to check is
warn_aggressive_loop_optimizations.

+      if (exit_warned && problem_stmts != vNULL)
+        {

!problem_stmts.empty ()

Otherwise it looks ok.

Thanks,
Richard.

> Andrew

Re: [patch] Warn on undefined loop exit

[Marek Polacek]

On Thu, Nov 20, 2014 at 05:27:35PM +0100, Richard Biener wrote:
> +      if (exit_warned && problem_stmts != vNULL)
> +        {
> 
> !problem_stmts.empty ()

/home/marek/src/gcc/gcc/tree-ssa-loop-niter.c: In function ‘void maybe_lower_iteration_bound(loop*)’:
/home/marek/src/gcc/gcc/tree-ssa-loop-niter.c:3420:38: error: ‘struct vec<gimple_statement_base*>’ has no member named ‘empty’
    if (exit_warned && !problem_stmts.empty ())
                                      ^
make: *** [tree-ssa-loop-niter.o] Error 1

I'm applying the following.

2014-11-20  Marek Polacek  <polacek@redhat.com>

	* tree-ssa-loop-niter.c (maybe_lower_iteration_bound): Fix typo.

diff --git gcc/tree-ssa-loop-niter.c gcc/tree-ssa-loop-niter.c
index 8ba365c..d17227f 100644
--- gcc/tree-ssa-loop-niter.c
+++ gcc/tree-ssa-loop-niter.c
@@ -3417,7 +3417,7 @@ maybe_lower_iteration_bound (struct loop *loop)
 		}
 	    }
 
-	  if (exit_warned && !problem_stmts.empty ())
+	  if (exit_warned && !problem_stmts.is_empty ())
 	    {
 	      gimple stmt;
 	      int index;

	Marek

Re: [patch] Warn on undefined loop exit

[Andrew Stubbs]

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

On 20/11/14 16:27, Richard Biener wrote:
> If it's really duplicated code can you split it out to a function?
>
> +      if (OPT_Waggressive_loop_optimizations)
> +    {
>
> this doesn't do what you think it does ;)  The variable to check is
> warn_aggressive_loop_optimizations.
>
> +      if (exit_warned && problem_stmts != vNULL)
> +        {
>
> !problem_stmts.empty ()
>
> Otherwise it looks ok.

I've committed the attached. I'll work up a patch to dedup the condition 
shortly.

Andrew


[-- Attachment #2: undef-warning.patch --]
[-- Type: text/x-patch, Size: 4581 bytes --]

2014-11-20  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..80260cc
--- /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 behavior" } */
+       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..dbea62c
--- /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 behavior" } */
+       && i < 100;   /* { dg-warning "loop exit may only be reached after undefined behavior" } */
+       i++)
+    doSomething(array1[i]);
+}
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index fd32d28..486e1a4 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 (warn_aggressive_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 behavior"))
+		       exit_warned = true;
+		   }
+		}
+	    }
+
+	  if (exit_warned && !problem_stmts.empty ())
+	    {
+	      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;
 }
 

Re: [patch] Warn on undefined loop exit

[Andrew Stubbs]

On 20/11/14 20:55, Marek Polacek wrote:
> On Thu, Nov 20, 2014 at 05:27:35PM +0100, Richard Biener wrote:
>> +      if (exit_warned && problem_stmts != vNULL)
>> +        {
>>
>> !problem_stmts.empty ()
>
> /home/marek/src/gcc/gcc/tree-ssa-loop-niter.c: In function ‘void maybe_lower_iteration_bound(loop*)’:
> /home/marek/src/gcc/gcc/tree-ssa-loop-niter.c:3420:38: error: ‘struct vec<gimple_statement_base*>’ has no member named ‘empty’
>      if (exit_warned && !problem_stmts.empty ())
>                                        ^

Oops, I had spotted that, but somewhere in the "svn up" process I've 
reapplied the broken version. :-(

Sorry for the mistake. I must stop coding late at night ...

Andrew

Re: [patch] Warn on undefined loop exit

[Jakub Jelinek]

On Thu, Nov 20, 2014 at 05:27:35PM +0100, Richard Biener wrote:
> On Wed, Nov 19, 2014 at 9:19 PM, Andrew Stubbs <ams@codesourcery.com> wrote:
> > On 19/11/14 16:39, Marek Polacek wrote:
> >>
> >> On Wed, Nov 19, 2014 at 04:32:43PM +0000, Andrew Stubbs wrote:
> >>>
> >>> +                    if (warning_at (gimple_location (elt->stmt),
> >>> +                                    OPT_Waggressive_loop_optimizations,
> >>> +                                    "Loop exit may only be reached after
> >>> undefined behaviour."))
> >>
> >>
> >> Warnings should start with a lowercase and should be without
> >> a fullstop at the end.
> >
> >
> > Fixed, and I spotted a britishism too.
> 
> If it's really duplicated code can you split it out to a function?
> 
> +      if (OPT_Waggressive_loop_optimizations)
> +    {
> 
> this doesn't do what you think it does ;)  The variable to check is
> warn_aggressive_loop_optimizations.
> 
> +      if (exit_warned && problem_stmts != vNULL)
> +        {
> 
> !problem_stmts.empty ()
> 
> Otherwise it looks ok.

This caused PR64491.  If the loop has multiple exits, the loop might be
exit earlier and so it would be just fine if the other loop exit may only be
reached after undefined behavior.

	Jakub