match: fold a remainder of a remainder by a multiple
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-aarch64-bootstrap |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 |
success
|
Build passed
|
Commit Message
From: Kyrylo Tkachov <ktkachov@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 <ktkachov@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
Comments
On 8/4/2026 3:50 AM, ktkachov@nvidia.com wrote:
> From: Kyrylo Tkachov <ktkachov@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 <ktkachov@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.
> + (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
> On 6 Aug 2026, at 06:16, Jeffrey Law <jeffrey.law@oss.qualcomm.com> wrote:
>
>
>
> On 8/4/2026 3:50 AM, ktkachov@nvidia.com wrote:
>> From: Kyrylo Tkachov <ktkachov@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 <ktkachov@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?
Kyrill
>
> Jeff
On 8/6/2026 8:42 AM, Kyrylo Tkachov wrote:
>
>> On 6 Aug 2026, at 06:16, Jeffrey Law <jeffrey.law@oss.qualcomm.com> wrote:
>>
>>
>>
>> On 8/4/2026 3:50 AM, ktkachov@nvidia.com wrote:
>>> From: Kyrylo Tkachov <ktkachov@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 <ktkachov@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
@@ -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))
+ (trunc_mod @0 @2)))
+
/* X % -C is the same as X % C. */
(simplify
(trunc_mod @0 INTEGER_CST@1)
new file mode 100644
@@ -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; }
+
+/* C2 does not divide C1 here, both remainders have to stay. */
+int f6 (int x) { return (x % 12) % 5; }
+
+/* Only the unfoldable pair keeps both remainders. */
+/* { dg-final { scan-tree-dump-times " % 12;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 5;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 4;" 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " % 25;" 1 "optimized" } } */