<[email protected]> writes:
> From: Kyrylo Tkachov <[email protected]>
>
> REDUC_MAX, REDUC_MIN, REDUC_AND and REDUC_IOR are idempotent. A
> reduction of a nonempty duplicate vector with one of these operations is
> the duplicated element:
>
> v = [vec_duplicate_expr] x;
> res = .REDUC_MAX (v);
>
> becomes:
>
> res = x;
>
> For example, the new SVE test contains:
>
> int __GIMPLE ()
> reduc_max (int x)
> {
> svint32_t v;
> int res;
>
> v = svdup_s32 (x);
> res = .REDUC_MAX (v);
> return res;
> }
>
> With -O2 -fgimple -march=armv8.2-a+sve, the code changes from:
>
> reduc_max:
> mov z31.s, w0
> ptrue p7.b, all
> smaxv s31, p7, z31.s
> fmov w0, s31
> ret
>
> to:
>
> reduc_max:
> ret
>
> An XOR reduction of a duplicate vector is zero when the number of lanes
> is even. GCC permits variable-length vectors whose lane count has
> unknown parity, such as [1, 1]. Fold REDUC_XOR only when multiple_p
> proves that every possible lane count has the required parity.
>
> Use the same two paths as IFN_VEC_EXTRACT and IFN_VEC_SHL_INSERT. Match
> a nonconstant VEC_DUPLICATE_EXPR directly in match.pd. Handle a
> VECTOR_CST in fold_const_reduction.
>
> Start constant folding with the explicitly encoded elements for both
> fixed-length and variable-length vectors. A non-stepped encoding can be
> used for an idempotent reduction when every encoded element is guaranteed
> to be present. For XOR, require the remaining encoded copies to cancel
> in pairs. Process two periods of a duplicate encoding, or the foreground
> and background of a two-element-per-pattern encoding. Use the exact
> element count as a fallback when it is known.
>
> Keep REDUC_MAX and REDUC_MIN when a shortened reduction could return a
> signaling NaN directly. The full reduction can quiet the NaN and raise an
> invalid-operation exception.
>
> These folds also let the constant reduction in the PR 127039 rule
> simplify for scalable constants. The scalar result cannot match the
> inverse reduction-pair rule, so the nontermination cycle stays blocked.
>
> Bootstrapped and tested on aarch64-none-linunx-gnu.
> Ok for trunk?
> Thanks,
> Kyrill
>
> gcc/ChangeLog:
>
> PR tree-optimization/127039
> * fold-const-call.cc (fold_const_reduction): Fold non-stepped constants
> when the available lane-count information determines the result.
> * match.pd (reduction of a vector duplicate): New simplifications to
> the duplicated element or zero.
>
> gcc/testsuite/ChangeLog:
>
> PR tree-optimization/127039
> * gcc.target/aarch64/sve/vec-reduc-dup-1.c: New test.
> * gcc.target/aarch64/sve/vec-reduc-pattern-1.c: New test.
> * gcc.target/aarch64/sve/vec-reduc-snan-1.c: New test.
> * gcc.target/aarch64/sve/vec-reduc-uniform-1.c: New test.
> * gcc.target/riscv/rvv/base/reduc-xor-uniform-1.c: New test.
>
> Signed-off-by: Kyrylo Tkachov <[email protected]>
> ---
> gcc/fold-const-call.cc | 36 +++-
> gcc/match.pd | 14 ++
> .../gcc.target/aarch64/sve/vec-reduc-dup-1.c | 63 +++++++
> .../aarch64/sve/vec-reduc-pattern-1.c | 156 ++++++++++++++++++
> .../gcc.target/aarch64/sve/vec-reduc-snan-1.c | 65 ++++++++
> .../aarch64/sve/vec-reduc-uniform-1.c | 71 ++++++++
> .../riscv/rvv/base/reduc-xor-uniform-1.c | 47 ++++++
> 7 files changed, 449 insertions(+), 3 deletions(-)
> create mode 100644 gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-dup-1.c
> create mode 100644 gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-pattern-1.c
> create mode 100644 gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-snan-1.c
> create mode 100644 gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-uniform-1.c
> create mode 100644
> gcc/testsuite/gcc.target/riscv/rvv/base/reduc-xor-uniform-1.c
>
> diff --git a/gcc/fold-const-call.cc b/gcc/fold-const-call.cc
> index c483b80e704..342a65f4217 100644
> --- a/gcc/fold-const-call.cc
> +++ b/gcc/fold-const-call.cc
> @@ -622,9 +622,39 @@ fold_const_builtin_nan (tree type, tree arg, bool quiet)
> static tree
> fold_const_reduction (tree type, tree arg, tree_code code)
> {
> - unsigned HOST_WIDE_INT nelts;
> - if (TREE_CODE (arg) != VECTOR_CST
> - || !VECTOR_CST_NELTS (arg).is_constant (&nelts))
> + if (TREE_CODE (arg) != VECTOR_CST)
> + return NULL_TREE;
> +
> + bool idempotent_p = (code == MAX_EXPR
> + || code == MIN_EXPR
> + || code == BIT_AND_EXPR
> + || code == BIT_IOR_EXPR);
> +
> + unsigned HOST_WIDE_INT nelts = vector_cst_encoded_nelts (arg);
> + bool singleton_snan_p
> + = (nelts == 1
> + && tree_expr_maybe_signaling_nan_p (VECTOR_CST_ELT (arg, 0)));
> +
> + if (idempotent_p
> + && !VECTOR_CST_STEPPED_P (arg)
> + && multiple_p (VECTOR_CST_NELTS (arg), nelts)
> + && !singleton_snan_p)
I don't understand why the singleton_snan_p exception is needed.
Doesn't that imply that we mishandle that situation below?
The condition seems to mean that a 128-bit SVE vector will be handled
differently for -msve-vector-bits=128 and -msve-vector-bits=scalable,
despite the behaviour being the same at runtime.
> + /* Operating on the first NELTS elements is enough. */
> + ;
> + else if (code == BIT_XOR_EXPR
> + && !VECTOR_CST_STEPPED_P (arg)
> + && multiple_p (VECTOR_CST_NELTS (arg), nelts * 2))
> + {
> + if (VECTOR_CST_DUPLICATE_P (arg))
> + {
> + /* Process two copies of a one-element-per-pattern encoding. */
> + nelts *= 2;
Oops, forgot to do that. (The braces aren't necessary though.)
Thanks,
Richard
> + }
> + else
> + gcc_checking_assert (VECTOR_CST_NELTS_PER_PATTERN (arg) == 2);
> + }
> +
> + else if (!VECTOR_CST_NELTS (arg).is_constant (&nelts))
> return NULL_TREE;
>
> tree res = VECTOR_CST_ELT (arg, 0);
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 04a3ee3ab20..dfedb8973e1 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -14363,6 +14363,20 @@ and,
> (if (elem)
> { build_vector_from_val (type, elem); }))))
>
> +/* A reduction of a duplicate vector with an idempotent operation is the
> + duplicated element. */
> +(for reduc (IFN_REDUC_MAX IFN_REDUC_MIN IFN_REDUC_AND IFN_REDUC_IOR)
> + (simplify
> + (reduc (vec_duplicate @0))
> + (if (!tree_expr_maybe_signaling_nan_p (@0))
> + @0)))
> +
> +/* Fold an XOR reduction of an even-length duplicate vector to zero. */
> +(simplify
> + (IFN_REDUC_XOR (vec_duplicate@1 @0))
> + (if (multiple_p (TYPE_VECTOR_SUBPARTS (TREE_TYPE (@1)), 2))
> + { build_zero_cst (type); }))
> +
> /* Push VEC_PERM earlier if that may help FMA perception (PR101895). */
> (simplify
> (plus:c (vec_perm:s (mult:c@0 @1 vec_same_elem_p@2) @0 @3) @4)
> diff --git a/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-dup-1.c
> b/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-dup-1.c
> new file mode 100644
> index 00000000000..9d5581d6811
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-dup-1.c
> @@ -0,0 +1,63 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fgimple -fdump-tree-forwprop1" } */
> +
> +#include <arm_sve.h>
> +
> +int __GIMPLE ()
> +reduc_max (int x)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdup_s32 (x);
> + res = .REDUC_MAX (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_min (int x)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdup_s32 (x);
> + res = .REDUC_MIN (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_and (int x)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdup_s32 (x);
> + res = .REDUC_AND (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_ior (int x)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdup_s32 (x);
> + res = .REDUC_IOR (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_xor (int x)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdup_s32 (x);
> + res = .REDUC_XOR (v);
> + return res;
> +}
> +
> +/* { dg-final { scan-tree-dump-not {\.REDUC_} "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {return x_} 4 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {return 0;} 1 "forwprop1" } } */
> diff --git a/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-pattern-1.c
> b/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-pattern-1.c
> new file mode 100644
> index 00000000000..59a3344f96b
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-pattern-1.c
> @@ -0,0 +1,156 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fgimple -fdump-tree-forwprop1" } */
> +
> +#include <arm_sve.h>
> +
> +/* Check reductions for which the encoded elements and lane count determine
> + the result. Keep reductions whose result can vary with the vector
> length. */
> +
> +int __GIMPLE ()
> +reduc_max_repeat (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdupq_s32 (3, 5, 3, 5);
> + res = .REDUC_MAX (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_min_repeat (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdupq_s32 (3, 5, 3, 5);
> + res = .REDUC_MIN (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_and_repeat (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdupq_s32 (3, 5, 3, 5);
> + res = .REDUC_AND (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_ior_repeat (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdupq_s32 (3, 5, 3, 5);
> + res = .REDUC_IOR (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_max_series (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svindex_s32 (1, 1);
> + res = .REDUC_MAX (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_plus_repeat (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdupq_s32 (3, 5, 3, 5);
> + res = .REDUC_PLUS (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_xor_unknown (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdupq_s32 (1, 2, 4, 8);
> + res = .REDUC_XOR (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_xor_repeat_even (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = svdupq_s32 (1, 2, 1, 2);
> + res = .REDUC_XOR (v);
> + return res;
> +}
> +
> +/* Form non-stepped constants with foreground and background elements. */
> +
> +static inline __attribute__ ((always_inline)) svint32_t
> +initial_one (void)
> +{
> + svint32_t v = { 3 };
> + return v;
> +}
> +
> +static inline __attribute__ ((always_inline)) svint32_t
> +initial_four (void)
> +{
> + svint32_t v = { -3, -5, -6, -7 };
> + return v;
> +}
> +
> +int __GIMPLE ()
> +reduc_max_initial_repeat (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = initial_one ();
> + res = .REDUC_MAX (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_xor_initial_repeat (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = initial_one ();
> + res = .REDUC_XOR (v);
> + return res;
> +}
> +
> +int __GIMPLE ()
> +reduc_max_incomplete_pattern (void)
> +{
> + svint32_t v;
> + int res;
> +
> + v = initial_four ();
> + res = .REDUC_MAX (v);
> + return res;
> +}
> +
> +/* { dg-final { scan-tree-dump-times {\.REDUC_} 4 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MAX \(\{ 1, 2, 3, \.\.\. \}\)}
> 1 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MAX \(\{ -3, -5, -6, -7, 0, 0,
> 0, 0, \.\.\. \}\)} 1 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_PLUS \(\{ 3, 5, \.\.\. \}\)} 1
> "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_XOR \(\{ 1, 2, 4, 8, \.\.\.
> \}\)} 1 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {return 5;} 1 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {return 3;} 3 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {return 1;} 1 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {return 7;} 1 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {return 0;} 1 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-not {return 6;} "forwprop1" } } */
> diff --git a/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-snan-1.c
> b/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-snan-1.c
> new file mode 100644
> index 00000000000..8781380510e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-snan-1.c
> @@ -0,0 +1,65 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fgimple -fsignaling-nans -fdump-tree-forwprop1" } */
> +
> +#include <arm_sve.h>
> +
> +#define SNAN_F32_BITS 0x7f800001U
> +
> +float __GIMPLE ()
> +reduc_max_dup (float x)
> +{
> + svfloat32_t v;
> + float res;
> +
> + v = svdup_f32 (x);
> + res = .REDUC_MAX (v);
> + return res;
> +}
> +
> +float __GIMPLE ()
> +reduc_min_dup (float x)
> +{
> + svfloat32_t v;
> + float res;
> +
> + v = svdup_f32 (x);
> + res = .REDUC_MIN (v);
> + return res;
> +}
> +
> +typedef float v4sf __attribute__ ((vector_size (16)));
> +typedef unsigned int v4su __attribute__ ((vector_size (16)));
> +
> +float __GIMPLE ()
> +reduc_max_cst (void)
> +{
> + v4su u;
> + v4sf v;
> + float res;
> +
> + u = _Literal (v4su) { SNAN_F32_BITS, SNAN_F32_BITS,
> + SNAN_F32_BITS, SNAN_F32_BITS };
> + v = __VIEW_CONVERT <v4sf> (u);
> + res = .REDUC_MAX (v);
> + return res;
> +}
> +
> +float __GIMPLE ()
> +reduc_min_cst (void)
> +{
> + v4su u;
> + v4sf v;
> + float res;
> +
> + u = _Literal (v4su) { SNAN_F32_BITS, SNAN_F32_BITS,
> + SNAN_F32_BITS, SNAN_F32_BITS };
> + v = __VIEW_CONVERT <v4sf> (u);
> + res = .REDUC_MIN (v);
> + return res;
> +}
> +
> +/* { dg-final { scan-tree-dump-times {vec_duplicate_expr} 2 "forwprop1" } }
> */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MAX} 2 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MIN} 2 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MAX \(.*Nan} 1 "forwprop1" } }
> */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MIN \(.*Nan} 1 "forwprop1" } }
> */
> diff --git a/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-uniform-1.c
> b/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-uniform-1.c
> new file mode 100644
> index 00000000000..9830511b18d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-uniform-1.c
> @@ -0,0 +1,71 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -msve-vector-bits=scalable
> -mautovec-preference=sve-only -fvect-cost-model=unlimited
> --param=vect-partial-vector-usage=0 -fdump-tree-vect-details
> -fdump-tree-forwprop4" } */
> +
> +/* Check reductions of scalable uniform vector constants. */
> +
> +char c1, c2, c3, c4, c5;
> +short d1, d2, d3, d4, d5;
> +int rmax, rmin, r_and, r_ior, r_xor;
> +unsigned n;
> +
> +__attribute__ ((noipa)) void
> +max_uniform (void)
> +{
> + for (short i = 0; i < n; i += 3)
> + {
> + c1 ^= d1;
> + rmax = rmax > 17 ? rmax : 17;
> + }
> +}
> +
> +__attribute__ ((noipa)) void
> +min_uniform (void)
> +{
> + for (short i = 0; i < n; i += 3)
> + {
> + c2 ^= d2;
> + rmin = rmin < -19 ? rmin : -19;
> + }
> +}
> +
> +__attribute__ ((noipa)) void
> +and_uniform (void)
> +{
> + for (short i = 0; i < n; i += 3)
> + {
> + c3 ^= d3;
> + r_and &= 1431655765;
> + }
> +}
> +
> +__attribute__ ((noipa)) void
> +ior_uniform (void)
> +{
> + for (short i = 0; i < n; i += 3)
> + {
> + c4 ^= d4;
> + r_ior |= 572662306;
> + }
> +}
> +
> +__attribute__ ((noipa)) void
> +xor_uniform (void)
> +{
> + for (short i = 0; i < n; i += 3)
> + {
> + c5 ^= d5;
> + r_xor ^= 858993459;
> + }
> +}
> +
> +/* { dg-final { scan-tree-dump-times {LOOP VECTORIZED} 5 "vect" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MAX} 1 "forwprop4" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MIN} 1 "forwprop4" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_AND} 1 "forwprop4" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_IOR} 1 "forwprop4" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MAX \(vect_rmax_lsm} 1
> "forwprop4" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MIN \(vect_rmin_lsm} 1
> "forwprop4" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_AND \(vect_r_and_lsm} 1
> "forwprop4" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_IOR \(vect_r_ior_lsm} 1
> "forwprop4" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_XOR} 5 "forwprop4" } } */
> +/* { dg-final { scan-tree-dump-not {\.REDUC_XOR \(\{ 0, \.\.\. \}\)}
> "forwprop4" } } */
> diff --git a/gcc/testsuite/gcc.target/riscv/rvv/base/reduc-xor-uniform-1.c
> b/gcc/testsuite/gcc.target/riscv/rvv/base/reduc-xor-uniform-1.c
> new file mode 100644
> index 00000000000..54339490fd8
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/riscv/rvv/base/reduc-xor-uniform-1.c
> @@ -0,0 +1,47 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fgimple -march=rv64im_zve64f -mabi=lp64
> -fdump-tree-forwprop1" } */
> +/* { dg-final { check-function-bodies "**" "" } } */
> +
> +#include "riscv_vector.h"
> +
> +/*
> +** reduc_xor_even:
> +** li a0,0
> +** ret
> +*/
> +long __GIMPLE ()
> +reduc_xor_even (void)
> +{
> + vbool32_t mask;
> + vint64m2_t ones;
> + long res;
> +
> + mask = _Literal (vint64m2_t) 0 == _Literal (vint64m2_t) 0;
> + ones = .VEC_CONVERT (mask);
> + res = .REDUC_XOR (ones);
> + return res;
> +}
> +
> +/*
> +** reduc_xor_unknown:
> +** vsetvli [a-x0-9]+,zero,e64,m1,ta,ma
> +** ...
> +** vredxor\.vs v[0-9]+,v[0-9]+,v[0-9]+
> +** ...
> +** ret
> +*/
> +long __GIMPLE ()
> +reduc_xor_unknown (void)
> +{
> + vbool64_t mask;
> + vint64m1_t ones;
> + long res;
> +
> + mask = _Literal (vint64m1_t) 0 == _Literal (vint64m1_t) 0;
> + ones = .VEC_CONVERT (mask);
> + res = .REDUC_XOR (ones);
> + return res;
> +}
> +
> +/* { dg-final { scan-tree-dump-times {\.REDUC_XOR} 1 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {return 0;} 1 "forwprop1" } } */
