[PATCH] match.pd: combine a pair of vector reductions

From: Kyrylo Tkachov <[email protected]>

Two reductions feeding the matching scalar operation are one reduction of
the elementwise operation:

  REDUC (a) op REDUC (b)  ->  REDUC (a op b)

The two sides accumulate the same multiset of lanes, just grouped
differently, so for the associative and commutative reductions the result
is identical.  This trades a lane-crossing reduction, which is the
expensive part, for an elementwise operation.

MIN, MAX, AND, IOR and XOR need no flag.  The sum needs one only for
floating point, where the regrouping is a reassociation; the integer sum
is done in the unsigned type, since the reduction wraps while the signed
vector type has undefined overflow.

  #include <arm_neon.h>
  int f (int32x4_t a, int32x4_t b) { return vaddvq_s32 (a) + vaddvq_s32 (b); }

aarch64 -O3 before:

	addv	s1, v1.4s
	addv	s0, v0.4s
	fmov	w1, s1
	fmov	w0, s0
	add	w0, w0, w1

after:

	add	v0.4s, v0.4s, v1.4s
	addv	s0, v0.4s
	fmov	w0, s0

A pair of maxima goes from 8 instructions to 3.  On a target without a
horizontal reduce instruction the reduction is open coded as a chain of
shuffles, so the saving is larger there, never smaller.

For integers, preserve trapping and sanitized scalar overflow.
For floating point, require reassociation, insignificant zero signs, and non-trapping exceptions.

Restrict the reassociative alternative to floating-point types.
Floating-point options must not license fixed-point saturation changes.

Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill

gcc/ChangeLog:

	* match.pd (REDUC (a) op REDUC (b)): New simplifications combining
	two reductions into one.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/vec-reduc-pair-1.c: New test.
	* gcc.dg/tree-ssa/vec-reduc-pair-2.c: New test.
	* gcc.dg/tree-ssa/vec-reduc-pair-3.c: New test.
	* gcc.dg/tree-ssa/vec-reduc-pair-4.c: New test.

Signed-off-by: Kyrylo Tkachov <[email protected]>
---
 gcc/match.pd                                  | 35 +++++++++++++++++++
 .../gcc.dg/tree-ssa/vec-reduc-pair-1.c        | 11 ++++++
 .../gcc.dg/tree-ssa/vec-reduc-pair-2.c        | 13 +++++++
 .../gcc.dg/tree-ssa/vec-reduc-pair-3.c        | 12 +++++++
 .../gcc.dg/tree-ssa/vec-reduc-pair-4.c        | 13 +++++++
 5 files changed, 84 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-2.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-3.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-4.c

diff --git a/gcc/match.pd b/gcc/match.pd
index fe058d8c2a8..85fea9fa18f 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -12038,6 +12038,41 @@ and,
   (simplify (reduc (op @0 VECTOR_CST@1))
     (op (reduc:type @0) (reduc:type @1))))
 
