re PR tree-optimization/22018 (VRP miscompiles multiply)

	PR 22018
	* tree-vrp.c (vrp_int_const_binop): New.
	(extract_range_from_binary_expr): Call it.
	Unify handling division and multiplication.

testsuite/ChangeLog:

	PR 22018
	* gcc.dg/tree-ssa/vrp13.c: Add multiplication tests.
	* gcc.dg/tree-ssa/pr22018.c: New test.

From-SVN: r100978

5 files changed, 282 insertions, 109 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d1fb305..49139aa 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2005-06-15  Diego Novillo  <dnovillo@redhat.com>
+
+	PR 22018
+	* tree-vrp.c (vrp_int_const_binop): New.
+	(extract_range_from_binary_expr): Call it.
+	Unify handling division and multiplication.
+
 2005-06-15  Aldy Hernandez  <aldyh@redhat.com>
 
 	* c-common.h (same_scalar_type_ignoring_signedness): Protoize.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index d6e6a64..53abe65 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2005-06-15  Diego Novillo  <dnovillo@redhat.com>
+
+	PR 22018
+	* gcc.dg/tree-ssa/vrp13.c: Add multiplication tests.
+	* gcc.dg/tree-ssa/pr22018.c: New test.
+
 2005-06-15  Aldy Hernandez  <aldyh@redhat.com>
 
 	* gcc.dg/simd-1.c: Update error messages.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr22018.c b/gcc/testsuite/gcc.dg/tree-ssa/pr22018.c
