PATCH RFC: Don't move to infinity until you've seen all edges

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

PR tree-optimization/31522 is about a case for which VRP expands to
infinity too early:

int f(int x)
{
  int y;
  if (x <= 4) y = 1;
  else y = x / 4;
  return y <= 0;
}

The first time VRP reaches the PHI node after the if statement, it
sees this:

Visiting PHI node: y_1 = PHI <1(2), y_4(3)>
    Argument #0 (2 -> 4 executable)
	1
	Value: [1, 1]

    Argument #1 (3 -> 4 not executable)


The second time, it sees this:

Visiting PHI node: y_1 = PHI <1(2), y_4(3)>
    Argument #0 (2 -> 4 executable)
	1
	Value: [1, 1]

    Argument #1 (3 -> 4 executable)
	y_4
	Value: [1, 536870911]  EQUIVALENCES: { } (0 elements)


When merging [1, 1] and [1, 536870911], VRP sees that the upper bound
has increased.  To avoid an infinite loop, it returns [1, +INF(OVF)].
For this test case, this then generates an overflow warning with
-Wstrict-overflow.

Of course, in this case, there is no loop and no overflow.  This patch
counts the number of executable edges seen at each PHI node.  It only
pushes to INF(OVF) when the number of executable edges stays the same.
The effect is to handle non-loops correctly at the cost of sometimes
executing one more iteration for loops.

This patch has been bootstrapped and tested on i686-pc-linux-gnu.
Does it look OK?

Ian


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

	PR tree-optimization/31522
	* tree-vrp.c (vr_phi_edge_counts): New static variable.
	(vrp_initialize): Allocate vr_phi_edge_counts.
	(vrp_visit_phi_node): Don't push to infinity if we saw a new
	executable edge.  Drop test for all constants.
	(vrp_finalize): Free vrp_phi_edge_counts.

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

	PR tree-optimization/31522
	* gcc.dg/Wstrict-overflow-16.c: New test.


Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 123724)
+++ gcc/tree-vrp.c	(working copy)
@@ -95,6 +95,11 @@ static sbitmap blocks_visited;
    of values that SSA name N_I may take.  */
 static value_range_t **vr_value;
 
+/* For a PHI node which sets SSA name N_I, VR_COUNTS[I] holds the
+   number of executable edges we saw the last time we visited the
+   node.  */
+static int *vr_phi_edge_counts;
+
 
 /* Return whether TYPE should use an overflow infinity distinct from
    TYPE_{MIN,MAX}_VALUE.  We use an overflow infinity value to
@@ -4305,6 +4310,7 @@ vrp_initialize (void)
   basic_block bb;
 
   vr_value = XCNEWVEC (value_range_t *, num_ssa_names);
+  vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
 
   FOR_EACH_BB (bb)
     {
@@ -5058,7 +5064,7 @@ vrp_visit_phi_node (tree phi)
   tree lhs = PHI_RESULT (phi);
   value_range_t *lhs_vr = get_value_range (lhs);
   value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
-  bool all_const = true;
+  int edges, old_edges;
 
   copy_value_range (&vr_result, lhs_vr);
 
@@ -5068,6 +5074,7 @@ vrp_visit_phi_node (tree phi)
       print_generic_expr (dump_file, phi, dump_flags);
     }
 
+  edges = 0;
   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
     {
       edge e = PHI_ARG_EDGE (phi, i);
@@ -5085,10 +5092,11 @@ vrp_visit_phi_node (tree phi)
 	  tree arg = PHI_ARG_DEF (phi, i);
 	  value_range_t vr_arg;
 
+	  ++edges;
+
 	  if (TREE_CODE (arg) == SSA_NAME)
 	    {
 	      vr_arg = *(get_value_range (arg));
-	      all_const = false;
 	    }
 	  else
 	    {
@@ -5114,14 +5122,20 @@ vrp_visit_phi_node (tree phi)
 	}
     }
 
+  old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)];
+  vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges;
+
   if (vr_result.type == VR_VARYING)
     goto varying;
 
   /* To prevent infinite iterations in the algorithm, derive ranges
      when the new value is slightly bigger or smaller than the
-     previous one.  */
+     previous one.  We don't do this if we have seen a new edge--we
+     only do it the second time we see a new edge.  This helps us
+     avoid an overflow infinity for conditionals which are not in a
+     loop.  */
   if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE
-      && !all_const)
+      && edges <= old_edges)
     {
       if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
 	{
@@ -5700,10 +5714,12 @@ vrp_finalize (void)
 
   free (single_val_range);
   free (vr_value);
+  free (vr_phi_edge_counts);
 
   /* So that we can distinguish between VRP data being available
      and not available.  */
   vr_value = NULL;
+  vr_phi_edge_counts = NULL;
 }
 
 
Index: gcc/testsuite/gcc.dg/Wstrict-overflow-16.c
===================================================================
--- gcc/testsuite/gcc.dg/Wstrict-overflow-16.c	(revision 0)
+++ gcc/testsuite/gcc.dg/Wstrict-overflow-16.c	(revision 0)
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-fstrict-overflow -O2 -Wstrict-overflow" } */
+
+/* From PR 31522.  */
+
+int f (int x) {
+  int y;
+  if (x <= 4) y = 1;
+  else y = x / 4;
+  return y <= 0;
+}