> -----Original Message-----
> From: Richard Biener <[email protected]>
> Sent: Tuesday, September 2, 2025 1:30 PM
> To: Tamar Christina <[email protected]>
> Cc: [email protected]; nd <[email protected]>
> Subject: Re: [PATCH v2 3/3]middle-end: Use addhn for compression instead of
> inclusive OR when reducing comparison values
>
> On Tue, 2 Sep 2025, Tamar Christina wrote:
>
> > Given a sequence such as
> >
> > int foo ()
> > {
> > #pragma GCC unroll 4
> > for (int i = 0; i < N; i++)
> > if (a[i] == 124)
> > return 1;
> >
> > return 0;
> > }
> >
> > where a[i] is long long, we will unroll the loop and use an OR reduction for
> > early break on Adv. SIMD. Afterwards the sequence is followed by a
> > compression
> > sequence to compress the 128-bit vectors into 64-bits for use by the branch.
> >
> > However if we have support for add halving and narrowing then we can instead
> of
> > using an OR, use an ADDHN which will do the combining and narrowing.
> >
> > Note that for now I only do the last OR, however if we have more than one
> > level
> > of unrolling we could technically chain them. I will revisit this in
> > another
> > up coming early break series, however an unroll of 2 is fairly common.
> >
> > Bootstrapped Regtested on aarch64-none-linux-gnu,
> > arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
> > -m32, -m64 and no issues and about a 10% improvements
> > in this sequence for Adv. SIMD.
> >
> > Ok for master?
>
> Hmm, so you are replacing the last bitwise OR with a
> addhn which produces a "smaller" vector. So like
>
> V4SI tem = V4SI | V4SI;
> if (tem != 0)
>
> ->
>
> V4HI tem = .VEC_ADD_HALVING_NARROW (V4SI, V4SI);
> if (tem != 0)
>
> whatever 'halving' now stands for (isn't that .VEC_ADD_HIGH_NARROW?)
>
Yeah, but it retrieved the high half, so open to suggestion but I think any name
would be confusion..
> I can't see how that's in any way faster? (the aarch64 testcases
> unfortunately stop matching after the addhn)
>
Which is intentional.
The original code with the ORR is
ldp q31, q30, [x0]
cmeq v31.2d, v31.2d, v29.2d
cmeq v30.2d, v30.2d, v29.2d
orr v31.16b, v31.16b, v30.16b
umaxp v31.4s, v31.4s, v31.4s
fmov x3, d31
because the result of the ORR is a 128-bit vector it needs to be compressed
into 64 bits to be transferred to GPR so the != 0 can be performed.
ADDHN does the combination and compression in one step. i.e.
Orr + umaxp -> addhn.
> Also the inputs are vector bools(?), so you should V_C_E them to
> data vectors before "adding" them. And check that they have
> a vector mode that's not VnBImode for which I guess the addhn
> semantics wouldn't be necessarily good enough.
ADDHN can't be used for SVE (and so the optab isn't implemented on SVE modes)
because SVE's version is even/odd. But for SVE we also don't want this codegen
because SVE can branch on the result of the data compare. So we don't want the
intermediate forced compression. So this is strictly for Adv. SIMD.
>
> How would you scale this to workset.length () > 2? I suppose
> for an even number reduce to the half element size first, for
> odd you could make it even by first reducing two vectors with IOR?
> If small, either check for another narrowing addhn operation or
> continue with IOR?
>
Because the instruction can't work on bytes, having > 2 just uses ORR
Until we have == 2 and then ADDHN. You could use ADDHN for the
Intermediate steps, but ADDHN hits a limit when you reach bytes.
However one big benefit of using the ADDHN even in > 2 cases is that
it prevents reassoc from breaking the ORR order we created in the
vectorizer as it can't reassociate them back to a linear form as it does
today.
And the reason we can't match the ADDHN in the backend is that in
order for us to know that the inputs are Boolean vectors we also have
to match the compares. This means that the chain is longer than what
combine tries since it has to match everything including the if_then_else
and the reduction to set the CC.
> That said, I still fail to see how addhn reduces the critical
> latency?
>
Because it replaces 2 instruction on the critical reduction path with 1
that is half the latency of the two it replaced. See example above.
Thanks,
Tamar
>
> > Thanks,
> > Tamar
> >
> > gcc/ChangeLog:
> >
> > * internal-fn.def (VEC_ADD_HALVING_NARROW): New.
> > * doc/generic.texi: Document it.
> > * optabs.def (vec_addh_narrow): New.
> > * doc/md.texi: Document it.
> > * tree-vect-stmts.cc (vectorizable_early_exit): Use addhn if supported.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.target/aarch64/vect-early-break-addhn_1.c: New test.
> > * gcc.target/aarch64/vect-early-break-addhn_2.c: New test.
> > * gcc.target/aarch64/vect-early-break-addhn_3.c: New test.
> > * gcc.target/aarch64/vect-early-break-addhn_4.c: New test.
> >
> > ---
> > diff --git a/gcc/doc/generic.texi b/gcc/doc/generic.texi
> > index
> d4ac580a7a8b9cd339d26cb97f7eb963f83746a4..ff16ff47bbf45e795df0d230e9
> a885d9d218d9af 100644
> > --- a/gcc/doc/generic.texi
> > +++ b/gcc/doc/generic.texi
> > @@ -1834,6 +1834,7 @@ a value from @code{enum annot_expr_kind}, the
> third is an @code{INTEGER_CST}.
> > @tindex IFN_VEC_WIDEN_MINUS_LO
> > @tindex IFN_VEC_WIDEN_MINUS_EVEN
> > @tindex IFN_VEC_WIDEN_MINUS_ODD
> > +@tindex IFN_VEC_ADD_HALVING_NARROW
> > @tindex VEC_UNPACK_HI_EXPR
> > @tindex VEC_UNPACK_LO_EXPR
> > @tindex VEC_UNPACK_FLOAT_HI_EXPR
> > @@ -1956,6 +1957,24 @@ vector of @code{N/2} subtractions. In the case of
> > vector are subtracted from the odd @code{N/2} of the first to produce the
> > vector of @code{N/2} subtractions.
> >
> > +@item IFN_VEC_ADD_HALVING_NARROW
> > +This internal function performs an addition of two input vectors,
> > +then extracts the most significant half of each result element and
> > +narrows it back to the original element width.
> > +
> > +Concretely, it computes:
> > +@code{(bits(a)/2)((a + b) >> bits(a))}
> > +
> > +where @code{bits(a)} is the width in bits of each input element.
> > +
> > +Its operands are vectors containing the same number of elements (@code{N})
> > +of the same integral type. The result is a vector of length @code{N}, with
> > +elements of an integral type whose size is half that of the input element
> > +type.
> > +
> > +This operation currently only used for early break result compression when
> > the
> > +result of a vector boolean can be represented as 0 or -1.
> > +
> > @item VEC_UNPACK_HI_EXPR
> > @itemx VEC_UNPACK_LO_EXPR
> > These nodes represent unpacking of the high and low parts of the input
> > vector,
> > diff --git a/gcc/doc/md.texi b/gcc/doc/md.texi
> > index
> aba93f606eca59d31c103a05b2567fd4f3be55f3..ec0193e4eee079e00168bbaf9
> b28ba8d52e5d464 100644
> > --- a/gcc/doc/md.texi
> > +++ b/gcc/doc/md.texi
> > @@ -6087,6 +6087,25 @@ vectors with N signed/unsigned elements of size
> S@. Find the absolute
> > difference between operands 1 and 2 and widen the resulting elements.
> > Put the N/2 results of size 2*S in the output vector (operand 0).
> >
> > +@cindex @code{vec_addh_narrow@var{m}} instruction pattern
> > +@item @samp{vec_addh_narrow@var{m}}
> > +Signed or unsigned addition of two input vectors, then extracts the
> > +most significant half of each result element and narrows it back to the
> > +original element width.
> > +
> > +Concretely, it computes:
> > +@code{(bits(a)/2)((a + b) >> bits(a))}
> > +
> > +where @code{bits(a)} is the width in bits of each input element.
> > +
> > +Its operands (@code{1} and @code{2}) are vectors containing the same
> number
> > +of signed or unsigned integral elements (@code{N}) of size @code{S}. The
> > +result (operand @code{0}) is a vector of length @code{N}, with elements of
> > +an integral type whose size is half that of @code{S}.
> > +
> > +This operation currently only used for early break result compression when
> > the
> > +result of a vector boolean can be represented as 0 or -1.
> > +
> > @cindex @code{vec_addsub@var{m}3} instruction pattern
> > @item @samp{vec_addsub@var{m}3}
> > Alternating subtract, add with even lanes doing subtract and odd
> > diff --git a/gcc/internal-fn.def b/gcc/internal-fn.def
> > index
> d2480a1bf7927476215bc7bb99c0b74197d2b7e9..cb18058d9f48cc0dff96ed4b
> 31d0abc9adb67867 100644
> > --- a/gcc/internal-fn.def
> > +++ b/gcc/internal-fn.def
> > @@ -422,6 +422,8 @@ DEF_INTERNAL_OPTAB_FN (COMPLEX_ADD_ROT270,
> ECF_CONST, cadd270, binary)
> > DEF_INTERNAL_OPTAB_FN (COMPLEX_MUL, ECF_CONST, cmul, binary)
> > DEF_INTERNAL_OPTAB_FN (COMPLEX_MUL_CONJ, ECF_CONST, cmul_conj,
> binary)
> > DEF_INTERNAL_OPTAB_FN (VEC_ADDSUB, ECF_CONST, vec_addsub, binary)
> > +DEF_INTERNAL_OPTAB_FN (VEC_ADD_HALVING_NARROW, ECF_CONST |
> ECF_NOTHROW,
> > + vec_addh_narrow, binary)
> > DEF_INTERNAL_WIDENING_OPTAB_FN (VEC_WIDEN_PLUS,
> > ECF_CONST | ECF_NOTHROW,
> > first,
> > diff --git a/gcc/optabs.def b/gcc/optabs.def
> > index
> 87a8b85da1592646d0a3447572e842ceb158cd97..b2bedc3692f914c2b80d797
> 2db81b542b32c9eb8 100644
> > --- a/gcc/optabs.def
> > +++ b/gcc/optabs.def
> > @@ -492,6 +492,7 @@ OPTAB_D (vec_widen_uabd_hi_optab,
> "vec_widen_uabd_hi_$a")
> > OPTAB_D (vec_widen_uabd_lo_optab, "vec_widen_uabd_lo_$a")
> > OPTAB_D (vec_widen_uabd_odd_optab, "vec_widen_uabd_odd_$a")
> > OPTAB_D (vec_widen_uabd_even_optab, "vec_widen_uabd_even_$a")
> > +OPTAB_D (vec_addh_narrow_optab, "vec_addh_narrow$a")
> > OPTAB_D (vec_addsub_optab, "vec_addsub$a3")
> > OPTAB_D (vec_fmaddsub_optab, "vec_fmaddsub$a4")
> > OPTAB_D (vec_fmsubadd_optab, "vec_fmsubadd$a4")
> > diff --git a/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_1.c
> b/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_1.c
> > new file mode 100644
> > index
> 0000000000000000000000000000000000000000..4ecb187513e525e0cd9b8
> b063e418a75a23c525d
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_1.c
> > @@ -0,0 +1,33 @@
> > +/* { dg-do compile } */
> > +/* { dg-additional-options "-O3 -fdump-tree-vect-details -std=c99" } */
> > +/* { dg-final { check-function-bodies "**" "" "" } } */
> > +
> > +#define TYPE int
> > +#define N 800
> > +
> > +#pragma GCC target "+nosve"
> > +
> > +TYPE a[N];
> > +
> > +/*
> > +** foo:
> > +** ...
> > +** ldp q[0-9]+, q[0-9]+, \[x[0-9]+\], 32
> > +** cmeq v[0-9]+.4s, v[0-9]+.4s, v[0-9]+.4s
> > +** cmeq v[0-9]+.4s, v[0-9]+.4s, v[0-9]+.4s
> > +** addhn v[0-9]+.4h, v[0-9]+.4s, v[0-9]+.4s
> > +** fmov x[0-9]+, d[0-9]+
> > +** ...
> > +*/
> > +
> > +int foo ()
> > +{
> > +#pragma GCC unroll 8
> > + for (int i = 0; i < N; i++)
> > + if (a[i] == 124)
> > + return 1;
> > +
> > + return 0;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump "VEC_ADD_HALFING_NARROW" "vect" } } */
> > diff --git a/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_2.c
> b/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_2.c
> > new file mode 100644
> > index
> 0000000000000000000000000000000000000000..d67d0d13d1733935aaf80
> 5e59188eb8155cb5f06
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_2.c
> > @@ -0,0 +1,33 @@
> > +/* { dg-do compile } */
> > +/* { dg-additional-options "-O3 -fdump-tree-vect-details -std=c99" } */
> > +/* { dg-final { check-function-bodies "**" "" "" } } */
> > +
> > +#define TYPE long long
> > +#define N 800
> > +
> > +#pragma GCC target "+nosve"
> > +
> > +TYPE a[N];
> > +
> > +/*
> > +** foo:
> > +** ...
> > +** ldp q[0-9]+, q[0-9]+, \[x[0-9]+\], 32
> > +** cmeq v[0-9]+.2d, v[0-9]+.2d, v[0-9]+.2d
> > +** cmeq v[0-9]+.2d, v[0-9]+.2d, v[0-9]+.2d
> > +** addhn v[0-9]+.2s, v[0-9]+.2d, v[0-9]+.2d
> > +** fmov x[0-9]+, d[0-9]+
> > +** ...
> > +*/
> > +
> > +int foo ()
> > +{
> > +#pragma GCC unroll 4
> > + for (int i = 0; i < N; i++)
> > + if (a[i] == 124)
> > + return 1;
> > +
> > + return 0;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump "VEC_ADD_HALFING_NARROW" "vect" } } */
> > diff --git a/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_3.c
> b/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_3.c
> > new file mode 100644
> > index
> 0000000000000000000000000000000000000000..57dbc44ae0cdcbcdccd3d8
> dbe98c79713eaf5607
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_3.c
> > @@ -0,0 +1,33 @@
> > +/* { dg-do compile } */
> > +/* { dg-additional-options "-O3 -fdump-tree-vect-details -std=c99" } */
> > +/* { dg-final { check-function-bodies "**" "" "" } } */
> > +
> > +#define TYPE short
> > +#define N 800
> > +
> > +#pragma GCC target "+nosve"
> > +
> > +TYPE a[N];
> > +
> > +/*
> > +** foo:
> > +** ...
> > +** ldp q[0-9]+, q[0-9]+, \[x[0-9]+\], 32
> > +** cmeq v[0-9]+.8h, v[0-9]+.8h, v[0-9]+.8h
> > +** cmeq v[0-9]+.8h, v[0-9]+.8h, v[0-9]+.8h
> > +** addhn v[0-9]+.8b, v[0-9]+.8h, v[0-9]+.8h
> > +** fmov x[0-9]+, d[0-9]+
> > +** ...
> > +*/
> > +
> > +int foo ()
> > +{
> > +#pragma GCC unroll 16
> > + for (int i = 0; i < N; i++)
> > + if (a[i] == 124)
> > + return 1;
> > +
> > + return 0;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump "VEC_ADD_HALFING_NARROW" "vect" } } */
> > diff --git a/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_4.c
> b/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_4.c
> > new file mode 100644
> > index
> 0000000000000000000000000000000000000000..8ad42b22024479283d681
> 4d815ef1dce411d1c72
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.target/aarch64/vect-early-break-addhn_4.c
> > @@ -0,0 +1,21 @@
> > +/* { dg-do compile } */
> > +/* { dg-additional-options "-O3 -fdump-tree-vect-details -std=c99" } */
> > +
> > +#define TYPE char
> > +#define N 800
> > +
> > +#pragma GCC target "+nosve"
> > +
> > +TYPE a[N];
> > +
> > +int foo ()
> > +{
> > +#pragma GCC unroll 32
> > + for (int i = 0; i < N; i++)
> > + if (a[i] == 124)
> > + return 1;
> > +
> > + return 0;
> > +}
> > +
> > +/* { dg-final { scan-tree-dump-not "VEC_ADD_HALFING_NARROW" "vect" } } */
> > diff --git a/gcc/tree-vect-stmts.cc b/gcc/tree-vect-stmts.cc
> > index
> 1545fab364792f75bcc786ba1311b8bdc82edd70..179ce5e0a66b6f88976ffb54
> 4c6874d7bec999a8 100644
> > --- a/gcc/tree-vect-stmts.cc
> > +++ b/gcc/tree-vect-stmts.cc
> > @@ -12328,7 +12328,7 @@ vectorizable_early_exit (loop_vec_info loop_vinfo,
> stmt_vec_info stmt_info,
> > gimple *orig_stmt = STMT_VINFO_STMT (vect_orig_stmt (stmt_info));
> > gcond *cond_stmt = as_a <gcond *>(orig_stmt);
> >
> > - tree cst = build_zero_cst (vectype);
> > + tree vectype_out = vectype;
> > auto bb = gimple_bb (cond_stmt);
> > edge exit_true_edge = EDGE_SUCC (bb, 0);
> > if (exit_true_edge->flags & EDGE_FALSE_VALUE)
> > @@ -12452,12 +12452,40 @@ vectorizable_early_exit (loop_vec_info
> loop_vinfo, stmt_vec_info stmt_info,
> > else
> > workset.splice (stmts);
> >
> > + /* See if we support ADDHN and use that for the reduction. */
> > + internal_fn ifn = IFN_VEC_ADD_HALVING_NARROW;
> > + bool addhn_supported_p
> > + = direct_internal_fn_supported_p (ifn, vectype, OPTIMIZE_FOR_SPEED);
> > + tree narrow_type = NULL_TREE;
> > + if (addhn_supported_p)
> > + {
> > + /* Calculate the narrowing type for the result. */
> > + auto halfprec = TYPE_PRECISION (TREE_TYPE (vectype)) / 2;
> > + auto unsignedp = TYPE_UNSIGNED (TREE_TYPE (vectype));
> > + tree itype = build_nonstandard_integer_type (halfprec, unsignedp);
> > + poly_uint64 nunits = TYPE_VECTOR_SUBPARTS (vectype);
> > + tree tmp_type = build_vector_type (itype, nunits);
> > + narrow_type = truth_type_for (tmp_type);
> > + }
> > +
> > while (workset.length () > 1)
> > {
> > - new_temp = make_temp_ssa_name (vectype, NULL, "vexit_reduc");
> > tree arg0 = workset.pop ();
> > tree arg1 = workset.pop ();
> > - new_stmt = gimple_build_assign (new_temp, BIT_IOR_EXPR, arg0, arg1);
> > + if (addhn_supported_p && workset.length () == 0)
> > + {
> > + new_stmt = gimple_build_call_internal (ifn, 2, arg0, arg1);
> > + vectype_out = narrow_type;
> > + new_temp = make_temp_ssa_name (vectype_out, NULL,
> "vexit_reduc");
> > + gimple_call_set_lhs (as_a <gcall *> (new_stmt), new_temp);
> > + gimple_call_set_nothrow (as_a <gcall *> (new_stmt), true);
> > + }
> > + else
> > + {
> > + new_temp = make_temp_ssa_name (vectype_out, NULL,
> "vexit_reduc");
> > + new_stmt
> > + = gimple_build_assign (new_temp, BIT_IOR_EXPR, arg0, arg1);
> > + }
> > vect_finish_stmt_generation (loop_vinfo, stmt_info, new_stmt,
> > &cond_gsi);
> > workset.quick_insert (0, new_temp);
> > @@ -12480,6 +12508,7 @@ vectorizable_early_exit (loop_vec_info loop_vinfo,
> stmt_vec_info stmt_info,
> >
> > gcc_assert (new_temp);
> >
> > + tree cst = build_zero_cst (vectype_out);
> > gimple_cond_set_condition (cond_stmt, NE_EXPR, new_temp, cst);
> > update_stmt (orig_stmt);
> >
> >
> >
> >
>
> --
> Richard Biener <[email protected]>
> SUSE Software Solutions Germany GmbH,
> Frankenstrasse 146, 90461 Nuernberg, Germany;
> GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
