The following implements merging of SLP subgraphs that overlap in
their low or highparts using VEC_PERM SLP nodes which already know
exactly how to extact half the number of lanes of another single node.
The motivating testcase is in PR126053 coming from 508.namd_r
Bootstrapped and tested on x86_64-unknown-linux-gnu.
The ??? comments show that restricting this to CSE SLP node halfs
(not vector halfs!) is probably a bit limiting if you consider
a three step 2-lane, 4-lane and 8-lane case where the 4-lane is
the lowpart of the 8-lane and the 2-lane the lowpart of the 4-lane.
That depends on the order of processing to CSE the 2-lane and if,
it will be CSEd to the 4-lane vector. I do not think we'd
handle 8-lane to 2-lane lowpart in vectorizable_slp_permutation
(but I did not perform actual experiments).
You can see how I restrict matching in vect_cse_gather_part_starts,
but for full generality we'd have to fully populate the
stmt -> SLP node map. To get defined ordering amongst candidates
we can order the SLP node vectors in that map by the number of
lanes of the candidate node.
I'll note that for 508.namd_r I only need the actual lowpart case,
not the highpart one.
While I think the redundant lane issue is present for loops as well
I did not enable the CSE there at this point.
Any comments? Any concerns about merging of SLP subgraphs with
differing number of lanes?
Thanks,
Richard.
PR tree-optimization/126099
PR tree-optimization/126053
* tree-vect-slp.cc (vect_cse_gather_part_starts): New function.
(vect_cse_slp_node_parts): Likewise.
(vect_optimize_slp): For BB SLP CSE to low/highparts of
other nodes.
* gcc.dg/vect/bb-slp-pr126099-1.c: New testcase.
* gcc.dg/vect/bb-slp-pr126099-2.c: Likewise.
* gcc.dg/vect/costmodel/x86_64/costmodel-pr126053.c: Likewise.
---
gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-1.c | 24 ++++
gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-2.c | 24 ++++
.../costmodel/x86_64/costmodel-pr126053.c | 131 +++++++++++++++++
gcc/tree-vect-slp.cc | 136 ++++++++++++++++++
4 files changed, 315 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-1.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-2.c
create mode 100644
gcc/testsuite/gcc.dg/vect/costmodel/x86_64/costmodel-pr126053.c
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-1.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-1.c
new file mode 100644
index 00000000000..7c3d08c2f56
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-1.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_long } */
+/* { dg-additional-options "-mavx2" { target avx2 } } */
+
+void foo (long *p, long *q, long *r)
+{
+ long tem0 = r[0];
+ long tem1 = r[1];
+ long tem2 = r[2];
+ long tem3 = r[3];
+ tem0 = tem0 + 1;
+ tem1 = tem1 + 2;
+ tem2 = tem2 + 3;
+ tem3 = tem3 + 4;
+ p[0] = tem0;
+ p[1] = tem1;
+ q[0] = tem0;
+ q[1] = tem1;
+ q[2] = tem2;
+ q[3] = tem3;
+}
+
+/* { dg-final { scan-tree-dump "CSEd node\[^\n\r\]*lowpart" "slp2" } } */
+/* { dg-final { scan-tree-dump "BIT_FIELD_REF" "slp2" { target avx2 } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-2.c
b/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-2.c
new file mode 100644
index 00000000000..ce6cda61683
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-2.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_long } */
+/* { dg-additional-options "-mavx2" { target avx2 } } */
+
+void foo (long *p, long *q, long *r)
+{
+ long tem0 = r[0];
+ long tem1 = r[1];
+ long tem2 = r[2];
+ long tem3 = r[3];
+ tem0 = tem0 + 1;
+ tem1 = tem1 + 2;
+ tem2 = tem2 + 3;
+ tem3 = tem3 + 4;
+ p[0] = tem2;
+ p[1] = tem3;
+ q[0] = tem0;
+ q[1] = tem1;
+ q[2] = tem2;
+ q[3] = tem3;
+}
+
+/* { dg-final { scan-tree-dump "CSEd node\[^\n\r\]*highpart" "slp2" } } */
+/* { dg-final { scan-tree-dump "BIT_FIELD_REF" "slp2" { target avx2 } } } */
diff --git a/gcc/testsuite/gcc.dg/vect/costmodel/x86_64/costmodel-pr126053.c
b/gcc/testsuite/gcc.dg/vect/costmodel/x86_64/costmodel-pr126053.c
new file mode 100644
index 00000000000..f129a36b47b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/costmodel/x86_64/costmodel-pr126053.c
@@ -0,0 +1,131 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-O3 -fno-signed-zeros -march=x86-64-v3
-fopt-info-vec" } */
+
+typedef double BigReal;
+
+struct Position {
+ BigReal x, y, z;
+};
+
+struct CompAtom {
+ struct Position position;
+ float charge;
+ short vdwType;
+ unsigned char partition;
+ unsigned char nonbondedGroupSize;
+};
+
+struct Force {
+ BigReal x, y, z;
+};
+
+struct SimParams {
+ BigReal offset_x, offset_y, offset_z;
+};
+
+enum { vXX, vXY, vXZ, vYY, vYZ, vZZ, fvXX, fvXY, fvXZ, fvYY, fvYZ, fvZZ };
+void calc_pair_energy_fullelect(
+ const struct CompAtom *__restrict p_0,
+ const struct CompAtom *__restrict p_1,
+ const struct SimParams *__restrict params, const int *__restrict
pairlist_n,
+ const int *__restrict pairlist_m, const int *__restrict npair_n_list,
+ const int *__restrict npair_m_list, int i_upper,
+ const BigReal *__restrict force_r_vals, struct Force *__restrict f_0,
+ struct Force *__restrict f_1, BigReal *__restrict reduction) {
+ BigReal virial_xx = 0, virial_xy = 0, virial_xz = 0;
+ BigReal virial_yy = 0, virial_yz = 0, virial_zz = 0;
+ BigReal fullElectVirial_xx = 0, fullElectVirial_xy = 0,
+ fullElectVirial_xz = 0;
+ BigReal fullElectVirial_yy = 0, fullElectVirial_yz = 0,
+ fullElectVirial_zz = 0;
+
+ int pn = 0, pm = 0;
+ for (int i = 0; i < i_upper; ++i) {
+ const struct CompAtom *p_i = p_0 + i;
+ const BigReal p_i_x = params->offset_x + p_i->position.x;
+ const BigReal p_i_y = params->offset_y + p_i->position.y;
+ const BigReal p_i_z = params->offset_z + p_i->position.z;
+
+ BigReal f_i_x = 0, f_i_y = 0, f_i_z = 0;
+
+ {
+ const int npairi = npair_n_list[i];
+ const int *pli = pairlist_n + pn;
+ const BigReal *fr = force_r_vals + pn;
+ for (int k = 0; k < npairi; ++k) {
+ const int j = pli[k];
+ const struct CompAtom *p_j = p_1 + j;
+ struct Force *f_j = f_1 + j;
+ const BigReal p_ij_x = p_i_x - p_j->position.x;
+ const BigReal p_ij_y = p_i_y - p_j->position.y;
+ const BigReal p_ij_z = p_i_z - p_j->position.z;
+ const BigReal force_r = fr[k];
+ BigReal tmp_x = force_r * p_ij_x;
+ virial_xx += tmp_x * p_ij_x;
+ virial_xy += tmp_x * p_ij_y;
+ virial_xz += tmp_x * p_ij_z;
+ f_i_x += tmp_x;
+ f_j->x -= tmp_x; /* { dg-optimized "basic block part vectorized using
16 byte vectors" } */
+ BigReal tmp_y = force_r * p_ij_y;
+ virial_yy += tmp_y * p_ij_y;
+ virial_yz += tmp_y * p_ij_z;
+ f_i_y += tmp_y;
+ f_j->y -= tmp_y;
+ BigReal tmp_z = force_r * p_ij_z;
+ virial_zz += tmp_z * p_ij_z;
+ f_i_z += tmp_z;
+ f_j->z -= tmp_z;
+ }
+ pn += npairi;
+ }
+ {
+ const int npairi = npair_m_list[i];
+ const int *pli = pairlist_m + pm;
+ const BigReal *fr = force_r_vals + pm;
+ for (int k = 0; k < npairi; ++k) {
+ const int j = pli[k];
+ const struct CompAtom *p_j = p_1 + j;
+ struct Force *f_j = f_1 + j;
+ const BigReal p_ij_x = p_i_x - p_j->position.x;
+ const BigReal p_ij_y = p_i_y - p_j->position.y;
+ const BigReal p_ij_z = p_i_z - p_j->position.z;
+ const BigReal force_r = fr[k];
+ BigReal tmp_x = force_r * p_ij_x;
+ virial_xx += tmp_x * p_ij_x;
+ virial_xy += tmp_x * p_ij_y;
+ virial_xz += tmp_x * p_ij_z;
+ f_i_x += tmp_x;
+ f_j->x -= tmp_x; /* { dg-optimized "basic block part vectorized using
16 byte vectors" } */
+
+ BigReal tmp_y = force_r * p_ij_y;
+ virial_yy += tmp_y * p_ij_y;
+ virial_yz += tmp_y * p_ij_z;
+ f_i_y += tmp_y;
+ f_j->y -= tmp_y;
+ BigReal tmp_z = force_r * p_ij_z;
+ virial_zz += tmp_z * p_ij_z;
+ f_i_z += tmp_z;
+ f_j->z -= tmp_z;
+ }
+ pm += npairi;
+ }
+
+ f_0[i].x += f_i_x; /* { dg-optimized "basic block part vectorized using 16
byte vectors" } */
+
+ f_0[i].y += f_i_y;
+ f_0[i].z += f_i_z;
+ }
+
+ reduction[vXX] += virial_xx; /* { dg-optimized "basic block part vectorized
using 32 byte vectors" } */
+ reduction[vXY] += virial_xy;
+ reduction[vXZ] += virial_xz;
+ reduction[vYY] += virial_yy;
+ reduction[vYZ] += virial_yz; /* { dg-optimized "basic block part vectorized
using 16 byte vectors" } */
+ reduction[vZZ] += virial_zz;
+ reduction[fvXX] += fullElectVirial_xx;
+ reduction[fvXY] += fullElectVirial_xy;
+ reduction[fvXZ] += fullElectVirial_xz;
+ reduction[fvYY] += fullElectVirial_yy;
+ reduction[fvYZ] += fullElectVirial_yz;
+ reduction[fvZZ] += fullElectVirial_zz;
+}
diff --git a/gcc/tree-vect-slp.cc b/gcc/tree-vect-slp.cc
index dcedb38c117..e59ba0cd9ce 100644
--- a/gcc/tree-vect-slp.cc
+++ b/gcc/tree-vect-slp.cc
@@ -8505,6 +8505,119 @@ vect_cse_slp_nodes (scalar_stmts_to_slp_tree_map_t
*bst_map, slp_tree& node)
*bst_map->get (SLP_TREE_SCALAR_STMTS (node)) = node;
}
+/* Associate stmts with possible starts of a subset of lanes of NODE
+ in PART_STARTS. */
+
+static void
+vect_cse_gather_part_starts (hash_set<slp_tree> &visited,
+ vec<vec<slp_tree>> part_starts, slp_tree node)
+{
+ /* CSEing external nodes complicates scheduling since we materialize
+ those at the latest position, so avoid that. */
+ if (SLP_TREE_DEF_TYPE (node) != vect_internal_def
+ || visited.add (node))
+ return;
+
+ /* Besides some VEC_PERM_EXPR, two-operator nodes also
+ lack scalar stmts and thus CSE doesn't work via bst_map. Ideally
+ we'd have sth that works for all internal and external nodes. */
+ if (!SLP_TREE_SCALAR_STMTS (node).is_empty ()
+ && SLP_TREE_LANES (node) > 2
+ && (SLP_TREE_LANES (node) & 1) == 0)
+ {
+ auto c0 = SLP_TREE_SCALAR_STMTS (node)[0];
+ if (c0)
+ {
+ /* Most stmts should be part of exactly one SLP node, so
+ a reserve_exact should pay off. */
+ part_starts[gimple_uid (c0->stmt)].reserve_exact (1);
+ part_starts[gimple_uid (c0->stmt)].safe_push (node);
+ }
+ auto c1 = SLP_TREE_SCALAR_STMTS (node)[SLP_TREE_LANES (node) / 2];
+ /* Avoid putting duplicate nodes on a stmts vector. */
+ if (c1 && c1 != c0)
+ {
+ part_starts[gimple_uid (c1->stmt)].reserve_exact (1);
+ part_starts[gimple_uid (c1->stmt)].safe_push (node);
+ }
+ }
+
+ for (slp_tree &child : SLP_TREE_CHILDREN (node))
+ if (child)
+ vect_cse_gather_part_starts (visited, part_starts, child);
+}
+
+/* Apply CSE to NODE and its children using lowparts of nodes in BST_MAP. */
+
+static void
+vect_cse_slp_node_parts (hash_set<slp_tree> &visited,
+ const vec<vec<slp_tree>> part_starts,
+ slp_tree node)
+{
+ if (SLP_TREE_DEF_TYPE (node) != vect_internal_def
+ || visited.add (node))
+ return;
+
+ /* Besides some VEC_PERM_EXPR, two-operator nodes also
+ lack scalar stmts and thus CSE doesn't work via bst_map. Ideally
+ we'd have sth that works for all internal and external nodes. */
+ if (!SLP_TREE_SCALAR_STMTS (node).is_empty ()
+ && SLP_TREE_SCALAR_STMTS (node)[0]
+ /* Avoid touching loads or permutes. */
+ && !SLP_TREE_PERMUTE_P (node)
+ && !STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (node)))
+ for (slp_tree cand
+ : part_starts[gimple_uid (SLP_TREE_SCALAR_STMTS (node)[0]->stmt)])
+ /* ??? When we release children below a subpart of the SLP graph
+ can become unreachable and released. But the stmt to node mapping
+ still points to the released parts (which are still reachable in
+ the alloc-pool), but we can't trivially update that mapping, so
+ verify by looking at the reference count. Up to now we are not
+ allocating new nodes for extra permutes.
+ ??? This also presents an ordering/optimality problem in that
+ the CSE then can keep a wider feeding live even though it itself
+ becomes dead by means of CSE. Which might be solvable by doing
+ the CSE in a wide-to-narrow order. */
+ if (SLP_TREE_REF_COUNT (cand) != 0
+ && SLP_TREE_LANES (cand) == 2 * SLP_TREE_LANES (node))
+ {
+ unsigned i;
+ for (i = 0;
+ i <= SLP_TREE_LANES (node); i += SLP_TREE_LANES (node))
+ {
+ unsigned j;
+ for (j = 0; j < SLP_TREE_LANES (node); ++j)
+ if (SLP_TREE_SCALAR_STMTS (cand)[i+j]
+ != SLP_TREE_SCALAR_STMTS (node)[j])
+ break;
+ if (j == SLP_TREE_LANES (node))
+ break;
+ }
+ if (i > SLP_TREE_LANES (node))
+ continue;
+ /* Found node within cand at i. Put a permute in place
+ of it, selecting the subset from cand. */
+ if (dump_enabled_p ())
+ dump_printf (MSG_NOTE, "CSEd node %p as %spart of node %p\n",
+ (void *)node, i == 0 ? "low" : "high", (void *)cand);
+ for (slp_tree child : SLP_TREE_CHILDREN (node))
+ vect_free_slp_tree (child);
+ SLP_TREE_CHILDREN (node).truncate (1);
+ SLP_TREE_REF_COUNT (cand)++;
+ SLP_TREE_CHILDREN (node)[0] = cand;
+ SLP_TREE_CODE (node) = VEC_PERM_EXPR;
+ SLP_TREE_REPRESENTATIVE (node) = NULL;
+ SLP_TREE_LANE_PERMUTATION (node).create (SLP_TREE_LANES (node));
+ for (unsigned j = i; j < i + SLP_TREE_LANES (node); ++j)
+ SLP_TREE_LANE_PERMUTATION (node).quick_push (std::make_pair (0, j));
+ return;
+ }
+
+ for (slp_tree &child : SLP_TREE_CHILDREN (node))
+ if (child)
+ vect_cse_slp_node_parts (visited, part_starts, child);
+}
+
/* Optimize the SLP graph of VINFO. */
void
@@ -8522,6 +8635,29 @@ vect_optimize_slp (vec_info *vinfo)
vect_cse_slp_nodes (bst_map, SLP_INSTANCE_TREE (inst));
release_scalar_stmts_to_slp_tree_map (bst_map);
+
+ if (!is_a <bb_vec_info> (vinfo))
+ return;
+
+ /* Attempt to merge SLP sub-graphs that intersect in low or highparts of
+ each other. Build the reverse mapping from stmt to SLP node for
+ lanes starting at the low or high part.
+ ??? In the future we can extend this to do a two-step permute
+ and extract or extract and permute to put the high/low part in
+ place on the original vector or permute the hogh/low part to
+ match up the target lane order. */
+ hash_set<slp_tree> visited;
+ vec<vec<slp_tree>> start_for_part;
+ start_for_part.create (vinfo->stmt_vec_infos.length () + 1);
+ start_for_part.quick_grow_cleared (vinfo->stmt_vec_infos.length () + 1);
+ for (auto inst : vinfo->slp_instances)
+ vect_cse_gather_part_starts (visited,
+ start_for_part, SLP_INSTANCE_TREE (inst));
+
+ /* Now replace low/highpart copies with extracting permutes. */
+ visited.empty ();
+ for (auto inst : vinfo->slp_instances)
+ vect_cse_slp_node_parts (visited, start_for_part, SLP_INSTANCE_TREE
(inst));
}
/* Gather loads reachable from the individual SLP graph entries. */
--
2.51.0
