[PATCH 3/3] tree-optimization/126099 - SLP subgraph merging with low/highpart extracts
Richard Biener <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
The following implements merging of SLP subgraphs that overlap in
their vectors low or highparts or in full vector copies using VEC_PERM
SLP nodes which know how to perform these extractions, but not more
in general.
The operation is to build a reverse mapping of scalar stmt to SLP node
for possible extraction starts - without knowing the extraction vector
type that's even lanes of SLP nodes with an even number of lanes. And
then for each SLP node lane zero checking whether it's fully contained
in one of the candidates with the restrictions implied by
vectorizable_slp_permutation.
The motivating testcase is in PR126053 coming from 508.namd_r. The
testcases gcc.dg/vect/bb-slp-pr126099-{4,5}.c are cases where schedule
verification strips one of the graph entries as subgraph merging
otherwise causes SSA verification failures.
Bootstrapped and tested on x86_64-unknown-linux-gnu. I've also
built SPEC CPU 2017 in various ways (which found quite some issues,
all fixed now).
Any comments?
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/bb-slp-pr126099-3.c: Likewise.
* gcc.dg/vect/bb-slp-pr126099-4.c: Likewise.
* gcc.dg/vect/bb-slp-pr126099-5.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 +++
gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-3.c | 24 +++
gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-4.c | 22 +++
gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-5.c | 23 +++
.../costmodel/x86_64/costmodel-pr126053.c | 131 +++++++++++++++
gcc/tree-vect-slp.cc | 154 ++++++++++++++++++
7 files changed, 402 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/bb-slp-pr126099-3.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-4.c
create mode 100644 gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-5.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/bb-slp-pr126099-3.c b/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-3.c
new file mode 100644
index 00000000000..cfd58317ef4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-3.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 *s)
+{
+ long tem0 = r[0];
+ long tem1 = r[1];
+ long tem2 = r[2];
+ long tem3 = r[3];
+ tem0 = tem0 + s[0];
+ tem1 = tem1 - s[1];
+ tem2 = tem2 + s[2];
+ tem3 = tem3 - s[3];
+ 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/bb-slp-pr126099-4.c b/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-4.c
new file mode 100644
index 00000000000..0a2148eb832
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-4.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+
+typedef unsigned v2si __attribute__((vector_size(8)));
+typedef unsigned v4si __attribute__((vector_size(16)));
+
+unsigned bar(unsigned);
+
+v4si x;
+v2si y;
+
+void foo(unsigned *p, unsigned i, unsigned j, unsigned k)
+{
+ unsigned tem0 = p[0] ^ i;
+ unsigned tem1 = p[1] ^ j;
+ unsigned p2 = p[2];
+ unsigned p3 = p[3];
+ y = (v2si) { tem0, tem1 };
+ k = bar (k);
+ unsigned tem2 = p2 ^ k;
+ unsigned tem3 = p3 ^ k;
+ x = (v4si) { tem0, tem1, tem2, tem3 };
+}
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-5.c b/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-5.c
new file mode 100644
index 00000000000..1b1adf8c817
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr126099-5.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+
+unsigned bar(unsigned);
+
+unsigned x[4];
+unsigned y[2];
+
+void foo(unsigned int *p, unsigned int i, unsigned int j, unsigned int k)
+{
+ unsigned int tem0 = p[0] ^ i;
+ unsigned int tem1 = p[1] ^ j;
+ unsigned p2 = p[2];
+ unsigned p3 = p[3];
+ y[0] = tem0;
+ y[1] = tem1;
+ k = bar (k);
+ unsigned int tem2 = p2 ^ k;
+ unsigned int tem3 = p3 ^ k;
+ x[0] = tem0;
+ x[1] = tem1;
+ x[2] = tem2;
+ x[3] = tem3;
+}
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 5ba19877f9e..944e36e490e 100644
--- a/gcc/tree-vect-slp.cc
+++ b/gcc/tree-vect-slp.cc
@@ -8494,6 +8494,127 @@ 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. For now gather two-lane aligned starts
+ of nodes with a multiple of two number of lanes. */
+ if (!SLP_TREE_SCALAR_STMTS (node).is_empty ()
+ && SLP_TREE_LANES (node) > 2
+ && (SLP_TREE_LANES (node) & 1) == 0)
+ {
+ auto_vec<unsigned, 8> uids;
+ for (unsigned i = 0; i < SLP_TREE_LANES (node); i += 2)
+ {
+ stmt_vec_info s = SLP_TREE_SCALAR_STMTS (node)[i];
+ if (!s)
+ continue;
+ unsigned uid = gimple_uid (s->stmt);
+ if (!uids.contains (uid))
+ {
+ uids.safe_push (uid);
+ part_starts[uid].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,
+ vec<slp_tree> &drops, 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. */
+ unsigned HOST_WIDE_INT c;
+ if (!SLP_TREE_SCALAR_STMTS (node).is_empty ()
+ && SLP_TREE_SCALAR_STMTS (node)[0]
+ /* Avoid touching loads which need care with load permutations
+ and specialities like load-lane representations. */
+ && !STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (node)))
+ for (slp_tree cand
+ : part_starts[gimple_uid (SLP_TREE_SCALAR_STMTS (node)[0]->stmt)])
+ /* ??? There is a possible 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_LANES (cand) > SLP_TREE_LANES (node)
+ /* We can do high/lo extracts and full vector copies. */
+ && constant_multiple_p
+ (TYPE_VECTOR_SUBPARTS (SLP_TREE_VECTYPE (cand)),
+ TYPE_VECTOR_SUBPARTS (SLP_TREE_VECTYPE (node)), &c)
+ && c <= 2)
+ {
+ unsigned HOST_WIDE_INT s;
+ bool const_p
+ = TYPE_VECTOR_SUBPARTS (SLP_TREE_VECTYPE (node)).is_constant (&s);
+ unsigned i;
+ for (i = 0; i <= SLP_TREE_LANES (cand) - SLP_TREE_LANES (node);)
+ {
+ unsigned j;
+ for (j = 0; j < SLP_TREE_LANES (node); ++j)
+ if (!SLP_TREE_SCALAR_STMTS (node)[j]
+ || (SLP_TREE_SCALAR_STMTS (cand)[i+j]
+ != SLP_TREE_SCALAR_STMTS (node)[j]))
+ break;
+ if (j == SLP_TREE_LANES (node))
+ break;
+ if (!const_p)
+ {
+ i = SLP_TREE_LANES (cand);
+ break;
+ }
+ /* We can extract only aligned on node vector type boundary. */
+ i += s;
+ }
+ if (i > SLP_TREE_LANES (cand) - 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))
+ /* Delay SLP tree release since we might still reference a node
+ from the part_starts map. */
+ drops.safe_push (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, drops, child);
+}
+
/* Optimize the SLP graph of VINFO. */
void
@@ -8511,6 +8632,39 @@ 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. */
+ auto_vec<slp_tree> drops;
+ visited.empty ();
+ for (auto inst : vinfo->slp_instances)
+ vect_cse_slp_node_parts (visited, start_for_part, drops,
+ SLP_INSTANCE_TREE (inst));
+
+ /* Now perform delayed releases of nodes. */
+ for (slp_tree node : drops)
+ vect_free_slp_tree (node);
+
+ for (auto v : start_for_part)
+ v.release ();
+ start_for_part.release ();
}
/* Gather loads reachable from the individual SLP graph entries. */
--
2.51.0