In the current loop vectorizer, negative-step contiguous DRs are
vectorized with VMAT_CONTIGUOUS_REVERSE, which normally requires
generating reverse permutations for the loaded or stored vectors.
However, if all DRs in a connected SLP subgraph use the same lane
layout, the reverse permutations can be potentially elided.
This patch adds an elide_rev_perms_p flag to the leader instance of each
connected SLP subgraph. During SLP graph optimization, we identify SLP
subgraphs in which reverse permutations might be elided and set the flag
on the leader instance.
Since the final VMAT is only known during vectorizable_{load|store}, we
may still clear the flag if an access is not VMAT_CONTIGUOUS_REVERSE.
Reverse permutation generation is omitted for DRs with the flag set in
the end.
For now, this optimization is conservatively limited to SLP instances of
slp_inst_kind_store. Support for reduction loops could be added in the
future.
This patch is bootstrapped and regression-tested on x86_64-linux-gnu,
arm-linux-gnueabihf and aarch64-linux-gnu with bootstrap-O3.
gcc/ChangeLog:
* tree-vect-slp.cc (vect_build_slp_instance): Initialize
elide_rev_perms_p.
(vect_analyze_slp_reduc_chain): Likewise.
(vect_analyze_slp_reduction): Likewise.
(vect_analyze_slp_reduction_group): Likewise.
(vect_analyze_slp_instance): Likewise.
(vect_can_elide_rev_perms_p): New helper function.
(vect_analyze_rev_perms_elision): New function.
(vect_optimize_slp): Call vect_analyze_rev_perms_elision.
* tree-vect-stmts.cc (vectorizable_store): Add a SLP instance
parameter and handle reverse permutation elision.
(vectorizable_load): Likewise.
(vect_analyze_stmt): Pass to SLP instance to vectorizable_load
and vectorizable_store.
(vect_transform_stmt): Likewise.
* tree-vectorizer.h: (_slp_instance::elide_rev_perms_p): New
member.
gcc/testsuite/ChangeLog:
* gcc.dg/vect/vect-elide-rev-perms-1.c: New test.
* gcc.dg/vect/vect-elide-rev-perms-2.c: New test.
* gcc.dg/vect/vect-elide-rev-perms-3.c: New test.
* gcc.dg/vect/vect-elide-rev-perms-4.c: New test.
* gcc.dg/vect/vect-elide-rev-perms-5.c: New test.
---
.../gcc.dg/vect/vect-elide-rev-perms-1.c | 34 ++++++
.../gcc.dg/vect/vect-elide-rev-perms-2.c | 39 +++++++
.../gcc.dg/vect/vect-elide-rev-perms-3.c | 38 +++++++
.../gcc.dg/vect/vect-elide-rev-perms-4.c | 38 +++++++
.../gcc.dg/vect/vect-elide-rev-perms-5.c | 42 ++++++++
gcc/tree-vect-slp.cc | 100 ++++++++++++++++++
gcc/tree-vect-stmts.cc | 70 ++++++++++--
gcc/tree-vectorizer.h | 4 +
8 files changed, 357 insertions(+), 8 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-1.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-2.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-3.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-4.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-5.c
diff --git a/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-1.c
b/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-1.c
new file mode 100644
index 00000000000..c4c9f6773d8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-1.c
@@ -0,0 +1,34 @@
+/* { dg-require-effective-target vect_int } */
+/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-details" } */
+
+#include "tree-vect.h"
+
+__attribute__((noipa))
+void
+foo (int *a)
+{
+ for (int i = 99; i >= 0; i--)
+ a[i] *= 2;
+}
+
+int
+main ()
+{
+ check_vect ();
+
+ int a[100];
+
+#pragma GCC novector
+ for (int i = 0; i < 100; i++)
+ a[i] = i + 1;
+
+ foo (a);
+
+#pragma GCC novector
+ for (int i = 0; i < 100; i++)
+ if (a[i] != 2 * (i + 1))
+ __builtin_abort ();
+}
+
+/* { dg-final { scan-tree-dump "Eliding reverse permutation for load" "vect" }
} */
+/* { dg-final { scan-tree-dump "Eliding reverse permutation for store" "vect"
} } */
\ No newline at end of file
diff --git a/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-2.c
b/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-2.c
new file mode 100644
index 00000000000..37ad890cba2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-2.c
@@ -0,0 +1,39 @@
+/* { dg-require-effective-target vect_int } */
+/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-details" } */
+
+#include "tree-vect.h"
+
+__attribute__((noipa))
+void
+foo (int *restrict a, int *restrict b, int *restrict c)
+{
+ for (int i = 99; i >= 0; i--)
+ {
+ b[i] = a[i] - 1;
+ c[i] = a[i] + 2;
+ }
+}
+
+int
+main ()
+{
+ check_vect ();
+
+ int a[100];
+ int b[100];
+ int c[100];
+
+#pragma GCC novector
+ for (int i = 0; i < 100; i++)
+ a[i] = i;
+
+ foo (a, b, c);
+
+#pragma GCC novector
+ for (int i = 0; i < 100; i++)
+ if (b[i] != i - 1 || c[i] != i + 2)
+ __builtin_abort ();
+}
+
+/* { dg-final { scan-tree-dump "Eliding reverse permutation for load" "vect" }
} */
+/* { dg-final { scan-tree-dump "Eliding reverse permutation for store" "vect"
} } */
\ No newline at end of file
diff --git a/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-3.c
b/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-3.c
new file mode 100644
index 00000000000..e1afb6fd9c4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-3.c
@@ -0,0 +1,38 @@
+/* { dg-require-effective-target vect_int } */
+/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-details" } */
+
+#include "tree-vect.h"
+
+__attribute__((noipa))
+void
+foo (int *restrict a, signed char *restrict b)
+{
+ for (int i = 99; i >= 0; i--)
+ a[i] += b[i];
+}
+
+int
+main ()
+{
+ check_vect ();
+
+ int a[100];
+ signed char b[100];
+
+#pragma GCC novector
+ for (int i = 0; i < 100; i++)
+ {
+ a[i] = i + 1;
+ b[i] = i - 1;
+ }
+
+ foo (a, b);
+
+#pragma GCC novector
+ for (int i = 0; i < 100; i++)
+ if (a[i] != 2 * i)
+ __builtin_abort ();
+}
+
+/* { dg-final { scan-tree-dump-not "Eliding reverse permutation for load"
"vect" } } */
+/* { dg-final { scan-tree-dump-not "Eliding reverse permutation for store"
"vect" } } */
\ No newline at end of file
diff --git a/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-4.c
b/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-4.c
new file mode 100644
index 00000000000..33e3300a190
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-4.c
@@ -0,0 +1,38 @@
+/* { dg-require-effective-target vect_int } */
+/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-details" } */
+
+#include "tree-vect.h"
+
+__attribute__((noipa))
+void
+foo (int *restrict a, int *restrict b)
+{
+ for (int i = 99; i >= 0; i--)
+ a[i] += b[99 - i];
+}
+
+int
+main ()
+{
+ check_vect ();
+
+ int a[100];
+ int b[100];
+
+#pragma GCC novector
+ for (int i = 0; i < 100; i++)
+ {
+ a[i] = i;
+ b[i] = i;
+ }
+
+ foo (a, b);
+
+#pragma GCC novector
+ for (int i = 0; i < 100; i++)
+ if (a[i] != 99)
+ __builtin_abort ();
+}
+
+/* { dg-final { scan-tree-dump-not "Eliding reverse permutation for load"
"vect" } } */
+/* { dg-final { scan-tree-dump-not "Eliding reverse permutation for store"
"vect" } } */
\ No newline at end of file
diff --git a/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-5.c
b/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-5.c
new file mode 100644
index 00000000000..89cf475cee1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-elide-rev-perms-5.c
@@ -0,0 +1,42 @@
+/* { dg-require-effective-target vect_int } */
+/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-details" } */
+
+#include "tree-vect.h"
+
+__attribute__((noipa))
+int
+foo (int *a)
+{
+ int x = 100;
+ for (int i = 99; i >= 0; i--)
+ {
+ x = a[i];
+ a[i] = x * 2;
+ }
+ return x - 1;
+}
+
+int
+main ()
+{
+ check_vect ();
+
+ int a[100];
+
+#pragma GCC novector
+ for (int i = 0; i < 100; i++)
+ a[i] = i;
+
+ int x = foo (a);
+
+#pragma GCC novector
+ for (int i = 0; i < 100; i++)
+ if (a[i] != 2 * i)
+ __builtin_abort ();
+
+ if (x != -1)
+ __builtin_abort ();
+}
+
+/* { dg-final { scan-tree-dump-not "Eliding reverse permutation for load"
"vect" } } */
+/* { dg-final { scan-tree-dump-not "Eliding reverse permutation for store"
"vect" } } */
\ No newline at end of file
diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
index fc08d10b872..725f686d26a 100644
--- a/gcc/tree-vect-slp.cc
+++ b/gcc/tree-vect-slp.cc
@@ -4213,6 +4213,7 @@ vect_build_slp_instance (vec_info *vinfo,
new_instance->cost_vec = vNULL;
new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
+ new_instance->elide_rev_perms_p = false;
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
@@ -4587,6 +4588,7 @@ vect_analyze_slp_reduc_chain (loop_vec_info vinfo,
new_instance->cost_vec = vNULL;
new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
+ new_instance->elide_rev_perms_p = false;
vinfo->slp_instances.safe_push (new_instance);
@@ -4652,6 +4654,7 @@ vect_analyze_slp_reduc_chain (loop_vec_info vinfo,
new_instance->cost_vec = vNULL;
new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
+ new_instance->elide_rev_perms_p = false;
vect_reduc_info reduc_info = info_for_reduction (vinfo, node);
reduc_info->is_reduc_chain = true;
@@ -4791,6 +4794,7 @@ vect_analyze_slp_reduction (loop_vec_info vinfo,
new_instance->cost_vec = vNULL;
new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
+ new_instance->elide_rev_perms_p = false;
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
@@ -4862,6 +4866,7 @@ vect_analyze_slp_reduction_group (loop_vec_info
loop_vinfo,
new_instance->cost_vec = vNULL;
new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
+ new_instance->elide_rev_perms_p = false;
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
@@ -5087,6 +5092,7 @@ vect_analyze_slp_instance (vec_info *vinfo,
new_instance->cost_vec = vNULL;
new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
+ new_instance->elide_rev_perms_p = false;
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
@@ -5327,6 +5333,7 @@ vect_analyze_slp_instance (vec_info *vinfo,
new_instance->cost_vec = vNULL;
new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
+ new_instance->elide_rev_perms_p = false;
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
@@ -8512,6 +8519,97 @@ vect_cse_slp_node_parts (hash_set<slp_tree> &visited,
vect_cse_slp_node_parts (visited, part_starts, drops, child);
}
+/* Helper function for recursively checking if the SLP subtree rooted
+ at NODE is suitable for reverse permutation elision. */
+
+static bool
+vect_can_elide_rev_perms_p (loop_vec_info loop_vinfo, slp_tree node)
+{
+ /* Reject permutation nodes. */
+ if (!node
+ || SLP_TREE_PERMUTE_P (node))
+ return false;
+
+ /* Constant and external defs are acceptable only if they are uniform
+ vectors. Reject other non-internal def types. */
+ vect_def_type def_type = SLP_TREE_DEF_TYPE (node);
+ if (def_type == vect_constant_def
+ || def_type == vect_external_def)
+ return vect_slp_tree_uniform_p (node);
+ else if (def_type != vect_internal_def)
+ return false;
+
+ /* If the result of a statement is used outside the loop, eliding the
+ reverse permutation could change the value observed by that use. */
+ stmt_vec_info stmt_info = SLP_TREE_REPRESENTATIVE (node);
+ if (!stmt_info
+ || STMT_VINFO_LIVE_P (stmt_info))
+ return false;
+
+ /* Only accept data references and GIMPLE assigns for now. */
+ if (STMT_VINFO_DATA_REF (stmt_info))
+ {
+ /* The final VMAT is unknown at this point, so here we only reject
+ obvious non-candidates. */
+ if (STMT_VINFO_STRIDED_P (stmt_info)
+ || STMT_VINFO_GATHER_SCATTER_P (stmt_info)
+ || compare_step_with_zero (loop_vinfo, stmt_info) >= 0)
+ return false;
+ }
+ else if (!is_gimple_assign (stmt_info->stmt))
+ return false;
+
+ poly_uint64 nunits = TYPE_VECTOR_SUBPARTS (SLP_TREE_VECTYPE (node));
+ for (slp_tree child : SLP_TREE_CHILDREN (node))
+ {
+ /* Reverse permutations can cancel each other out only if both nodes
+ have the same number of elements per vector. */
+ if (child
+ && SLP_TREE_DEF_TYPE (child) == vect_internal_def
+ && maybe_ne (nunits, TYPE_VECTOR_SUBPARTS (SLP_TREE_VECTYPE (child))))
+ return false;
+
+ /* Recursively check the child. */
+ if (!vect_can_elide_rev_perms_p (loop_vinfo, child))
+ return false;
+ }
+
+ return true;
+}
+
+/* Identify SLP subgraphs in which reverse permutations for negative-step
+ contiguous DRs might be elided. Record the tentative decision in
+ elide_rev_perms_p on each subgraph leader. The flag can be cleared
+ later if one of the final VMATs is not VMAT_CONTIGUOUS_REVERSE. */
+
+static void
+vect_analyze_rev_perms_elision (vec_info *vinfo)
+{
+ loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo);
+ if (!loop_vinfo)
+ return;
+
+ /* Partition the SLP graph and initialize elide_rev_perms_p to true for
+ leader SLP instances. */
+ vect_partition_graph (vinfo);
+ for (auto inst : vinfo->slp_instances)
+ if (inst->leader_instance == inst)
+ inst->elide_rev_perms_p = true;
+
+ /* Clear the flag on the leader if reverse permutations cannot be elided. */
+ for (auto inst : vinfo->slp_instances)
+ {
+ slp_instance leader = inst->leader_instance;
+ if (!leader->elide_rev_perms_p)
+ continue;
+
+ slp_tree root = SLP_INSTANCE_TREE (inst);
+ if (SLP_INSTANCE_KIND (inst) != slp_inst_kind_store
+ || !vect_can_elide_rev_perms_p (loop_vinfo, root))
+ leader->elide_rev_perms_p = false;
+ }
+}
+
/* Optimize the SLP graph of VINFO. */
void
@@ -8530,6 +8628,8 @@ vect_optimize_slp (vec_info *vinfo)
release_scalar_stmts_to_slp_tree_map (bst_map);
+ vect_analyze_rev_perms_elision (vinfo);
+
if (!is_a <bb_vec_info> (vinfo))
return;
diff --git a/gcc/tree-vect-stmts.cc b/gcc/tree-vect-stmts.cc
index 09e45d0629a..dd7d670bea6 100644
--- a/gcc/tree-vect-stmts.cc
+++ b/gcc/tree-vect-stmts.cc
@@ -8104,7 +8104,7 @@ vectorizable_scan_store (vec_info *vinfo, stmt_vec_info
stmt_info,
static bool
vectorizable_store (vec_info *vinfo,
stmt_vec_info stmt_info, gimple_stmt_iterator *gsi,
- slp_tree slp_node,
+ slp_tree slp_node, slp_instance node_instance,
stmt_vector_for_cost *cost_vec)
{
tree data_ref;
@@ -8128,6 +8128,7 @@ vectorizable_store (vec_info *vinfo,
poly_uint64 vf;
vec_load_store_type vls_type;
tree ref_type;
+ bool elide_rev_perms_p = false;
if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
return false;
@@ -8319,6 +8320,29 @@ vectorizable_store (vec_info *vinfo,
"Vectorizing an unaligned access.\n");
}
+ /* Honor the reverse permutation elision decision of the SLP subgraph.
+ During analysis, invalidate the decision if the final memory access
+ type is not VMAT_CONTIGUOUS_REVERSE. */
+ if (loop_vinfo
+ && node_instance
+ && node_instance->leader_instance
+ && node_instance->leader_instance->elide_rev_perms_p)
+ {
+ elide_rev_perms_p = true;
+ if (costing_p
+ && memory_access_type != VMAT_CONTIGUOUS_REVERSE)
+ {
+ elide_rev_perms_p = false;
+ node_instance->leader_instance->elide_rev_perms_p = false;
+ }
+
+ if (!costing_p
+ && dump_enabled_p ()
+ && elide_rev_perms_p)
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "Eliding reverse permutation for store.\n");
+ }
+
/* Transform. */
if (!costing_p)
@@ -9363,7 +9387,8 @@ vectorizable_store (vec_info *vinfo,
if (!costing_p)
vec_oprnd = vec_oprnds[i];
- if (memory_access_type == VMAT_CONTIGUOUS_REVERSE)
+ if (memory_access_type == VMAT_CONTIGUOUS_REVERSE
+ && !elide_rev_perms_p)
{
if (costing_p)
inside_cost += record_stmt_cost (cost_vec, 1, vec_perm,
@@ -9711,7 +9736,7 @@ hoist_defs_of_uses (gimple *stmt, class loop *loop, bool
hoist_p)
static bool
vectorizable_load (vec_info *vinfo,
stmt_vec_info stmt_info, gimple_stmt_iterator *gsi,
- slp_tree slp_node,
+ slp_tree slp_node, slp_instance node_instance,
stmt_vector_for_cost *cost_vec)
{
tree scalar_dest;
@@ -9746,6 +9771,7 @@ vectorizable_load (vec_info *vinfo,
tree ref_type;
enum vect_def_type mask_dt = vect_unknown_def_type;
enum vect_def_type els_dt = vect_unknown_def_type;
+ bool elide_rev_perms_p = false;
if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
return false;
@@ -9992,6 +10018,29 @@ vectorizable_load (vec_info *vinfo,
vinfo->any_known_not_updated_vssa = true;
}
+ /* Honor the reverse permutation elision decision of the SLP subgraph.
+ During analysis, invalidate the decision if the final memory access
+ type is not VMAT_CONTIGUOUS_REVERSE. */
+ if (loop_vinfo
+ && node_instance
+ && node_instance->leader_instance
+ && node_instance->leader_instance->elide_rev_perms_p)
+ {
+ elide_rev_perms_p = true;
+ if (costing_p
+ && memory_access_type != VMAT_CONTIGUOUS_REVERSE)
+ {
+ elide_rev_perms_p = false;
+ node_instance->leader_instance->elide_rev_perms_p = false;
+ }
+
+ if (!costing_p
+ && dump_enabled_p ()
+ && elide_rev_perms_p)
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "Eliding reverse permutation for load.\n");
+ }
+
/* For now just use the first available else value.
get_supported_else_vals tries MASK_LOAD_ELSE_ZERO first so we will
select it here if it is supported. */
@@ -11909,7 +11958,8 @@ vectorizable_load (vec_info *vinfo,
}
}
- if (memory_access_type == VMAT_CONTIGUOUS_REVERSE)
+ if (memory_access_type == VMAT_CONTIGUOUS_REVERSE
+ && !elide_rev_perms_p)
{
if (costing_p)
inside_cost = record_stmt_cost (cost_vec, 1, vec_perm,
@@ -13089,8 +13139,10 @@ vect_analyze_stmt (vec_info *vinfo,
|| vectorizable_conversion (vinfo, stmt_info, NULL, node, cost_vec)
|| vectorizable_operation (vinfo, stmt_info, NULL, node, cost_vec)
|| vectorizable_assignment (vinfo, stmt_info, NULL, node, cost_vec)
- || vectorizable_load (vinfo, stmt_info, NULL, node, cost_vec)
- || vectorizable_store (vinfo, stmt_info, NULL, node, cost_vec)
+ || vectorizable_load (vinfo, stmt_info, NULL, node, node_instance,
+ cost_vec)
+ || vectorizable_store (vinfo, stmt_info, NULL, node, node_instance,
+ cost_vec)
|| vectorizable_shift (vinfo, stmt_info, NULL, node, cost_vec)
|| vectorizable_condition (vinfo, stmt_info, NULL, node, cost_vec)
|| vectorizable_comparison (vinfo, stmt_info, NULL, node, cost_vec)
@@ -13185,12 +13237,14 @@ vect_transform_stmt (vec_info *vinfo,
break;
case load_vec_info_type:
- done = vectorizable_load (vinfo, stmt_info, gsi, slp_node, NULL);
+ done = vectorizable_load (vinfo, stmt_info, gsi, slp_node,
+ slp_node_instance, NULL);
gcc_assert (done);
break;
case store_vec_info_type:
- done = vectorizable_store (vinfo, stmt_info, gsi, slp_node, NULL);
+ done = vectorizable_store (vinfo, stmt_info, gsi, slp_node,
+ slp_node_instance, NULL);
gcc_assert (done);
break;
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index d8b1bef98cd..c4e49a3ff26 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -460,6 +460,10 @@ public:
/* The type of operation the SLP instance is performing. */
slp_instance_kind kind;
+ /* For a subgraph leader, whether reverse permutations throughout the
+ subgraph can be elided. Only meaningful for leader instances. */
+ bool elide_rev_perms_p;
+
dump_user_location_t location () const;
} *slp_instance;
--
2.43.0
