[PATCH] match: fold a remainder compared with its dividend

From: Kyrylo Tkachov <[email protected]>

A remainder of non-negative operands equals its dividend exactly when the
dividend is smaller than the divisor.  Comparing the two therefore does
not need the division at all.  This sits next to the (X / Y) == 0 rule,
which has the same shape and the same non-negativity requirement.

  int f (unsigned x, unsigned y) { return x % y == x; }

aarch64 -O2:

  before                          after
    udiv  w2, w0, w1                cmp   w0, w1
    msub  w2, w2, w1, w0            cset  w0, cc
    cmp   w2, w0
    cset  w0, eq

The :s marker cannot reject this flat replacement.  Remove the inactive
marker.

A zero divisor can raise a non-call exception.  Keep the division or
remainder when the divisor might be zero and non-call exceptions are
enabled.  Also keep an explicit zero divisor for diagnostics.

Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill

gcc/ChangeLog:

	* match.pd ((X / Y) ==/!= 0): Preserve a possible zero-divisor
	exception.
	((X % Y) ==/!= X): New simplification.  Preserve a possible
	zero-divisor exception.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/modcmp-1.c: New test.
	* gcc.dg/tree-ssa/modcmp-noncall-1.c: Likewise.

Signed-off-by: Kyrylo Tkachov <[email protected]>
---
 gcc/match.pd                                  | 16 +++++++++--
 gcc/testsuite/gcc.dg/tree-ssa/modcmp-1.c      | 22 +++++++++++++++
 .../gcc.dg/tree-ssa/modcmp-noncall-1.c        | 27 +++++++++++++++++++
 3 files changed, 63 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modcmp-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modcmp-noncall-1.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 285e3ead48a..d797893d228 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3160,13 +3160,25 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 
 /* Transform:
    (X / Y) == 0 -> X < Y if X, Y are non-negative.
-   (X / Y) != 0 -> X >= Y, if X, Y are non-negative.  */
+   (X / Y) != 0 -> X >= Y, if X, Y are non-negative.
+   (X % Y) == X -> X < Y if X, Y are non-negative.
+   (X % Y) != X -> X >= Y, if X, Y are non-negative.  */
 (for cmp (eq ne)
      ocmp (lt ge)
  (simplify
   (cmp (trunc_div tree_expr_nonnegative_p@0 tree_expr_nonnegative_p@1) integer_zerop)
        /* Complex ==/!= is allowed, but not </>=.  */
-  (if (TREE_CODE (TREE_TYPE (@0)) != COMPLEX_TYPE
+  (if (!integer_zerop (@1)
+       && (!flag_non_call_exceptions || tree_expr_nonzero_p (@1))
+       && TREE_CODE (TREE_TYPE (@0)) != COMPLEX_TYPE
+       && (VECTOR_TYPE_P (type) || !VECTOR_TYPE_P (TREE_TYPE (@0))))
+   (ocmp @0 @1)))
+ (simplify
+  (cmp:c (trunc_mod tree_expr_nonnegative_p@0 tree_expr_nonnegative_p@1) @0)
+  /* A complex modulo cannot exist, so unlike the division above this
+     needs no complex exclusion.  */
+  (if (!integer_zerop (@1)
+       && (!flag_non_call_exceptions || tree_expr_nonzero_p (@1))
        && (VECTOR_TYPE_P (type) || !VECTOR_TYPE_P (TREE_TYPE (@0))))
    (ocmp @0 @1))))
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modcmp-1.c b/gcc/testsuite/gcc.dg/tree-ssa/modcmp-1.c
new file mode 100644
index 00000000000..a59882e66a3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modcmp-1.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* A remainder of non-negative operands equals its dividend exactly when the
+   dividend is smaller than the divisor, so the division can go away.  */
+
+int f1 (unsigned int x, unsigned int y) { return x % y == x; }
+int f2 (unsigned int x, unsigned int y) { return x % y != x; }
+int f3 (unsigned long x, unsigned long y) { return x == x % y; }
+int f4 (int x, int y)
+{
+  x &= __INT_MAX__;
+  y &= __INT_MAX__;
+  return x % y == x;
+}
+
+/* Signed operands that may be negative do not have that property.  */
+int f5 (int x, int y) { return x % y == x; }
+
+/* { dg-final { scan-tree-dump-times " % " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " < " 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " >= " 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modcmp-noncall-1.c b/gcc/testsuite/gcc.dg/tree-ssa/modcmp-noncall-1.c
new file mode 100644
index 00000000000..aa5074b4517
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modcmp-noncall-1.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fnon-call-exceptions -fdump-tree-optimized" } */
+
+/* A possibly zero divisor can trap when non-call exceptions are enabled,
+   so the comparison must keep the division or remainder.  */
+
+int f1 (unsigned int x, unsigned int y) { return x / y == 0; }
+int f2 (unsigned int x, unsigned int y) { return x / y != 0; }
+int f3 (unsigned int x, unsigned int y) { return x % y == x; }
+int f4 (unsigned int x, unsigned int y) { return x % y != x; }
+
+/* A known nonzero divisor can still fold.  */
+int f5 (unsigned int x) { return x / 3 == 0; }
+int f6 (unsigned int x) { return x % 3 == x; }
+
+/* An explicit zero must retain the front-end diagnostic and trap.  */
+int f7 (unsigned int x)
+{
+  return x / 0 == 0; /* { dg-warning "division by zero" } */
+}
+int f8 (unsigned int x)
+{
+  return x % 0 == x; /* { dg-warning "division by zero" } */
+}
+
+/* { dg-final { scan-tree-dump-times " / " 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % " 3 "optimized" } } */
-- 
2.50.1 (Apple Git-155)