PR 64454: Improve VRP for %

[Marc Glisse <marc dot glisse at inria dot fr>]

Hello,

this patch tries to tighten a bit the range estimate for x%y. slp-perm-7.c 
started failing by vectorizing more than expected, I assumed it was a good 
thing and updated the test. I am less conservative than Jakub with 
division by 0, but I still don't really understand how empty ranges are 
supposed to be represented in VRP.

Bootstrap+testsuite on x86_64-linux-gnu.

2015-05-02  Marc Glisse  <marc.glisse@inria.fr>

	PR tree-optimization/64454
gcc/
	* tree-vrp.c (extract_range_from_binary_expr_1) <TRUNC_MOD_EXPR>:
	Rewrite.
gcc/testsuite/
	* gcc.dg/tree-ssa/vrp97.c: New file.
	* gcc.dg/vect/slp-perm-7.c: Update.

--
Marc Glisse

Index: gcc/testsuite/gcc.dg/tree-ssa/vrp97.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/vrp97.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp97.c	(working copy)
@@ -0,0 +1,13 @@
+/* PR tree-optimization/64454 */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+int f(int a, int b)
+{
+    if (a < -3 || a > 13) __builtin_unreachable();
+    if (b < -6 || b > 9) __builtin_unreachable();
+    int c = a % b;
+    return c >= -3 && c <= 8;
+}
+
+/* { dg-final { scan-tree-dump "return 1;" "vrp1" } } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/vect/slp-perm-7.c
===================================================================
--- gcc/testsuite/gcc.dg/vect/slp-perm-7.c	(revision 222708)
+++ gcc/testsuite/gcc.dg/vect/slp-perm-7.c	(working copy)
@@ -63,15 +63,15 @@ int main (int argc, const char* argv[])
 
   foo (input, output, input2, output2);
 
   for (i = 0; i < N; i++)
      if (output[i] != check_results[i] || output2[i] != check_results2[i])
        abort ();
 
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect"  { target vect_perm } } } */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect"  { target vect_perm } } } */
 /* { dg-final { scan-tree-dump-times "vectorizing stmts using SLP" 1 "vect" { target vect_perm } } } */
 /* { dg-final { cleanup-tree-dump "vect" } } */
 
 
Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 222708)
+++ gcc/tree-vrp.c	(working copy)
@@ -3189,40 +3189,83 @@ extract_range_from_binary_expr_1 (value_
 	    }
 	}
       else
 	{
 	  extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
 	  return;
 	}
     }
   else if (code == TRUNC_MOD_EXPR)
     {
-      if (vr1.type != VR_RANGE
-	  || range_includes_zero_p (vr1.min, vr1.max) != 0
-	  || vrp_val_is_min (vr1.min))
+      if (range_is_null (&vr1))
+	{
+	  set_value_range_to_undefined (vr);
+	  return;
+	}
+      // Some propagation of symbolic ranges should be possible
+      // at least in the unsigned case.
+      bool has_vr0 = vr0.type == VR_RANGE && !symbolic_range_p (&vr0);
+      bool has_vr1 = vr1.type == VR_RANGE && !symbolic_range_p (&vr1);
+      if (!has_vr0 && !has_vr1)
 	{
 	  set_value_range_to_varying (vr);
 	  return;
 	}
       type = VR_RANGE;
-      /* Compute MAX <|vr1.min|, |vr1.max|> - 1.  */
-      max = fold_unary_to_constant (ABS_EXPR, expr_type, vr1.min);
-      if (tree_int_cst_lt (max, vr1.max))
-	max = vr1.max;
-      max = int_const_binop (MINUS_EXPR, max, build_int_cst (TREE_TYPE (max), 1));
-      /* If the dividend is non-negative the modulus will be
-	 non-negative as well.  */
-      if (TYPE_UNSIGNED (expr_type)
-	  || value_range_nonnegative_p (&vr0))
-	min = build_int_cst (TREE_TYPE (max), 0);
+      if (TYPE_UNSIGNED (expr_type))
+	{
+	  // A % B is at most A and smaller than B.
+	  min = build_int_cst (expr_type, 0);
+	  if (has_vr0 && (!has_vr1 || tree_int_cst_lt (vr0.max, vr1.max)))
+	    max = vr0.max;
+	  else
+	    max = int_const_binop (MINUS_EXPR, vr1.max,
+				   build_int_cst (expr_type, 1));
+	}
       else
-	min = fold_unary_to_constant (NEGATE_EXPR, expr_type, max);
+	{
+	  tree min1 = NULL_TREE;
+	  tree max1 = NULL_TREE;
+	  if (has_vr1)
+	    {
+	      // ABS (A % B) < ABS (B)
+	      max1 = fold_unary_to_constant (ABS_EXPR, expr_type, vr1.min);
+	      if (tree_int_cst_lt (max1, vr1.max))
+		max1 = vr1.max;
+	      max1 = int_const_binop (MINUS_EXPR, max1,
+				      build_int_cst (expr_type, 1));
+	      min1 = fold_unary_to_constant (NEGATE_EXPR, expr_type, max1);
+	    }
+	  if (has_vr0)
+	    {
+	      // Either 0 <= A % B <= A or A <= A % B <= 0.
+	      max = vr0.max;
+	      min = vr0.min;
+	      tree zero = build_int_cst (expr_type, 0);
+	      if (tree_int_cst_lt (zero, min))
+		min = zero;
+	      if (tree_int_cst_lt (max, zero))
+		max = zero;
+	      if (has_vr1)
+		{
+		  if (tree_int_cst_lt (min, min1))
+		    min = min1;
+		  if (tree_int_cst_lt (max1, max))
+		    max = max1;
+		}
+	    }
+	  else
+	    {
+	      min = min1;
+	      max = max1;
+	    }
+	}
     }
   else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR)
     {
       bool int_cst_range0, int_cst_range1;
       wide_int may_be_nonzero0, may_be_nonzero1;
       wide_int must_be_nonzero0, must_be_nonzero1;
 
       int_cst_range0 = zero_nonzero_bits_from_vr (expr_type, &vr0,
 						  &may_be_nonzero0,
 						  &must_be_nonzero0);