> -----Original Message-----
> From: Richard Biener <[email protected]>
> Sent: 16 July 2026 10:41
> To: Tamar Christina <[email protected]>
> Cc: [email protected]
> Subject: RE: [PATCH] Improve BB vectorization of reductions
>
> 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).
Right, though this depends a bit on the type of reduction right,
since if we needed something like a FOLD_LEFT_ then the smaller
lane groupings could end up being more expensive.
>
> 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.
>
Right, so essentially instead of rejecting the tree and rebuilding
from the matches/scalars we just trim the tree that was built?
> 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.
Thanks!
I was also thinking how to extend this later after Chris's BB SLP
patch since for there we don't have the pow2 restriction but a
maximum size restriction.
Cheers,
Tamar
>
> 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)