new file mode 100644
index 0000000..d4d332c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr22018.c
@@ -0,0 +1,32 @@
+/* { dg-do run }  */
+/* { dg-options -O2 }  */
+
+void abort (void);
+void g(int);
+void f(int l)
+{
+  unsigned i;
+  for (i = 0; i < l; i++)
+    {
+      int y = i;
+      /* VRP was wrongfully computing z's range to be [0, 0] instead
+	 of [-INF, 0].  */
+      int z = y*-32;
+      g(z);
+    }
+}
+
+void g(int i)
+{
+  static int x = 0;
+  if (i == 0)
+    x ++;
+  if (x > 1)
+    abort ();
+}
+
+int main(void)
+{
+  f(3);
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp13.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp13.c
index cfc55d8..4b3afdb 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp13.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp13.c
@@ -3,7 +3,7 @@
 
 extern void abort (void);
 
-foo (int i, int j)
+foo_div (int i, int j)
 {
   int k;
 
@@ -112,27 +112,146 @@ foo (int i, int j)
 }
 
 
+foo_mult (int i, int j)
+{
+  int k;
+
+  /* [-20, -10] * [2, 10] should give [-200, -20].  */
+  if (i >= -20)
+    if (i <= -10)
+      if (j >= 2)
+	if (j <= 10)
+	  {
+	    k = i * j;
+	    if (k < -200)
+	      link_error ();
+	    if (k > -20)
+	      link_error ();
+
+	    return k;
+	  }
+
+  /* [-20, -10] * [-10, -2] should give [20, 200].  */
+  if (i >= -20)
+    if (i <= -10)
+      if (j >= -10)
+	if (j <= -2)
+	  {
+	    k = i * j;
+	    if (k < 20)
+	      link_error ();
+	    if (k > 200)
+	      link_error ();
+
+	    return k;
+	  }
+
+  /* [-20, 10] * [2, 10] should give [-200, 100].  */
+  if (i >= -20)
+    if (i <= 10)
+      if (j >= 2)
+	if (j <= 10)
+	  {
+	    k = i * j;
+	    if (k < -200)
+	      link_error ();
+	    if (k > 100)
+	      link_error ();
+
+	    return k;
+	  }
+
+  /* [-20, 10] * [-10, -2] should give [-100, 200].  */
+  if (i >= -20)
+    if (i <= 10)
+      if (j >= -10)
+	if (j <= -2)
+	  {
+	    k = i * j;
+	    if (k < -100)
+	      link_error ();
+	    if (k > 200)
+	      link_error ();
+
+	    return k;
+	  }
+
+  /* [10, 20] * [2, 10] should give [20, 200].  */
+  if (i >= 10)
+    if (i <= 20)
+      if (j >= 2)
+	if (j <= 10)
+	  {
+	    k = i * j;
+	    if (k < 20)
+	      link_error ();
+	    if (k > 200)
+	      link_error ();
+
+	    return k;
+	  }
+
+  /* [10, 20] * [-10, -2] should give [-200, -20].  */
+  if (i >= 10)
+    if (i <= 20)
+      if (j >= -10)
+	if (j <= -2)
+	  {
+	    k = i * j;
+	    if (k < -200)
+	      link_error ();
+	    if (k > -20)
+	      link_error ();
+
+	    return k;
+	  }
+
+  abort ();
+}
+
+
 main()
 {
-  if (foo (-10, 5) != -2)
+  if (foo_div (-10, 5) != -2)
+    abort ();
+
+  if (foo_div (-16, 4) != -4)
+    abort ();
+
+  if (foo_div (-15, -5) != 3)
+    abort ();
+
+  if (foo_div (8, 2) != 4)
+    abort ();
+
+  if (foo_div (10, -2) != -5)
+    abort ();
+
+  if (foo_div (20, 5) != 4)
+    abort ();
+
+  if (foo_div (15, -3) != -5)
+    abort ();
+
+  if (foo_mult (-10, 5) != -50)
     abort ();
 
-  if (foo (-16, 4) != -4)
+  if (foo_mult (-16, 4) != -64)
     abort ();
 
-  if (foo (-15, -5) != 3)
+  if (foo_mult (-15, -5) != 75)
     abort ();
 
-  if (foo (8, 2) != 4)
+  if (foo_mult (8, 2) != 16)
     abort ();
 
-  if (foo (10, -2) != -5)
+  if (foo_mult (10, -2) != -20)
     abort ();
 
-  if (foo (20, 5) != 4)
+  if (foo_mult (20, 5) != 100)
     abort ();
 
-  if (foo (15, -3) != -5)
+  if (foo_mult (15, -3) != -45)
     abort ();
 
   return 0;
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 24078a7..2569267 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -969,6 +969,50 @@ extract_range_from_ssa_name (value_range_t *vr, tree var)
 }
 
 
+/* Wrapper around int_const_binop.  If the operation overflows and we
+   are not using wrapping arithmetic, then adjust the result to be
+   -INF or +INF depending on CODE, VAL1 and VAL2.  */
+
+static inline tree
+vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
+{
+  tree res;
+
+  if (flag_wrapv)
+    return int_const_binop (code, val1, val2, 0);
+
+  /* If we are not using wrapping arithmetic, operate symbolically
+     on -INF and +INF.  */
+  res = int_const_binop (code, val1, val2, 0);
+
+  /* If the operation overflowed but neither VAL1 nor VAL2 are
+     overflown, return -INF or +INF depending on whether VAL1 CODE
+     VAL2 is a growing function or not.  */
+  if (TREE_OVERFLOW (res)
+      && !TREE_OVERFLOW (val1)
+      && !TREE_OVERFLOW (val2))
+    {
+      bool grows = false;
+      int sgn1 = tree_int_cst_sgn (val1);
+      int sgn2 = tree_int_cst_sgn (val2);
+
+      /* Notice that we only need to handle the restricted set of
+	 operations handled by extract_range_from_binary_expr.  */
+      if (((code == PLUS_EXPR || code == MAX_EXPR) && sgn2 >= 0)
+	  || (code == MULT_EXPR && sgn1 == sgn2)
+	  || (code == MINUS_EXPR && sgn2 < 0))
+	grows = true;
+
+      if (grows)
+	return TYPE_MAX_VALUE (TREE_TYPE (res));
+      else
+	return TYPE_MIN_VALUE (TREE_TYPE (res));
+    }
+
+  return res;
+}
+
+
 /* Extract range information from a binary expression EXPR based on
    the ranges of each of its operands and the expression code.  */
 
@@ -1076,96 +1120,85 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr)
       max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
     }
   else if (code == PLUS_EXPR
-	   || code == MULT_EXPR
 	   || code == MIN_EXPR
 	   || code == MAX_EXPR)
     {
       /* For operations that make the resulting range directly
 	 proportional to the original ranges, apply the operation to
 	 the same end of each range.  */
-      min = int_const_binop (code, vr0.min, vr1.min, 0);
-      max = int_const_binop (code, vr0.max, vr1.max, 0);
+      min = vrp_int_const_binop (code, vr0.min, vr1.min);
+      max = vrp_int_const_binop (code, vr0.max, vr1.max);
     }
