PR rtl-optimization/38245

	* tree-vrp.c (abs_extent_range): New function.
	(extract_range_from_binary_expr): Compute range
	for *_DIV_EXPR even if vr1 is VR_VARYING, VR_ANTI_RANGE
	or includes zero or if vr1 is VR_RANGE and op0 has some
	other range.

	* gcc.dg/pr38245-1.c: New test.
	* gcc.dg/pr38245-2.c: New test.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@142317 138bc75d-0d04-0410-961f-82ee72b054a4

5 files changed, 349 insertions, 68 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 82da5df425d..05b970b7f46 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,12 @@
+2008-12-01  Jakub Jelinek  <jakub@redhat.com>
+
+	PR rtl-optimization/38245
+	* tree-vrp.c (abs_extent_range): New function.
+	(extract_range_from_binary_expr): Compute range
+	for *_DIV_EXPR even if vr1 is VR_VARYING, VR_ANTI_RANGE
+	or includes zero or if vr1 is VR_RANGE and op0 has some
+	other range.
+
 2008-12-01  Uros Bizjak  <ubizjak@gmail.com>
 
 	PR middle-end/37908
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index f6ee64bf384..88adf43bda1 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2008-12-01  Jakub Jelinek  <jakub@redhat.com>
+
+	PR rtl-optimization/38245
+	* gcc.dg/pr38245-1.c: New test.
+	* gcc.dg/pr38245-2.c: New test.
+
 2008-11-30  Daniel Kraft  <d@domob.eu>
 
 	PR fortran/37779
