On Sun, Jul 26, 2026 at 9:23 PM T G <[email protected]> wrote:
>
> Apologies, I sent this patch without the intended cover note. Adding
> the context here.
>
> Generative AI was used in preparing this patch. I found the missed
> optimization through a differential TSVC sweep against clang, diagnosed
> the recognition and transform failures, and ran all of the verification
> below myself.
Can you clarify whether the AI produced the patch?
> What the patch does: it teaches the vectorizer to handle chained
> first-order recurrences, the shape in TSVC s255:
>
> for (i) { a[i] = (b[i] + x + y) * c; y = x; x = b[i]; }
>
> Here x carries a value from one iteration back and y from two, so y's
> latch definition is another header PHI.
> vect_phi_first_order_recurrence_p rejects that outright, which is why
> GCC leaves s255 scalar while clang vectorizes it.
>
> The patch adds vect_recurrence_chain_p, which accepts an acyclic chain
> of header PHIs terminating in a non-PHI definition inside the loop, and
> rejects cycles (two PHIs swapping values), chains containing a PHI
> already classified as another kind of scalar cycle (the induction PHI
> in the loop of PR 107302), and chains whose terminating definition
> feeds back into a chain member. On the transform side, the vectorized
> latch value of a chained recurrence is the permute emitted for the
> latch child, so the permute is inserted after that child's last
> vectorized def rather than after the scalar latch definition, which for
> a chain is a PHI we cannot insert after.
>
> Testing: bootstrapped and regtested on x86_64-linux-gnu at the
> 2026-06-10 trunk revision with no regressions;
> gcc.dg/vect/tsvc/vect-tsvc-s255.c and vect-tsvc-s292.c newly vectorize.
> The patch rebases cleanly onto current trunk; on the rebased tree I
> re-verified on riscv64 with a cross-compiler under QEMU, where the s255
> chain, a depth-three chain and a plain single recurrence all produce
> output bit-identical to the scalar reference with slide counts scaling
> with chain depth, the swap case compiles to scalar code, and PR 107302
> no longer ICEs. I have not re-run a full bootstrap and regtest on
> current trunk.
>
> Feedback on the approach is welcome, in particular on whether the chain
> walk belongs in vect_phi_first_order_recurrence_p or somewhere else.
I think it belongs there. But given that PHI nodes are un-ordered I wonder
if you can rely on vect_first_order_recurrence - that's why you also allow
unknown_def_type, right?
You'll analyze each PHI entry to the recurrence chain, so quite some redundant
work. I wonder if we can classify the whole chain as
vect_first_order_recurrence
and restrict to analyzing PHIs with the latch def not being a PHI via
vect_phi_first_order_recurrence_p and walk "backwards" from there?
Thanks,
Richard.
>
> 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
> >
