On 8/4/2026 3:50 AM, [email protected] wrote:
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))
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.
+ (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.
Generally it looks good. Just like to nail down that the SIGNED
argument is really what we want.
Jeff
