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

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