[PATCH] Fix PR68963

[PATCH] Fix PR68963

[Richard Biener]

The following patch fixes invalid upper bounds recorded for conditonal
array accesses - it doesn't depend on whether their IV wrap or not
(and we were unsetting 'reliable' only anyway).  In fact conditional
accesses should be good enough for an estimate, just wrapping ones
not.  Until we determine whether the controlling expression is
dependent on the loop IV that's probably the best to do here.

Bootstrap and regtest running on x86_64-unknown-linux-gnu.

Honza, about reliable vs. non-reliable - was that the original intent
or did you want to always record 'reliable' but really reset 'upper'
here?

Thanks,
Richard.

2016-02-22  Richard Biener  <rguenther@suse.de>

	PR middle-end/68963
	* tree-ssa-loop-niter.c (idx_infer_loop_bounds): Do not record an
	upper bound for accesses not always executed.  Do not record an
	estimate for accesses with wrapping IVs.

	* gcc.dg/torture/pr68963.c: New testcase.

Index: gcc/tree-ssa-loop-niter.c
===================================================================
*** gcc/tree-ssa-loop-niter.c	(revision 233598)
--- gcc/tree-ssa-loop-niter.c	(working copy)
*************** idx_infer_loop_bounds (tree base, tree *
*** 3183,3196 ****
        && tree_int_cst_compare (next, high) <= 0)
      return true;
  
!   /* If access is not executed on every iteration, we must ensure that overlow may
!      not make the access valid later.  */
!   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
!       && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num),
! 				step, data->stmt, loop, true))
      reliable = false;
  
!   record_nonwrapping_iv (loop, init, step, data->stmt, low, high, reliable, upper);
    return true;
  }
  
--- 3183,3200 ----
        && tree_int_cst_compare (next, high) <= 0)
      return true;
  
!   /* If access is not executed on every iteration we cannot derive any
!      upper bound.  */
!   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt)))
!     upper = false;
!   /* If the IV of the access may wrap then the array size is not good for
!      an estimate either.  */
!   if (scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num),
! 			     step, data->stmt, loop, true))
      reliable = false;
  
!   record_nonwrapping_iv (loop, init, step, data->stmt, low, high,
! 			 reliable, upper);
    return true;
  }
  
Index: gcc/testsuite/gcc.dg/torture/pr68963.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr68963.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr68963.c	(working copy)
***************
*** 0 ****
--- 1,41 ----
+ /* { dg-do run } */
+ 
+ static const float a[3] = { 1, 2, 3 };
+ int b = 3;
+ 
+ __attribute__((noinline, noclone)) void
+ bar (int x)
+ {
+   if (x != b++)
+     __builtin_abort ();
+ }
+ 
+ void
+ foo (float *x, int y)
+ {
+   int i;
+   for (i = 0; i < 2 * y; ++i)
+     {
+       if (i < y)
+ 	x[i] = a[i];
+       else
+ 	{
+ 	  bar (i);
+ 	  x[i] = a[i - y];
+ 	}
+     }
+ }
+ 
+ int
+ main ()
+ {
+   float x[10];
+   unsigned int i;
+   for (i = 0; i < 10; ++i)
+     x[i] = 1337;
+   foo (x, 3);
+   for (i = 0; i < 10; ++i)
+     if (x[i] != (i < 6 ? (i % 3) + 1 : 1337))
+       __builtin_abort ();
+   return 0;
+ }

Re: [PATCH] Fix PR68963

[Richard Biener]

On Mon, 22 Feb 2016, Richard Biener wrote:

> 
> The following patch fixes invalid upper bounds recorded for conditonal
> array accesses - it doesn't depend on whether their IV wrap or not
> (and we were unsetting 'reliable' only anyway).  In fact conditional
> accesses should be good enough for an estimate, just wrapping ones
> not.  Until we determine whether the controlling expression is
> dependent on the loop IV that's probably the best to do here.
> 
> Bootstrap and regtest running on x86_64-unknown-linux-gnu.
> 
> Honza, about reliable vs. non-reliable - was that the original intent
> or did you want to always record 'reliable' but really reset 'upper'
> here?

Ok, so this was the wrong place to fix and we should actually record
those bounds.  But the actual bound recorded is wrong as
record_nonwrapping_iv for IVs { -y, +, 1 }_1 and an array index
range of [0, 3] falls back to using 0 for the initial value of the
IV for the purpose of niter compute - that's of course only valid
if the stmt is always executed.

And in fact if the IV were { -1, +, 1 }_1 and the array index
range [0, 3] we could conclude the loop doesn't loop at all as
the first iteration would contain undefined behavior (if the
stmt was always executed) - currently we compute an upper bound
of 3 - (-1) here which is overly conservative.

