On Thu, 16 Jul 2026, Tamar Christina wrote:
> > -----Original Message-----
> > From: Richard Biener <[email protected]>
> > Sent: 16 July 2026 13:49
> > To: [email protected]
> > Cc: Tamar Christina <[email protected]>
> > Subject: [PATCH][v2] 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
> > larger of the matching or non-matching part.
> >
> > For gcc.dg/vect/pr106081.c we now BB vectorize parts which
> > just confuses the loop vectorization dump scanning, so disable it.
> >
> > Bootstrapped and tested on x86_64-unknown-linux-gnu.
> >
> > v2: relax power-of-two size restiction by simply recursing on
> > the larger, matching or not matching part
> >
> > OK?
>
> Ah. Clever, using integer division.
>
> Still is an improvement and LGTM, but I think the fact that the
> vect testsuite is running the tests with -fno-vect-cost-model makes
> it hide that we'd never vectorizer gcc.dg/vect/bb-slp-reduc-3.c normally.
>
> The group gets created in the middle of the DR group, and so SLP seems to
> think it has to preserve the load order and can't do a vector load.
>
> So the example ends up doing
>
> foo:
> ldp s28, s31, [x0, 12]
> eor w2, w2, 1
> ldp s29, s30, [x1, 12]
> ins v31.s[1], v28.s[0]
> ldp w3, w4, [x0, 4]
> ins v30.s[1], v29.s[0]
> ins v31.s[2], w4
> ldp w4, w5, [x1, 4]
> ins v30.s[2], w5
> ld1 {v31.s}[3], [x0]
> orr w3, w3, w4
> add w2, w2, w3
> ld1 {v30.s}[3], [x1]
> orr v30.16b, v31.16b, v30.16b
> addv s31, v30.4s
> fmov w0, s31
> add w0, w0, w2
> ret
>
> so it's constructing the vector piecewise through scalars.
>
> I avoided this before by creating the groups to use from the trailing
> elements instead so there's no DRs after the vector load, but that is
> admittedly
> a hack..
>
> This corresponds to what clang does in this case too
> https://godbolt.org/z/eqs9hfvY6
>
> But I think as you mentioned before this is a problem elsewhere, since
> there's no
> reason for it to think the group can't be loaded as a linear vector.
>
> So still LGTM, maybe we should file a PR to track the scalarization above?
Yeah, I think this is similar to PR126079 as we run into the same
t.c:3:18: missed: BB vectorization with gaps at the end of a load is not
supported
for some reason we pick
t.c:3:18: note: op template: _18 = MEM[(int *)b_24(D) + 16B];
t.c:3:18: note: stmt 0 _18 = MEM[(int *)b_24(D) + 16B];
t.c:3:18: note: stmt 1 _14 = MEM[(int *)b_24(D) + 12B];
t.c:3:18: note: stmt 2 _10 = MEM[(int *)b_24(D) + 8B];
t.c:3:18: note: stmt 3 _3 = *b_24(D);
t.c:3:18: note: load permutation { 4 3 2 0 }
which is likely because we "swap" operands and we do not sort ops
in any meaningful way. That it worked when cutting from the other
end was probably just luck. I have amended the above PR and pushed
the change.
Richard.
> Cheers,
> Tamar
>
> >
> > 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.
> >
> > * gcc.dg/vect/bb-slp-reduc-2.c: New testcase.
> > * gcc.dg/vect/bb-slp-reduc-3.c: Likewise.
> > * gcc.dg/vect/pr106081.c: Disable BB vectorization.
> > ---
> > gcc/testsuite/gcc.dg/vect/bb-slp-reduc-2.c | 12 ++++
> > gcc/testsuite/gcc.dg/vect/bb-slp-reduc-3.c | 12 ++++
> > gcc/testsuite/gcc.dg/vect/pr106081.c | 2 +-
> > gcc/tree-vect-slp.cc | 68 ++++++++++++++++++----
> > 4 files changed, 83 insertions(+), 11 deletions(-)
> > create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-reduc-2.c
> > create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-reduc-3.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/testsuite/gcc.dg/vect/bb-slp-reduc-3.c
> > b/gcc/testsuite/gcc.dg/vect/bb-slp-reduc-3.c
> > new file mode 100644
> > index 00000000000..acb9bf59f76
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/vect/bb-slp-reduc-3.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]) +
> > (a[4] | b[4]));
> > +}
> > +
> > +/* 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/testsuite/gcc.dg/vect/pr106081.c
> > b/gcc/testsuite/gcc.dg/vect/pr106081.c
> > index 8f97af2d642..23b3127be0a 100644
> > --- a/gcc/testsuite/gcc.dg/vect/pr106081.c
> > +++ b/gcc/testsuite/gcc.dg/vect/pr106081.c
> > @@ -1,5 +1,5 @@
> > /* { dg-do compile } */
> > -/* { dg-additional-options "-ffast-math -fdump-tree-optimized" } */
> > +/* { dg-additional-options "-ffast-math -fno-tree-slp-vectorize
> > -fdump-tree-
> > optimized" } */
> > /* { dg-additional-options "-mavx2" { target x86_64-*-* i?86-*-* } } */
> > /* { dg-require-effective-target vect_double } */
> > /* { dg-require-effective-target vect_unpack } */
> > diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
> > index ea6e57aacb3..d1317fdde6e 100644
> > --- a/gcc/tree-vect-slp.cc
> > +++ b/gcc/tree-vect-slp.cc
> > @@ -4321,6 +4321,63 @@ vect_build_slp_instance (vec_info *vinfo,
> > vect_analyze_slp_instance now. */
> > gcc_assert (kind != slp_inst_kind_store || group_size == 1);
> >
> > + /* For BB vectorization we get failures only in case of the need of
> > + unrolling, as otherwise we'll simply get operands built from scalars.
> > + Iff there is any mismatches in the toplevel stmts those will prevail,
> > + otherwise we get the non-power-of-two tail of the lanes failed.
> > + For BB reductions we mainly want to catch the first case so we pick
> > + a more useful subset of lanes to reduce. */
> > + if (kind == slp_inst_kind_bb_reduc && matches[0])
> > + {
> > + unsigned n_matching = 0;
> > + for (unsigned i = 0; i < group_size; ++i)
> > + 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 && n_matching >= group_size / 2)
> > + {
> > + /* As we know the matches[] stmts match up, recursing for
> > + non-power-of-two sizes will just force-fail the tail
> > + for us at hopefully optimal vector size and succesfully
> > + finish discovery. */
> > + 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 (group_size - n_matching >= 2)
> > + {
> > + /* We do not know whether the !matches[] part matches, so avoid
> > + cutting to a multiple of the vector size too early. We should
> > + make progress by means of remain only growing and most of the
> > + time prefering the matching[] part. */
> > + 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);
> > + }
> > + }
> > +
> > /* Free the allocated memory. */
> > scalar_stmts.release ();
> >
> > @@ -9984,7 +10041,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 +10055,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 +10068,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)
