vectorizable_induction reduces the number of generated SLP induction
IVs when group_size is evenly divisible by const_nunits. Existing
code did this without checking that the vector chunks being folded have
the same scalar initial values and steps with their counterparts.
If either differed, reusing an earlier IV produced wrong code.
Compute the unreduced IV count first and use the reduced count only when
each folded chunk has initial values and steps equal to its corresponding
earlier chunk. When initial values come from an SLP node and their scalar
values are unavailable, conservatively keep the unreduced count.
Added tests for mismatched initial values, mismatched steps, and a valid
multi-IV reuse pattern.
gcc/ChangeLog:
* tree-vect-loop.cc (vect_slp_induction_reuse_p): New function.
(vectorizable_induction): Validate SLP induction IV reuse. Reuse
generated IVs cyclically when filling the SLP group.
gcc/testsuite/ChangeLog:
* gcc.dg/vect/vect-iv-12.c: New test.
* gcc.dg/vect/vect-iv-13.c: New test.
* gcc.dg/vect/vect-iv-14.c: New test.
Signed-off-by: Cem Akgok <[email protected]>
---
Godbolt: https://godbolt.org/z/Mbohx7sEn
Wrong code at -O2.
All major versions from 11 to trunk affected. (11 miscompiles at -O3 only)
Compiles correctly with -fno-tree-loop-vectorize.
Bisected to: 092cdbd9198497593fb034971d0f80fc931ab145
("Re-instantiate SLP induction IV CSE")
Two missed optimization cases I realize, one is when inits come from SLP node.
Another is because only one candidate reduction is tried. It doesn't explore
some smaller
reuse period that could shrink nivs. I'm not sure how worthwhile or even
feasible it is to work on them though.
Bootstrapped and regtested on x86_64-pc-linux-gnu
gcc/testsuite/gcc.dg/vect/vect-iv-12.c | 60 ++++++++++++++++++++
gcc/testsuite/gcc.dg/vect/vect-iv-13.c | 60 ++++++++++++++++++++
gcc/testsuite/gcc.dg/vect/vect-iv-14.c | 78 ++++++++++++++++++++++++++
gcc/tree-vect-loop.cc | 70 ++++++++++++++++++++---
4 files changed, 261 insertions(+), 7 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-iv-12.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-iv-13.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-iv-14.c
diff --git a/gcc/testsuite/gcc.dg/vect/vect-iv-12.c
b/gcc/testsuite/gcc.dg/vect/vect-iv-12.c
new file mode 100644
index 00000000000..59783886933
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-iv-12.c
@@ -0,0 +1,60 @@
+/* { dg-require-effective-target vect_int } */
+/* { dg-additional-options "-mprefer-vector-width=128" { target { x86_64-*-*
i?86-*-* } } } */
+
+/* Ensure that SLP induction does not blindly reuse IVs when the scalar
+ initial values of the lanes differ. */
+
+#include "tree-vect.h"
+
+#define N 16
+
+static const int expected[N] = {
+ 1, 1, 1, 1, 2, 2, 2, 2,
+ 3, 3, 3, 3, 4, 4, 4, 4
+};
+
+__attribute__ ((noipa))
+void
+fill (int *ans, int rounds)
+{
+ int x = 1;
+ int y = 2;
+ int i = 0;
+
+ while (rounds > 0)
+ {
+ ans[i++] = x;
+ ans[i++] = x;
+ ans[i++] = x;
+ ans[i++] = x;
+ ans[i++] = y;
+ ans[i++] = y;
+ ans[i++] = y;
+ ans[i++] = y;
+
+ --rounds;
+ x += 2;
+ y += 2;
+ }
+}
+
+int
+main (void)
+{
+ int ans[N] = { 0 };
+
+ check_vect ();
+
+ fill (ans, 2);
+
+#pragma GCC novector
+ for (int i = 0; i < N; ++i)
+ if (ans[i] != expected[i])
+ abort ();
+
+ return 0;
+}
+
+/* Multi-lane SLP inductions are not yet supported for variable-length
+ vectors. */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail
vect_variable_length } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-iv-13.c
b/gcc/testsuite/gcc.dg/vect/vect-iv-13.c
new file mode 100644
index 00000000000..0843a10f6fc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-iv-13.c
@@ -0,0 +1,60 @@
+/* { dg-require-effective-target vect_int } */
+/* { dg-additional-options "-mprefer-vector-width=128" { target { x86_64-*-*
i?86-*-* } } } */
+
+/* Ensure that SLP induction does not blindly reuse IVs when the scalar
+ steps of the lanes differ. */
+
+#include "tree-vect.h"
+
+#define N 16
+
+static const int expected[N] = {
+ 1, 1, 1, 1, 1, 1, 1, 1,
+ 3, 3, 3, 3, 4, 4, 4, 4
+};
+
+__attribute__ ((noipa))
+void
+fill (int *ans, int rounds)
+{
+ int x = 1;
+ int y = 1;
+ int i = 0;
+
+ while (rounds > 0)
+ {
+ ans[i++] = x;
+ ans[i++] = x;
+ ans[i++] = x;
+ ans[i++] = x;
+ ans[i++] = y;
+ ans[i++] = y;
+ ans[i++] = y;
+ ans[i++] = y;
+
+ --rounds;
+ x += 2;
+ y += 3;
+ }
+}
+
+int
+main (void)
+{
+ int ans[N] = { 0 };
+
+ check_vect ();
+
+ fill (ans, 2);
+
+#pragma GCC novector
+ for (int i = 0; i < N; ++i)
+ if (ans[i] != expected[i])
+ abort ();
+
+ return 0;
+}
+
+/* Multi-lane SLP inductions are not yet supported for variable-length
+ vectors. */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail
vect_variable_length } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-iv-14.c
b/gcc/testsuite/gcc.dg/vect/vect-iv-14.c
new file mode 100644
index 00000000000..f39897b0a65
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-iv-14.c
@@ -0,0 +1,78 @@
+/* { dg-require-effective-target vect_int } */
+/* { dg-additional-options "-mprefer-vector-width=128" { target { x86_64-*-*
i?86-*-* } } } */
+
+#include "tree-vect.h"
+
+#define N 48
+
+#define STORE4(RESULT, VALUE) \
+ do { \
+ (RESULT)[i++] = (VALUE); \
+ (RESULT)[i++] = (VALUE); \
+ (RESULT)[i++] = (VALUE); \
+ (RESULT)[i++] = (VALUE); \
+ } while (0)
+
+static const int expected[N] = {
+ /* Round 1. */
+ 1, 1, 1, 1, 10, 10, 10, 10, 1, 1, 1, 1,
+ 1, 1, 1, 1, 10, 10, 10, 10, 1, 1, 1, 1,
+ /* Round 2 (x + 2, y + 3). */
+ 3, 3, 3, 3, 13, 13, 13, 13, 3, 3, 3, 3,
+ 3, 3, 3, 3, 13, 13, 13, 13, 3, 3, 3, 3
+};
+
+/* To test the multi-IV generation path (CANDIDATE_NIVS > 1), force a
+ geometry where CANDIDATE_NIVS < NIVS. On four-lane integer vectors,
+ the minimum SLP group size that satisfies this is 24, creating 6 vectors.
+
+ The first three (X, Y, X) vectors form the first period. The last three
+ form the repeated period, which exercises the IVN % CANDIDATE_NIVS reuse
+ path. */
+__attribute__ ((noipa))
+void
+fill (int *ans, int rounds)
+{
+ int x = 1;
+ int y = 10;
+ int i = 0;
+
+ while (rounds > 0)
+ {
+ /* First period. */
+ STORE4 (ans, x);
+ STORE4 (ans, y);
+ STORE4 (ans, x);
+
+ /* Repeated period. */
+ STORE4 (ans, x);
+ STORE4 (ans, y);
+ STORE4 (ans, x);
+
+ --rounds;
+ x += 2;
+ y += 3;
+ }
+}
+
+int
+main (void)
+{
+ int ans[N] = { 0 };
+
+ check_vect ();
+
+ fill (ans, 2);
+
+#pragma GCC novector
+ for (int i = 0; i < N; ++i)
+ if (ans[i] != expected[i])
+ abort ();
+
+ return 0;
+}
+
+/* Multi-lane SLP inductions are not yet supported for variable-length
+ vectors. */
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail
vect_variable_length } } } */
+/* { dg-final { scan-tree-dump-times "reusing 3 SLP induction IVs for 6 vector
chunks" 1 "vect" { target { x86_64-*-* i?86-*-* } } } } */
diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
index 931b942d7cb..5264e07604d 100644
--- a/gcc/tree-vect-loop.cc
+++ b/gcc/tree-vect-loop.cc
@@ -9502,6 +9502,44 @@ vectorizable_nonlinear_induction (loop_vec_info
loop_vinfo,
return true;
}
+/* Return true if the scalar initial values and steps of the SLP induction
+ lanes allow the first CANDIDATE_NIVS IVs to be reused circularly for the
+ remaining lanes. */
+static bool
+vect_slp_induction_reuse_p (tree *steps, tree *inits, unsigned group_size,
+ unsigned HOST_WIDE_INT const_nunits,
+ unsigned candidate_nivs, unsigned nivs)
+{
+ gcc_assert (candidate_nivs > 0);
+ gcc_assert (candidate_nivs < nivs);
+
+ /* This function compares only STEPS and INITS, so all checked lanes must
+ precede the first wrap of the SLP group. */
+ gcc_assert (nivs * const_nunits <= group_size);
+
+ /* Be conservative when initial values come from an SLP node, since their
+ scalar values are not available here for a lane-wise comparison. */
+ if (!inits)
+ return false;
+
+ for (unsigned ivn = candidate_nivs; ivn < nivs; ++ivn)
+ {
+ unsigned reuse_ivn = ivn % candidate_nivs;
+ for (unsigned HOST_WIDE_INT eltn = 0; eltn < const_nunits; ++eltn)
+ {
+ unsigned HOST_WIDE_INT elt = ivn * const_nunits + eltn;
+ unsigned HOST_WIDE_INT reused_elt
+ = reuse_ivn * const_nunits + eltn;
+
+ if (!operand_equal_p (steps[elt], steps[reused_elt], 0)
+ || !operand_equal_p (inits[elt], inits[reused_elt], 0))
+ return false;
+ }
+ }
+
+ return true;
+}
+
/* Function vectorizable_induction
Check if STMT_INFO performs an induction computation that can be vectorized.
@@ -9736,13 +9774,28 @@ vectorizable_induction (loop_vec_info loop_vinfo,
else if (nunits.is_constant (&const_nunits)
&& LOOP_VINFO_IV_INCREMENT_INVARIANT_P (loop_vinfo))
{
- /* Compute the number of distinct IVs we need. First reduce
- group_size if it is a multiple of const_nunits so we get
- one IV for a group_size of 4 but const_nunits 2. */
+ /* Compute the number of distinct IVs we need. We can reduce the
+ number when later vector chunks are equal to earlier chunks. */
+ nivs = least_common_multiple (group_size, const_nunits) / const_nunits;
unsigned group_sizep = group_size;
if (group_sizep % const_nunits == 0)
- group_sizep = group_sizep / const_nunits;
- nivs = least_common_multiple (group_sizep, const_nunits) / const_nunits;
+ {
+ group_sizep = group_sizep / const_nunits;
+ unsigned candidate_nivs
+ = least_common_multiple (group_sizep, const_nunits) / const_nunits;
+ if (candidate_nivs < nivs
+ && vect_slp_induction_reuse_p (steps, init_node ? NULL : inits,
+ group_size, const_nunits,
+ candidate_nivs, nivs))
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "reusing %u SLP induction IVs for %u "
+ "vector chunks\n",
+ candidate_nivs, nivs);
+ nivs = candidate_nivs;
+ }
+ }
}
else
{
@@ -9958,10 +10011,13 @@ vectorizable_induction (loop_vec_info loop_vinfo,
else
nivs = 1;
vec_steps.reserve (nivs-ivn);
+ unsigned generated_nivs = ivn;
+ gcc_assert (generated_nivs > 0);
for (; ivn < nivs; ++ivn)
{
- slp_node->push_vec_def (SLP_TREE_VEC_DEFS (slp_node)[0]);
- vec_steps.quick_push (vec_steps[0]);
+ unsigned reuse_ivn = ivn % generated_nivs;
+ slp_node->push_vec_def (SLP_TREE_VEC_DEFS (slp_node)[reuse_ivn]);
+ vec_steps.quick_push (vec_steps[reuse_ivn]);
}
}
--
2.55.0
