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

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

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 >= 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 (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.
+
+   All four spellings are listed because a relational carries a fixed operand
+   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)))
+(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)))
+
+/* 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..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 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; }
+
+/* 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 >= m ? x - m : x; }
+
+/* { dg-final { scan-tree-dump-times "MIN_EXPR" 7 "optimized" } } */
-- 
2.50.1 (Apple Git-155)