<[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 is even.
>
> 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. Keep fixed-length constants on the
> existing exact-element path.
>
> A scalable VECTOR_CST can store one element from each pattern and repeat
> the encoded elements. Reduce one copy of such a nonuniform pattern for
> the four idempotent operations. Do not use this path for stepped
> constants or operations whose result depends on the number of repeats.
>
> Keep REDUC_MAX and REDUC_MIN when a repeated element can be a signaling
> NaN. The 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-linux-gnu.
> Ok for trunk?
> Thanks,
> Kyrill
>
> gcc/ChangeLog:
>
> PR tree-optimization/127039
> * fold-const-call.cc (fold_const_reduction): Fold uniform and
> repeating 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 | 35 ++++++-
> gcc/match.pd | 14 +++
> .../gcc.target/aarch64/sve/vec-reduc-dup-1.c | 63 +++++++++++++
> .../aarch64/sve/vec-reduc-pattern-1.c | 93 +++++++++++++++++++
> .../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, 385 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..50c08329286 100644
> --- a/gcc/fold-const-call.cc
> +++ b/gcc/fold-const-call.cc
> @@ -622,11 +622,40 @@ 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;
>
> + unsigned HOST_WIDE_INT nelts;
> + if (!VECTOR_CST_NELTS (arg).is_constant (&nelts))
> + {
I'd normally prefer to structure this kind of thing so that we do
the same calculation for the same encoding regardless of VLA vs VLS.
If operating on the first few elements is good enough for VLA then
it is for VLS too.
> + bool idempotent_p = (code == MAX_EXPR
> + || code == MIN_EXPR
> + || code == BIT_AND_EXPR
> + || code == BIT_IOR_EXPR);
> +
> + /* Fold uniform reductions when the available lane-count information is
> + sufficient to determine the result. */
> + if (tree elem = uniform_vector_p (arg))
> + {
> + if (idempotent_p
> + && !tree_expr_maybe_signaling_nan_p (elem))
> + return elem;
> +
> + if (code == BIT_XOR_EXPR
> + && multiple_p (VECTOR_CST_NELTS (arg), 2))
> + return build_zero_cst (type);
> +
> + return NULL_TREE;
> + }
I'm not sure why this needs to be a special case. Couldn't we instead
handle it in the loop below? Specific suggestion below.
> +
> + /* A nonuniform duplicate constant repeats its encoded elements. An
> + idempotent reduction therefore needs to process them only once. */
> + if (!idempotent_p || !VECTOR_CST_DUPLICATE_P (arg))
> + return NULL_TREE;
> +
> + nelts = vector_cst_encoded_nelts (arg);
> + }
> +
It looks like we could instead structure this as follows:
nelts = vector_cst_encoded_nelts (arg);
if (idempotent_p
&& !VECTOR_CST_STEPPED_P (arg)
&& multiple_p (VECTOR_CST_NELTS (arg), nelts))
/* 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))
/* Everything after the first NELTS elements cancels out to zero. */;
else if (!VECTOR_CST_NELTS (arg).is_constant (&nelts))
return NULL_TREE;
That is, any encoding without VECTOR_CST_STEPPED_P will only include
copies of the explicitly-encoded elements. It can therefore be used
for idemptotent operations if every element is guaranteed to be present.
For the XOR VECTOR_CST_NELTS_PER_PATTERN == 2 case, we'll have one
copy of the first VECTOR_CST_NPATTERNS elements and an odd number
(3 or more) copies of the second VECTOR_CST_NPATTERNS elements.
The fold works there too, not just for the duplicate case.
Thanks,
Richard
> tree res = VECTOR_CST_ELT (arg, 0);
> for (unsigned HOST_WIDE_INT i = 1; i < nelts; i++)
> {
> 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..f2f6837ca28
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/sve/vec-reduc-pattern-1.c
> @@ -0,0 +1,93 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fgimple -fdump-tree-forwprop1" } */
> +
> +#include <arm_sve.h>
> +
> +/* Check that idempotent reductions process a repeated pattern once. Keep
> + reductions that depend on the repeat count or use a stepped pattern. */
> +
> +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;
> +}
> +
> +/* { dg-final { scan-tree-dump-times {\.REDUC_} 3 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {\.REDUC_MAX \(\{ 1, 2, 3, \.\.\. \}\)}
> 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;} 1 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {return 1;} 1 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times {return 7;} 1 "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" } } */