-  else if (code == TRUNC_DIV_EXPR
+  else if (code == MULT_EXPR
+	   || code == TRUNC_DIV_EXPR
 	   || code == FLOOR_DIV_EXPR
 	   || code == CEIL_DIV_EXPR
 	   || code == EXACT_DIV_EXPR
 	   || code == ROUND_DIV_EXPR)
     {
-      tree zero;
+      tree val[4];
+      size_t i;
+
+      /* Multiplications and divisions are a bit tricky to handle,
+	 depending on the mix of signs we have in the two ranges, we
+	 need to operate on different values to get the minimum and
+	 maximum values for the new range.  One approach is to figure
+	 out all the variations of range combinations and do the
+	 operations.
 
-      /* Divisions are a bit tricky to handle, depending on the mix of
-	 signs we have in the two range, we will need to divide
-	 different values to get the minimum and maximum values for
-	 the new range.  If VR1 includes zero, the result is VARYING.  */
-      if (range_includes_zero_p (&vr1))
+	 However, this involves several calls to compare_values and it
+	 is pretty convoluted.  It's simpler to do the 4 operations
+	 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
+	 MAX1) and then figure the smallest and largest values to form
+	 the new range.  */
+
+      /* Divisions by zero result in a VARYING value.  */
+      if (code != MULT_EXPR && range_includes_zero_p (&vr1))
 	{
 	  set_value_range_to_varying (vr);
 	  return;
 	}
 
-      /* We have three main variations to handle for VR0: all negative
-	 values, all positive values and a mix of negative and
-	 positive.  For each of these, we need to consider if VR1 is
-	 all negative or all positive.  In total, there are 6
-	 combinations to handle.  */
-      zero = build_int_cst (TREE_TYPE (expr), 0);
-      if (compare_values (vr0.max, zero) == -1)
-	{
-	  /* VR0 is all negative.  */
-	  if (compare_values (vr1.min, zero) == 1)
-	    {
-	      /* If VR1 is all positive, the new range is obtained
-		 with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MAX].  */
-	      min = int_const_binop (code, vr0.min, vr1.min, 0);
-	      max = int_const_binop (code, vr0.max, vr1.max, 0);
-	    }
-	  else
-	    {
-	      /* If VR1 is all negative, the new range is obtained
-		 with [VR0.MAX / VR1.MIN, VR0.MIN / VR1.MAX].  */
-	      gcc_assert (compare_values (vr1.max, zero) == -1);
-	      min = int_const_binop (code, vr0.max, vr1.min, 0);
-	      max = int_const_binop (code, vr0.min, vr1.max, 0);
-	    }
-	}
-      else if (range_includes_zero_p (&vr0))
-	{
-	  /* VR0 is a mix of negative and positive values.  */
-	  if (compare_values (vr1.min, zero) == 1)
-	    {
-	      /* If VR1 is all positive, the new range is obtained
-		 with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MIN].  */
-	      min = int_const_binop (code, vr0.min, vr1.min, 0);
-	      max = int_const_binop (code, vr0.max, vr1.min, 0);
-	    }
-	  else
-	    {
-	      /* If VR1 is all negative, the new range is obtained
-		 with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MAX].  */
-	      gcc_assert (compare_values (vr1.max, zero) == -1);
-	      min = int_const_binop (code, vr0.max, vr1.max, 0);
-	      max = int_const_binop (code, vr0.min, vr1.max, 0);
-	    }
-	}
-      else
+      /* Compute the 4 cross operations.  */
+      val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
+
+      val[1] = (vr1.max != vr1.min)
+	       ? vrp_int_const_binop (code, vr0.min, vr1.max)
+	       : NULL_TREE;
+
+      val[2] = (vr0.max != vr0.min)
+	       ? vrp_int_const_binop (code, vr0.max, vr1.min)
+	       : NULL_TREE;
+
+      val[3] = (vr0.min != vr1.min && vr0.max != vr1.max)
+	       ? vrp_int_const_binop (code, vr0.max, vr1.max)
+	       : NULL_TREE;
+
+      /* Set MIN to the minimum of VAL[i] and MAX to the maximum
+	 of VAL[i].  */
+      min = val[0];
+      max = val[0];
+      for (i = 1; i < 4; i++)
 	{
-	  /* VR0 is all positive.  */
-	  gcc_assert (compare_values (vr0.min, zero) == 1);
-	  if (compare_values (vr1.min, zero) == 1)
-	    {
-	      /* If VR1 is all positive, the new range is obtained
-		 with [VR0.MIN / VR1.MAX, VR0.MAX / VR1.MIN].  */
-	      min = int_const_binop (code, vr0.min, vr1.max, 0);
-	      max = int_const_binop (code, vr0.max, vr1.min, 0);
-	    }
-	  else
+	  if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
+	    break;
+
+	  if (val[i])
 	    {
-	      /* If VR1 is all negative, the new range is obtained
-		 with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MIN].  */
-	      gcc_assert (compare_values (vr1.max, zero) == -1);
-	      min = int_const_binop (code, vr0.max, vr1.max, 0);
-	      max = int_const_binop (code, vr0.min, vr1.min, 0);
+	      if (TREE_OVERFLOW (val[i]))
+		{
+		  /* If we found an overflowed value, set MIN and MAX
+		     to it so that we set the resulting range to
+		     VARYING.  */
+		  min = max = val[i];
+		  break;
+		}
+
+	      if (compare_values (val[i], min) == -1)
+		min = val[i];
+
+	      if (compare_values (val[i], max) == 1)
+		max = val[i];
 	    }
 	}
     }
