On Fri, 4 Sep 2026, Pengfei Li wrote:
>
> On 03/09/2026 15:07, Richard Biener wrote:
> > 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.
>
> Thanks for pointing out this.
>
> PR125177 seems to be about the scalar coverage in BB SLP. Could it also be an
> issue in loop SLP? My impression is that shared scalar coverage across
> iterations are usually loop invariants and they are usually hoisted outside
> the loop before vectorization.
I never tested the SLP graph partitioning code on loop SLP, there might
be unexpected differences. I suspect since you exclude externs/constants
that are not uniform things will be fine but those might be the area
where differences might show up.
> btw, do you plan to address this in the near future?
It's on my list ... but given it "only" affects costing currently it
wasn't high priority.
Richard.
> Thanks,
> Pengfei
>
>
> >
> > 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)
