> On 6 Aug 2026, at 06:16, Jeffrey Law <[email protected]> wrote: > > > > 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. >
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?
Kyrill
>
> Jeff
0001-match-fold-a-remainder-of-a-remainder-by-a-multiple.patch
Description: 0001-match-fold-a-remainder-of-a-remainder-by-a-multiple.patch