Bootstrap and regtest running on x86_64-unknown-linux-gnu.

Richard.

2016-02-24  Richard Biener  <rguenther@suse.de>

	PR middle-end/68963
	* tree-ssa-loop-niter.c (derive_constant_upper_bound_ops): Fix
	bogus check.
	(record_nonwrapping_iv): Do not fall back to the low/high bound
	for non-constant IV bases if the stmt is not always executed.

	* gcc.dg/torture/pr68963.c: New testcase.

Index: gcc/testsuite/gcc.dg/torture/pr68963.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr68963.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr68963.c	(working copy)
***************
*** 0 ****
--- 1,41 ----
+ /* { dg-do run } */
+ 
+ static const float a[3] = { 1, 2, 3 };
+ int b = 3;
+ 
+ __attribute__((noinline, noclone)) void
+ bar (int x)
+ {
+   if (x != b++)
+     __builtin_abort ();
+ }
+ 
+ void
+ foo (float *x, int y)
+ {
+   int i;
+   for (i = 0; i < 2 * y; ++i)
+     {
+       if (i < y)
+ 	x[i] = a[i];
+       else
+ 	{
+ 	  bar (i);
+ 	  x[i] = a[i - y];
+ 	}
+     }
+ }
+ 
+ int
+ main ()
+ {
+   float x[10];
+   unsigned int i;
+   for (i = 0; i < 10; ++i)
+     x[i] = 1337;
+   foo (x, 3);
+   for (i = 0; i < 10; ++i)
+     if (x[i] != (i < 6 ? (i % 3) + 1 : 1337))
+       __builtin_abort ();
+   return 0;
+ }
Index: gcc/tree-ssa-loop-niter.c
===================================================================
*** gcc/tree-ssa-loop-niter.c	(revision 233634)
--- gcc/tree-ssa-loop-niter.c	(working copy)
*************** derive_constant_upper_bound_ops (tree ty
*** 2757,2763 ****
  				 enum tree_code code, tree op1)
  {
    tree subtype, maxt;
!   widest_int bnd, max, mmax, cst;
    gimple *stmt;
  
    if (INTEGRAL_TYPE_P (type))
--- 2757,2763 ----
  				 enum tree_code code, tree op1)
  {
    tree subtype, maxt;
!   widest_int bnd, max, cst;
    gimple *stmt;
  
    if (INTEGRAL_TYPE_P (type))
*************** derive_constant_upper_bound_ops (tree ty
*** 2823,2830 ****
  	  /* OP0 + CST.  We need to check that
  	     BND <= MAX (type) - CST.  */
  
! 	  mmax -= cst;
! 	  if (wi::ltu_p (bnd, max))
  	    return max;
  
  	  return bnd + cst;
--- 2823,2830 ----
  	  /* OP0 + CST.  We need to check that
  	     BND <= MAX (type) - CST.  */
  
! 	  widest_int mmax = max - cst;
! 	  if (wi::leu_p (bnd, mmax))
  	    return max;
  
  	  return bnd + cst;
*************** record_nonwrapping_iv (struct loop *loop
*** 3065,3071 ****
  	  && get_range_info (orig_base, &min, &max) == VR_RANGE
  	  && wi::gts_p (high, max))
  	base = wide_int_to_tree (unsigned_type, max);
!       else if (TREE_CODE (base) != INTEGER_CST)
  	base = fold_convert (unsigned_type, high);
        delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
        step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
--- 3065,3073 ----
  	  && get_range_info (orig_base, &min, &max) == VR_RANGE
  	  && wi::gts_p (high, max))
  	base = wide_int_to_tree (unsigned_type, max);
!       else if (TREE_CODE (base) != INTEGER_CST
! 	       && dominated_by_p (CDI_DOMINATORS,
! 				  loop->latch, gimple_bb (stmt)))
  	base = fold_convert (unsigned_type, high);
        delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
        step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
*************** record_nonwrapping_iv (struct loop *loop
*** 3080,3086 ****
  	  && get_range_info (orig_base, &min, &max) == VR_RANGE
  	  && wi::gts_p (min, low))
  	base = wide_int_to_tree (unsigned_type, min);
!       else if (TREE_CODE (base) != INTEGER_CST)
  	base = fold_convert (unsigned_type, low);
        delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
      }
--- 3082,3090 ----
  	  && get_range_info (orig_base, &min, &max) == VR_RANGE
  	  && wi::gts_p (min, low))
  	base = wide_int_to_tree (unsigned_type, min);
!       else if (TREE_CODE (base) != INTEGER_CST
! 	       && dominated_by_p (CDI_DOMINATORS,
! 				  loop->latch, gimple_bb (stmt)))
  	base = fold_convert (unsigned_type, low);
        delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
      }