The following tries to address us BB vectorizing a loop body that
swaps consecutive elements of an array like for bubble-sort. This
causes the vector store in the previous iteration to fail to forward
to the vector load in the current iteration since there's a partial
overlap.
We try to detect this situation by looking for a load to store
data dependence and analyze this with respect to the containing loop
for a proven problematic access. Currently the search for a
problematic pair is limited to loads and stores in the same SLP
instance which means the problematic load happens in the next
loop iteration and larger dependence distances are not considered.
On x86 with generic costing this avoids vectorizing the loop body,
but once you do core-specific tuning the saved cost for the vector
store vs. the scalar stores makes vectorization still profitable,
but at least the STLF issue is avoided.
For example on my Zen4 machine with -O2 -march=znver4 the testcase in
the PR is improving from
insertion_sort => 2327
to
insertion_sort => 997
but plain -O2 (or -fno-tree-slp-vectorize) gives
insertion_sort => 183
In the end a better target-side cost model for small vector
vectorization is needed to reject this vectorization from this side.
I'll note this is a machine independent heuristic (similar to the
avoid-store-forwarding RTL optimization pass), I expect that uarchs
implementing vectors will suffer from this kind of issue. I know
some aarch64 uarchs can forward from upper/lower part stores, this
isn't considered at the moment. The actual vector size/overlap
distance check could be moved to a target hook if it turns out
necessary.
There might be the chance to use a smaller vector size for the loads
avoiding the penalty rather than falling back to elementwise accesses,
that's not implemented either.
Bootstrapped and tested on x86_64-unknown-linux-gnu. At this point
queued for stage1, possibly for backport for 15.2.
Richard.
PR tree-optimization/1157777
* tree-vectorizer.h (_slp_tree::avoid_stlf_fail): New member.
* tree-vet-slp.cc (_slp_tree::_slp_tree): Initialize it.
(vect_print_slp_tree): Dump it.
* tree-vect-data.refs.cc (vect_slp_analyze_instance_dependence):
For dataflow dependent loads of a store check whether there's
a cross-iteration data dependence that for sure prohibits
store-to-load forwarding and mark involved loads.
* tree-vect-stmts.cc (get_group_load_store_type): For avoid_stlf_fail
marked loads use VMAT_ELEMENTWISE.
* gcc.dg/vect/bb-slp-pr115777.c: New testcase.
---
gcc/testsuite/gcc.dg/vect/bb-slp-pr115777.c | 15 ++++
gcc/tree-vect-data-refs.cc | 91 +++++++++++++++++++++
gcc/tree-vect-slp.cc | 4 +-
gcc/tree-vect-stmts.cc | 8 ++
gcc/tree-vectorizer.h | 3 +
5 files changed, 120 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr115777.c
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr115777.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr115777.c
new file mode 100644
index 00000000000..bba0dc75f6f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr115777.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+
+typedef unsigned int T;
+
+#define SWAP(A, B) do { T tmp = A; A = B; B = tmp; } while (0)
+
+void
+insertion_sort(T *v, int n)
+{
+ for (int i = 1; i < n; ++i)
+ for (int k = i; k > 0 && v[k-1] > v[k]; --k)
+ SWAP(v[k-1], v[k]);
+}
+
+/* { dg-final { scan-tree-dump "using element-wise load" "slp1" { target { {
x86_64-*-* i?86-*-* } && { ! ia32 } } } } } */
diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc
index c9395e33fcd..231a3cab4f8 100644
--- a/gcc/tree-vect-data-refs.cc
+++ b/gcc/tree-vect-data-refs.cc
@@ -1203,6 +1203,97 @@ vect_slp_analyze_instance_dependence (vec_info *vinfo,
slp_instance instance)
for (unsigned k = 0; k < SLP_TREE_SCALAR_STMTS (store).length (); ++k)
gimple_set_visited (SLP_TREE_SCALAR_STMTS (store)[k]->stmt, false);
+ /* If this is a SLP instance with a store check if there's a dependent
+ load that cannot be forwarded from a previous iteration of a loop
+ both are in. This is to avoid situations like that in PR115777. */
+ if (res && store)
+ {
+ stmt_vec_info store_info
+ = DR_GROUP_FIRST_ELEMENT (SLP_TREE_SCALAR_STMTS (store)[0]);
+ class loop *store_loop = gimple_bb (store_info->stmt)->loop_father;
+ if (! loop_outer (store_loop))
+ return res;
+ vec<loop_p> loop_nest;
+ loop_nest.create (1);
+ loop_nest.quick_push (store_loop);
+ data_reference *drs = nullptr;
+ for (slp_tree &load : SLP_INSTANCE_LOADS (instance))
+ {
+ if (! STMT_VINFO_GROUPED_ACCESS (SLP_TREE_SCALAR_STMTS (load)[0]))
+ continue;
+ stmt_vec_info load_info
+ = DR_GROUP_FIRST_ELEMENT (SLP_TREE_SCALAR_STMTS (load)[0]);
+ if (gimple_bb (load_info->stmt)->loop_father != store_loop)
+ continue;
+
+ /* For now concern ourselves with write-after-read as we also
+ only look for re-use of the store within the same SLP instance.
+ We can still get a RAW here when the instance contais a PHI
+ with a backedge though, thus this test. */
+ if (! vect_stmt_dominates_stmt_p (STMT_VINFO_STMT (load_info),
+ STMT_VINFO_STMT (store_info)))
+ continue;
+
+ if (! drs)
+ {
+ drs = create_data_ref (loop_preheader_edge (store_loop),
+ store_loop,
+ DR_REF (STMT_VINFO_DATA_REF (store_info)),
+ store_info->stmt, false, false);
+ if (! DR_BASE_ADDRESS (drs)
+ || TREE_CODE (DR_STEP (drs)) != INTEGER_CST)
+ break;
+ }
+ data_reference *drl
+ = create_data_ref (loop_preheader_edge (store_loop),
+ store_loop,
+ DR_REF (STMT_VINFO_DATA_REF (load_info)),
+ load_info->stmt, true, false);
+
+ /* See whether the DRs have a known constant distance throughout
+ the containing loop iteration. */
+ if (! DR_BASE_ADDRESS (drl)
+ || ! operand_equal_p (DR_STEP (drs), DR_STEP (drl))
+ || ! operand_equal_p (DR_BASE_ADDRESS (drs),
+ DR_BASE_ADDRESS (drl))
+ || ! operand_equal_p (DR_OFFSET (drs), DR_OFFSET (drl)))
+ {
+ free_data_ref (drl);
+ continue;
+ }
+
+ /* If the next iteration load overlaps with a non-power-of-two offset
+ we are surely failing any STLF attempt. */
+ HOST_WIDE_INT step = TREE_INT_CST_LOW (DR_STEP (drl));
+ unsigned HOST_WIDE_INT sizes
+ = (TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drs))))
+ * DR_GROUP_SIZE (store_info));
+ unsigned HOST_WIDE_INT sizel
+ = (TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drl))))
+ * DR_GROUP_SIZE (load_info));
+ if (ranges_overlap_p (TREE_INT_CST_LOW (DR_INIT (drl)) + step, sizel,
+ TREE_INT_CST_LOW (DR_INIT (drs)), sizes))
+ {
+ unsigned HOST_WIDE_INT dist
+ = absu_hwi (TREE_INT_CST_LOW (DR_INIT (drl)) + step
+ - TREE_INT_CST_LOW (DR_INIT (drs)));
+ poly_uint64 loadsz = tree_to_poly_uint64
+ (TYPE_SIZE_UNIT (SLP_TREE_VECTYPE (load)));
+ poly_uint64 storesz = tree_to_poly_uint64
+ (TYPE_SIZE_UNIT (SLP_TREE_VECTYPE (store)));
+ /* When the overlap aligns with vector sizes used for the loads
+ and the vector stores are larger or equal to the loads
+ forwarding should work. */
+ if (maybe_gt (loadsz, storesz) || ! multiple_p (dist, loadsz))
+ load->avoid_stlf_fail = true;
+ }
+ free_data_ref (drl);
+ }
+ if (drs)
+ free_data_ref (drs);
+ loop_nest.release ();
+ }
+
return res;
}
diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
index 19beeed8a3a..23a14ae6071 100644
--- a/gcc/tree-vect-slp.cc
+++ b/gcc/tree-vect-slp.cc
@@ -122,6 +122,7 @@ _slp_tree::_slp_tree ()
SLP_TREE_DEF_TYPE (this) = vect_uninitialized_def;
SLP_TREE_CODE (this) = ERROR_MARK;
this->ldst_lanes = false;
+ this->avoid_stlf_fail = false;
SLP_TREE_VECTYPE (this) = NULL_TREE;
SLP_TREE_REPRESENTATIVE (this) = NULL;
SLP_TREE_MEMORY_ACCESS_TYPE (this) = VMAT_INVARIANT;
@@ -3104,7 +3105,8 @@ vect_print_slp_tree (dump_flags_t dump_kind,
dump_location_t loc,
SLP_TREE_REF_COUNT (node));
if (SLP_TREE_VECTYPE (node))
dump_printf (metadata, " %T", SLP_TREE_VECTYPE (node));
- dump_printf (metadata, "\n");
+ dump_printf (metadata, "%s\n",
+ node->avoid_stlf_fail ? " (avoid-stlf-fail)" : "");
if (SLP_TREE_DEF_TYPE (node) == vect_internal_def)
{
if (SLP_TREE_CODE (node) == VEC_PERM_EXPR)
diff --git a/gcc/tree-vect-stmts.cc b/gcc/tree-vect-stmts.cc
index 51b66a1883e..ffca2ab50d5 100644
--- a/gcc/tree-vect-stmts.cc
+++ b/gcc/tree-vect-stmts.cc
@@ -2134,6 +2134,14 @@ get_group_load_store_type (vec_info *vinfo,
stmt_vec_info stmt_info,
: vect_store_lanes_supported (vectype, group_size,
masked_p))) !=
IFN_LAST)
*memory_access_type = VMAT_LOAD_STORE_LANES;
+ else if (!loop_vinfo && slp_node->avoid_stlf_fail)
+ {
+ *memory_access_type = VMAT_ELEMENTWISE;
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "using element-wise load to avoid disrupting "
+ "cross iteration store-to-load forwarding\n");
+ }
else
*memory_access_type = VMAT_CONTIGUOUS;
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 97caf61b345..933d1a4a1ac 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -265,6 +265,9 @@ struct _slp_tree {
/* Whether uses of this load or feeders of this store are suitable
for load/store-lanes. */
bool ldst_lanes;
+ /* For BB vect, flag to indicate this load node should be vectorized
+ as to avoid STLF fails because of related stores. */
+ bool avoid_stlf_fail;
int vertex;
--
2.43.0
