On 03/09/2026 14:44, Richard Biener wrote:
On Thu, 27 Aug 2026, Pengfei Li wrote: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;Checking STMT_VINFO_LIVE_P on the representative is not enough, you have to traverse all SLP_TREE_SCALAR_STMTS and check on those.+ + /* 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))You have to use a visited set to track already visited node, otherwise you'll run into cycles and exponential complexity because you are traversing a geneal directed graph.+ 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.ccindex 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;I'm not sure it's sound to do this during analysis, we might have used elide_rev_perms_p = true already, no?
I think It's sound (only) from correctness perspective. The flag on the leader instance is cleared so that the elision would be disabled on the whole subgraph during transformation. The local elide_rev_perm is also cleared here to cost current DR with reverse permutation.
But, the cost can still be inaccurate, as you mentioned, when an earlier DR is not costed with reverse permutation. So far I haven't seen an obvious clean way to handle this case, mainly because the final VMAT is only known in vectorizable_{load|store}. Do you have any ideas?
Thanks, Pengfei
+ } + + 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.hindex 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;
