On Sun, 4 Oct 2026, Hongtao Liu wrote:
> On Wed Sep 23, 2026 at 5:56 AM PDT, Richard Biener wrote:
> > This implements umul<mode>3_highpart for V2DI, V4DI and V8DI using
> > SSE2 instructions, specifically exercising pmuludq. I wasn't able
> > to produce a scalar vectorizer pattern open-coding a sequence that
> > would vectorize to this, specifically with the same VF and the
> > setup of the input to the pmuludq, so I opted for implementing
> > this in the target.
> >
> > I added a testcase for a V2DI loop that shouldn't be vectorized
> > and one for a V4DI loop that should.
> >
> > This speeds up 750.sealcrypto_r by ~20% on Zen4 and should recover what
> > was lost with r17-3437.
> >
> > Bootstrapped and tested on x86_64-unknown-linux-gnu.
> >
> > OK for trunk?
> >
> > Thanks,
> > Richard.
> >
> > PR tree-optimization/127452
> > * config/i386/i386-protos.h (ix86_expand_umulvndi_highpart): Declare.
> > * config/i386/i386-expand.cc (ix86_expand_umulvndi_highpart):
> > New function.
> > * config/i386/sse.md (umul<mode>3_highpart): Add for VI8_AVX2_AVX512F.
> > * config/i386/i386.cc (ix86_vector_costs::add_stmt_cost): Cost
> > IFN_MULH as we implement it.
> >
> > * gcc.target/i386/vect-umulv2di_high.c: New testcase.
> > * gcc.target/i386/vect-umulv4di_high.c: Likewise.
> > ---
> > gcc/config/i386/i386-expand.cc | 74 +++++++++++++++++++
> > gcc/config/i386/i386-protos.h | 1 +
> > gcc/config/i386/i386.cc | 21 ++++++
> > gcc/config/i386/sse.md | 11 +++
> > .../gcc.target/i386/vect-umulv2di_high.c | 14 ++++
> > .../gcc.target/i386/vect-umulv4di_high.c | 12 +++
> > 6 files changed, 133 insertions(+)
> > create mode 100644 gcc/testsuite/gcc.target/i386/vect-umulv2di_high.c
> > create mode 100644 gcc/testsuite/gcc.target/i386/vect-umulv4di_high.c
> >
> > diff --git a/gcc/config/i386/i386-expand.cc b/gcc/config/i386/i386-expand.cc
> > index 9e112d01734..f81867e30d0 100644
> > --- a/gcc/config/i386/i386-expand.cc
> > +++ b/gcc/config/i386/i386-expand.cc
> > @@ -28467,6 +28467,80 @@ ix86_expand_sse2_mulvxdi3 (rtx op0, rtx op1, rtx
> > op2)
> > gen_rtx_MULT (mode, op1, op2));
> > }
> >
> > +void
> > +ix86_expand_umulvndi_highpart (rtx op0, rtx op1, rtx op2)
> > +{
> > + /* The following sequence can be used with SSE2. */
> > + machine_mode mode = GET_MODE (op0);
> > + rtx (*umul) (rtx, rtx, rtx);
> > + machine_mode nmode;
> > + if (mode == V2DImode)
> > + {
> > + umul = gen_vec_widen_umult_even_v4si;
> > + nmode = V4SImode;
> > + }
> > + else if (mode == V4DImode)
> > + {
> > + umul = gen_vec_widen_umult_even_v8si;
> > + nmode = V8SImode;
> > + }
> > + else if (mode == V8DImode)
> > + {
> > + umul = gen_vec_widen_umult_even_v16si;
> > + nmode = V16SImode;
> > + }
> > + else
> > + gcc_unreachable ();
> > +
> > + rtx t32 = GEN_INT (32);
> > +
> > + /* Shift input vectors right 32 bits so we can get high parts of
> > operands. */
> > + rtx op1_hi = expand_binop (mode, lshr_optab, op1, t32, NULL, 1,
> > OPTAB_DIRECT);
> > + rtx op2_hi = expand_binop (mode, lshr_optab, op2, t32, NULL, 1,
> > OPTAB_DIRECT);
> > +
> > + /* Multiply low parts. */
> > + rtx p0 = gen_reg_rtx (mode);
> > + emit_insn (umul (p0, gen_lowpart (nmode, op1), gen_lowpart (nmode,
> > op2)));
> > +
> > + /* Multiply high parts by low parts. */
> > + rtx p1 = gen_reg_rtx (mode);
> > + emit_insn (umul (p1, gen_lowpart (nmode, op1_hi), gen_lowpart (nmode,
> > op2)));
> > + rtx p2 = gen_reg_rtx (mode);
> > + emit_insn (umul (p2, gen_lowpart (nmode, op1), gen_lowpart (nmode,
> > op2_hi)));
> > +
> > + /* Multiply high parts. */
> > + rtx p3 = gen_reg_rtx (mode);
> > + emit_insn (umul (p3, gen_lowpart (nmode, op1_hi),
> > + gen_lowpart (nmode, op2_hi)));
> > +
> > + /* Extract high 32 bits of products. */
> > + rtx p0_hi = expand_binop (mode, lshr_optab, p0, t32, NULL, 1,
> > OPTAB_DIRECT);
> > + rtx p1_hi = expand_binop (mode, lshr_optab, p1, t32, NULL, 1,
> > OPTAB_DIRECT);
> > + rtx p2_hi = expand_binop (mode, lshr_optab, p2, t32, NULL, 1,
> > OPTAB_DIRECT);
> > +
> > + /* Extract low 32 bits of products by masking with 0xffffffff. */
> > + rtx mask = gen_reg_rtx (mode);
> > + emit_insn (gen_rtx_SET (mask, CONSTM1_RTX (mode)));
> > + mask = expand_binop (mode, lshr_optab, mask, t32, NULL, 1, OPTAB_DIRECT);
> > +
> > + rtx p1_lo = expand_binop (mode, and_optab, p1, mask, NULL, 1,
> > OPTAB_DIRECT);
> > + rtx p2_lo = expand_binop (mode, and_optab, p2, mask, NULL, 1,
> > OPTAB_DIRECT);
> > +
> > + /* s_lo = (p0 >> 32) + p1_lo + p2_lo */
> > + rtx s_lo = expand_binop (mode, add_optab, p0_hi, p1_lo, NULL, 1,
> > + OPTAB_DIRECT);
> > + s_lo = expand_binop (mode, add_optab, s_lo, p2_lo, NULL, 1,
> > OPTAB_DIRECT);
> > +
> > + /* s_lo_hi = s_lo >> 32 */
> > + rtx s_lo_hi = expand_binop (mode, lshr_optab, s_lo, t32, NULL, 1,
> > + OPTAB_DIRECT);
> > +
>
> Cross check with llvm's output + AI assistant, I think the codegen can be
> improved as below:
>
> With a = a1·2³² + a0, b = b1·2³² + b0, the partial products are p0 = a0·b0,
> p1 = a1·b0, p2 = a0·b1, p3 = a1·b1, and M =
> 0xffffffff.
>
> Patch: split both cross products first, then sum.
> s = (p0 >> 32) + (p1 & M) + (p2 & M)
> high = p3 + (p1 >> 32) + (p2 >> 32) + (s >> 32)
>
> Reassociated: fold the carry in one cross product at a time.
> t = (p0 >> 32) + p1
> u = (t & M) + p2
> high = p3 + (t >> 32) + (u >> 32)
>
> Neither t nor u can overflow, because (2³²−1) + (2³²−1)² = 2⁶⁴ − 2³² < 2⁶⁴.
>
> - Saves one shift, one AND and one add: 17 → 14 in-loop ops
True, the dependence length is worse though, resource allocation might
hide that. I will put it through benchmarking. The original patch
might also save latency by associating a bit.
> > + rtx high = expand_binop (mode, add_optab, p3, p1_hi, NULL, 1,
> > OPTAB_DIRECT);
> > + high = expand_binop (mode, add_optab, high, p2_hi, NULL, 1,
> > OPTAB_DIRECT);
> > + force_expand_binop (mode, add_optab, high, s_lo_hi, op0, 1,
> > OPTAB_DIRECT);
> > +}
> > +
> > /* Return 1 if control transfer instruction INSN
> > should be encoded with notrack prefix. */
> >
> > diff --git a/gcc/config/i386/i386-protos.h b/gcc/config/i386/i386-protos.h
> > index 4e56bf70c8d..23f82b6239e 100644
> > --- a/gcc/config/i386/i386-protos.h
> > +++ b/gcc/config/i386/i386-protos.h
> > @@ -310,6 +310,7 @@ extern void ix86_expand_mul_widen_evenodd (rtx, rtx,
> > rtx, bool, bool);
> > extern void ix86_expand_mul_widen_hilo (rtx, rtx, rtx, bool, bool);
> > extern void ix86_expand_sse2_mulv4si3 (rtx, rtx, rtx);
> > extern void ix86_expand_sse2_mulvxdi3 (rtx, rtx, rtx);
> > +extern void ix86_expand_umulvndi_highpart (rtx, rtx, rtx);
> > extern void ix86_expand_sse2_abs (rtx, rtx);
> > extern bool ix86_expand_vector_init_duplicate (bool, machine_mode, rtx,
> > rtx);
> > diff --git a/gcc/config/i386/i386.cc b/gcc/config/i386/i386.cc
> > index 705ebb6c014..766164c63a2 100644
> > --- a/gcc/config/i386/i386.cc
> > +++ b/gcc/config/i386/i386.cc
> > @@ -26916,6 +26916,27 @@ ix86_vector_costs::add_stmt_cost (int count,
> > vect_cost_for_stmt kind,
> > break;
> > }
> > }
> > + else if ((kind == vector_stmt || kind == scalar_stmt)
> > + && stmt_info
> > + && stmt_info->stmt
> > + && is_gimple_call (stmt_info->stmt))
> > + {
> > + auto ifn = (gimple_call_internal_p (stmt_info->stmt)
> > + ? gimple_call_internal_fn (stmt_info->stmt) : IFN_LAST);
> > + switch (ifn)
> > + {
> > + case IFN_MULH:
> > + if (kind == vector_stmt && GET_MODE_INNER (mode) == DImode)
> > + {
> > + /* ix86_expand_umulvndi_highpart */
> > + stmt_cost = ix86_multiplication_cost (ix86_cost, mode) * 4;
> > + /* 6 shifts by 32bit, 2 and, 5 adds. */
> > + stmt_cost += ix86_vec_cost (mode, ix86_cost->sse_op) * 13;
> > + }
> > + break;
> > + default:;
> Further down there's separate case CFN_MULH which unconditionally does
> stmt_cost = ix86_multiplication_cost (ix86_cost, mode);. And that will
> discard you cost setting?
Good catch - I merged both paths and moved the existing block in the above
place.
> Should we also handle MULT_HIGHPART_EXPR which is generated by
> vect_recog_divmod_pattern?
> .i.e
> #include <stdint.h>
>
> void
> udiv3 (uint64_t *__restrict r, uint64_t *a)
> {
> for (int i = 0; i < 128; ++i)
> r[i] = a[i] / 3;
> }
>
> the upper testcase will be vectorized w/o any profit due to wrong cost model
> after the patch.
Yes, I amended the existing MULT_HIGHPART_EXPR costing.
I'll send out a v2 after producing benchmark numbers.
Richard.
> > + }
> > + }
> >
> > /* Record number of load/store/gather/scatter in vectorized body. */
> > if (where == vect_body && !m_costing_for_scalar)
> > diff --git a/gcc/config/i386/sse.md b/gcc/config/i386/sse.md
> > index 0ce82789dc6..3abc91b2904 100644
> > --- a/gcc/config/i386/sse.md
> > +++ b/gcc/config/i386/sse.md
> > @@ -17404,6 +17404,17 @@
> > (set_attr "prefix" "orig,vex")
> > (set_attr "mode" "<sseinsnmode>")])
> >
> > +(define_expand "umul<mode>3_highpart"
> > + [(set (match_operand:VI8_AVX2_AVX512F 0 "register_operand")
> > + (umul_highpart:VI8_AVX2_AVX512F
> > + (match_operand:VI8_AVX2_AVX512F 1 "vector_operand")
> > + (match_operand:VI8_AVX2_AVX512F 2 "vector_operand")))]
> > + "TARGET_SSE2"
> > +{
> > + ix86_expand_umulvndi_highpart (operands[0], operands[1], operands[2]);
> > + DONE;
> > +})
> > +
> > (define_expand "vec_widen_umult_even_v16si<mask_name>"
> > [(set (match_operand:V8DI 0 "register_operand")
> > (mult:V8DI
> > diff --git a/gcc/testsuite/gcc.target/i386/vect-umulv2di_high.c
> > b/gcc/testsuite/gcc.target/i386/vect-umulv2di_high.c
> > new file mode 100644
> > index 00000000000..ca839983dc9
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.target/i386/vect-umulv2di_high.c
> > @@ -0,0 +1,14 @@
> > +/* { dg-do compile { target { ! ia32 } } } */
> > +/* { dg-options "-O2 -msse2 -mno-avx" } */
> > +
> > +#include <stdint.h>
> > +
> > +void mulu64_high (uint64_t * __restrict r, uint64_t *a, uint64_t *b)
> > +{
> > + for (int i = 0; i < 128; ++i)
> > + r[i] = ((unsigned __int128)a[i] * (unsigned __int128)b[i]) >> 64;
> > +}
> > +
> > +/* Vectorizing two 64bit unsigned highpart multiplies with 4 pmuludq plus
> > + more is slower than two iterations with a mulq each. */
> > +/* { dg-final { scan-assembler-times "pmuludq" 0 } } */
> > diff --git a/gcc/testsuite/gcc.target/i386/vect-umulv4di_high.c
> > b/gcc/testsuite/gcc.target/i386/vect-umulv4di_high.c
> > new file mode 100644
> > index 00000000000..ef966b4ec07
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.target/i386/vect-umulv4di_high.c
> > @@ -0,0 +1,12 @@
> > +/* { dg-do compile { target { ! ia32 } } } */
> > +/* { dg-options "-O2 -mavx2 -mprefer-vector-width=256" } */
> > +
> > +#include <stdint.h>
> > +
> > +void mulu64_high (uint64_t * __restrict r, uint64_t *a, uint64_t *b)
> > +{
> > + for (int i = 0; i < 128; ++i)
> > + r[i] = ((unsigned __int128)a[i] * (unsigned __int128)b[i]) >> 64;
> > +}
> > +
> > +/* { dg-final { scan-assembler-times "pmuludq" 4 } } */
> > --
> > 2.51.0
>
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Stefan Gaiser, Jochen Jaser, Abhinav Puri; (HRB 36809, AG Nuernberg)
