Re: [PATCH][v2] match.pd: fold an unsigned modular reduction into MIN

On Wed, Aug 5, 2026 at 4:50 AM <[email protected]> wrote:
>
> From: Kyrylo Tkachov <[email protected]>
>
> The reduction step of a modular arithmetic loop, X >= Y ? X - Y : X on an
> unsigned type, is exactly MIN (X, X - Y).  When X >= Y the difference is at
> most X, and when X < Y it wraps to X - Y + 2**N, which is above X because Y
> is below 2**N.  The subtraction already feeds both arms, so the compare and
> the select fold into one operation.
>
>   unsigned f (unsigned x, unsigned m) { return x >= m ? x - m : x; }
>
> aarch64 -O2 -march=armv8.9-a before:
>
>         cmp     w0, w1
>         csel    w1, w1, wzr, cs
>         sub     w0, w0, w1
>
> after:
>
>         sub     w1, w0, w1
>         umin    w0, w1, w0
>
> The larger effect is on a loop.  A MIN_EXPR vectorises to a single umin,
> where the select needed a compare, a subtract and a blend:
>
>         cmhs    v29.4s, v30.4s, v31.4s        sub       v29.4s, v30.4s, v31.4s
>         sub     v28.4s, v30.4s, v31.4s   ->   umin      v29.4s, v29.4s, v30.4s
>         bif     v28.16b, v30.16b, v29.16b
>
> The :c marker on each variable comparison covers both operand orders.  A
> constant modulus needs two more patterns.  There the subtraction is
> canonicalised to an addition of the negated modulus and the compare to a
> strict one against the modulus less one, so the two constants are related
> rather than equal.  phiopt feeds the diamond in as a COND_EXPR, so the branch
> form is covered as well as the select.
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
> Ok for trunk?
> Thanks,
> Kyrill
>
> gcc/ChangeLog:
>
>         * match.pd (X >= Y ? X - Y : X): New simplification.
>         (X > C - 1 ? X + -C : X): Likewise.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/modred-min-1.c: New test.
>         * gcc.dg/tree-ssa/modred-min-2.c: Likewise.
>
> Signed-off-by: Kyrylo Tkachov <[email protected]>
> ---
>  gcc/match.pd                                 | 32 ++++++++++++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/modred-min-1.c | 14 +++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/modred-min-2.c |  9 ++++++
>  3 files changed, 55 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modred-min-1.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modred-min-2.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 2b7cc0cb412..69be93d41c7 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -6333,6 +6333,38 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>   (if (INTEGRAL_TYPE_P (type) ? TYPE_UNSIGNED (type) : POINTER_TYPE_P (type))
>    (max @1 @0)))
>
> +/* An unsigned modular reduction, X >= Y ? X - Y : X, is MIN (X, X - Y).
> +   When X >= Y the difference is at most X, and when X < Y the difference
> +   wraps to X - Y + 2**N, which exceeds X because Y is below 2**N.  The
> +   subtraction feeds both arms of the select, so the compare and the select
> +   collapse into a single operation, and the result is one MIN_EXPR that the
> +   vectoriser can use directly instead of a compare and a blend.
> +
> +   The :c on each relational covers both operand orders.  */
> +(simplify
> + (cond (ge:c @0 @1) (minus@2 @0 @1) @0)
> + (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type))
> +  (min @0 @2)))
> +(simplify
> + (cond (lt:c @0 @1) @0 (minus@2 @0 @1))
> + (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type))
> +  (min @0 @2)))

Seems like this could support vec_cond too ...

> +
> +/* The same reduction by a constant modulus.  There the subtraction has been
> +   canonicalised to an addition of the negated modulus and the compare to a
> +   strict one against the modulus less one, so the two constants are related
> +   rather than equal.  */
> +(simplify
> + (cond (gt @0 INTEGER_CST@1) (plus@2 @0 INTEGER_CST@3) @0)
> + (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type)
> +      && wi::to_wide (@1) + 1 == -wi::to_wide (@3))
> +  (min @0 @2)))
> +(simplify
> + (cond (le @0 INTEGER_CST@1) @0 (plus@2 @0 INTEGER_CST@3))
> + (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type)
> +      && wi::to_wide (@1) + 1 == -wi::to_wide (@3))
> +  (min @0 @2)))
> +
>  #if GIMPLE
>  (match (nop_atomic_bit_test_and_p @0 @1 @4)
>   (bit_and (convert?@4 (ATOMIC_FETCH_OR_XOR_N @2 INTEGER_CST@0 @3))
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modred-min-1.c b/gcc/testsuite/gcc.dg/tree-ssa/modred-min-1.c
> new file mode 100644
> index 00000000000..dcc4f7d373f
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/modred-min-1.c
> @@ -0,0 +1,14 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +/* An unsigned modular reduction is a MIN of the value and the difference.  */
> +
> +unsigned f1 (unsigned x, unsigned m) { return x >= m ? x - m : x; }
> +unsigned f2 (unsigned x, unsigned m) { return m <= x ? x - m : x; }
> +unsigned f3 (unsigned x, unsigned m) { return x < m ? x : x - m; }
> +unsigned f4 (unsigned x, unsigned m) { return m > x ? x : x - m; }
> +unsigned long f5 (unsigned long x, unsigned long m) { if (x >= m) x -= m; return x; }
> +unsigned f6 (unsigned x) { return x >= 97 ? x - 97 : x; }
> +unsigned f7 (unsigned x) { return x < 97 ? x : x - 97; }
> +
> +/* { dg-final { scan-tree-dump-times "MIN_EXPR " 7 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/modred-min-2.c b/gcc/testsuite/gcc.dg/tree-ssa/modred-min-2.c
> new file mode 100644
> index 00000000000..cd2f90a72ae
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/modred-min-2.c
> @@ -0,0 +1,9 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +/* A signed difference can overflow, so the unsigned identity does not
> +   apply.  */
> +
> +int keep (int x, int m) { return x >= m ? x - m : x; }
> +
> +/* { dg-final { scan-tree-dump-not "MIN_EXPR " "optimized" } } */
> --
> 2.50.1 (Apple Git-155)
>