[v2] match.pd: fold an unsigned modular reduction into MIN
Checks
Commit Message
From: Kyrylo Tkachov <ktkachov@nvidia.com>
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 <ktkachov@nvidia.com>
---
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
Comments
On Wed, Aug 5, 2026 at 4:50 AM <ktkachov@nvidia.com> wrote:
>
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> 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 <ktkachov@nvidia.com>
> ---
> 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)
>
@@ -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)))
+
+/* 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))
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */