[PATCH] Introduce -Waggressive-loop-optimizations (PR tree-optimization/53265)

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

This patch is an attempt to warn about undefined behavior in simple loops
with known constant number of latch executions, which probably is the most
common case where gcc 4.8 started to turn finite loops involving undefined
behavior before reaching last iteration into endless loops.

Of course the patch doesn't guarantee warning for all such mistakes, and for
loops without known constant number of latch executions it is question on
what exactly we should warn about.  Honza has some prototype patch, perhaps
that could be done if loop->warned_aggressive_loop_optimizations is still
false.

To avoid false positives in some cases (e.g. exp_ch7.adb during bootstrap),
I had to start warning only later on (with the advantage that at that point
loops are preserved and thus we can set flag in the loop structure whether
we've warned already).

I had to tweak a couple of testcases (pr49518.c clearly can result in
undefined behavior conditionally, longbranch2.C also had obvious undefined
behavior (I've verified that r80000 cc1plus generated exactly same size and
insn type code with original and fixed testcase, the only thing that
differed were immediates in some instructions due to different field sizes).
In cunroll-10.c we no longer do anything as it had known constant number of
latch executions, thus no undefined behavior discovery is performed.
In libgcc, the DW_CFA_GNU_window_save handling code was hardcoding SPARC
register window setup, but that is also undefined behavior on targets that
have fewer than 32 DWARF_FRAME_REGISTERS.  I've just shut it up there, after
all DW_CFA_GNU_window_save is only ever used on SPARC anyway.

I've bootstrapped/regtested the patch together with a debugging patch to
show where the last hunk in estimate_numbers_of_iterations_loop actually
changed anything.  It happened in
../../gcc/ada/exp_ch7.adb:3540 (see the PR, in dead code), we'd need a
copyprop pass with cfgcleanup before cunrolli to avoid that,
then in {sse4_2,avx}-vpcmp{i,e}strm-{1,2}.c
/usr/src/gcc/gcc/testsuite/gcc.target/i386/sse4_2-pcmpstr.h:339
(reduced testcase -O2:
short t[8];
static inline void bar (int x, int y)
{
  short s[8]; int i, d = (x & 1) == 0 ? 16 : 8;
  if (x & 0x40) for (i = 0; i < d; i++) if (d == 8) s[i] = (y & (1 << i)) ? -1 : 0;
  __builtin_memcpy (t, s, sizeof s);
}
void foo (int y)
{
  bar (0x26, y);
}
) - here number_of_latch_iterations returns 0, apparently because it finds
out that the loop will be never executed.
Then gcc.dg/torture/pr49518.c:11 (see above, ok) and gcc.dg/pr53265.c
(expected, many).  So, I think we're fine.

Ok for 4.8?

2013-03-13  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/53265
	* common.opt (Waggressive-loop-optimizations): New option.
	* tree-ssa-loop-niter.c: Include tree-pass.h.
	(do_warn_aggressive_loop_optimizations): New function.
	(record_estimate): Call it.  Don't add !is_exit bounds to loop->bounds
	if number_of_latch_executions returned constant.
	(estimate_numbers_of_iterations_loop): Call number_of_latch_executions
	early.  If number_of_latch_executions returned constant, set
	nb_iterations_upper_bound back to it.
	* cfgloop.h (struct loop): Add warned_aggressive_loop_optimizations
	field.
	* Makefile.in (tree-ssa-loop-niter.o): Depend on $(TREE_PASS_H).
	* doc/invoke.texi (-Wno-aggressive-loop-optimizations): Document.

	* gcc.dg/pr53265.c: New test.
	* gcc.dg/torture/pr49518.c: Add -Wno-aggressive-loop-optimizations
	to dg-options.
	* g++.dg/opt/longbranch2.C (EBCOTLut): Double sizes of a2 and a3
	arrays.
	* gcc.dg/tree-ssa/cunroll-10.c (main): Rename to foo.  Add argument
	n, use it as high bound instead of 4.

	* unwind-dw2.c (execute_cfa_program): Avoid
	-Waggressive-array-optimizations warnings for DW_CFA_GNU_window_save
	on targets with DWARF_FRAME_REGISTERS < 32.

	* testsuite/libmudflap.c/fail37-frag.c: Add optimization barrier.

--- gcc/common.opt.jj	2013-03-12 09:59:34.692099982 +0100
+++ gcc/common.opt	2013-03-12 13:47:08.922161154 +0100
@@ -505,6 +505,10 @@ Waggregate-return
 Common Var(warn_aggregate_return) Warning
 Warn about returning structures, unions or arrays
 
+Waggressive-loop-optimizations
+Common Var(warn_aggressive_loop_optimizations) Init(1) Warning
+Warn if a loop with constant number of iterations triggers undefined behavior
+
 Warray-bounds
 Common Var(warn_array_bounds) Warning
 Warn if an array is accessed out of bounds
--- gcc/tree-ssa-loop-niter.c.jj	2013-03-12 09:59:34.740099692 +0100
+++ gcc/tree-ssa-loop-niter.c	2013-03-13 11:19:02.100060913 +0100
@@ -37,6 +37,7 @@ along with GCC; see the file COPYING3.
 #include "flags.h"
 #include "diagnostic-core.h"
 #include "tree-inline.h"
+#include "tree-pass.h"
 
 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
 
@@ -2525,6 +2526,40 @@ record_niter_bound (struct loop *loop, d
     loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
 }
 
+/* Emit a -Waggressive-loop-optimizations warning if needed.  */
+
+static void
+do_warn_aggressive_loop_optimizations (struct loop *loop,
+				       double_int i_bound, gimple stmt)
+{
+  /* Don't warn if the loop doesn't have known constant bound.  */
+  if (!loop->nb_iterations
+      || TREE_CODE (loop->nb_iterations) != INTEGER_CST
+      || !warn_aggressive_loop_optimizations
+      /* To avoid warning multiple times for the same loop,
+	 only start warning when we preserve loops.  */
+      || (cfun->curr_properties & PROP_loops) == 0
+      /* Only warn once per loop.  */
+      || loop->warned_aggressive_loop_optimizations
+      /* Only warn if undefined behavior gives us lower estimate than the
+	 known constant bound.  */
+      || i_bound.ucmp (tree_to_double_int (loop->nb_iterations)) >= 0
+      /* And undefined behavior happens unconditionally.  */
+      || !dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt)))
+    return;
+
+  edge e = single_exit (loop);
+  if (e == NULL)
+    return;
+
+  gimple estmt = last_stmt (e->src);
+  warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations,
+	      "iteration %E invokes undefined behavior",
+	      double_int_to_tree (TREE_TYPE (loop->nb_iterations), i_bound));
+  inform (gimple_location (estmt), "containing loop");
+  loop->warned_aggressive_loop_optimizations = true;
+}
+
 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP.  IS_EXIT
    is true if the loop is exited immediately after STMT, and this exit
    is taken at last when the STMT is executed BOUND + 1 times.