@@ -1173,42 +1206,18 @@ extract_range_from_binary_expr (value_range_t *vr, tree expr)
     {
       /* For MINUS_EXPR, apply the operation to the opposite ends of
 	 each range.  */
-      min = int_const_binop (code, vr0.min, vr1.max, 0);
-      max = int_const_binop (code, vr0.max, vr1.min, 0);
+      min = vrp_int_const_binop (code, vr0.min, vr1.max);
+      max = vrp_int_const_binop (code, vr0.max, vr1.min);
     }
   else
     gcc_unreachable ();
 
-  /* If MAX overflowed, then the result depends on whether we are
-     using wrapping arithmetic or not.  */
-  if (TREE_OVERFLOW (max))
+  /* If either MIN or MAX overflowed, then set the resulting range to
+     VARYING.  */
+  if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
     {
-      /* If we are using wrapping arithmetic, set the result to
-	 VARYING.  */
-      if (flag_wrapv)
-	{
-	  set_value_range_to_varying (vr);
-	  return;
-	}
-
-      /* Otherwise, set MAX to +INF.  */
-      max = TYPE_MAX_VALUE (TREE_TYPE (expr));
-    }
-
-  /* If MIN overflowed, then the result depends on whether we are
-     using wrapping arithmetic or not.  */
-  if (TREE_OVERFLOW (min))
-    {
-      /* If we are using wrapping arithmetic, set the result to
-	 VARYING.  */
-      if (flag_wrapv)
-	{
-	  set_value_range_to_varying (vr);
-	  return;
-	}
-
-      /* Otherwise, set MIN to -INF.  */
-      min = TYPE_MIN_VALUE (TREE_TYPE (expr));
+      set_value_range_to_varying (vr);
+      return;
     }
 
   cmp = compare_values (min, max);