+/* Fold REDUC_PLUS (@0) +- REDUC_PLUS (@1) as REDUC_PLUS (@0 +- @1).  This
+   trades one lane-crossing reduction for one elementwise operation.  The
+   elementwise operation is done in the unsigned type because the reduction
+   itself wraps and the signed vector type has undefined overflow.  */
+(for op (plus minus)
+ (simplify
+  (op (IFN_REDUC_PLUS:s @0) (IFN_REDUC_PLUS:s @1))
+  (if (types_match (TREE_TYPE (@0), TREE_TYPE (@1))
+       && ((ANY_INTEGRAL_TYPE_P (type)
+	    && !TYPE_OVERFLOW_TRAPS (type)
+	    && !TYPE_OVERFLOW_SANITIZED (type))
+	   || (FLOAT_TYPE_P (type)
+	       && flag_associative_math
+	       && !HONOR_SIGNED_ZEROS (type)
+	       && !flag_trapping_math))
+       && target_supports_op_p (TREE_TYPE (@0), op, optab_vector))
+   (with { tree vtype = (ANY_INTEGRAL_TYPE_P (type)
+			 ? unsigned_type_for (TREE_TYPE (@0))
+			 : TREE_TYPE (@0));
+	   tree stype = TREE_TYPE (vtype); }
+    (convert (IFN_REDUC_PLUS:stype
+	      (op (view_convert:vtype @0) (view_convert:vtype @1))))))))
+
+/* Fold REDUC (@0) op REDUC (@1) as REDUC (@0 op @1) for the reductions whose
+   scalar operation is associative and commutative with no flag needed.  This
+   removes one lane-crossing reduction.  */
+(for reduc (IFN_REDUC_MAX IFN_REDUC_MIN IFN_REDUC_AND IFN_REDUC_IOR
+	    IFN_REDUC_XOR)
+     op (max min bit_and bit_ior bit_xor)
+ (simplify
+  (op (reduc:s @0) (reduc:s @1))
+  (if (types_match (TREE_TYPE (@0), TREE_TYPE (@1))
+       && target_supports_op_p (TREE_TYPE (@0), op, optab_vector))
+   (reduc (op @0 @1)))))
+
 /* Simplify .REDUC_IOR (@0) ==/!= 0 to @0 ==/!= 0.  */
 (for cmp (eq ne)
  (simplify
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-1.c b/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-1.c
new file mode 100644
index 00000000000..01da5c2da34
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-1.c
@@ -0,0 +1,11 @@
+/* { dg-do compile { target aarch64*-*-* } } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* Two reductions feeding the matching scalar operation are one reduction of
+   the elementwise operation, which trades a lane-crossing reduction for an
+   elementwise one.  */
+#include <arm_neon.h>
+int f (int32x4_t a, int32x4_t b) { return vaddvq_s32 (a) + vaddvq_s32 (b); }
+int g (int32x4_t a, int32x4_t b) { return vaddvq_s32 (a) - vaddvq_s32 (b); }
+int h (int32x4_t a, int32x4_t b) { int x = vmaxvq_s32 (a), y = vmaxvq_s32 (b); return x > y ? x : y; }
+/* { dg-final { scan-tree-dump-times "REDUC_PLUS" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "REDUC_MAX" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-2.c b/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-2.c
new file mode 100644
index 00000000000..75d4369fc9f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-2.c
@@ -0,0 +1,13 @@
+/* { dg-do compile { target aarch64*-*-* } } */
+/* { dg-options "-O2 -ftrapv -fdump-tree-optimized" } */
+
+#include <arm_neon.h>
+
+int
+f (int32x4_t a, int32x4_t b)
+{
+  return vaddvq_s32 (a) + vaddvq_s32 (b);
+}
+
+/* Trapping scalar addition must remain outside the reductions.  */
+/* { dg-final { scan-tree-dump-times "REDUC_PLUS" 2 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-3.c b/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-3.c
new file mode 100644
index 00000000000..4a9a3639b93
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-3.c
@@ -0,0 +1,12 @@
+/* { dg-do compile { target aarch64*-*-* } } */
+/* { dg-options "-O2 -fassociative-math -fno-signed-zeros -fno-trapping-math -fdump-tree-optimized" } */
+
+#include <arm_neon.h>
+
+double
+f (float64x2_t a, float64x2_t b)
+{
+  return vaddvq_f64 (a) - vaddvq_f64 (b);
+}
+
+/* { dg-final { scan-tree-dump-times "REDUC_PLUS" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-4.c b/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-4.c
new file mode 100644
index 00000000000..cf0b0b6d44f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vec-reduc-pair-4.c
@@ -0,0 +1,13 @@
+/* { dg-do compile { target aarch64*-*-* } } */
+/* { dg-options "-O2 -ftrapping-math -fdump-tree-optimized" } */
+
+#include <arm_neon.h>
+
+__attribute__((optimize ("associative-math,no-signed-zeros")))
+double
+f (float64x2_t a, float64x2_t b)
+{
+  return vaddvq_f64 (a) - vaddvq_f64 (b);
+}
+
+/* { dg-final { scan-tree-dump-times "REDUC_PLUS" 2 "optimized" } } */
-- 
2.50.1 (Apple Git-155)