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

[Jeffrey Law]

On 8/6/2026 8:42 AM, Kyrylo Tkachov wrote:

On 6 Aug 2026, at 06:16, Jeffrey Law <jeffrey....@oss.qualcomm.com> wrote:



On 8/4/2026 3:50 AM, ktkac...@nvidia.com wrote:

From: Kyrylo Tkachov <ktkac...@nvidia.com>

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 <ktkac...@nvidia.com>
---
  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))

Is SIGNED really correct for that argument to wi::multiple_of_p? I don't have a 
testcase where it matters.  Just a generic question.

I think so, yes. UNSIGNED would misinterpret negative constants.
One change I did make is guard against (X % -1) % C2 to avoid removing a trap 
or diagnostic under -ftrapv for x = INT_MIN.

+  (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; }

For f5, do you want to verify it collapses to an & 3?  I guess the lack of % 12 or 
%4 for it is probably sufficient since the other counts would get thrown off if we 
failed to optimize f5 down to &3.

Yes, I’ve made that change

Generally it looks good.  Just like to nail down that the SIGNED argument is 
really what we want.

Thanks, attached is an updated version. Is this one ok?

Yea.  This is OK for the trunk.

jeff