First-order recurrence vectorization rejects a loop in which the latch
definition of a header PHI is itself a header PHI. That is the shape
of TSVC s255, where two scalars carry values from one and two
iterations back. Such a chain of header PHIs, each the latch
definition of the previous one and terminating in a non-PHI definition
inside the loop, is a series of first-order recurrences that can all
be vectorized. A cyclic chain, for example two PHIs swapping values,
cannot, so the new vect_recurrence_chain_p rejects cycles. It also
rejects chains involving a PHI classified as another kind of scalar
cycle, like the induction PHI in the loop of PR 107302, and chains
whose terminating definition uses a chain PHI, a value cycle as in a
reduction.
For the transform, the vectorized latch value of a chained recurrence
is the permute emitted for the latch child, which the SLP scheduler
has already transformed. Insert the chained permute after the last
vectorized def of that child instead of after the scalar latch
definition, which for a chain is a PHI we cannot insert after.
PR tree-optimization/116338
gcc/ChangeLog:
* tree-vect-loop.cc (vect_recurrence_chain_p): New function.
(vect_phi_first_order_recurrence_p): Accept a latch definition
that is a header PHI starting an acyclic recurrence chain. Do
not require dominance for a use as the latch argument of
another header PHI.
(vectorizable_recurr): For a chained recurrence insert the
permute after the last vectorized def of the latch child.
gcc/testsuite/ChangeLog:
* gcc.dg/vect/pr116338-1.c: New testcase.
* gcc.dg/vect/pr116338-2.c: New testcase.
* gcc.dg/vect/pr116338-3.c: New testcase.
Signed-off-by: Tanmay Gulhane <[email protected]>
---
gcc/testsuite/gcc.dg/vect/pr116338-1.c | 43 +++++++++
gcc/testsuite/gcc.dg/vect/pr116338-2.c | 43 +++++++++
gcc/testsuite/gcc.dg/vect/pr116338-3.c | 23 +++++
gcc/tree-vect-loop.cc | 121 ++++++++++++++++++++++---
4 files changed, 218 insertions(+), 12 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/vect/pr116338-1.c
create mode 100644 gcc/testsuite/gcc.dg/vect/pr116338-2.c
create mode 100644 gcc/testsuite/gcc.dg/vect/pr116338-3.c
diff --git a/gcc/testsuite/gcc.dg/vect/pr116338-1.c
b/gcc/testsuite/gcc.dg/vect/pr116338-1.c
new file mode 100644
index 000000000..940b2b56d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/pr116338-1.c
@@ -0,0 +1,43 @@
+/* { dg-do run } */
+/* { dg-require-effective-target vect_int } */
+
+#include "tree-vect.h"
+
+int a[64], b[64];
+
+void __attribute__((noipa))
+foo (void)
+{
+ int x = b[63];
+ int y = b[62];
+ for (int i = 0; i < 64; ++i)
+ {
+ a[i] = b[i] + x + y;
+ y = x;
+ x = b[i];
+ }
+}
+
+int
+main ()
+{
+ check_vect ();
+ for (int i = 0; i < 64; ++i)
+ {
+ b[i] = i * 7 + 3;
+ __asm__ volatile ("" ::: "memory");
+ }
+ foo ();
+ int x = b[63], y = b[62];
+#pragma GCC novector
+ for (int i = 0; i < 64; ++i)
+ {
+ if (a[i] != b[i] + x + y)
+ __builtin_abort ();
+ y = x;
+ x = b[i];
+ }
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "vectorized 1 loops" "vect" { target vect_perm
} } } */
diff --git a/gcc/testsuite/gcc.dg/vect/pr116338-2.c
b/gcc/testsuite/gcc.dg/vect/pr116338-2.c
new file mode 100644
index 000000000..889eaab08
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/pr116338-2.c
@@ -0,0 +1,43 @@
+/* { dg-do run } */
+/* { dg-require-effective-target vect_float } */
+
+#include "tree-vect.h"
+
+float a[64], b[64];
+
+void __attribute__((noipa))
+foo (void)
+{
+ float x = b[63];
+ float y = b[62];
+ for (int i = 0; i < 64; ++i)
+ {
+ a[i] = (b[i] + x + y) * 0.5f;
+ y = x;
+ x = b[i];
+ }
+}
+
+int
+main ()
+{
+ check_vect ();
+ for (int i = 0; i < 64; ++i)
+ {
+ b[i] = i * 7 + 3;
+ __asm__ volatile ("" ::: "memory");
+ }
+ foo ();
+ float x = b[63], y = b[62];
+#pragma GCC novector
+ for (int i = 0; i < 64; ++i)
+ {
+ if (a[i] != (b[i] + x + y) * 0.5f)
+ __builtin_abort ();
+ y = x;
+ x = b[i];
+ }
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "vectorized 1 loops" "vect" { target vect_perm
} } } */
diff --git a/gcc/testsuite/gcc.dg/vect/pr116338-3.c
b/gcc/testsuite/gcc.dg/vect/pr116338-3.c
new file mode 100644
index 000000000..2de4e1764
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/pr116338-3.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+
+/* PR tree-optimization/116338. A cycle of header PHIs, here two values
+ swapping every iteration, is not a chain of first-order recurrences
+ and must not be treated as one. Verify we neither vectorize this
+ nor ICE on it. */
+
+void
+swap (int * __restrict__ a, int * __restrict__ b, int n)
+{
+ int x = b[n-1];
+ int y = b[n-2];
+ for (int i = 0; i < n; ++i)
+ {
+ a[i] = b[i] + 2 * x - y;
+ int t = x;
+ x = y;
+ y = t;
+ }
+}
+
+/* { dg-final { scan-tree-dump-not "vectorized 1 loops" "vect" } } */
diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
index a9335ed68..7f1c05ad7 100644
--- a/gcc/tree-vect-loop.cc
+++ b/gcc/tree-vect-loop.cc
@@ -289,6 +289,67 @@ vect_is_nonlinear_iv_evolution (class loop* loop,
stmt_vec_info stmt_info,
return true;
}
+/* PHI is a loop header PHI of LOOP, the loop vectorized as LOOP_VINFO,
+ whose latch definition is the header PHI CHAIN. Return true if
+ CHAIN starts an acyclic chain of header
+ PHIs, each being the latch definition of the previous one, terminating
+ in a non-PHI definition inside LOOP. Such a chain represents a series
+ of recurrences each delayed by one more iteration and can be
+ vectorized as chained first-order recurrences. A cyclic chain, for
+ example two PHIs swapping values, cannot, and neither can a chain
+ that involves another kind of scalar cycle such as an induction
+ or reduction. */
+
+static bool
+vect_recurrence_chain_p (loop_vec_info loop_vinfo, class loop *loop,
+ gphi *phi, gphi *chain)
+{
+ /* Bound the walk by the number of PHIs in the header; a longer walk
+ means we revisited a PHI, i.e. the chain is cyclic. */
+ unsigned limit = 0;
+ for (gphi_iterator gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ limit++;
+ edge latch = loop_latch_edge (loop);
+ auto_vec<gphi *, 4> members;
+ members.safe_push (phi);
+ gimple *def_stmt = chain;
+ while (gphi *p = dyn_cast <gphi *> (def_stmt))
+ {
+ if (gimple_bb (p) != loop->header
+ || p == phi
+ || limit-- == 0)
+ return false;
+ /* A PHI already classified as another kind of scalar cycle,
+ for example the induction PHI of the loop in PR 107302,
+ cannot be a member of a recurrence chain. */
+ stmt_vec_info p_info = loop_vinfo->lookup_stmt (p);
+ if (!p_info
+ || (STMT_VINFO_DEF_TYPE (p_info) != vect_unknown_def_type
+ && STMT_VINFO_DEF_TYPE (p_info)
+ != vect_first_order_recurrence))
+ return false;
+ members.safe_push (p);
+ tree ldef = PHI_ARG_DEF_FROM_EDGE (p, latch);
+ if (TREE_CODE (ldef) != SSA_NAME
+ || SSA_NAME_IS_DEFAULT_DEF (ldef)
+ || !flow_bb_inside_loop_p (loop,
+ gimple_bb (SSA_NAME_DEF_STMT (ldef))))
+ return false;
+ def_stmt = SSA_NAME_DEF_STMT (ldef);
+ }
+ /* Also reject a value cycle: if the terminating definition uses
+ any PHI of the chain the values feed back into themselves, as
+ in a reduction, rather than forming delayed recurrences. */
+ ssa_op_iter iter;
+ use_operand_p use_p;
+ FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_USE)
+ for (gphi *m : members)
+ if (USE_FROM_PTR (use_p) == gimple_phi_result (m))
+ return false;
+ return true;
+}
+
/* Returns true if Phi is a first-order recurrence. A first-order
recurrence is a non-reduction recurrence relation in which the value of
the recurrence in the current loop iteration equals a value defined in
@@ -307,7 +368,12 @@ vect_phi_first_order_recurrence_p (loop_vec_info
loop_vinfo, class loop *loop,
tree ldef = PHI_ARG_DEF_FROM_EDGE (phi, latch);
if (TREE_CODE (ldef) != SSA_NAME
|| SSA_NAME_IS_DEFAULT_DEF (ldef)
- || is_a <gphi *> (SSA_NAME_DEF_STMT (ldef))
+ /* The latch definition may itself be a header PHI when it forms
+ an acyclic chain of recurrences (PR tree-optimization/116338). */
+ || (is_a <gphi *> (SSA_NAME_DEF_STMT (ldef))
+ && !vect_recurrence_chain_p (loop_vinfo, loop, phi,
+ as_a <gphi *>
+ (SSA_NAME_DEF_STMT (ldef))))
|| !flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (ldef))))
return false;
@@ -318,11 +384,25 @@ vect_phi_first_order_recurrence_p (loop_vec_info
loop_vinfo, class loop *loop,
imm_use_iterator imm_iter;
use_operand_p use_p;
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
- if (!is_gimple_debug (USE_STMT (use_p))
- && (SSA_NAME_DEF_STMT (ldef) == USE_STMT (use_p)
- || !vect_stmt_dominates_stmt_p (SSA_NAME_DEF_STMT (ldef),
- USE_STMT (use_p))))
- return false;
+ {
+ gimple *use_stmt = USE_STMT (use_p);
+ if (is_gimple_debug (use_stmt))
+ continue;
+ /* A use as the latch argument of another header PHI is realized
+ by vectorizing that PHI as a chained first-order recurrence.
+ If that PHI does not qualify the loop fails to vectorize as a
+ whole, so this exemption cannot produce wrong code. */
+ if (gphi *q = dyn_cast <gphi *> (use_stmt))
+ {
+ if (gimple_bb (q) == loop->header
+ && PHI_ARG_DEF_FROM_EDGE (q, latch) == def)
+ continue;
+ }
+ if (SSA_NAME_DEF_STMT (ldef) == use_stmt
+ || !vect_stmt_dominates_stmt_p (SSA_NAME_DEF_STMT (ldef),
+ use_stmt))
+ return false;
+ }
/* First-order recurrence autovectorization needs shuffle vector. */
tree scalar_type = TREE_TYPE (def);
@@ -8852,14 +8932,31 @@ vectorizable_recurr (loop_vec_info loop_vinfo,
stmt_vec_info stmt_info,
vectorized the latch definition. */
edge le = loop_latch_edge (LOOP_VINFO_LOOP (loop_vinfo));
gimple *latch_def = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, le));
- gimple_stmt_iterator gsi2 = gsi_for_stmt (latch_def);
- do
- {
+ gimple_stmt_iterator gsi2;
+ if (is_a <gphi *> (latch_def))
+ {
+ /* For a chained recurrence the latch value is itself a recurrence
+ PHI. We cannot insert after a PHI; insert after the last
+ vectorized def of the latch child, its permute, which has been
+ emitted already since the SCC scheduler transforms children
+ first and an acyclic chain is a DAG. */
+ slp_tree latch_child = SLP_TREE_CHILDREN (slp_node)[le->dest_idx];
+ gcc_assert (SLP_TREE_VEC_DEFS (latch_child).length () == ncopies);
+ tree last = SLP_TREE_VEC_DEFS (latch_child)[ncopies - 1];
+ gsi2 = gsi_for_stmt (SSA_NAME_DEF_STMT (last));
gsi_next (&gsi2);
}
- /* Skip inserted vectorized stmts for the latch definition. We have to
- insert after those. */
- while (gsi_stmt (gsi2) && gimple_uid (gsi_stmt (gsi2)) == 0);
+ else
+ {
+ gsi2 = gsi_for_stmt (latch_def);
+ do
+ {
+ gsi_next (&gsi2);
+ }
+ /* Skip inserted vectorized stmts for the latch definition. We
+ have to insert after those. */
+ while (gsi_stmt (gsi2) && gimple_uid (gsi_stmt (gsi2)) == 0);
+ }
for (unsigned i = 0; i < ncopies; ++i)
{
--
2.53.0
