[PATCH] Improve VRP

[PATCH] Improve VRP

[Richard Biener]

This improves VRP of induction variables tested against zero
and handles overflow detection in a less awkward way.  It does
that by, instead of dropping to +-INF on iteration, drop to
+INF-1 or -INF+1 and letting the next iteration figure that out.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Richard.

2014-04-28  Richard Biener  <rguenther@suse.de>

	* tree-vrp.c (vrp_var_may_overflow): Remove.
	(vrp_visit_phi_node): Rather than bumping to +-INF possibly
	with overflow immediately bump to one before that value and
	let iteration figure out overflow status.

	* gcc.dg/tree-ssa/vrp91.c: New testcase.
	* gcc.dg/Wstrict-overflow-14.c: XFAIL.
	* gcc.dg/Wstrict-overflow-15.c: Likewise.
	* gcc.dg/Wstrict-overflow-18.c: Remove XFAIL.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig	2014-04-25 11:53:37.930478725 +0200
--- gcc/tree-vrp.c	2014-04-28 13:05:03.952338031 +0200
*************** adjust_range_with_scev (value_range_t *v
*** 4026,4077 ****
      }
  }
  
- /* Return true if VAR may overflow at STMT.  This checks any available
-    loop information to see if we can determine that VAR does not
-    overflow.  */
- 
- static bool
- vrp_var_may_overflow (tree var, gimple stmt)
- {
-   struct loop *l;
-   tree chrec, init, step;
- 
-   if (current_loops == NULL)
-     return true;
- 
-   l = loop_containing_stmt (stmt);
-   if (l == NULL
-       || !loop_outer (l))
-     return true;
- 
-   chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
-   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
-     return true;
- 
-   init = initial_condition_in_loop_num (chrec, l->num);
-   step = evolution_part_in_loop_num (chrec, l->num);
- 
-   if (step == NULL_TREE
-       || !is_gimple_min_invariant (step)
-       || !valid_value_p (init))
-     return true;
- 
-   /* If we get here, we know something useful about VAR based on the
-      loop information.  If it wraps, it may overflow.  */
- 
-   if (scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
- 			     true))
-     return true;
- 
-   if (dump_file && (dump_flags & TDF_DETAILS) != 0)
-     {
-       print_generic_expr (dump_file, var, 0);
-       fprintf (dump_file, ": loop information indicates does not overflow\n");
-     }
- 
-   return false;
- }
- 
  
  /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
  
--- 4026,4031 ----
*************** vrp_visit_phi_node (gimple phi)
*** 8453,8484 ****
  	  && (cmp_min != 0 || cmp_max != 0))
  	goto varying;
  
!       /* If the new minimum is smaller or larger than the previous
! 	 one, go all the way to -INF.  In the first case, to avoid
! 	 iterating millions of times to reach -INF, and in the
! 	 other case to avoid infinite bouncing between different
! 	 minimums.  */
!       if (cmp_min > 0 || cmp_min < 0)
! 	{
! 	  if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
! 	      || !vrp_var_may_overflow (lhs, phi))
! 	    vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
! 	  else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
! 	    vr_result.min =
! 		negative_overflow_infinity (TREE_TYPE (vr_result.min));
! 	}
! 
!       /* Similarly, if the new maximum is smaller or larger than
! 	 the previous one, go all the way to +INF.  */
!       if (cmp_max < 0 || cmp_max > 0)
! 	{
! 	  if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
! 	      || !vrp_var_may_overflow (lhs, phi))
! 	    vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
! 	  else if (supports_overflow_infinity (TREE_TYPE (vr_result.max)))
! 	    vr_result.max =
! 		positive_overflow_infinity (TREE_TYPE (vr_result.max));
! 	}
  
        /* If we dropped either bound to +-INF then if this is a loop
  	 PHI node SCEV may known more about its value-range.  */
--- 8407,8438 ----
  	  && (cmp_min != 0 || cmp_max != 0))
  	goto varying;
  
