On Thu, 16 Jul 2026, Tamar Christina wrote:
> > -----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.
Yeah, I have a patch to make us handle 2-lane in-order reductions,
but otherwise these are not handled yet.
> >
> > 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?
That might be possible as well, but I thought to just have more
useful data here - basically have a mode that never builds from
scalars but fails with some depth indication. And even per
lane. For loop vect we already get the former for free, but if
we want to consider "forking" the graph during discovery the
latter might be also useful. But of course it comes at discovery cost.
> > 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.
Yeah, which is why I didn't even consider to touch the early
failure due to unrolling - if all lanes match we still fail
due to that, but too early, in case we'd get more useful split
hints from downward operand build failures.
Richard.
> 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)
>
--
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)