@@ -2560,8 +2595,12 @@ record_estimate (struct loop *loop, tree
     return;
 
   /* If we have a guaranteed upper bound, record it in the appropriate
-     list.  */
-  if (upper)
+     list, unless this is an !is_exit bound (i.e. undefined behavior in
+     at_stmt) in a loop with known constant number of iterations.  */
+  if (upper
+      && (is_exit
+	  || loop->nb_iterations == NULL_TREE
+	  || TREE_CODE (loop->nb_iterations) != INTEGER_CST))
     {
       struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound ();
 
@@ -2591,6 +2630,8 @@ record_estimate (struct loop *loop, tree
   if (i_bound.ult (delta))
     return;
 
+  if (upper && !is_exit)
+    do_warn_aggressive_loop_optimizations (loop, i_bound, at_stmt);
   record_niter_bound (loop, i_bound, realistic, upper);
 }
 
@@ -3311,6 +3352,11 @@ estimate_numbers_of_iterations_loop (str
   /* Force estimate compuation but leave any existing upper bound in place.  */
   loop->any_estimate = false;
 
+  /* Ensure that loop->nb_iterations is computed if possible.  If it turns out
+     to be constant, we avoid undefined behavior implied bounds and instead
+     diagnose those loops with -Waggressive-loop-optimizations.  */
+  number_of_latch_executions (loop);
+
   exits = get_loop_exit_edges (loop);
   likely_exit = single_likely_exit (loop);
   FOR_EACH_VEC_ELT (exits, i, ex)
@@ -3345,6 +3391,17 @@ estimate_numbers_of_iterations_loop (str
       bound = gcov_type_to_double_int (nit);
       record_niter_bound (loop, bound, true, false);
     }
+
+  /* If we know the exact number of iterations of this loop, try to
+     not break code with undefined behavior by not recording smaller
+     maximum number of iterations.  */
+  if (loop->nb_iterations
+      && TREE_CODE (loop->nb_iterations) == INTEGER_CST)
+    {
+      loop->any_upper_bound = true;
+      loop->nb_iterations_upper_bound
+	= tree_to_double_int (loop->nb_iterations);
+    }
 }
 
 /* Sets NIT to the estimated number of executions of the latch of the
--- gcc/cfgloop.h.jj	2013-03-12 09:59:34.677100070 +0100
+++ gcc/cfgloop.h	2013-03-12 13:47:08.919161106 +0100
@@ -159,6 +159,10 @@ struct GTY ((chain_next ("%h.next"))) lo
   /* True if the loop can be parallel.  */
   bool can_be_parallel;
 
+  /* True if -Waggressive-loop-optimizations warned about this loop
+     already.  */
+  bool warned_aggressive_loop_optimizations;
+
   /* An integer estimation of the number of iterations.  Estimate_state
      describes what is the state of the estimation.  */
   enum loop_estimation estimate_state;
--- gcc/Makefile.in.jj	2013-03-12 09:59:34.988098249 +0100
+++ gcc/Makefile.in	2013-03-12 13:47:08.919161106 +0100
@@ -2446,7 +2446,7 @@ tree-ssa-loop-niter.o : tree-ssa-loop-ni
    $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \
    $(TREE_INLINE_H) $(DIAGNOSTIC_H) $(TM_H) coretypes.h dumpfile.h \
    $(DIAGNOSTIC_CORE_H) $(FLAGS_H) $(TREE_DATA_REF_H) \
-   $(BASIC_BLOCK_H) $(GGC_H) intl.h $(GIMPLE_PRETTY_PRINT_H)
+   $(BASIC_BLOCK_H) $(GGC_H) intl.h $(GIMPLE_PRETTY_PRINT_H) $(TREE_PASS_H)
 tree-ssa-loop-ivcanon.o : tree-ssa-loop-ivcanon.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \
    $(TREE_INLINE_H) $(DIAGNOSTIC_H) $(TM_H) coretypes.h \
--- gcc/doc/invoke.texi.jj	2013-03-12 14:22:01.000000000 +0100
+++ gcc/doc/invoke.texi	2013-03-12 16:45:04.580807698 +0100
@@ -232,7 +232,8 @@ Objective-C and Objective-C++ Dialects}.
 @xref{Warning Options,,Options to Request or Suppress Warnings}.
 @gccoptlist{-fsyntax-only  -fmax-errors=@var{n}  -Wpedantic @gol
 -pedantic-errors @gol
--w  -Wextra  -Wall  -Waddress  -Waggregate-return  -Warray-bounds @gol
+-w  -Wextra  -Wall  -Waddress  -Waggregate-return  @gol
+-Waggressive-loop-optimizations -Warray-bounds @gol
 -Wno-attributes -Wno-builtin-macro-redefined @gol
 -Wc++-compat -Wc++11-compat -Wcast-align  -Wcast-qual  @gol
 -Wchar-subscripts -Wclobbered  -Wcomment @gol
@@ -4423,6 +4424,12 @@ Warn if any functions that return struct
 called.  (In languages where you can return an array, this also elicits
 a warning.)
 
+@item -Wno-aggressive-loop-optimizations
+@opindex Wno-aggressive-loop-optimizations
+@opindex Waggressive-loop-optimizations
+Warn if in a loop with constant number of iterations the compiler detects
+undefined behavior in some statement during one or more of the iterations.
+
 @item -Wno-attributes
 @opindex Wno-attributes
 @opindex Wattributes
--- gcc/testsuite/gcc.dg/pr53265.c.jj	2013-03-12 13:47:08.922161154 +0100
+++ gcc/testsuite/gcc.dg/pr53265.c	2013-03-13 11:23:52.592338941 +0100
@@ -0,0 +1,156 @@
+/* PR tree-optimization/53265 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -Wall" } */
+
+void bar (void *);
+int baz (int);
+
+void
+fn1 (void)
+{
+  unsigned int a[128];
+  int i;
+
+  for (i = 0; i < 128; ++i)	/* { dg-message "note: containing loop" } */
+    a[i] = i * 0x02000001;	/* { dg-warning "invokes undefined behavior" } */
+  bar (a);
+}
+
+void
+fn2 (void)
+{
+  unsigned long long a[128];
+  int i;
+
+  for (i = 0; i < 128; i++)			/* { dg-message "note: containing loop" } */
+    a[i] = (i + 1LL) * 0x0123456789ABCDEFLL;	/* { dg-warning "invokes undefined behavior" } */
+  bar (a);
+}
+
+void
+fn3 (void)
+{
+  unsigned char a[16], b[16], c[16];
+  int i;
+
+  bar (b);
+  for (i = 0; i < (int) (sizeof (a) / sizeof (a[0])); i++)	/* { dg-message "note: containing loop" } */
+    {
+      c[i + 8] = b[i];	/* { dg-warning "invokes undefined behavior" } */
+      a[i + 8] = b[i + 8];
+    }
+  bar (a);
+  bar (c);
+}
+
+void
+fn4 (void)
+{
+  unsigned int *a[32], *o, i;
+
+  bar (a);
+  for (i = 0; i <= sizeof (a) / sizeof (a[0]); i++)	/* { dg-message "note: containing loop" "" { xfail *-*-* } } */
+    {
+      o = a[i];	/* { dg-warning "invokes undefined behavior" "" { xfail *-*-* } } */
+      bar (o);
+    }
+}
+
+void
+fn5 (void)
+{
+  unsigned short a[23940];
+  unsigned int b[1140];
+  int j;
+
+  bar (b);
+  for (j = 0; j < 1140; j++)	/* { dg-message "note: containing loop" } */
+    a[23940 + j - 950] = b[j];	/* { dg-warning "invokes undefined behavior" } */
+  bar (a);
+}
+
+void
+fn6 (void)
+{
+  double a[4][3], b[12];
+  int i;
+  bar (b);
+  for (i = 0; i < 12; i++)	/* { dg-message "note: containing loop" } */
+    a[0][i] = b[i] / 10000.0;	/* { dg-warning "invokes undefined behavior" } */
+  bar (a);
+}
+
+void
+fn7 (void)
+{
+  int a[16], b, c;
+  bar (a);
+  for (b = a[c = 0]; c < 16; b = a[++c])	/* { dg-warning "invokes undefined behavior" "" { xfail *-*-* } } */
+    baz (b);
+}
+
+/* { dg-message "note: containing loop" "" { xfail *-*-* } 88 } */
+
+const void *va, *vb, *vc, *vd, *ve;
+const void *vf[4];
+void
+fn8 (void)
+{
+  unsigned long i;
+  vf[0] = va; vf[1] = vb; vf[2] = vc; vf[3] = vd;
+  for (i = 0; i < (sizeof (vf) / sizeof (vf[0])); i++)
+    if (!vf[i])
+      vf[i] = ve;
+}
+
+int wa, wb[53][5], wc[53][5];
+
+void
+fn9 (void)
+{
+  int i, j, k;
+  for (i = 0; i < 53; i++)
+    for (j = 16 / (((wa & 1) != 0) ? 8 : 4); j > 0; j--)
+      {
+	int d = 1;
+	if (wb[i][j] == 0 || wc[i][1] != 0)
+	  continue;
+	for (k = 0; k < j; k++)
+	  if (wc[i + k][1])
+	    {
+	      d = 0;
+	      break;
+	    }
+	if (!d)
+	  continue;
+	wc[i][j] = baz (0);
+      }
+}
+
+int xa[18];
+
+void
+fn10 (void)
+{
+  int i;
+  for (i = 16; i < 32; i++)	/* { dg-message "note: containing loop" } */
+    xa[i] = 26;			/* { dg-warning "invokes undefined behavior" } */
+}
+
+__attribute__((noinline)) static void
+fn11 (int x)
+{
+  int i = 1;
+  if (x > 1)
+    do
+      baz (i);
+    while (++i != x);		/* { dg-bogus "invokes undefined behavior" } */
+}
+
+void
+fn12 (void)
+{
+  fn11 (1);
+  fn11 (1);
+  fn11 (1);
+}
--- gcc/testsuite/gcc.dg/torture/pr49518.c	(revision 196628)
+++ gcc/testsuite/gcc.dg/torture/pr49518.c	(working copy)
@@ -1,4 +1,5 @@
 /* { dg-do compile } */
+/* { dg-options "-Wno-aggressive-loop-optimizations" } */
 
 int a, b;
 struct S { unsigned int s, t, u; } c, d = { 0, 1, 0 };
--- gcc/testsuite/g++.dg/opt/longbranch2.C.jj	2011-07-11 10:39:36.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/longbranch2.C	2013-03-13 15:02:59.814892282 +0100
@@ -15,8 +15,8 @@ public:
 
 class EBCOTLut : public JKeeper {
   unsigned char a1[1<<8];   
-  unsigned char a2[1<<8];
-  unsigned char a3[1<<8];
+  unsigned char a2[1<<9];
+  unsigned char a3[1<<9];
   long          a4[1<<9];
 public:
   EBCOTLut(void);
--- gcc/testsuite/gcc.dg/tree-ssa/cunroll-10.c.jj	2012-11-05 08:55:20.000000000 +0100
+++ gcc/testsuite/gcc.dg/tree-ssa/cunroll-10.c	2013-03-13 18:48:20.000000000 +0100
@@ -2,10 +2,11 @@
 /* { dg-options "-O3 -Warray-bounds -fdump-tree-cunroll-details" } */
 int a[3];
 int b[4];
-main()
+int
+foo (int n)
 {
   int i;
-  for (i=0;i<4;i++)
+  for (i=0;i<n;i++)
     if (b[i]==2)
      a[i]++;
 }
--- libgcc/unwind-dw2.c.jj	2013-02-05 09:06:55.000000000 +0100
+++ libgcc/unwind-dw2.c	2013-03-12 16:41:08.665181831 +0100
@@ -1128,11 +1128,12 @@ execute_cfa_program (const unsigned char
 
 	case DW_CFA_GNU_window_save:
 	  /* ??? Hardcoded for SPARC register window configuration.  */
-	  for (reg = 16; reg < 32; ++reg)
-	    {
-	      fs->regs.reg[reg].how = REG_SAVED_OFFSET;
-	      fs->regs.reg[reg].loc.offset = (reg - 16) * sizeof (void *);
-	    }
+	  if (DWARF_FRAME_REGISTERS >= 32)
+	    for (reg = 16; reg < 32; ++reg)
+	      {
+		fs->regs.reg[reg].how = REG_SAVED_OFFSET;
+		fs->regs.reg[reg].loc.offset = (reg - 16) * sizeof (void *);
+	      }
 	  break;
 
 	case DW_CFA_GNU_args_size:
--- libmudflap/testsuite/libmudflap.c/fail37-frag.c.jj	2008-09-05 12:57:41.000000000 +0200
+++ libmudflap/testsuite/libmudflap.c/fail37-frag.c	2013-03-13 11:32:36.925228158 +0100
@@ -13,7 +13,11 @@ main ()
 {
   int i;
   for (i = 0; i < 5; i++)
-    x.s[i].f = 0;
+    {
+      /* Optimization barrier.  Prevent gcc from seeing the undefined behavior.  */
+      __asm ("" : "+r" (i));
+      x.s[i].f = 0;
+    }
   exit (0);
 }
 /* { dg-output "mudflap violation 1.*" } */

	Jakub