[v2] Improve BB vectorization of reductions
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_gcc_build--master-arm |
success
|
Build passed
|
Commit Message
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?
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
Comments
> -----Original Message-----
> From: Richard Biener <rguenther@suse.de>
> Sent: 16 July 2026 13:49
> To: gcc-patches@gcc.gnu.org
> Cc: Tamar Christina <Tamar.Christina@arm.com>
> 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?
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
On Thu, 16 Jul 2026, Tamar Christina wrote:
> > -----Original Message-----
> > From: Richard Biener <rguenther@suse.de>
> > Sent: 16 July 2026 13:49
> > To: gcc-patches@gcc.gnu.org
> > Cc: Tamar Christina <Tamar.Christina@arm.com>
> > 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
>
new file mode 100644
@@ -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-*-* } } } } } */
new file mode 100644
@@ -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-*-* } } } } } */
@@ -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 } */
@@ -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);