On Thu, 16 Jul 2026, Tamar Christina wrote:
> > -----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.
I think we can improve on this, yes. Like the previous handling
just maked the lane count even by adding one item to remain (which
is basically picking a subset of accumulated values).
But we should realize what BB vectorization gives us as matches[]
isn't a very good heuristic given we'll happily build things from
scalars once the root stmts match up and fail that, even if so,
when it requires unrolling, producing exactly the power-of-two
reduction as matches[].
I wanted to avoid to read too much into matches[] here and for
the !matches[] case specifically to recurse down to lower and
lower power-of-two number of lanes.
There's also the chance that when instead of trimming down to
the next power of two for say, 6 to 4 lanes, doing 2 lane
discovery with a smaller mode might get us more SLP coverage
(again because of build from scalars).
For BB SLP first-shot discovery we'd really like to have us
continue building even on mismatch, possibly tracking
a failure depth in matches[], that would be more useful
information on how to split up the lanes for roots like
reductions. Possibly also figure how to not pick lane zero
as "matching" but one that gets us the most matches.
The motivation of the patch is to handle better the failures
that are forced upon us due to "unrolling" (otherwise we'll
succeed by building from scalars anyway!) - in that case
the mismatches in the toplevel stmts are exposed in matches[].
I probably should reflect this better in comments. But you
are correct in that further iteration will just what you
proposed - if not power of two all toplevel stmts would
still match, unrolling will force the non-power-of-two tail
to matches[] == false and we'd recurse to build the power-of-two
part. For the !matches[] path we don't yet know which toplevel
stmts match, so there's possible "unbound" recursion.
I'll think of how to best improve this.
Richard.
> 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
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Jochen Jaser, Andrew McDonald, Abhinav Puri; (HRB 36809, AG Nuernberg)
