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)
