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

On 8/6/2026 8:42 AM, Kyrylo Tkachov wrote:
>
>> 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?
Yea.  This is OK for the trunk.

jeff