The Linaro precommit CI flagged 4 "regressions" on aarch64, but all four
are XPASSes on the two tests this patch is meant to fix:
XPASS: gcc.dg/vect/tsvc/vect-tsvc-s255.c scan-tree-dump vect "vectorized
1 loops"
XPASS: gcc.dg/vect/tsvc/vect-tsvc-s292.c scan-tree-dump vect "vectorized
1 loops"
(and the same two under -flto -ffat-lto-objects)
Both currently carry an unconditional marker:
/* { dg-final { scan-tree-dump "vectorized 1 loops" "vect" { xfail *-*-*
} } } */
so the XPASSes are the intended effect rather than a regression, and it
is useful confirmation the patch works on aarch64 as well as x86_64 and
riscv64.
I would rather narrow the marker than remove it, since both files are
gated only on vect_float and the transform needs a permute:
/* { dg-final { scan-tree-dump "vectorized 1 loops" "vect" { xfail { !
vect_perm } } } } */
That matches the { target vect_perm } guard on the new testcases in this
patch. I have not run the testsuite on a target without permute support
to confirm that is the right selector for both, so I am happy to be
corrected.
Shall I fold this into a v2, or would you prefer it as a separate
testsuite patch?
On Mon, Jul 27, 2026 at 12:47 AM Tanmay Gulhane <[email protected]>
wrote:
> 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
>
>
