The existing SLP graph partitioning code is specific to BB SLP. This
patch generalizes it so that it can also be used by loop SLP to support
reverse permutations elision.
This adds a leader_instance member to _slp_instance. It points to the
leader instance of the connected SLP subgraph containing the current
instance, or NULL if the graph has not been partitioned.
Bootstrapped and tested on aarch64-linux-gnu and x86_64-linux-gnu.
gcc/ChangeLog:
* tree-vect-slp.cc (vect_partition_graph): Renamed from
vect_bb_partition_graph and generalized.
(vect_build_slp_instance): Initialize leader_instance.
(vect_analyze_slp_reduc_chain): Likewise.
(vect_analyze_slp_reduction): Likewise.
(vect_analyze_slp_reduction_group): Likewise.
(vect_analyze_slp_instance): Likewise.
(vect_partition_graph_r): Renamed from
vect_bb_partition_graph_r and adjusted.
(vect_bb_slp_scalar_cost): Update comments.
(vect_slp_analyze_bb_1): Adjust call to vect_partition_graph.
* tree-vectorizer.h (_slp_instance::leader_instance): New
member.
---
gcc/tree-vect-slp.cc | 53 ++++++++++++++++++++++++++-----------------
gcc/tree-vectorizer.h | 6 ++++-
2 files changed, 37 insertions(+), 22 deletions(-)
diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
index d8884fbd88a..fc08d10b872 100644
--- a/gcc/tree-vect-slp.cc
+++ b/gcc/tree-vect-slp.cc
@@ -69,6 +69,7 @@ static int vectorizable_slp_permutation_1 (vec_info *,
gimple_stmt_iterator *,
vec<slp_tree> &, bool);
static void vect_print_slp_tree (dump_flags_t, dump_location_t, slp_tree);
static bool vect_slp_can_convert_to_external (const vec<stmt_vec_info> &);
+static void vect_partition_graph (vec_info *);
static object_allocator<_slp_tree> *slp_tree_pool;
static slp_tree slp_first_node;
@@ -4210,6 +4211,7 @@ vect_build_slp_instance (vec_info *vinfo,
SLP_INSTANCE_KIND (new_instance) = kind;
new_instance->reduc_phis = NULL;
new_instance->cost_vec = vNULL;
+ new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
if (dump_enabled_p ())
@@ -4583,6 +4585,7 @@ vect_analyze_slp_reduc_chain (loop_vec_info vinfo,
SLP_INSTANCE_KIND (new_instance) = slp_inst_kind_reduc_chain;
new_instance->reduc_phis = NULL;
new_instance->cost_vec = vNULL;
+ new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
vinfo->slp_instances.safe_push (new_instance);
@@ -4647,6 +4650,7 @@ vect_analyze_slp_reduc_chain (loop_vec_info vinfo,
SLP_INSTANCE_KIND (new_instance) = slp_inst_kind_reduc_chain;
new_instance->reduc_phis = NULL;
new_instance->cost_vec = vNULL;
+ new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
vect_reduc_info reduc_info = info_for_reduction (vinfo, node);
@@ -4785,6 +4789,7 @@ vect_analyze_slp_reduction (loop_vec_info vinfo,
SLP_INSTANCE_KIND (new_instance) = kind;
new_instance->reduc_phis = NULL;
new_instance->cost_vec = vNULL;
+ new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
if (dump_enabled_p ())
@@ -4855,6 +4860,7 @@ vect_analyze_slp_reduction_group (loop_vec_info
loop_vinfo,
SLP_INSTANCE_KIND (new_instance) = slp_inst_kind_reduc_group;
new_instance->reduc_phis = NULL;
new_instance->cost_vec = vNULL;
+ new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
if (dump_enabled_p ())
@@ -5079,6 +5085,7 @@ vect_analyze_slp_instance (vec_info *vinfo,
SLP_INSTANCE_KIND (new_instance) = kind;
new_instance->reduc_phis = NULL;
new_instance->cost_vec = vNULL;
+ new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
if (dump_enabled_p ())
@@ -5318,6 +5325,7 @@ vect_analyze_slp_instance (vec_info *vinfo,
SLP_INSTANCE_KIND (new_instance) = kind;
new_instance->reduc_phis = NULL;
new_instance->cost_vec = vNULL;
+ new_instance->leader_instance = NULL;
new_instance->subgraph_entries = vNULL;
if (dump_enabled_p ())
@@ -9511,7 +9519,7 @@ get_ultimate_leader (slp_instance instance,
}
namespace {
-/* Subroutine of vect_bb_partition_graph_r. Map KEY to INSTANCE in
+/* Subroutine of vect_partition_graph_r. Map KEY to INSTANCE in
KEY_TO_INSTANCE, making INSTANCE the leader of any previous mapping
for KEY. Return true if KEY was already in KEY_TO_INSTANCE.
@@ -9543,14 +9551,13 @@ vect_map_to_instance (slp_instance instance, T key,
}
}
-/* Worker of vect_bb_partition_graph, recurse on NODE. */
+/* Worker of vect_partition_graph, recurse on NODE. */
static void
-vect_bb_partition_graph_r (bb_vec_info bb_vinfo,
- slp_instance instance, slp_tree node,
- hash_map<stmt_vec_info, slp_instance>
&stmt_to_instance,
- hash_map<slp_tree, slp_instance> &node_to_instance,
- hash_map<slp_instance, slp_instance>
&instance_leader)
+vect_partition_graph_r (slp_instance instance, slp_tree node,
+ hash_map<stmt_vec_info, slp_instance> &stmt_to_instance,
+ hash_map<slp_tree, slp_instance> &node_to_instance,
+ hash_map<slp_instance, slp_instance> &instance_leader)
{
for (auto stmt_info : SLP_TREE_SCALAR_STMTS (node))
if (stmt_info)
@@ -9563,16 +9570,16 @@ vect_bb_partition_graph_r (bb_vec_info bb_vinfo,
for (auto child : SLP_TREE_CHILDREN (node))
if (child && SLP_TREE_DEF_TYPE (child) == vect_internal_def)
- vect_bb_partition_graph_r (bb_vinfo, instance, child, stmt_to_instance,
- node_to_instance, instance_leader);
+ vect_partition_graph_r (instance, child, stmt_to_instance,
+ node_to_instance, instance_leader);
}
-/* Partition the SLP graph into pieces that can be costed independently. */
+/* Partition the SLP graph into connected subgraphs. */
static void
-vect_bb_partition_graph (bb_vec_info bb_vinfo)
+vect_partition_graph (vec_info *vinfo)
{
- DUMP_VECT_SCOPE ("vect_bb_partition_graph");
+ DUMP_VECT_SCOPE ("vect_partition_graph");
/* First walk the SLP graph assigning each involved scalar stmt a
corresponding SLP graph entry and upon visiting a previously
@@ -9581,20 +9588,24 @@ vect_bb_partition_graph (bb_vec_info bb_vinfo)
hash_map<slp_tree, slp_instance> node_to_instance;
hash_map<slp_instance, slp_instance> instance_leader;
slp_instance instance;
- for (unsigned i = 0; bb_vinfo->slp_instances.iterate (i, &instance); ++i)
+ for (unsigned i = 0; vinfo->slp_instances.iterate (i, &instance); ++i)
{
instance_leader.put (instance, instance);
- vect_bb_partition_graph_r (bb_vinfo,
- instance, SLP_INSTANCE_TREE (instance),
- stmt_to_instance, node_to_instance,
- instance_leader);
+ vect_partition_graph_r (instance, SLP_INSTANCE_TREE (instance),
+ stmt_to_instance, node_to_instance,
+ instance_leader);
}
/* Then collect entries to each independent subgraph. */
- for (unsigned i = 0; bb_vinfo->slp_instances.iterate (i, &instance); ++i)
+ for (unsigned i = 0; vinfo->slp_instances.iterate (i, &instance); ++i)
{
slp_instance leader = get_ultimate_leader (instance, instance_leader);
- leader->subgraph_entries.safe_push (instance);
+ instance->leader_instance = leader;
+
+ /* Collect subgraph_entries only for BB SLP. */
+ if (is_a <bb_vec_info> (vinfo))
+ leader->subgraph_entries.safe_push (instance);
+
if (dump_enabled_p ()
&& leader != instance)
dump_printf_loc (MSG_NOTE, vect_location,
@@ -9653,7 +9664,7 @@ vect_bb_slp_scalar_cost (bb_vec_info vinfo,
continue;
}
- /* The following assert verifies that vect_bb_partition_graph
+ /* The following assert verifies that vect_partition_graph
partitions the SLP graph in a way that each scalar stmt of
the coverage of the SLP graph belongs to exactly one subgraph.
??? This is currently not guaranteed since the function
@@ -10344,7 +10355,7 @@ vect_slp_analyze_bb_1 (bb_vec_info bb_vinfo, int
n_stmts, bool &fatal,
/* Compute vectorizable live stmts. */
vect_bb_slp_mark_live_stmts (bb_vinfo);
- vect_bb_partition_graph (bb_vinfo);
+ vect_partition_graph (bb_vinfo);
return true;
}
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 4d542d57e6d..d8b1bef98cd 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -449,7 +449,11 @@ public:
/* Vector cost of this entry to the SLP graph. */
stmt_vector_for_cost cost_vec;
- /* If this instance is the main entry of a subgraph the set of
+ /* The leader SLP instance of the connected SLP subgraph containing this
+ instance, or NULL if the graph has not been partitioned. */
+ _slp_instance *leader_instance;
+
+ /* If this instance is the leader of a connected subgraph, the set of
entries into the same subgraph, including itself. */
vec<_slp_instance *> subgraph_entries;
--
2.43.0
