PATCH COMMITTED: Use loop info to improve -Wstrict-overflow

[Ian Lance Taylor <iant at google dot com>]

The appended test case was triggering a warning with
-Wstrict-overflow.  It started with a loop like this:

    for (i = 0; i < n; ++i)
      {
        if (i > 0)
          C1;
        C2;
      }

This is turned into, effectively, this (the real case has some
additional complexities, namely that C2 can modify n, which lead us
away from an easier simplification):

    if (n > 0)
      {
        i = 0;
        goto L2;
      L1:
        if (i > 0)
          C1;
      L2:
        C2;
        ++i;
        if (i < n)
          goto L1;
      }

Now we can eliminate the "i > 0" in the middle of the loop.  However,
because "i" is a variable which increases in a loop, VRP pushes it to
overflow infinity.  Thus eliminating the test relies on undefined
signed overflow.  This is technically correct when n is unsigned and
can vary within the loop, since it is possible for i to wrap all the
way around.  But we've already decided that it's OK to assume that
ordinary loops do not wrap, and we can use that to see that
eliminating "i > 0" is safe.

This patch takes advantage of the information we already have about
whether loop induction variables are likely to overflow.  It uses that
when deciding whether the bound of a variable should be infinity or
overflow infinity.

Bootstrapped and tested on i686-pc-linux-gnu.  Committed to mainline
and 4.2 branch.

Ian


gcc/ChangeLog:
2007-06-04  Ian Lance Taylor  <iant@google.com>

	* tree-vrp.c (adjust_range_with_scev): When loop is not expected
	to overflow, reduce overflow infinity to regular infinity.
	(vrp_var_may_overflow): New static function.
	(vrp_visit_phi_node): Check vrp_var_may_overflow.

gcc/testsuite/ChangeLog:
2007-06-04  Ian Lance Taylor  <iant@google.com>

	* gcc.dg/Wstrict-overflow-18.c: New test.


Index: tree-vrp.c
===================================================================
--- tree-vrp.c	(revision 125269)
+++ tree-vrp.c	(working copy)
@@ -2695,6 +2695,13 @@ adjust_range_with_scev (value_range_t *v
 	      if (compare_values (min, max) == 1)
 		return;
 	    }
+
+	  /* According to the loop information, the variable does not
+	     overflow.  If we think it does, probably because of an
+	     overflow due to arithmetic on a different INF value,
+	     reset now.  */
+	  if (is_negative_overflow_infinity (min))
+	    min = tmin;
 	}
       else
 	{
@@ -2707,12 +2714,60 @@ adjust_range_with_scev (value_range_t *v
 	      if (compare_values (min, max) == 1)
 		return;
 	    }
+
+	  if (is_positive_overflow_infinity (max))
+	    max = tmax;
 	}
 
       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
     }
 }
 
+/* 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, tree stmt)
+{
+  struct loop *l;
+  tree chrec, init, step;
+
+  if (current_loops == NULL)
+    return true;
+
+  l = loop_containing_stmt (stmt);
+  if (l == NULL)
+    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:
    
@@ -5391,7 +5446,8 @@ vrp_visit_phi_node (tree phi)
 	      if (vrp_val_is_max (vr_result.max))
 		goto varying;
 
-	      if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)))
+	      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 =
@@ -5409,7 +5465,8 @@ vrp_visit_phi_node (tree phi)
 	      if (vrp_val_is_min (vr_result.min))
 		goto varying;
 
-	      if (!needs_overflow_infinity (TREE_TYPE (vr_result.max)))
+	      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 =
Index: testsuite/gcc.dg/Wstrict-overflow-18.c
===================================================================
--- testsuite/gcc.dg/Wstrict-overflow-18.c	(revision 0)
+++ testsuite/gcc.dg/Wstrict-overflow-18.c	(revision 0)
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-fstrict-overflow -O2 -Wstrict-overflow" } */
+
+/* Don't warn about an overflow when folding i > 0.  The loop analysis
+   should determine that i does not wrap.  */
+
+struct c { unsigned int a; unsigned int b; };
+extern void bar (struct c *);
+int
+foo (struct c *p)
+{
+  int i;
+  int sum = 0;
+
+  for (i = 0; i < p->a - p->b; ++i)
+    {
+      if (i > 0)
+	sum += 2;
+      bar (p);
+    }
+  return sum;
+}