This patch relaxes one speculative-load check used by early-break
vectorization. The vectorizer correctly rejects SLP load permutations for
speculative loads because an arbitrary permutation can invalidate the load
layout assumptions. However, a single-element permutation of { 0 } is
fine: it is just the loaded scalar value being replicated, so it does
not introduce a real alignment-changing permutation.
A simplified C example is:
void **find_ptr (void **first, void **last, void *needle)
{
while (first != last && *first != needle)
++first;
return first;
}
Before this patch the vectorizer could reject the speculative load because it
saw an SLP load permutation and treated it like a real permute:
missed: loads with load permutations not supported for speculative loads
After this patch, the { 0 } load permutation is accepted and the
loop can continue down the early-break vectorization path.
Bootstrapped Regtested on aarch64-none-linux-gnu,
arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
-m32, -m64 and no issues.
-O3, profiled, profiled -O3 and -O3 -LTO bootstrap tested and no issues.
Also SPECCPU 2017 and SPECCPU 2026 tested.
Any feedback?
Thanks,
Tamar
gcc/ChangeLog:
* tree-vect-stmts.cc (get_load_store_type): Allow degenerate SLP
permutations for speculative early-break loads.
gcc/testsuite/ChangeLog:
* g++.dg/vect/vect-early-break-pr-spec-find.cc: New test.
---
diff --git a/gcc/testsuite/g++.dg/vect/vect-early-break-pr-spec-find.cc
b/gcc/testsuite/g++.dg/vect/vect-early-break-pr-spec-find.cc
new file mode 100644
index
0000000000000000000000000000000000000000..05e82345f0214d70da355a07053e10a9a069ab73
--- /dev/null
+++ b/gcc/testsuite/g++.dg/vect/vect-early-break-pr-spec-find.cc
@@ -0,0 +1,96 @@
+/* { dg-do compile } */
+/* { dg-add-options vect_early_break } */
+/* { dg-require-effective-target vect_early_break } */
+/* { dg-require-effective-target vect_long_long } */
+/* { dg-additional-options "-O3 -fno-tree-loop-distribute-patterns" } */
+
+struct X;
+
+template<typename Value>
+struct iter_equals_val
+{
+ Value& value;
+
+ explicit
+ iter_equals_val (Value& val)
+ : value (val)
+ {}
+
+ template<typename Iter>
+ bool
+ operator() (Iter it)
+ { return *it == value; }
+};
+
+template<typename Iter, typename Pred>
+inline Iter
+find_if (Iter first, Iter last, Pred pred)
+{
+#pragma GCC unroll 4
+ while (first != last && !pred (first))
+ ++first;
+ return first;
+}
+
+__attribute__((noipa, noinline))
+X **
+find_ptr (X **first, X **last, X *needle)
+{
+ iter_equals_val<X *> pred (needle);
+ return find_if (first, last, pred);
+}
+
+struct object_pool
+{
+ X **first;
+ X **last;
+
+ __attribute__((noipa, noinline))
+ bool
+ return_object (X *needle, bool reset)
+ {
+ iter_equals_val<X *> pred (needle);
+ X **pos = find_if (first, last, pred);
+ if (pos == last)
+ return false;
+
+ if (!reset)
+ {
+ for (X **it = pos; it + 1 != last; ++it)
+ *it = *(it + 1);
+ --last;
+ }
+
+ return true;
+ }
+};
+
+__attribute__((noipa, noinline))
+bool
+return_to_pool (object_pool *pool, X *needle, bool reset)
+{
+ return pool->return_object (needle, reset);
+}
+
+__attribute__((noipa, noinline))
+bool
+dom_string_equals (const unsigned short *lhs, unsigned long lhs_length,
+ const unsigned short *rhs, unsigned long rhs_length)
+{
+ if (lhs_length != rhs_length)
+ return false;
+ if (lhs_length == 0)
+ return true;
+
+ const unsigned short *end = lhs + lhs_length;
+ while (*lhs == *rhs)
+ {
+ ++lhs;
+ if (lhs == end)
+ return true;
+ ++rhs;
+ }
+ return false;
+}
+
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
diff --git a/gcc/tree-vect-stmts.cc b/gcc/tree-vect-stmts.cc
index
c0c07929083f440af2d108656c3987d733ae937f..54755f9468c6a8c97e09a9e8b45dfcd844e903eb
100644
--- a/gcc/tree-vect-stmts.cc
+++ b/gcc/tree-vect-stmts.cc
@@ -2637,13 +2637,20 @@ get_load_store_type (vec_info *vinfo, stmt_vec_info
stmt_info,
the blend. This is what the x86_64 backend does for instance. As
such only the first load in the group is aligned, the rest are not.
Because of this the permutes may break the alignment requirements that
- have been set, and as such we should for now, reject them. */
- if (SLP_TREE_LOAD_PERMUTATION (slp_node).exists ())
+ have been set, and as such we should for now, reject them. However a
+ permute of { 0 } does not change alignment and is just a load and
+ replicate of the scalar value. */
+ load_permutation_t perm = SLP_TREE_LOAD_PERMUTATION (slp_node);
+ if (perm.exists ()
+ && !(single_element_p
+ && gap == 0
+ && perm.length () == 1
+ && perm[0] == 0))
{
if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"loads with load permutations not supported for "
- "speculative early break loads for %G",
+ "speculative loads for %G",
STMT_VINFO_STMT (stmt_info));
return false;
}
--
diff --git a/gcc/testsuite/g++.dg/vect/vect-early-break-pr-spec-find.cc b/gcc/testsuite/g++.dg/vect/vect-early-break-pr-spec-find.cc
new file mode 100644
index 0000000000000000000000000000000000000000..05e82345f0214d70da355a07053e10a9a069ab73
--- /dev/null
+++ b/gcc/testsuite/g++.dg/vect/vect-early-break-pr-spec-find.cc
@@ -0,0 +1,96 @@
+/* { dg-do compile } */
+/* { dg-add-options vect_early_break } */
+/* { dg-require-effective-target vect_early_break } */
+/* { dg-require-effective-target vect_long_long } */
+/* { dg-additional-options "-O3 -fno-tree-loop-distribute-patterns" } */
+
+struct X;
+
+template<typename Value>
+struct iter_equals_val
+{
+ Value& value;
+
+ explicit
+ iter_equals_val (Value& val)
+ : value (val)
+ {}
+
+ template<typename Iter>
+ bool
+ operator() (Iter it)
+ { return *it == value; }
+};
+
+template<typename Iter, typename Pred>
+inline Iter
+find_if (Iter first, Iter last, Pred pred)
+{
+#pragma GCC unroll 4
+ while (first != last && !pred (first))
+ ++first;
+ return first;
+}
+
+__attribute__((noipa, noinline))
+X **
+find_ptr (X **first, X **last, X *needle)
+{
+ iter_equals_val<X *> pred (needle);
+ return find_if (first, last, pred);
+}
+
+struct object_pool
+{
+ X **first;
+ X **last;
+
+ __attribute__((noipa, noinline))
+ bool
+ return_object (X *needle, bool reset)
+ {
+ iter_equals_val<X *> pred (needle);
+ X **pos = find_if (first, last, pred);
+ if (pos == last)
+ return false;
+
+ if (!reset)
+ {
+ for (X **it = pos; it + 1 != last; ++it)
+ *it = *(it + 1);
+ --last;
+ }
+
+ return true;
+ }
+};
+
+__attribute__((noipa, noinline))
+bool
+return_to_pool (object_pool *pool, X *needle, bool reset)
+{
+ return pool->return_object (needle, reset);
+}
+
+__attribute__((noipa, noinline))
+bool
+dom_string_equals (const unsigned short *lhs, unsigned long lhs_length,
+ const unsigned short *rhs, unsigned long rhs_length)
+{
+ if (lhs_length != rhs_length)
+ return false;
+ if (lhs_length == 0)
+ return true;
+
+ const unsigned short *end = lhs + lhs_length;
+ while (*lhs == *rhs)
+ {
+ ++lhs;
+ if (lhs == end)
+ return true;
+ ++rhs;
+ }
+ return false;
+}
+
+/* { dg-final { scan-tree-dump "LOOP VECTORIZED" "vect" } } */
diff --git a/gcc/tree-vect-stmts.cc b/gcc/tree-vect-stmts.cc
index c0c07929083f440af2d108656c3987d733ae937f..54755f9468c6a8c97e09a9e8b45dfcd844e903eb 100644
--- a/gcc/tree-vect-stmts.cc
+++ b/gcc/tree-vect-stmts.cc
@@ -2637,13 +2637,20 @@ get_load_store_type (vec_info *vinfo, stmt_vec_info stmt_info,
the blend. This is what the x86_64 backend does for instance. As
such only the first load in the group is aligned, the rest are not.
Because of this the permutes may break the alignment requirements that
- have been set, and as such we should for now, reject them. */
- if (SLP_TREE_LOAD_PERMUTATION (slp_node).exists ())
+ have been set, and as such we should for now, reject them. However a
+ permute of { 0 } does not change alignment and is just a load and
+ replicate of the scalar value. */
+ load_permutation_t perm = SLP_TREE_LOAD_PERMUTATION (slp_node);
+ if (perm.exists ()
+ && !(single_element_p
+ && gap == 0
+ && perm.length () == 1
+ && perm[0] == 0))
{
if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
"loads with load permutations not supported for "
- "speculative early break loads for %G",
+ "speculative loads for %G",
STMT_VINFO_STMT (stmt_info));
return false;
}
