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

On Tue, Aug 4, 2026 at 2:58=E2=80=AFAM <[email protected]> wrote:
>
> From: Kyrylo Tkachov <[email protected]>
>
> The reduction step of a modular arithmetic loop, X >=3D Y ? X - Y : X on =
an
> unsigned type, is exactly MIN (X, X - Y).  When X >=3D Y the difference i=
s 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 a=
nd
> the select fold into one operation.
>
>   unsigned f (unsigned x, unsigned m) { return x >=3D m ? x - m : x; }
>
> aarch64 -O2 -march=3Darmv8.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, v=
31.4s
>         sub     v28.4s, v30.4s, v31.4s   ->   umin      v29.4s, v29.4s, v=
30.4s
>         bif     v28.16b, v30.16b, v29.16b
>
> Four spellings of the variable form are written out because a relational
> carries a fixed operand order, so neither :c nor an inverted arm order is
> available.  A constant modulus needs two more: 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.
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
> Ok for trunk?
> Thanks,
> Kyrill
>
> gcc/ChangeLog:
>
>         * match.pd (X >=3D 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.
>
> Signed-off-by: Kyrylo Tkachov <[email protected]>
> ---
>  gcc/match.pd                                 | 41 ++++++++++++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/modred-min-1.c | 18 +++++++++
>  2 files changed, 59 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/modred-min-1.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 71de58f2fd8..e0ec2626842 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -6345,6 +6345,47 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>   (if (INTEGRAL_TYPE_P (type) ? TYPE_UNSIGNED (type) : POINTER_TYPE_P (ty=
pe))
>    (max @1 @0)))
>
> +/* An unsigned modular reduction, X >=3D Y ? X - Y : X, is MIN (X, X - Y=
).
> +   When X >=3D Y the difference is at most X, and when X < Y the differe=
nce
> +   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 sel=
ect
> +   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.
> +
> +   All four spellings are listed because a relational carries a fixed op=
erand
> +   order, so neither :c nor an inverted arm order is available here.  */
> +(simplify
> + (cond (ge @0 @1) (minus@2 @0 @1) @0)
> + (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type))
> +  (min @0 @2)))
> +(simplify
> + (cond (le @1 @0) (minus@2 @0 @1) @0)
> + (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type))
> +  (min @0 @2)))

These 2 patterns can be combined using the `:c` option on the ge. For
comparisons :c allows for swapped operands and does the right thing.

> +(simplify
> + (cond (lt @0 @1) @0 (minus@2 @0 @1))
> + (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type))
> +  (min @0 @2)))
> +(simplify
> + (cond (gt @1 @0) @0 (minus@2 @0 @1))
> + (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type))
> +  (min @0 @2)))
Likewise.

(I am still thinking of a way to reduce the number of patterns needed
for cond/vec_cond for inverse of the true/false).

> +
> +/* The same reduction by a constant modulus.  There the subtraction has =
been
> +   canonicalised to an addition of the negated modulus and the compare t=
o a
> +   strict one against the modulus less one, so the two constants are rel=
ated
> +   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 =3D=3D -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 =3D=3D -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..f0c3830afb0
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/modred-min-1.c
> @@ -0,0 +1,18 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +/* An unsigned modular reduction is a MIN of the value and the differenc=
e.  */
> +
> +unsigned f1 (unsigned x, unsigned m) { return x >=3D m ? x - m : x; }
> +unsigned f2 (unsigned x, unsigned m) { return m <=3D 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 >=3D m) x -=
=3D m; return x; }
> +unsigned f6 (unsigned x) { return x >=3D 97 ? x - 97 : x; }
> +unsigned f7 (unsigned x) { return x < 97 ? x : x - 97; }
> +
> +/* Must not fold: on a signed type the difference can overflow, and the
> +   wrapping argument that makes the identity hold needs an unsigned type=
.  */
> +int keep (int x, int m) { return x >=3D m ? x - m : x; }
> +
> +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 7 "optimized" } } */

Can you split up the testcase into 2, one for the ones which should be
handled and one that should not be handled.
The reason is your scan only counts the number of MIN_EXPR but it
could be the wrong ones.

Also please add a space after MIN_EXPR so it does not match a
file/directory name.

> --
> 2.50.1 (Apple Git-155)
>