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

[Richard Biener <rguenther at suse dot de>]

On Wed, 13 Mar 2013, Jakub Jelinek wrote:

> 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?

Looks good to me.

Ok,

Thanks,
Richard.

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

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend