[gcc r17-3053] match: fold a remainder of a remainder by a multiple

https://gcc.gnu.org/g:980c3302d34f1a6977f69cacbe327ac894844e1d

commit r17-3053-g980c3302d34f1a6977f69cacbe327ac894844e1d
Author: Kyrylo Tkachov <[email protected]>
Date:   Wed Jul 29 21:26:46 2026 +0200

    match: fold a remainder of a remainder by a multiple
    
    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
    
    Use signed divisibility because wi::to_widest preserves the signed
    value of a negative constant.  Keep an inner remainder by -1 when it
    can trap or carry sanitizer instrumentation.  An outer remainder by
    -1 is zero after a safe inner remainder and folds without introducing
    an INT_MIN % -1 operation.
    
    Bootstrapped and tested on aarch64-none-linux-gnu.
    
    gcc/ChangeLog:
    
            * match.pd ((X % C1) % C2): New simplification.
    
    gcc/testsuite/ChangeLog:
    
            * gcc.dg/tree-ssa/modmod-1.c: New test.
            * gcc.dg/tree-ssa/modmod-2.c: Likewise.
            * gcc.dg/tree-ssa/modmod-3.c: Likewise.
            * gcc.dg/tree-ssa/modmod-4.c: Likewise.
            * gcc.dg/tree-ssa/modmod-5.c: Likewise.
    
    Signed-off-by: Kyrylo Tkachov <[email protected]>

Diff:
---
 gcc/match.pd                             | 16 ++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c | 17 +++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/modmod-2.c |  8 ++++++++
 gcc/testsuite/gcc.dg/tree-ssa/modmod-3.c | 10 ++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/modmod-4.c | 11 +++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/modmod-5.c | 19 +++++++++++++++++++
 6 files changed, 81 insertions(+)

diff --git a/gcc/match.pd b/gcc/match.pd
index 94801f19fc61..62cc01380bcc 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -940,6 +940,22 @@ 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)
+	   && !TYPE_OVERFLOW_SANITIZED (type))
+	  || !integer_minus_onep (@1))
+      && !integer_zerop (@1)
+      && !integer_zerop (@2)
+      && wi::multiple_of_p (wi::to_widest (@1), wi::to_widest (@2), SIGNED))
+  (if (!TYPE_UNSIGNED (type) && integer_minus_onep (@2))
+   { build_zero_cst (type); }
+   (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 000000000000..aa5cd9858c2e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-1.c
@@ -0,0 +1,17 @@
+/* { 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 % -15) % 3; }
+int f4 (int x) { return (x % 15) % -3; }
+unsigned int f5 (unsigned int x) { return (x % 12) % 4; }
+
+/* Each pair folds to one remainder.  */
+/* { dg-final { scan-tree-dump-not " % 12;" "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 4;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 25;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 3;" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & 3;" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-2.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-2.c
new file mode 100644
index 000000000000..0fe749327769
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-2.c
@@ -0,0 +1,8 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Five does not divide twelve, so both remainders have to stay.  */
+int f (int x) { return (x % 12) % 5; }
+
+/* { dg-final { scan-tree-dump-times " % 12;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 5;" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-3.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-3.c
new file mode 100644
index 000000000000..9d90173f6a53
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-3.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftrapv -fdump-tree-optimized" } */
+
+/* Interpreting -15 as signed proves that three divides it.  The inner
+   remainder cannot overflow, so trapping arithmetic does not block the
+   fold.  */
+int f (int x) { return (x % -15) % 3; }
+
+/* { dg-final { scan-tree-dump-not " % 15;" "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 3;" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-4.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-4.c
new file mode 100644
index 000000000000..a19da7928f91
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-4.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fsanitize=signed-integer-overflow -fdump-tree-optimized" } */
+
+int f1 (int x) { return (x % -1) % 1; }
+int f2 (int x) { return (x % -15) % 3; }
+
+/* Keep the possible INT_MIN % -1 diagnostic in f1.  The safe f2 pair still
+   folds.  */
+/* { dg-final { scan-tree-dump-times "__ubsan_handle_divrem_overflow" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-not " % 15;" "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 3;" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modmod-5.c b/gcc/testsuite/gcc.dg/tree-ssa/modmod-5.c
new file mode 100644
index 000000000000..d76fb619990c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/modmod-5.c
@@ -0,0 +1,19 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -ftrapv" } */
+
+#include <limits.h>
+
+__attribute__ ((noipa))
+static int
+f (int x)
+{
+  return (x % 12) % -1;
+}
+
+int
+main (void)
+{
+  if (f (INT_MIN) != 0 || f (-1) != 0 || f (0) != 0 || f (INT_MAX) != 0)
+    __builtin_abort ();
+  return 0;
+}