Simplify more EXACT_DIV_EXPR comparisons

2019-05-31  Marc Glisse  <marc.glisse@inria.fr>

gcc/
	* match.pd (X/[ex]D<Y/[ex]D): Handle negative denominator.
	((size_t)(A /[ex] B) CMP C): New transformation.

gcc/testsuite/
	* gcc.dg/tree-ssa/cmpexactdiv-3.c: New file.
	* gcc.dg/tree-ssa/cmpexactdiv-4.c: New file.
	* gcc.dg/Walloca-13.c: Xfail.

From-SVN: r271816

6 files changed, 62 insertions, 2 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 0ab4075..67cfc44 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,8 @@
+2019-05-31  Marc Glisse  <marc.glisse@inria.fr>
+
+	* match.pd (X/[ex]D<Y/[ex]D): Handle negative denominator.
+	((size_t)(A /[ex] B) CMP C): New transformation.
+
 2019-05-31  Richard Sandiford  <richard.sandiford@arm.com>
 
 	* doc/md.texi: Document define_insn_and_rewrite.
diff --git a/gcc/match.pd b/gcc/match.pd
index e1fa75c..99ffb16 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1497,7 +1497,9 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (simplify
   (cmp (exact_div @0 INTEGER_CST@2) (exact_div @1 @2))
   (if (wi::gt_p (wi::to_wide (@2), 0, TYPE_SIGN (TREE_TYPE (@2))))
-   (cmp @0 @1))))
+   (cmp @0 @1)
+   (if (wi::lt_p (wi::to_wide (@2), 0, TYPE_SIGN (TREE_TYPE (@2))))
+    (cmp @1 @0)))))
 
 /* X / C1 op C2 into a simple range test.  */
 (for cmp (simple_comparison)
@@ -3633,6 +3635,33 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 			      != (cmp == LT_EXPR || cmp == LE_EXPR), type); }
      (cmp @0 { wide_int_to_tree (TREE_TYPE (@0), prod); }))))))
 
+/* Fold (size_t)(A /[ex] B) CMP C to (size_t)A CMP (size_t)B * C or A CMP' 0.
+
+   For small C (less than max/B), this is (size_t)A CMP (size_t)B * C.
+   For large C (more than min/B+2^size), this is also true, with the
+   multiplication computed modulo 2^size.
+   For intermediate C, this just tests the sign of A.  */
+(for cmp  (lt le gt ge)
+     cmp2 (ge ge lt lt)
+ (simplify
+  (cmp (convert (exact_div @0 INTEGER_CST@1)) INTEGER_CST@2)
+  (if (tree_nop_conversion_p (TREE_TYPE (@0), TREE_TYPE (@2))
+       && TYPE_UNSIGNED (TREE_TYPE (@2)) && !TYPE_UNSIGNED (TREE_TYPE (@0))
+       && wi::gt_p (wi::to_wide (@1), 0, TYPE_SIGN (TREE_TYPE (@1))))
+   (with
+    {
+      tree utype = TREE_TYPE (@2);
+      wide_int denom = wi::to_wide (@1);
+      wide_int right = wi::to_wide (@2);
+      wide_int smax = wi::sdiv_trunc (wi::max_value (TREE_TYPE (@0)), denom);
+      wide_int smin = wi::sdiv_trunc (wi::min_value (TREE_TYPE (@0)), denom);
+      bool small = wi::leu_p (right, smax);
+      bool large = wi::geu_p (right, smin);
+    }
+    (if (small || large)
+     (cmp (convert:utype @0) (mult @2 (convert @1)))
+     (cmp2 @0 { build_zero_cst (TREE_TYPE (@0)); }))))))
+
 /* Unordered tests if either argument is a NaN.  */
 (simplify
  (bit_ior (unordered @0 @0) (unordered @1 @1))
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 3174376..5893b18 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2019-05-31  Marc Glisse  <marc.glisse@inria.fr>
+
+	* gcc.dg/tree-ssa/cmpexactdiv-3.c: New file.
+	* gcc.dg/tree-ssa/cmpexactdiv-4.c: New file.
+	* gcc.dg/Walloca-13.c: Xfail.
+
 2019-05-31  Bill Schmidt  <wschmidt@linux.ibm.com>
 	    Michael Meissner  <meissner@linux.ibm.com>
 
diff --git a/gcc/testsuite/gcc.dg/Walloca-13.c b/gcc/testsuite/gcc.dg/Walloca-13.c
index d3af0c5..12e9f6c 100644
--- a/gcc/testsuite/gcc.dg/Walloca-13.c
+++ b/gcc/testsuite/gcc.dg/Walloca-13.c
@@ -8,5 +8,5 @@ void g (int *p, int *q)
 {
   __SIZE_TYPE__ n = (__SIZE_TYPE__)(p - q);
   if (n < 100)
-    f (__builtin_alloca (n));
+    f (__builtin_alloca (n)); // { dg-bogus "may be too large due to conversion" "" { xfail { *-*-* } } }
 }
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-3.c b/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-3.c
new file mode 100644
index 0000000..57e280b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-3.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized-raw" } */
+
+int f(int*a,int*b){
+  if(sizeof(__SIZE_TYPE__)!=sizeof(__PTRDIFF_TYPE__)) return -1;
+  __SIZE_TYPE__ d = b - a;
+  return d >= 5;
+}
+
+/* { dg-final { scan-tree-dump-not "exact_div_expr" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-4.c b/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-4.c
new file mode 100644
index 0000000..1370309
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cmpexactdiv-4.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized-raw" } */
+
+int f(int*a,int*b,int*c){
+  __PTRDIFF_TYPE__ x = -(b - a);
+  __PTRDIFF_TYPE__ y = -(c - a);
+  return x < y;
+}
+
+/* { dg-final { scan-tree-dump-not "exact_div_expr" "optimized" } } */