diff --git a/gcc/testsuite/gcc.dg/pr38245-1.c b/gcc/testsuite/gcc.dg/pr38245-1.c
new file mode 100644
index 00000000000..17b969c7de0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr38245-1.c
@@ -0,0 +1,36 @@
+/* PR rtl-optimization/38245 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+static inline int
+f1 (int si1, int si2)
+{
+  return si2 == 0 ? si1 : si1 / si2;
+}
+
+static inline unsigned long long
+f2 (unsigned long long ui1, unsigned long long ui2)
+{
+  return ui1 % ui2;
+}
+
+unsigned char g;
+volatile unsigned int h;
+
+void
+f3 (void)
+{
+  if (!((signed char) f1 (0, f2 (g, 2123)) - 1))
+    h;
+}
+
+int
+main (void)
+{
+  f3 ();
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "% 2123" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "0 / " "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/pr38245-2.c b/gcc/testsuite/gcc.dg/pr38245-2.c
new file mode 100644
index 00000000000..2998299375d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr38245-2.c
@@ -0,0 +1,110 @@
+/* PR rtl-optimization/38245 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+extern void link_error (void);
+
+void
+f1 (unsigned int a)
+{
+  if (a != 28)
+    {
+      if (4 / a == 5)
+	link_error ();
+    }
+}
+
+void
+f2 (unsigned int a)
+{
+  if (4 / a == 5)
+    link_error ();
+}
+
+void
+f3 (unsigned int a)
+{
+  if (4 / (a & 0xff) == 5)
+    link_error ();
+}
+
+void
+f4 (unsigned int a, unsigned int b)
+{
+  if ((b & 3) / ((a & 0xff) + 1) == 5)
+    link_error ();
+}
+
+void
+f5 (int a)
+{
+  if (a != 28)
+    {
+      if (4 / a == 5)
+	link_error ();
+    }
+}
+
+void
+f6 (int a)
+{
+  if (4 / a == 5)
+    link_error ();
+}
+
+void
+f7 (int a)
+{
+  if (4 / (a & 0xff) == 5)
+    link_error ();
+}
+
+void
+f8 (int a, int b)
+{
+  if ((b & 3) / ((a & 0xff) + 1) == 5)
+    link_error ();
+}
+
+void
+f9 (int a, int b)
+{
+  if (b >= 4)
+    if ((a / b) == __INT_MAX__ / 2)
+      link_error ();
+}
+
+void
+f10 (unsigned int a, unsigned int b)
+{
+  if (b >= 16)
+    if ((a / b) == __INT_MAX__ / 4)
+      link_error ();
+}
+
+void
+f11 (int a, int b)
+{
+  if (b <= -32)
+    if ((a / b) == -__INT_MAX__ / 16)
+      link_error ();
+}
+
+void
+f12 (int a, int b)
+{
+  if (a >= -6 && a <= 4)
+    if ((a / b) == -7 || (a / b) == 7)
+      link_error ();
+}
+
+void
+f13 (unsigned int a, unsigned int b)
+{
+  if (a <= 4)
+    if ((a / b) == 5)
+      link_error ();
+}
+
+/* { dg-final { scan-tree-dump-not "link_error" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 949b73c2d0a..1289c49ef1d 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -599,6 +599,42 @@ set_value_range_to_undefined (value_range_t *vr)
 }
 
 
+/* If abs (min) < abs (max), set VR to [-max, max], if
+   abs (min) >= abs (max), set VR to [-min, min].  */
+
+static void
+abs_extent_range (value_range_t *vr, tree min, tree max)
+{
+  int cmp;
+
+  gcc_assert (TREE_CODE (min) == INTEGER_CST);
+  gcc_assert (TREE_CODE (max) == INTEGER_CST);
+  gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (min)));
+  gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (min)));
+  min = fold_unary (ABS_EXPR, TREE_TYPE (min), min);
+  max = fold_unary (ABS_EXPR, TREE_TYPE (max), max);
+  if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
+    {
+      set_value_range_to_varying (vr);
+      return;
+    }
+  cmp = compare_values (min, max);
+  if (cmp == -1)
+    min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), max);
+  else if (cmp == 0 || cmp == 1)
+    {
+      max = min;
+      min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), min);
+    }
+  else
+    {
+      set_value_range_to_varying (vr);
+      return;
+    }
+  set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
+}
+
+
 /* Return value range information for VAR.  
 
    If we have no values ranges recorded (ie, VRP is not running), then
@@ -2108,11 +2144,17 @@ extract_range_from_binary_expr (value_range_t *vr,
   /* Refuse to operate on VARYING ranges, ranges of different kinds
      and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
      because we may be able to derive a useful range even if one of
-     the operands is VR_VARYING or symbolic range.  TODO, we may be
-     able to derive anti-ranges in some cases.  */
+     the operands is VR_VARYING or symbolic range.  Similarly for
+     divisions.  TODO, we may be able to derive anti-ranges in
+     some cases.  */
   if (code != BIT_AND_EXPR
       && code != TRUTH_AND_EXPR
       && code != TRUTH_OR_EXPR
+      && code != TRUNC_DIV_EXPR
+      && code != FLOOR_DIV_EXPR
+      && code != CEIL_DIV_EXPR
+      && code != EXACT_DIV_EXPR
+      && code != ROUND_DIV_EXPR
       && (vr0.type == VR_VARYING
 	  || vr1.type == VR_VARYING
 	  || vr0.type != vr1.type
@@ -2276,6 +2318,86 @@ extract_range_from_binary_expr (value_range_t *vr,
 	    }
 	}
 
+      else if ((code == TRUNC_DIV_EXPR
+		|| code == FLOOR_DIV_EXPR
+		|| code == CEIL_DIV_EXPR
+		|| code == EXACT_DIV_EXPR
+		|| code == ROUND_DIV_EXPR)
+	       && (vr0.type != VR_RANGE || symbolic_range_p (&vr0)))
+	{
+	  /* For division, if op1 has VR_RANGE but op0 does not, something
+	     can be deduced just from that range.  Say [min, max] / [4, max]
+	     gives [min / 4, max / 4] range.  */
+	  if (vr1.type == VR_RANGE
+	      && !symbolic_range_p (&vr1)
+	      && !range_includes_zero_p (&vr1))
+	    {
+	      vr0.type = type = VR_RANGE;
+	      vr0.min = vrp_val_min (TREE_TYPE (op0));
+	      vr0.max = vrp_val_max (TREE_TYPE (op1));
+	    }
+	  else
+	    {
+	      set_value_range_to_varying (vr);
+	      return;
+	    }
+	}
+
+      /* For divisions, if op0 is VR_RANGE, we can deduce a range
+	 even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can
+	 include 0.  */
+      if ((code == TRUNC_DIV_EXPR
+	   || code == FLOOR_DIV_EXPR
+	   || code == CEIL_DIV_EXPR
+	   || code == EXACT_DIV_EXPR
+	   || code == ROUND_DIV_EXPR)
+	  && vr0.type == VR_RANGE
+	  && (vr1.type != VR_RANGE
+	      || symbolic_range_p (&vr1)
+	      || range_includes_zero_p (&vr1)))
+	{
+	  tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
+	  int cmp;
+
+	  sop = false;
+	  min = NULL_TREE;
+	  max = NULL_TREE;
+	  if (vrp_expr_computes_nonnegative (op1, &sop) && !sop)
+	    {
+	      /* For unsigned division or when divisor is known
+		 to be non-negative, the range has to cover
+		 all numbers from 0 to max for positive max
+		 and all numbers from min to 0 for negative min.  */
+	      cmp = compare_values (vr0.max, zero);
+	      if (cmp == -1)
+		max = zero;
+	      else if (cmp == 0 || cmp == 1)
+		max = vr0.max;
+	      else
+		type = VR_VARYING;
+	      cmp = compare_values (vr0.min, zero);
+	      if (cmp == 1)
+		min = zero;
+	      else if (cmp == 0 || cmp == -1)
+		min = vr0.min;
+	      else
+		type = VR_VARYING;
+	    }
+	  else
+	    {
+	      /* Otherwise the range is -max .. max or min .. -min
+		 depending on which bound is bigger in absolute value,
+		 as the division can change the sign.  */
+	      abs_extent_range (vr, vr0.min, vr0.max);
+	      return;
+	    }
+	  if (type == VR_VARYING)
+	    {
+	      set_value_range_to_varying (vr);
+	      return;
+	    }
+	}
+
       /* 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
@@ -2288,84 +2410,82 @@ extract_range_from_binary_expr (value_range_t *vr,
 	 (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.  */
-      else if (code != MULT_EXPR
-	       && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
-	{
-	  set_value_range_to_varying (vr);
-	  return;
-	}
-
-      /* Compute the 4 cross operations.  */
-      sop = false;
-      val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
-      if (val[0] == NULL_TREE)
-	sop = true;
-
-      if (vr1.max == vr1.min)
-	val[1] = NULL_TREE;
       else
 	{
-	  val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
-	  if (val[1] == NULL_TREE)
-	    sop = true;
-	}
+	  gcc_assert ((vr0.type == VR_RANGE
+		       || (code == MULT_EXPR && vr0.type == VR_ANTI_RANGE))
+		      && vr0.type == vr1.type);
 
-      if (vr0.max == vr0.min)
-	val[2] = NULL_TREE;
-      else
-	{
-	  val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
-	  if (val[2] == NULL_TREE)
+	  /* Compute the 4 cross operations.  */
+	  sop = false;
+	  val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
+	  if (val[0] == NULL_TREE)
 	    sop = true;
-	}
 
-      if (vr0.min == vr0.max || vr1.min == vr1.max)
-	val[3] = NULL_TREE;
-      else
-	{
-	  val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
-	  if (val[3] == NULL_TREE)
-	    sop = true;
-	}
+	  if (vr1.max == vr1.min)
+	    val[1] = NULL_TREE;
+	  else
+	    {
+	      val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
+	      if (val[1] == NULL_TREE)
+		sop = true;
+	    }
 
-      if (sop)
-	{
-	  set_value_range_to_varying (vr);
-	  return;
-	}
+	  if (vr0.max == vr0.min)
+	    val[2] = NULL_TREE;
+	  else
+	    {
+	      val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
+	      if (val[2] == NULL_TREE)
+		sop = true;
+	    }
 
-      /* 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++)
-	{
-	  if (!is_gimple_min_invariant (min)
-	      || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
-	      || !is_gimple_min_invariant (max)
-	      || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
-	    break;
+	  if (vr0.min == vr0.max || vr1.min == vr1.max)
+	    val[3] = NULL_TREE;
+	  else
+	    {
+	      val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
+	      if (val[3] == NULL_TREE)
+		sop = true;
+	    }
+
+	  if (sop)
+	    {
+	      set_value_range_to_varying (vr);
+	      return;
+	    }
 
-	  if (val[i])
+	  /* 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++)
 	    {
-	      if (!is_gimple_min_invariant (val[i])
-		  || (TREE_OVERFLOW (val[i])
-		      && !is_overflow_infinity (val[i])))
+	      if (!is_gimple_min_invariant (min)
+		  || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
+		  || !is_gimple_min_invariant (max)
+		  || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
+		break;
+
+	      if (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 (!is_gimple_min_invariant (val[i])
+		      || (TREE_OVERFLOW (val[i])
+			  && !is_overflow_infinity (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], min) == -1)
+		    min = val[i];
 
-	      if (compare_values (val[i], max) == 1)
-		max = val[i];
+		  if (compare_values (val[i], max) == 1)
+		    max = val[i];
+		}
 	    }
 	}
     }