!       /* If the new minimum is larger than than the previous one
! 	 retain the old value.  If the new minimum value is smaller
! 	 than the previous one and not -INF go all the way to -INF + 1.
! 	 In the first case, to avoid infinite bouncing between different
! 	 minimums, and in the other case to avoid iterating millions of
! 	 times to reach -INF.  Going to -INF + 1 also lets the following
! 	 iteration compute whether there will be any overflow, at the
! 	 expense of one additional iteration.  */
!       if (cmp_min < 0)
! 	vr_result.min = lhs_vr->min;
!       else if (cmp_min > 0
! 	       && !vrp_val_is_min (vr_result.min))
! 	vr_result.min
! 	  = int_const_binop (PLUS_EXPR,
! 			     vrp_val_min (TREE_TYPE (vr_result.min)),
! 			     build_int_cst (TREE_TYPE (vr_result.min), 1));
! 
!       /* Similarly for the maximum value.  */
!       if (cmp_max > 0)
! 	vr_result.max = lhs_vr->max;
!       else if (cmp_max < 0
! 	       && !vrp_val_is_max (vr_result.max))
! 	vr_result.max
! 	  = int_const_binop (MINUS_EXPR,
! 			     vrp_val_max (TREE_TYPE (vr_result.min)),
! 			     build_int_cst (TREE_TYPE (vr_result.min), 1));
  
        /* If we dropped either bound to +-INF then if this is a loop
  	 PHI node SCEV may known more about its value-range.  */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp91.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp91.c	2014-04-28 13:05:03.981338029 +0200
***************
*** 0 ****
--- 1,22 ----
+ /* { dg-do compile } */
+ /* { dg-options "-S -O2 -fdump-tree-vrp2" } */
+ 
+ unsigned short data;
+ void foo ()
+ {
+   unsigned char  x16;
+   unsigned int i;
+   for (i = 0; i < 8; i++)
+     {
+       x16 = data & 1;
+       data >>= 1;
+       if (x16 == 1)
+ 	{
+ 	  data ^= 0x4;
+ 	}
+       data >>= 1;
+     }
+ }
+ 
+ /* { dg-final { scan-tree-dump "\\\[0, 7\\\]" "vrp2" } } */
+ /* { dg-final { cleanup-tree-dump "vrp2" } } */
Index: gcc/testsuite/gcc.dg/Wstrict-overflow-14.c
===================================================================
*** gcc/testsuite/gcc.dg/Wstrict-overflow-14.c.orig	2007-11-30 13:59:34.000000000 +0100
--- gcc/testsuite/gcc.dg/Wstrict-overflow-14.c	2014-04-28 13:05:19.210336980 +0200
*************** foo (int j)
*** 10,15 ****
    int sum = 0;
  
    for (i = 1; i < j; i += i)
!     sum += i / 16; /* { dg-warning "assuming signed overflow does not occur" "" } */
    return sum;
  }
--- 10,15 ----
    int sum = 0;
  
    for (i = 1; i < j; i += i)
!     sum += i / 16; /* { dg-warning "assuming signed overflow does not occur" ""  { xfail *-*-* } } */
    return sum;
  }
Index: gcc/testsuite/gcc.dg/Wstrict-overflow-15.c
===================================================================
*** gcc/testsuite/gcc.dg/Wstrict-overflow-15.c.orig	2007-11-30 13:59:35.000000000 +0100
--- gcc/testsuite/gcc.dg/Wstrict-overflow-15.c	2014-04-28 13:06:04.487333863 +0200
*************** foo (int j)
*** 10,15 ****
    int sum = 0;
  
    for (i = 1; i < j; i += i)
!     sum += __builtin_abs (i); /* { dg-warning "assuming signed overflow does not occur" "" } */
    return sum;
  }
--- 10,15 ----
    int sum = 0;
  
    for (i = 1; i < j; i += i)
!     sum += __builtin_abs (i); /* { dg-warning "assuming signed overflow does not occur" "" { xfail *-*-* } } */
    return sum;
  }
Index: gcc/testsuite/gcc.dg/Wstrict-overflow-18.c
===================================================================
*** gcc/testsuite/gcc.dg/Wstrict-overflow-18.c.orig	2010-02-16 16:59:28.000000000 +0100
--- gcc/testsuite/gcc.dg/Wstrict-overflow-18.c	2014-04-28 13:08:07.364325403 +0200
*************** foo (struct c *p)
*** 17,23 ****
  
    for (i = 0; i < p->a - p->b; ++i)
      {
!       if (i > 0)  /* { dg-bogus "warning" "" { xfail *-*-* } } */
  	sum += 2;
        bar (p);
      }
--- 17,23 ----
  
    for (i = 0; i < p->a - p->b; ++i)
      {
!       if (i > 0)  /* { dg-bogus "warning" "" } */
  	sum += 2;
        bar (p);
      }