On Thu, 27 Aug 2026, Pengfei Li wrote:
> 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.
Hmm, so you are now relying on vect_bb_partition_graph to be
conservatively correct, for now it's only used for costing.
There is PR125177 which says it is not correct.
Otherwise this looks reasonable.
> 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;
>
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Jochen Jaser, Andrew McDonald, Abhinav Puri; (HRB 36809, AG Nuernberg)
