[PATCH] match: fold a remainder of a remainder by a multiple

From: Kyrylo Tkachov <[email protected]>

Truncating remainder keeps the sign of the dividend and its magnitude
modulo the divisor, so reducing X % C1 again modulo C2 gives the same
result as reducing X directly whenever C2 divides C1.  Folding the pair
removes one division.

  int f (int x) { return (x % 12) % 4; }

aarch64 -O2:

  before                          after
    mov   w1, 12                    negs  w1, w0
    sdiv  w1, w0, w1                and   w0, w0, 3
    add   w1, w1, w1, lsl 1         and   w1, w1, 3
    sub   w0, w0, w1, lsl 2         csneg w0, w0, w1, mi
    negs  w1, w0
    and   w0, w0, 3
    and   w1, w1, 3
    csneg w0, w0, w1, mi

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

gcc/ChangeLog:

	* match.pd ((X % C1) % C2): New simplification.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/modmod-1.c: New test.

Signed-off-by: Kyrylo Tkachov <[email protected]>
---
 gcc/match.pd                             | 12 ++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c | 19 +++++++++++++++++++
 2 files changed, 31 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 4fca75d6fb6..22202af2cc1 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -975,6 +975,18 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); }
      (cmp (mod (convert:utype @0) (convert:utype @2)) (convert:utype @1)))))))
 
+/* (X % C1) % C2 is X % C2 when C2 divides C1.  Truncating remainder keeps
+   the sign of X and the magnitude modulo C1, so reducing modulo C2 gives
+   the same result as reducing X directly.  */
+(simplify
+ (trunc_mod (trunc_mod @0 INTEGER_CST@1) INTEGER_CST@2)
+ (if (INTEGRAL_TYPE_P (type)
+      && !TYPE_OVERFLOW_TRAPS (type)
+      && !integer_zerop (@1)
+      && !integer_zerop (@2)
+      && wi::multiple_of_p (wi::to_widest (@1), wi::to_widest (@2), SIGNED))
+  (trunc_mod @0 @2)))
+
 /* X % -C is the same as X % C.  */
 (simplify
  (trunc_mod @0 INTEGER_CST@1)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c
new file mode 100644
index 00000000000..6689a518ff3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* (X % C1) % C2 is X % C2 when C2 divides C1.  */
+
+int f1 (int x) { return (x % 12) % 4; }
+int f2 (int x) { return (x % 100) % 25; }
+int f3 (int x) { return (x % -12) % 4; }
+int f4 (int x) { return (x % 12) % -4; }
+unsigned int f5 (unsigned int x) { return (x % 12) % 4; }
+
+/* C2 does not divide C1 here, both remainders have to stay.  */
+int f6 (int x) { return (x % 12) % 5; }
+
+/* Only the unfoldable pair keeps both remainders.  */
+/* { dg-final { scan-tree-dump-times " % 12;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 5;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 4;" 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 25;" 1 "optimized" } } */
-- 
2.50.1 (Apple Git-155)