This allows for vectorization of cases where a data dependency could
possibly be within IV increment.
Note, this only works for vect_partial_vectors_while_ult partial vector
style right now. It should be relatively easy to extend it to the other
partial vector styles.
Also note this does *not* use partial vectors. This is because the
calculation of the loop masks within each loop would be fairly expensive
and so it is done at the end of the loop, and then an epilogue with the
known fixed cap of iterations is used.
Also note, this only works for counted loops at the moment.
gcc/ChangeLog:
* tree-vect-loop-manip.cc (vect_set_loop_condition_normal):
Add mask initialization for capped iv increment loops.
(vect_get_loop_iv_increment): Add case for capped iv increment.
* tree-vect-loop.cc (_loop_vec_info::_loop_vec_info):
Add iv_increment_cap member initialization.
(vect_analyze_loop_2): Add case to set iv increment cap.
* tree-vectorizer.h (LOOP_VINFO_IV_INCREMENT_CAP): New macro.
(LOOP_VINFO_FULLY_MASKED_P): Update to be masked when iv
increment is capped.
(vect_use_loop_mask_for_alignment_p): Update to exclude cases
when not using partial vectors.
(vect_max_iv_increment): Update for iv increment cap.
(vect_min_iv_increment): Likewise.
(vect_known_iv_increment): Likewise.
(vect_iv_increment_for_cost): Likewise.
gcc/testsuite/ChangeLog:
* gcc.target/aarch64/sve/pr98119.c: Update test.
* gcc.target/aarch64/sve/vect-safe-max-vf.c: New test.
* gcc.target/aarch64/sve/vect-safe-max-vf2.c: New test.
---
.../gcc.target/aarch64/sve/pr98119.c | 7 +--
.../gcc.target/aarch64/sve/vect-safe-max-vf.c | 51 +++++++++++++++++++
.../aarch64/sve/vect-safe-max-vf2.c | 50 ++++++++++++++++++
gcc/tree-vect-loop-manip.cc | 49 ++++++++++++++++++
gcc/tree-vect-loop.cc | 40 +++++++++++++--
gcc/tree-vectorizer.h | 20 +++++++-
6 files changed, 206 insertions(+), 11 deletions(-)
create mode 100644 gcc/testsuite/gcc.target/aarch64/sve/vect-safe-max-vf.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/sve/vect-safe-max-vf2.c
diff --git a/gcc/testsuite/gcc.target/aarch64/sve/pr98119.c
b/gcc/testsuite/gcc.target/aarch64/sve/pr98119.c
index da6208c2ce3..6a2a331f1c7 100644
--- a/gcc/testsuite/gcc.target/aarch64/sve/pr98119.c
+++ b/gcc/testsuite/gcc.target/aarch64/sve/pr98119.c
@@ -1,4 +1,4 @@
-/* { dg-options "-O3 -msve-vector-bits=512 -mtune=thunderx" } */
+/* { dg-options "-O3 -msve-vector-bits=512 -mtune=thunderx
-fdump-tree-vect-details" } */
void
f (unsigned short *x)
@@ -7,7 +7,4 @@ f (unsigned short *x)
x[i] += x[i - 16];
}
-/* { dg-final { scan-assembler-not {\tubfx\t[wx][0-9]+, [wx][0-9]+, #?1,
#?5\n} } } */
-/* { dg-final { scan-assembler-not {\tand\tx[0-9]+, x[0-9]+, #?-63\n} } } */
-/* { dg-final { scan-assembler {\tubfx\t[wx][0-9]+, [wx][0-9]+, #?1, #?4\n} }
} */
-/* { dg-final { scan-assembler {\tand\tx[0-9]+, x[0-9]+, #?-31\n} } } */
+/* { dg-final { scan-tree-dump "applying an iv increment cap of 16 for data
dependency" "vect" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/sve/vect-safe-max-vf.c
b/gcc/testsuite/gcc.target/aarch64/sve/vect-safe-max-vf.c
new file mode 100644
index 00000000000..8b7e222aabf
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/sve/vect-safe-max-vf.c
@@ -0,0 +1,51 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-all
-fno-vect-cost-model --param=aarch64-autovec-mode=VNx16QI
--param=vect-epilogues-nomask=0" } */
+/* { dg-final { check-function-bodies "**" "" "" } } */
+
+/* foo1 can use a regular partial loop. */
+/*
+** foo1:
+** ...
+** whilelo p[0-9]+\.b, wzr, [wx][0-9]+
+** ...
+** ld1b z[0-9]+\.b, p[0-9]+/z, \[x[0-9]+, x[0-9]+\]
+** ld1b z[0-9]+\.b, p[0-9]+/z, \[x[0-9]+, x[0-9]+\]
+** ...
+** st1b z[0-9]+\.b, p[0-9]+, \[x[0-9]+, x[0-9]+\]
+** ...
+** whilelo p[0-9]+\.b, [wx][0-9+], [wx][0-9]+
+** b\.any .*
+** ...
+** ret
+** ...
+*/
+void foo1 (char *a, unsigned n) {
+ for (int i = 0; i < n; ++i)
+ a[i+256] += a[i];
+}
+
+/* foo2 must use a capped loop. */
+/*
+** foo2:
+** ...
+** mov w[0-9]+, 255
+** ...
+** whilelo p[0-9]+\.b, wzr, w[0-9]+
+** ...
+** ld1b z[0-9]+\.b, p[0-9]+/z, \[x[0-9]+, x[0-9]+\]
+** ld1b z[0-9]+\.b, p[0-9]+/z, \[x[0-9]+, x[0-9]+\]
+** ...
+** st1b z[0-9]+\.b, p[0-9]+, \[x[0-9]+, x[0-9]+\]
+** ...
+** cmp [xw][0-9]+, [xw][0-9]+
+** ...
+** ret
+** ...
+*/
+void foo2 (char *a, unsigned n) {
+ for (int i = 0; i < n; ++i)
+ a[i+255] += a[i];
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" } } */
+/* { dg-final { scan-tree-dump-not "bad data dependence" "vect" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/sve/vect-safe-max-vf2.c
b/gcc/testsuite/gcc.target/aarch64/sve/vect-safe-max-vf2.c
new file mode 100644
index 00000000000..5c97954f638
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/sve/vect-safe-max-vf2.c
@@ -0,0 +1,50 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-all
-fno-vect-cost-model --param=aarch64-autovec-mode=VNx4QI
--param=vect-epilogues-nomask=0" } */
+
+/* foo3 can use a regular partial loop. */
+/*
+** foo3:
+** ...
+** whilelo p[0-9]+\.s, wzr, [wx][0-9]+
+** ...
+** ld1w z[0-9]+\.s, p[0-9]+/z, \[x[0-9]+, x[0-9]+\]
+** ld1w z[0-9]+\.s, p[0-9]+/z, \[x[0-9]+, x[0-9]+\]
+** ...
+** st1w z[0-9]+\.s, p[0-9]+, \[x[0-9]+, x[0-9]+\]
+** ...
+** whilelo p[0-9]+\.s, [wx][0-9+], [wx][0-9]+
+** b\.any .*
+** ...
+** ret
+** ...
+*/
+void foo3 (int *a, unsigned n) {
+ for (int i = 0; i < n; ++i)
+ a[i+64] += a[i];
+}
+
+/* foo4 must use a capped loop. */
+/*
+** foo4:
+** ...
+** mov w[0-9]+, 63
+** ...
+** whilelo p[0-9]+\.b, wzr, w[0-9]+
+** ...
+** ld1s z[0-9]+\.w, p[0-9]+/z, \[x[0-9]+, x[0-9]+\]
+** ld1s z[0-9]+\.w, p[0-9]+/z, \[x[0-9]+, x[0-9]+\]
+** ...
+** st1s z[0-9]+\.w, p[0-9]+, \[x[0-9]+, x[0-9]+\]
+** ...
+** cmp [xw][0-9]+, [xw][0-9]+
+** ...
+** ret
+** ...
+*/
+void foo4 (int *a, unsigned n) {
+ for (int i = 0; i < n; ++i)
+ a[i+63] += a[i];
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" } } */
+/* { dg-final { scan-tree-dump-not "bad data dependence" "vect" } } */
diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc
index 979486eca79..34e18f1583b 100644
--- a/gcc/tree-vect-loop-manip.cc
+++ b/gcc/tree-vect-loop-manip.cc
@@ -1374,6 +1374,48 @@ vect_set_loop_condition_normal (loop_vec_info
loop_vinfo, edge exit_edge,
loop->nb_iterations = fold_build2 (TRUNC_DIV_EXPR, niters_type,
limit, step);
+ gimple_seq preheader_seq = NULL;
+ /* Initialize all the capped VF masks. */
+ if (loop_vinfo && LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo))
+ {
+ if (LOOP_VINFO_PARTIAL_VECTORS_STYLE (loop_vinfo)
+ == vect_partial_vectors_while_ult)
+ for (rgroup_controls &rgc : LOOP_VINFO_MASKS (loop_vinfo).rgc_vec)
+ {
+ tree ctrl_type = rgc.type;
+ poly_uint64 nitems_per_ctrl
+ = TYPE_VECTOR_SUBPARTS (ctrl_type) * rgc.factor;
+ unsigned HOST_WIDE_INT cap
+ = LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo);
+
+ unsigned int nitems_per_iter
+ = rgc.max_nscalars_per_iter * rgc.factor;
+
+ unsigned HOST_WIDE_INT this_cap
+ = nitems_per_iter * cap;
+
+ tree ctrl;
+ unsigned i;
+ FOR_EACH_VEC_ELT_REVERSE (rgc.controls, i, ctrl)
+ {
+ poly_uint64 bias = nitems_per_ctrl * i;
+ tree cap_ctrl = vect_gen_while (
+ &preheader_seq, ctrl_type,
+ build_int_cst (LOOP_VINFO_RGROUP_COMPARE_TYPE (loop_vinfo),
+ bias),
+ build_int_cst (LOOP_VINFO_RGROUP_COMPARE_TYPE (loop_vinfo),
+ this_cap),
+ "capped_mask");
+ gassign *assign = gimple_build_assign (ctrl, cap_ctrl);
+ gimple_seq_add_stmt (&preheader_seq, assign);
+ }
+ }
+ else
+ gcc_unreachable ();
+ }
+ if (preheader_seq)
+ add_preheader_seq (loop, preheader_seq);
+
if (final_iv)
{
gassign *assign;
@@ -3129,6 +3171,13 @@ vect_get_loop_iv_increment (loop_vec_info loop_vinfo)
/* For now, set this as varying. */
return build_call_expr_internal_loc (UNKNOWN_LOCATION, IFN_VARYING,
sizetype, 0);
+ else if (LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo) != 0)
+ return fold_build2
+ (MIN_EXPR, sizetype,
+ build_int_cst (sizetype,
+ LOOP_VINFO_VECT_FACTOR (loop_vinfo)),
+ build_int_cst (sizetype,
+ LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo)));
else
return build_int_cst (sizetype, LOOP_VINFO_VECT_FACTOR (loop_vinfo));
}
diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
index 749aae69f11..02f30d04674 100644
--- a/gcc/tree-vect-loop.cc
+++ b/gcc/tree-vect-loop.cc
@@ -752,6 +752,7 @@ _loop_vec_info::_loop_vec_info (class loop *loop_in,
vec_info_shared *shared,
versioning_threshold (0),
vectorization_factor (0),
iv_increment (NULL),
+ iv_increment_cap (0),
main_loop_edge (nullptr),
skip_main_loop_edge (nullptr),
skip_this_loop_edge (nullptr),
@@ -2359,6 +2360,8 @@ vect_analyze_loop_2 (loop_vec_info loop_vinfo, int
masked_p, bool &fatal,
bool saved_can_use_partial_vectors_p
= LOOP_VINFO_CAN_USE_PARTIAL_VECTORS_P (loop_vinfo);
+ bool using_vf_for_ssr = false;
+
/* This is the point where we can re-start analysis with single-lane
SLP forced. */
start_over:
@@ -2415,10 +2418,6 @@ start_over:
LOOP_VINFO_INT_NITERS (loop_vinfo));
}
- if (max_vf != MAX_VECTORIZATION_FACTOR
- && maybe_lt (max_vf, LOOP_VINFO_VECT_FACTOR (loop_vinfo)))
- return opt_result::failure_at (vect_location, "bad data dependence.\n");
-
loop_vinfo->vector_costs = init_cost (loop_vinfo, false);
/* Analyze the alignment of the data-refs in the loop. */
@@ -2481,6 +2480,37 @@ start_over:
LOOP_VINFO_CAN_USE_PARTIAL_VECTORS_P (loop_vinfo) = false;
}
+ for (slp_instance &instance : LOOP_VINFO_SLP_INSTANCES (loop_vinfo))
+ for (slp_tree &load : SLP_INSTANCE_LOADS (instance))
+ /* Alignment is maintained in the first element of the group. */
+ if (dr_safe_speculative_read_required (SLP_TREE_SCALAR_STMTS (load)[0]))
+ using_vf_for_ssr = true;
+
+ if (max_vf != MAX_VECTORIZATION_FACTOR
+ && maybe_lt (max_vf, LOOP_VINFO_VECT_FACTOR (loop_vinfo), false))
+ {
+ /* For now we only support capped iv increment for masked vectorization.
+ It would also be possible to support it for len based vectorzation. */
+ if (!LOOP_VINFO_MASKS (loop_vinfo).is_empty ()
+ && LOOP_VINFO_CAN_USE_PARTIAL_VECTORS_P (loop_vinfo)
+ && !using_vf_for_ssr
+ && !LOOP_VINFO_EPILOGUE_P (loop_vinfo)
+ && !LOOP_VINFO_NITERS_UNCOUNTED_P (loop_vinfo)
+ && LOOP_VINFO_PARTIAL_VECTORS_STYLE (loop_vinfo)
+ == vect_partial_vectors_while_ult)
+ {
+ LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo) = max_vf;
+ /* We cannot use partial vectors for capped VF vectorization. */
+ LOOP_VINFO_CAN_USE_PARTIAL_VECTORS_P (loop_vinfo) = false;
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location, "applying an iv "
+ "increment cap of %d for data dependency\n",
+ max_vf);
+ }
+ else
+ return opt_result::failure_at (vect_location, "bad data dependence.\n");
+ }
+
/* Decide whether this loop_vinfo should use partial vectors or peeling,
assuming that the loop will be used as a main loop. We will redo
this analysis later if we instead decide to use the loop as an
@@ -2768,8 +2798,10 @@ again:
"re-trying with single-lane SLP\n");
/* Reset the vectorization factor. */
+ using_vf_for_ssr = false;
LOOP_VINFO_VECT_FACTOR (loop_vinfo) = 0;
LOOP_VINFO_IV_INCREMENT (loop_vinfo) = NULL_TREE;
+ LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo) = 0;
/* Free the SLP instances. */
FOR_EACH_VEC_ELT (LOOP_VINFO_SLP_INSTANCES (loop_vinfo), j, instance)
vect_free_slp_instance (instance);
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 5b75483f2de..7f90126c8a4 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -1002,6 +1002,9 @@ public:
iteration, and therefore how much to increment each IV by. */
tree iv_increment;
+ /* Static cap the the iv increment for data dependency safety. */
+ unsigned HOST_WIDE_INT iv_increment_cap;
+
/* If this loop is an epilogue loop whose main loop can be skipped,
MAIN_LOOP_EDGE is the edge from the main loop to this loop's
preheader. SKIP_MAIN_LOOP_EDGE is then the edge that skips the
@@ -1327,6 +1330,7 @@ public:
#define LOOP_VINFO_PARTIAL_LOAD_STORE_BIAS(L) (L)->partial_load_store_bias
#define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor
#define LOOP_VINFO_IV_INCREMENT(L) (L)->iv_increment
+#define LOOP_VINFO_IV_INCREMENT_CAP(L) (L)->iv_increment_cap
#define LOOP_VINFO_IV_INCREMENT_INVARIANT_P(L) \
(!LOOP_VINFO_USING_SELECT_VL_P (L))
#define LOOP_VINFO_MAX_VECT_FACTOR(L) (L)->max_vectorization_factor
@@ -1386,7 +1390,8 @@ public:
#define LOOP_VINFO_ALTERNATE_DEFS(L) (L)->alternate_defs
#define LOOP_VINFO_FULLY_MASKED_P(L) \
- (LOOP_VINFO_USING_PARTIAL_VECTORS_P (L) \
+ ((LOOP_VINFO_USING_PARTIAL_VECTORS_P (L) \
+ || LOOP_VINFO_IV_INCREMENT_CAP (L)) \
&& !LOOP_VINFO_MASKS (L).is_empty ())
#define LOOP_VINFO_FULLY_WITH_LENGTH_P(L) \
@@ -2341,6 +2346,7 @@ vect_use_loop_mask_for_alignment_p (loop_vec_info
loop_vinfo)
implemented the same way as vectorizable_linear_induction. However we
can't test this today so reject it. */
return (LOOP_VINFO_FULLY_MASKED_P (loop_vinfo)
+ && LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo)
&& LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo)
&& !(LOOP_VINFO_NON_LINEAR_IV (loop_vinfo)
&& LOOP_VINFO_EARLY_BREAKS (loop_vinfo)));
@@ -2403,6 +2409,9 @@ vect_max_vf (loop_vec_info loop_vinfo)
inline unsigned HOST_WIDE_INT
vect_max_iv_increment (loop_vec_info loop_vinfo)
{
+ if (LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo))
+ return MIN (LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo),
+ vect_max_vf (loop_vinfo));
return vect_max_vf (loop_vinfo);
}
@@ -2416,6 +2425,9 @@ vect_min_iv_increment (loop_vec_info loop_vinfo)
if (!LOOP_VINFO_IV_INCREMENT_INVARIANT_P (loop_vinfo))
return 1;
+ if (LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo))
+ return MIN (constant_lower_bound (LOOP_VINFO_VECT_FACTOR (loop_vinfo)),
+ LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo));
else
return constant_lower_bound (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
}
@@ -2450,7 +2462,8 @@ vect_known_iv_increment (loop_vec_info loop_vinfo,
/* If IV increment is loop variant or we have capped vf and don't know it
is a constant then it is not statically known. */
- if (LOOP_VINFO_IV_INCREMENT_INVARIANT_P (loop_vinfo))
+ if (LOOP_VINFO_IV_INCREMENT_INVARIANT_P (loop_vinfo)
+ || LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo))
return false;
if (iv_increment != NULL)
@@ -2475,6 +2488,9 @@ vect_iv_increment_for_cost (loop_vec_info loop_vinfo)
unsigned int estimate
= estimated_poly_value (LOOP_VINFO_VECT_FACTOR (loop_vinfo));
+ /* If there is a VF cap, take that into account. */
+ if (LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo))
+ return MIN (estimate, LOOP_VINFO_IV_INCREMENT_CAP (loop_vinfo));
return estimate;
}
--
2.56.0
