> -----Original Message-----
> From: Richard Biener <[email protected]>
> Sent: 16 July 2026 08:43
> To: [email protected]
> Cc: Tamar Christina <[email protected]>
> Subject: [PATCH] Improve BB vectorization of reductions
>
> When there's not a uniform chain of operations gathered from the
> reduction operation chain we currently simply fail and to make
> success more likely we strip off the last operation to make the
> number of lanes at least even. This isn't ideal and somewhat
> random as can be seen in PR126028 which is the motivating case
> and has a three lane reduction. So the following removes the
> early stripping down to an even number of lanes and uses SLP
> discovery of the whole group to direct re-analysis of the
> (possibly) matching part if it happens to be of power-of-two
> size which is mainly to reduce possible recursion but could be
> relaxed if there is motivating cases.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> OK?
LGTM, just some suggestions below
>
> Thanks,
> Richard.
>
> PR tree-optimization/126028
> * tree-vect-slp.cc (vect_slp_check_for_roots): Do not
> force the BB reduction root to have an even number of lanes.
> (vect_build_slp_instance): For failed discovery of a BB
> reduction attempt to re-try discovery on the matching or
> non-matching part if either of those is of power-of-two
> size.
>
> * gcc.dg/vect/bb-slp-reduc-2.c: New testcase.
> ---
> gcc/testsuite/gcc.dg/vect/bb-slp-reduc-2.c | 12 +++++
> gcc/tree-vect-slp.cc | 58 ++++++++++++++++++----
> 2 files changed, 60 insertions(+), 10 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-reduc-2.c
>
> diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-reduc-2.c
> b/gcc/testsuite/gcc.dg/vect/bb-slp-reduc-2.c
> new file mode 100644
> index 00000000000..d4cfadfaa3b
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/vect/bb-slp-reduc-2.c
> @@ -0,0 +1,12 @@
> +/* { dg-do compile } */
> +/* { dg-require-effective-target vect_int } */
> +
> +int foo (int *a, int *b, int c)
> +{
> + return (c ^ 1) + ((a[0] | b[0]) + (a[1] | b[1]) + (a[2] | b[2]) + (a[3] |
> b[3]));
> +}
> +
> +/* Make sure that we pick matching lanes when attempting to BB vectorize
> + a reduction rather than arbitrarily cutting back to the number of
> + vector lanes. */
> +/* { dg-final { scan-tree-dump "optimized: basic block part vectorized"
> "slp2"
> { target { vect_hw_misalign && { x86_64-*-* i?86-*-* aarch64-*-* } } } } } */
> diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
> index ea6e57aacb3..63baa17d09d 100644
> --- a/gcc/tree-vect-slp.cc
> +++ b/gcc/tree-vect-slp.cc
> @@ -4321,6 +4321,53 @@ vect_build_slp_instance (vec_info *vinfo,
> vect_analyze_slp_instance now. */
> gcc_assert (kind != slp_inst_kind_store || group_size == 1);
>
> + /* For BB reductions try to extend remain by the non-matching lanes from
> + the above discovery attempt if the matching part might be of power-of-
> two
> + size. */
> + if (kind == slp_inst_kind_bb_reduc && matches[0])
> + {
> + unsigned n_matching = 0;
> + for (unsigned i = 0; i < group_size; ++i)
NIT: since we already tested matches[0] here we can technically start
n_matching at 1
and skip start i at 1 too.
> + if (matches[i])
> + n_matching++;
> + vec<stmt_vec_info> scalar_stmts2 = vNULL;
> + /* Try matched parts and put the rest to remain. */
> + if (n_matching >= 2 && pow2p_hwi (n_matching))
> + {
> + scalar_stmts2.create (n_matching);
> + for (unsigned i = 0; i < group_size; ++i)
> + if (matches[i])
> + scalar_stmts2.quick_push (scalar_stmts[i]);
> + else
> + remain.safe_push
> + (gimple_get_lhs (vect_orig_stmt (scalar_stmts[i])->stmt));
> + }
> + /* Try the non-matching part. */
> + else if (scalar_stmts.length () - n_matching >= 2
> + && pow2p_hwi (scalar_stmts.length () - n_matching))
> + {
> + scalar_stmts2.create (scalar_stmts.length () - n_matching);
> + for (unsigned i = 0; i < group_size; ++i)
> + if (!matches[i])
> + scalar_stmts2.quick_push (scalar_stmts[i]);
> + else
> + remain.safe_push
> + (gimple_get_lhs (vect_orig_stmt (scalar_stmts[i])->stmt));
> + }
> + if (scalar_stmts2.exists ())
> + {
> + if (dump_enabled_p ())
> + dump_printf_loc (MSG_NOTE, vect_location, "Splitting %d "
> + "non-matching lanes to scalar remains\n",
> + scalar_stmts.length () - scalar_stmts2.length ());
> + scalar_stmts.release ();
> + return vect_build_slp_instance (vinfo, kind, scalar_stmts2,
> + root_stmt_infos, remain,
> + max_tree_size, limit, bst_map,
> + force_single_lane);
> + }
> + }
For this part can we not deal with the non-power of two cases by rounding down
to
the nearest power of two and then consuming matches in reverse order (so the
datarefs
don't think we want to slice out a chunk of data in the middle of the block).
i.e. we can BB SLP this block no?
int foo (int *a, int *b, int c)
{
return (c ^ 1) + ((a[0] | b[0]) + (a[1] | b[1]) + (a[2] | b[2]) + (a[3] |
b[3]) + (a[4] | b[4]));
}
Rounding down and consuming from the back (in a very quick hacky way) gives me
foo:
ldr q31, [x0]
eor w2, w2, 1
ldr q30, [x1]
ldr w0, [x0, 16]
ldr w1, [x1, 16]
orr v30.16b, v31.16b, v30.16b
orr w0, w0, w1
add w2, w2, w0
addv s31, v30.4s
fmov w0, s31
add w0, w0, w2
ret
which looks good.
Thanks,
Tamar
> +
> /* Free the allocated memory. */
> scalar_stmts.release ();
>
> @@ -9984,7 +10031,6 @@ vect_slp_check_for_roots (bb_vec_info bb_vinfo)
> /* ??? For now do not allow mixing ops or externs/constants. */
> bool invalid = false;
> unsigned remain_cnt = 0;
> - unsigned last_idx = 0;
> for (unsigned i = 0; i < chain.length (); ++i)
> {
> if (chain[i].code != code)
> @@ -9999,13 +10045,7 @@ vect_slp_check_for_roots (bb_vec_info
> bb_vinfo)
> (chain[i].op)->stmt)
> != chain[i].op))
> remain_cnt++;
> - else
> - last_idx = i;
> }
> - /* Make sure to have an even number of lanes as we later do
> - all-or-nothing discovery, not trying to split further. */
> - if ((chain.length () - remain_cnt) & 1)
> - remain_cnt++;
> if (!invalid && chain.length () - remain_cnt > 1)
> {
> vec<stmt_vec_info> stmts;
> @@ -10018,9 +10058,7 @@ vect_slp_check_for_roots (bb_vec_info
> bb_vinfo)
> stmt_vec_info stmt_info;
> if (chain[i].dt == vect_internal_def
> && ((stmt_info = bb_vinfo->lookup_def
> (chain[i].op)),
> - gimple_get_lhs (stmt_info->stmt) == chain[i].op)
> - && (i != last_idx
> - || (stmts.length () & 1)))
> + gimple_get_lhs (stmt_info->stmt) == chain[i].op))
> stmts.quick_push (stmt_info);
> else
> remain.quick_push (chain[i].op);
> --
> 2.51.0
