This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Improve VRP of integer division (PR rtl-optimization/38245)


Hi!

This PR has two parts, this patch addresses just the part why
tree optimizers weren't able to optimize the division and modulo away
and only RTL optimizers were able to DCE it away.

On the tree side, fold doesn't optimize away 0 / x into x, 0
as simplify-rtx does (not addressed in this patch) and VRP isn't
able to optimize almost anything related to divisions (yielding
almost always VARYING ranges).  In many cases we can do much better.
Say for int x (VARYING) and int y ([4, __INT_MAX__]) we know the
range is [__INT_MIN__ / 4, __INT_MAX__ / 4], or for x's VR
[-4, 8] and y VARYING we know x / y is [-8, 8] (integer
division never makes the number bigger, only if the divisor isn't
known to be non-negative it can change the sign).  VRP was bailing
out even if both ranges were RANGE, if divisor's range could include 0,
but I don't think we guarantee anything about preserving code that divides
by 0 (it is undefined behavior in both C and C++ and we happily optimize
away say void foo () { 2 / 0; } at gimplification time, or return 0 / x;
into return 0 in simplify-rtx and other places).  My guess is that
it was done because the generic MULT_EXPR + RSHIFT_EXPR + *_DIV_EXPR
algorithm of computing min0 op min1, min0 op max1, max0 op min1, max0 op
max1 and using minimum and maximum of these values doesn't work in that
case.

The following patch has been bootstrapped/regtested on x86_64-linux
(and the testcase from PR now works), ok for trunk?

2008-11-29  Jakub Jelinek  <jakub@redhat.com>

	PR rtl-optimization/38245
	* tree-vrp.c (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.

--- gcc/tree-vrp.c.jj	2008-10-02 11:10:48.000000000 +0200
+++ gcc/tree-vrp.c	2008-11-29 12:12:45.000000000 +0100
@@ -2108,11 +2108,17 @@ extract_range_from_binary_expr (value_ra
   /* 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
@@ -2289,83 +2295,189 @@ extract_range_from_binary_expr (value_ra
 	 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)))
+	       && (vr0.type != VR_RANGE || symbolic_range_p (&vr0)))
 	{
-	  set_value_range_to_varying (vr);
-	  return;
+	  /* For division, if op1 has VR_RANGE, 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));
+	      if (!vr0.min || !vr0.max)
+		{
+		  set_value_range_to_varying (vr);
+		  return;
+		}
+	    }
+	  else
+	    {
+	      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
+      /* For divisions, if op0 is VR_RANGE, we can deduce a range
+	 even if op1 is VARYING, ANTI_RANGE, symbolic or can include 0.  */
+      if (code != MULT_EXPR
+	  && code != RSHIFT_EXPR
+	  && (vr0.type != vr1.type
+	      || symbolic_range_p (&vr1)
+	      || range_includes_zero_p (&vr1)))
 	{
-	  val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
-	  if (val[1] == NULL_TREE)
-	    sop = true;
-	}
+	  tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
+	  int cmp;
 
-      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;
+	  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.  */
+	      gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (vr0.min)));
+	      cmp = compare_values (vr0.min, zero);
+	      if (cmp == 0 || cmp == 1)
+		{
+		  min = fold_unary (NEGATE_EXPR, TREE_TYPE (vr0.min), vr0.max);
+		  max = vr0.max;
+		}
+	      else if (cmp == -1)
+		{
+		  if (vrp_val_is_min (vr0.min))
+		    type = VR_VARYING;
+		  else
+		    {
+		      tree tem = fold_unary (NEGATE_EXPR, TREE_TYPE (vr0.min),
+					     vr0.min);
+		      if (tem == NULL)
+			type = VR_VARYING;
+		      else
+			{
+			  cmp = compare_values (tem, vr0.max);
+			  if (cmp == -1 || cmp == 0)
+			    {
+			      min = vr0.min;
+			      max = tem;
+			    }
+			  else if (cmp == 1)
+			    {
+			      min = fold_unary (NEGATE_EXPR,
+						TREE_TYPE (vr0.min), vr0.max);
+			      max = vr0.max;
+			    }
+			  else
+			    type = VR_VARYING;
+			}
+		    }
+		}
+	      else
+		type = VR_VARYING;
+	    }
+	  if (type == VR_VARYING)
+	    {
+	      set_value_range_to_varying (vr);
+	      return;
+	    }
 	}
-
-      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)
+	  /* 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 (sop)
-	{
-	  set_value_range_to_varying (vr);
-	  return;
-	}
+	  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;
+	    }
 
-      /* 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.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;
+	    }
 
-	  if (val[i])
+	  if (vr0.min == vr0.max || vr1.min == vr1.max)
+	    val[3] = NULL_TREE;
+	  else
 	    {
-	      if (!is_gimple_min_invariant (val[i])
-		  || (TREE_OVERFLOW (val[i])
-		      && !is_overflow_infinity (val[i])))
+	      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;
+	    }
+
+	  /* 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 (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];
+		}
 	    }
 	}
     }
--- gcc/testsuite/gcc.dg/pr38245-2.c.jj	2008-11-28 22:23:07.000000000 +0100
+++ gcc/testsuite/gcc.dg/pr38245-2.c	2008-11-29 20:53:20.000000000 +0100
@@ -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" } } */
--- gcc/testsuite/gcc.dg/pr38245-1.c.jj	2008-11-28 22:23:07.000000000 +0100
+++ gcc/testsuite/gcc.dg/pr38245-1.c	2008-11-28 22:23:07.000000000 +0100
@@ -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" } } */

	Jakub


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]