On Tue, Jul 14, 2026 at 6:05 PM Konstantinos Eleftheriou <[email protected]> wrote: > > Extend the long-multiply fold to the ladder forms, which propagate > the cross-product carries via a sequence of mask / shift / add steps > on intermediate sums rather than via an explicit overflow compare. > Three structural shapes are recognized: > > ladder_sum1 = (hilo & mask) + hilo' + (xl*yl >> N) > ladder_part_sum = (xl*yl >> N) + hilo > ladder_sum2 = (ladder_part_sum & mask) + hilo' > ladder_sum3 = (hilo & mask) + (hilo' & mask) + (xl*yl >> N) > > The full HIGH_PART chain looks like: > > xh*yh + (hilo >> N) + (ladder_sumN >> N) [+ ...] > > The corresponding LOW_PART recovers (xl*yl & mask) | (ladder_sumN << N). > match_long_mul picks up each shape via its table row; classifier > ordering keeps more-constrained ladder forms ahead of mul_low_sum > and mul_cross_sum to avoid shadowing.
LGTM. > gcc/ChangeLog: > > * match.pd: Add mul_ladder_sum1, mul_ladder_sum2, > mul_ladder_sum3 and mul_ladder_part_sum atom recognizers. > * tree-ssa-forwprop.cc (gimple_mul_ladder_sum1): Declare. > (gimple_mul_ladder_sum2): Likewise. > (gimple_mul_ladder_sum3): Likewise. > (gimple_mul_ladder_part_sum): Likewise. > (enum long_mul_kind): Add LMK_LADDER_SUM1 / LMK_LADDER_SUM2 > / LMK_LADDER_SUM3 / LMK_LADDER_PART_SUM. > (long_mul_set_summand): Handle the new kinds. > (long_mul_classify_plus_kinds): Try mul_ladder_sum3 and > mul_ladder_sum1 before mul_low_sum (more-constrained > first); add mul_ladder_sum2. > (long_mul_classify_hi_extract): Add mul_ladder_part_sum > branch. > (long_mul_table): Add HIGH_PART and LOW_PART rows for each > ladder form. > > gcc/testsuite/ChangeLog: > > * gcc.target/aarch64/long_mul.c: Add mulh_ladder and > mulh_ladder_32 functions; bump expected umulh / umull > scan counts from 1 to 2. > * gcc.target/i386/long_mul.c: Same for mulq / imulq. > * gcc.dg/tree-ssa/long-mul-ladder.c: New test. > > Signed-off-by: Konstantinos Eleftheriou <[email protected]> > --- > > (no changes since v1) > > gcc/match.pd | 54 +++ > .../gcc.dg/tree-ssa/long-mul-ladder.c | 329 ++++++++++++++++++ > gcc/testsuite/gcc.target/aarch64/long_mul.c | 50 ++- > gcc/testsuite/gcc.target/i386/long_mul.c | 50 ++- > gcc/tree-ssa-forwprop.cc | 93 ++++- > 5 files changed, 561 insertions(+), 15 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c > > diff --git a/gcc/match.pd b/gcc/match.pd > index 85a60848b2e6..ca6d57814776 100644 > --- a/gcc/match.pd > +++ b/gcc/match.pd > @@ -12256,6 +12256,60 @@ and, > (mul_lolo @op0 @op1 INTEGER_CST@0) > INTEGER_CST@1) > (mul_lo (mul_cross_sum @mul_hilo0 @mul_hilo1) INTEGER_CST@0))) > +/* Ladder sum form 1: (hilo0 & mask) + hilo1 + (xl*yl >> N). > + First variant: @mul_hilo1 is inside the inner plus:c alongside > + (mul_lo ...). */ > +(match (mul_ladder_sum1 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (plus:c > + (mul_lo > + @mul_hilo0 > + INTEGER_CST@0) > + @mul_hilo1) > + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1))) > +/* Second variant: @mul_hilo1 is the outermost addend and could match > + anything, so guard that its definition is a MULT_EXPR. */ > +(match (mul_ladder_sum1 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (plus:c > + (mul_lo @mul_hilo0 INTEGER_CST@0) > + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1)) > + @mul_hilo1) > + (with { > + tree_code mul_hilo_code = TREE_CODE (@mul_hilo1); > + tree_code rhs_code = ERROR_MARK; > + if (mul_hilo_code == SSA_NAME) > + { > + gimple *def = SSA_NAME_DEF_STMT (@mul_hilo1); > + if (def && gimple_code (def) == GIMPLE_ASSIGN) > + rhs_code = gimple_assign_rhs_code (def); > + } } > + (if (rhs_code == MULT_EXPR)))) > +/* Partial ladder sum: (xl*yl >> N) + hilo. */ > +(match (mul_ladder_part_sum @op0 @op1 @mul_hilo0 @0 @1) > + (plus:c > + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1) > + @mul_hilo0)) > +/* Ladder sum form 2: (ladder_part_sum & mask) + hilo. */ > +(match (mul_ladder_sum2 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (mul_lo > + (mul_ladder_part_sum @op0 @op1 @mul_hilo0 INTEGER_CST@0 INTEGER_CST@1) > + INTEGER_CST@0) > + @mul_hilo1)) > +/* Ladder sum form 3: (hilo0 & mask) + (hilo1 & mask) + (xl*yl >> N). */ > +(match (mul_ladder_sum3 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (plus:c > + (mul_lo @mul_hilo0 INTEGER_CST@0) > + (mul_lo @mul_hilo1 INTEGER_CST@0)) > + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1))) > +(match (mul_ladder_sum3 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (plus:c > + (mul_lo @mul_hilo0 INTEGER_CST@0) > + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1)) > + (mul_lo @mul_hilo1 INTEGER_CST@0))) > #endif > > /* Floatint point/integer comparison and integer->integer > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c > b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c > new file mode 100644 > index 000000000000..36eadd05aae1 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c > @@ -0,0 +1,329 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -fdump-tree-forwprop-details" } */ > + > +typedef __UINT32_TYPE__ uint32_t; > +typedef __UINT64_TYPE__ uint64_t; > +typedef struct { uint32_t v[2]; } v2i32; > +typedef struct { uint64_t v[2]; } v2i64; > + > +uint64_t mulh_ladder (uint64_t x, uint64_t y) > +{ > + uint64_t x_lo = x & 0xFFFFFFFF; > + uint64_t y_lo = y & 0xFFFFFFFF; > + uint64_t x_hi = x >> 32; > + uint64_t y_hi = y >> 32; > + uint64_t t0 = y_lo * x_lo; > + uint64_t t1 = y_lo * x_hi; > + uint64_t t2 = y_hi * x_lo; > + uint64_t t3 = y_hi * x_hi; > + uint64_t t0_hi = t0 >> 32; > + uint64_t u0 = t0_hi + t1; > + uint64_t u0_lo = u0 & 0xFFFFFFFF; > + uint64_t u0_hi = u0 >> 32; > + uint64_t u1 = u0_lo + t2; > + uint64_t u1_hi = u1 >> 32; > + uint64_t u2 = u0_hi + t3; > + uint64_t hw64 = u2 + u1_hi; > + > + return hw64; > +} > + > +uint64_t mulh_ladder_comm (uint64_t x, uint64_t y) > +{ > + uint64_t x_lo = x & 0xFFFFFFFF; > + uint64_t y_lo = y & 0xFFFFFFFF; > + uint64_t x_hi = x >> 32; > + uint64_t y_hi = y >> 32; > + uint64_t t0 = x_lo * y_lo; > + uint64_t t1 = x_lo * y_hi; > + uint64_t t2 = x_hi * y_lo; > + uint64_t t3 = x_hi * y_hi; > + uint64_t t0_hi = t0 >> 32; > + uint64_t u0 = t1 + t0_hi; > + uint64_t u0_lo = u0 & 0xFFFFFFFF; > + uint64_t u0_hi = u0 >> 32; > + uint64_t u1 = t2 + u0_lo; > + uint64_t u1_hi = u1 >> 32; > + uint64_t u2 = u1_hi + u0_hi; > + uint64_t hw64 = t3 + u2; > + > + return hw64; > +} > + > +uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = y_hi * x_lo; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_lo = u0 & 0xFFFF; > + uint32_t u0_hi = u0 >> 16; > + uint32_t u1 = u0_lo + t2; > + uint32_t u1_hi = u1 >> 16; > + uint32_t u2 = u0_hi + t3; > + uint32_t hw64 = u2 + u1_hi; > + > + return hw64; > +} > + > +/* The 128-bit variant lowers to longhand in pass_optimize_widening_mul; > + no target provides a 256-bit multiply. */ > +#ifdef __SIZEOF_INT128__ > +__uint128_t umulh_variant_i128 (__uint128_t x, __uint128_t y) > +{ > + __uint128_t x_lo = x & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t y_lo = y & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t x_hi = x >> 64; > + __uint128_t y_hi = y >> 64; > + __uint128_t t0 = y_lo * x_lo; > + __uint128_t t1 = y_lo * x_hi; > + __uint128_t t2 = y_hi * x_lo; > + __uint128_t t3 = y_hi * x_hi; > + __uint128_t t0_hi = t0 >> 64; > + __uint128_t u0 = t0_hi + t1; > + __uint128_t u0_lo = u0 & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t u0_hi = u0 >> 64; > + __uint128_t u1 = u0_lo + t2; > + __uint128_t u1_hi = u1 >> 64; > + __uint128_t u2 = u0_hi + t3; > + __uint128_t hw64 = u2 + u1_hi; > + > + return hw64; > +} > +#endif > + > +v2i64 full_mul_ladder (uint64_t x, uint64_t y) > +{ > + uint64_t and_x = x & 0xFFFFFFFF; > + uint64_t and_y = y & 0xFFFFFFFF; > + uint64_t mul_i = and_y * and_x; > + uint64_t shr_x = x >> 32; > + uint64_t mul_i27 = and_y * shr_x; > + uint64_t shr_y = y >> 32; > + uint64_t mul_i28 = shr_y * and_x; > + uint64_t mul_i29 = shr_y * shr_x; > + uint64_t shr10 = mul_i >> 32; > + uint64_t and11 = mul_i27 & 0xFFFFFFFF; > + uint64_t add = and11 + mul_i28; > + uint64_t add12 = add + shr10; > + uint64_t shr13 = mul_i27 >> 32; > + uint64_t shr14 = add12 >> 32; > + uint64_t add15 = shr13 + mul_i29; > + uint64_t add16 = add15 + shr14; > + uint64_t shl = add12 << 32; > + uint64_t and17 = mul_i & 0xFFFFFFFF; > + uint64_t or_val = shl | and17; > + v2i64 result; > + result.v[0] = or_val; > + result.v[1] = add16; > + return result; > +} > + > +/* This will be optimized during the second forwprop run. > + Disable SLP so the expected fold count is target-independent. */ > +__attribute__((optimize("no-tree-slp-vectorize"))) > +v2i32 mulh_ladder_v2i32 (v2i32 x, v2i32 y) > +{ > + v2i32 result; > + for(int i=0; i<2; ++i) > + { > + uint32_t x_lo = x.v[i] & 0xFFFF; > + uint32_t y_lo = y.v[i] & 0xFFFF; > + uint32_t x_hi = x.v[i] >> 16; > + uint32_t y_hi = y.v[i] >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = y_hi * x_lo; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_lo = u0 & 0xFFFF; > + uint32_t u0_hi = u0 >> 16; > + uint32_t u1 = u0_lo + t2; > + uint32_t u1_hi = u1 >> 16; > + uint32_t u2 = u0_hi + t3; > + result.v[i] = u2 + u1_hi; > + } > + > + return result; > +} > + > +/* Ladder-long variants: hi-part sum uses the long form > + (xh*yh + cross_hi_a + cross_hi_b + mid_hi). */ > + > +uint32_t mulh_ladder_long (uint32_t x, uint32_t y) > +{ > + uint32_t xl = x & 0xFFFF; > + uint32_t xh = x >> 16; > + uint32_t yl = y & 0xFFFF; > + uint32_t yh = y >> 16; > + uint32_t mulll = xl * yl; > + uint32_t mullh = xl * yh; > + uint32_t mulhl = xh * yl; > + uint32_t mulhh = xh * yh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mullh & 0xFFFF; > + uint32_t add = shr8 + conv10; > + uint32_t conv12 = mulhl & 0xFFFF; > + uint32_t add13 = add + conv12; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mullh >> 16; > + uint32_t add16 = mulhh + shr15; > + uint32_t shr17 = mulhl >> 16; > + uint32_t add18 = add16 + shr17; > + uint32_t add19 = add18 + shr14; > + > + return add19; > +} > + > +void full_mul_ladder_long (uint32_t x, uint32_t y, uint32_t *p) > +{ > + uint32_t xl = x & 0xFFFF; > + uint32_t xh = x >> 16; > + uint32_t yl = y & 0xFFFF; > + uint32_t yh = y >> 16; > + uint32_t mulll = xl * yl; > + uint32_t mullh = xl * yh; > + uint32_t mulhl = xh * yl; > + uint32_t mulhh = xh * yh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mullh & 0xFFFF; > + uint32_t add = shr8 + conv10; > + uint32_t conv12 = mulhl & 0xFFFF; > + uint32_t add13 = add + conv12; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mullh >> 16; > + uint32_t add16 = mulhh + shr15; > + uint32_t shr17 = mulhl >> 16; > + uint32_t add18 = add16 + shr17; > + uint32_t add19 = add18 + shr14; > + p[1] = add19; > + uint32_t add_13_shl = add13 << 16; > + uint32_t and17 = mulll & 0xFFFF; > + uint32_t or_val = add_13_shl | and17; > + p[0] = or_val; > +} > + > +uint32_t mulh_ladder_long_comm (uint32_t x, uint32_t y) > +{ > + uint32_t xl = x & 0xFFFF; > + uint32_t xh = x >> 16; > + uint32_t yl = y & 0xFFFF; > + uint32_t yh = y >> 16; > + uint32_t mulll = yl * xl; > + uint32_t mullh = yh * xl; > + uint32_t mulhl = yl * xh; > + uint32_t mulhh = yh * xh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mullh & 0xFFFF; > + uint32_t add = conv10 + shr8; > + uint32_t conv12 = mulhl & 0xFFFF; > + uint32_t add13 = conv12 + add; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mullh >> 16; > + uint32_t shr17 = mulhl >> 16; > + uint32_t add16 = shr14 + shr17; > + uint32_t add18 = add16 + shr15; > + uint32_t add19 = mulhh + add18; > + > + return add19; > +} > + > +/* The 128-bit variant lowers to longhand in pass_optimize_widening_mul; > + no target provides a 256-bit multiply. */ > +#ifdef __SIZEOF_INT128__ > +__uint128_t mulh_ladder_long_128 (__uint128_t x, __uint128_t y) > +{ > + __uint128_t xl = x & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t xh = x >> 64; > + __uint128_t yl = y & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t yh = y >> 64; > + __uint128_t mulll = xl * yl; > + __uint128_t mullh = xl * yh; > + __uint128_t mulhl = xh * yl; > + __uint128_t mulhh = xh * yh; > + __uint128_t shr8 = mulll >> 64; > + __uint128_t conv10 = mullh & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t add = shr8 + conv10; > + __uint128_t conv12 = mulhl & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t add13 = add + conv12; > + __uint128_t shr14 = add13 >> 64; > + __uint128_t shr15 = mullh >> 64; > + __uint128_t add16 = mulhh + shr15; > + __uint128_t shr17 = mulhl >> 64; > + __uint128_t add18 = add16 + shr17; > + __uint128_t add19 = add18 + shr14; > + > + return add19; > +} > +#endif > + > +uint32_t mulh_ladder_long_hllh (uint32_t x, uint32_t y) > +{ > + uint32_t xl = x & 0xFFFF; > + uint32_t xh = x >> 16; > + uint32_t yl = y & 0xFFFF; > + uint32_t yh = y >> 16; > + uint32_t mulll = xl * yl; > + uint32_t mullh = xl * yh; > + uint32_t mulhl = xh * yl; > + uint32_t mulhh = xh * yh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mulhl & 0xFFFF; > + uint32_t add = shr8 + conv10; > + uint32_t conv12 = mullh & 0xFFFF; > + uint32_t add13 = add + conv12; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mulhl >> 16; > + uint32_t add16 = mulhh + shr15; > + uint32_t shr17 = mullh >> 16; > + uint32_t add18 = add16 + shr17; > + uint32_t add19 = add18 + shr14; > + > + return add19; > +} > + > +/* This will be optimized during the second forwprop run. > + Disable SLP so the expected fold count is target-independent. */ > +__attribute__((optimize("no-tree-slp-vectorize"))) > +v2i32 mul_ladder_long_v2i32 (v2i32 x, v2i32 y) > +{ > + v2i32 result; > + for (int i = 0; i < 2; i++) > + { > + uint32_t xl = x.v[i] & 0xFFFF; > + uint32_t xh = x.v[i] >> 16; > + uint32_t yl = y.v[i] & 0xFFFF; > + uint32_t yh = y.v[i] >> 16; > + uint32_t mulll = xl * yl; > + uint32_t mullh = xl * yh; > + uint32_t mulhl = xh * yl; > + uint32_t mulhh = xh * yh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mullh & 0xFFFF; > + uint32_t add = shr8 + conv10; > + uint32_t conv12 = mulhl & 0xFFFF; > + uint32_t add13 = add + conv12; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mullh >> 16; > + uint32_t add16 = mulhh + shr15; > + uint32_t shr17 = mulhl >> 16; > + uint32_t add18 = add16 + shr17; > + result.v[i] = add18 + shr14; > + } > + > + return result; > +} > + > +/* On LP64 the __int128-guarded highpart also folds; on non-LP64 it > + is elided by #ifdef and the count drops by 2. */ > +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." > 8 "forwprop1" { target lp64 } } } */ > +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." > 5 "forwprop1" { target { ! lp64 } } } } */ > +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." > 2 "forwprop2" } } */ > +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." > 2 "forwprop1" } } */ > diff --git a/gcc/testsuite/gcc.target/aarch64/long_mul.c > b/gcc/testsuite/gcc.target/aarch64/long_mul.c > index 2a4709ecbfd0..f9c765380d8c 100644 > --- a/gcc/testsuite/gcc.target/aarch64/long_mul.c > +++ b/gcc/testsuite/gcc.target/aarch64/long_mul.c > @@ -4,6 +4,27 @@ > typedef __UINT32_TYPE__ uint32_t; > typedef __UINT64_TYPE__ uint64_t; > > +/* 64-bit ladder pattern for high part. */ > +uint64_t mulh_ladder (uint64_t x, uint64_t y) > +{ > + uint64_t x_lo = x & 0xFFFFFFFF; > + uint64_t y_lo = y & 0xFFFFFFFF; > + uint64_t x_hi = x >> 32; > + uint64_t y_hi = y >> 32; > + uint64_t t0 = y_lo * x_lo; > + uint64_t t1 = y_lo * x_hi; > + uint64_t t2 = y_hi * x_lo; > + uint64_t t3 = y_hi * x_hi; > + uint64_t t0_hi = t0 >> 32; > + uint64_t u0 = t0_hi + t1; > + uint64_t u0_lo = u0 & 0xFFFFFFFF; > + uint64_t u0_hi = u0 >> 32; > + uint64_t u1 = u0_lo + t2; > + uint64_t u1_hi = u1 >> 32; > + uint64_t u2 = u0_hi + t3; > + return u2 + u1_hi; > +} > + > /* 64-bit carry pattern for high part. */ > uint64_t mulh_carry (uint64_t x, uint64_t y) > { > @@ -28,6 +49,27 @@ uint64_t mulh_carry (uint64_t x, uint64_t y) > return interm_plus_carry + low_accum_hi; > } > > +/* 32-bit ladder pattern for high part. */ > +uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = y_hi * x_lo; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_lo = u0 & 0xFFFF; > + uint32_t u0_hi = u0 >> 16; > + uint32_t u1 = u0_lo + t2; > + uint32_t u1_hi = u1 >> 16; > + uint32_t u2 = u0_hi + t3; > + return u2 + u1_hi; > +} > + > /* 32-bit carry pattern for high part. */ > uint32_t mulh_carry_32 (uint32_t x, uint32_t y) > { > @@ -52,7 +94,7 @@ uint32_t mulh_carry_32 (uint32_t x, uint32_t y) > return interm_plus_carry + low_accum_hi; > } > > -/* 64-bit pattern should emit umulh. */ > -/* { dg-final { scan-assembler-times "umulh\t" 1 } } */ > -/* 32-bit pattern should emit umull (32x32->64 widening multiply). */ > -/* { dg-final { scan-assembler-times "umull\t" 1 } } */ > +/* 64-bit patterns should emit umulh. */ > +/* { dg-final { scan-assembler-times "umulh\t" 2 } } */ > +/* 32-bit patterns should emit umull (32x32->64 widening multiply). */ > +/* { dg-final { scan-assembler-times "umull\t" 2 } } */ > diff --git a/gcc/testsuite/gcc.target/i386/long_mul.c > b/gcc/testsuite/gcc.target/i386/long_mul.c > index 6ec87eb8dd21..d4b03ed1beda 100644 > --- a/gcc/testsuite/gcc.target/i386/long_mul.c > +++ b/gcc/testsuite/gcc.target/i386/long_mul.c > @@ -4,6 +4,27 @@ > typedef __UINT32_TYPE__ uint32_t; > typedef __UINT64_TYPE__ uint64_t; > > +/* 64-bit ladder pattern for high part. */ > +uint64_t mulh_ladder (uint64_t x, uint64_t y) > +{ > + uint64_t x_lo = x & 0xFFFFFFFF; > + uint64_t y_lo = y & 0xFFFFFFFF; > + uint64_t x_hi = x >> 32; > + uint64_t y_hi = y >> 32; > + uint64_t t0 = y_lo * x_lo; > + uint64_t t1 = y_lo * x_hi; > + uint64_t t2 = y_hi * x_lo; > + uint64_t t3 = y_hi * x_hi; > + uint64_t t0_hi = t0 >> 32; > + uint64_t u0 = t0_hi + t1; > + uint64_t u0_lo = u0 & 0xFFFFFFFF; > + uint64_t u0_hi = u0 >> 32; > + uint64_t u1 = u0_lo + t2; > + uint64_t u1_hi = u1 >> 32; > + uint64_t u2 = u0_hi + t3; > + return u2 + u1_hi; > +} > + > /* 64-bit carry pattern for high part. */ > uint64_t mulh_carry (uint64_t x, uint64_t y) > { > @@ -28,6 +49,27 @@ uint64_t mulh_carry (uint64_t x, uint64_t y) > return interm_plus_carry + low_accum_hi; > } > > +/* 32-bit ladder pattern for high part. */ > +uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = y_hi * x_lo; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_lo = u0 & 0xFFFF; > + uint32_t u0_hi = u0 >> 16; > + uint32_t u1 = u0_lo + t2; > + uint32_t u1_hi = u1 >> 16; > + uint32_t u2 = u0_hi + t3; > + return u2 + u1_hi; > +} > + > /* 32-bit carry pattern for high part. */ > uint32_t mulh_carry_32 (uint32_t x, uint32_t y) > { > @@ -52,7 +94,7 @@ uint32_t mulh_carry_32 (uint32_t x, uint32_t y) > return interm_plus_carry + low_accum_hi; > } > > -/* 64-bit pattern should emit mulq (unsigned 64x64->128 multiply). */ > -/* { dg-final { scan-assembler-times "\tmulq" 1 } } */ > -/* 32-bit pattern should emit imulq (64-bit multiply of zero-extended > operands). */ > -/* { dg-final { scan-assembler-times "\timulq" 1 } } */ > +/* 64-bit patterns should emit mulq (unsigned 64x64->128 multiply). */ > +/* { dg-final { scan-assembler-times "\tmulq" 2 } } */ > +/* 32-bit patterns should emit imulq (64-bit multiply of zero-extended > operands). */ > +/* { dg-final { scan-assembler-times "\timulq" 2 } } */ > diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc > index ea989c809181..f9c0f1a9854d 100644 > --- a/gcc/tree-ssa-forwprop.cc > +++ b/gcc/tree-ssa-forwprop.cc > @@ -3605,6 +3605,10 @@ extern bool gimple_mul_low_accum (tree, tree *, tree > (*)(tree)); > extern bool gimple_mul_carry_cross_sum (tree, tree *, tree (*)(tree)); > extern bool gimple_mul_carry_low_sum (tree, tree *, tree (*)(tree)); > extern bool gimple_mul_carry_low (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_ladder_sum1 (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_ladder_sum2 (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_ladder_sum3 (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_ladder_part_sum (tree, tree *, tree (*)(tree)); > > /* Replace STMT with a high-part multiply of OP1 and OP2, emitted as > (N)(((2N) op1 * (2N) op2) >> N). > @@ -3674,6 +3678,10 @@ enum long_mul_kind { > LMK_CROSS_SUM, > LMK_LOW_ACCUM, > LMK_LOW_SUM, > + LMK_LADDER_SUM1, > + LMK_LADDER_SUM2, > + LMK_LADDER_SUM3, > + LMK_LADDER_PART_SUM, > LMK_CARRY_LOW, > LMK_CARRY_CROSS_SUM, > LMK_CARRY_LOW_SUM, > @@ -3792,9 +3800,16 @@ long_mul_set_summand (long_mul_summand *info, > long_mul_kind kind, > break; > case LMK_LOW_ACCUM: > case LMK_LOW_SUM: > + case LMK_LADDER_SUM1: > + case LMK_LADDER_SUM2: > + case LMK_LADDER_SUM3: > n_ops = 2; > n_hilos = 2; > break; > + case LMK_LADDER_PART_SUM: > + n_ops = 2; > + n_hilos = 1; > + break; > case LMK_CARRY_CROSS_SUM: > n_hilos = 3; > shift_idx = 3; > @@ -3855,9 +3870,10 @@ long_mul_classify_carry (tree leaf, long_mul_summand > *info) > } > > /* Plus-based summand kinds shared by the (X >> SHIFT) and (X << SHIFT) > - classifiers. Order is by specificity: mul_low_sum's first arm is > - any plus, so mul_low_accum (which constrains both arms) shadows it > - and must come first. */ > + classifiers. Order is by specificity: mul_low_sum's first arm is any > + plus, so mul_ladder_sum1/3 (which constrain that arm to a plus > + containing a mul_lo) and mul_low_accum (which constrains both arms) > + shadow it and must come first. */ > > static bool > long_mul_classify_plus_kinds (tree inner, long_mul_summand *info) > @@ -3868,18 +3884,34 @@ long_mul_classify_plus_kinds (tree inner, > long_mul_summand *info) > long_mul_set_summand (info, LMK_LOW_ACCUM, res_ops); > return true; > } > + if (gimple_mul_ladder_sum3 (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_SUM3, res_ops); > + return true; > + } > + if (gimple_mul_ladder_sum1 (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_SUM1, res_ops); > + return true; > + } > if (gimple_mul_low_sum (inner, res_ops, NULL)) > { > long_mul_set_summand (info, LMK_LOW_SUM, res_ops); > return true; > } > + if (gimple_mul_ladder_sum2 (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_SUM2, res_ops); > + return true; > + } > return false; > } > > /* Classify INNER -- already unwrapped from an outer (X >> SHIFT) -- as > a high-half-extracted summand. mul_hilo (mult-shape) is orthogonal > - to the plus-based kinds and is tried first; mul_cross_sum (any plus) > - is the fallback after the shared plus-based kinds. */ > + to the plus-based kinds and is tried first; ladder_part_sum (one arm > + unconstrained) and mul_cross_sum (any plus) are the fallbacks after > + the shared plus-based ladder. */ > > static bool > long_mul_classify_hi_extract (tree inner, unsigned HOST_WIDE_INT shift, > @@ -3895,6 +3927,11 @@ long_mul_classify_hi_extract (tree inner, unsigned > HOST_WIDE_INT shift, > } > if (long_mul_classify_plus_kinds (inner, info)) > return true; > + if (gimple_mul_ladder_part_sum (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_PART_SUM, res_ops); > + return true; > + } > if (gimple_mul_cross_sum (inner, res_ops, NULL)) > { > long_mul_set_summand (info, LMK_CROSS_SUM, res_ops); > @@ -3922,8 +3959,8 @@ long_mul_classify_lo_extract (tree inner, unsigned > HOST_WIDE_INT mask, > } > > /* Classify INNER -- already unwrapped from an outer (X << SHIFT) -- as > - a left-shifted summand. No mul_hilo here -- that shape appears only > - under (X >> SHIFT). */ > + a left-shifted summand. No mul_hilo / ladder_part_sum here -- those > + shapes appear only under (X >> SHIFT). */ > > static bool > long_mul_classify_shl_extract (tree inner, unsigned HOST_WIDE_INT shift, > @@ -4272,6 +4309,30 @@ static const long_mul_row long_mul_table[] = { > { LMK_CARRY_LOW, LMX_NONE }, > { LMK_CARRY_CROSS_SUM, LMX_NONE } }, > long_mul_check_two_carries }, > + /* xh*yh + (hilo >> N) + (ladder_sum1 >> N), > + ladder_sum1 = (hilo & mask) + hilo' + (xl*yl >> N), > + hilo, hilo' the two cross-half products. */ > + { long_mul_row::HIGH_PART, PLUS_EXPR, 3, > + { { LMK_MUL_HIHI, LMX_NONE }, > + { LMK_MUL_HILO, LMX_HI }, > + { LMK_LADDER_SUM1, LMX_HI } }, > + NULL }, > + /* xh*yh + (ladder_sum2 >> N) + (ladder_part_sum >> N), > + ladder_part_sum = (xl*yl >> N) + hilo, > + ladder_sum2 = (ladder_part_sum & mask) + hilo'. */ > + { long_mul_row::HIGH_PART, PLUS_EXPR, 3, > + { { LMK_MUL_HIHI, LMX_NONE }, > + { LMK_LADDER_SUM2, LMX_HI }, > + { LMK_LADDER_PART_SUM, LMX_HI } }, > + NULL }, > + /* xh*yh + (hilo >> N) + (hilo' >> N) + (ladder_sum3 >> N), > + ladder_sum3 = (hilo & mask) + (hilo' & mask) + (xl*yl >> N). */ > + { long_mul_row::HIGH_PART, PLUS_EXPR, 4, > + { { LMK_MUL_HIHI, LMX_NONE }, > + { LMK_MUL_HILO, LMX_HI }, > + { LMK_MUL_HILO, LMX_HI }, > + { LMK_LADDER_SUM3, LMX_HI } }, > + NULL }, > /* LOW-PART folds. Recover the lower 2N bits from xl*yl plus a > shifted cross-half term. */ > /* (xl*yl & mask) | (low_accum << N), > @@ -4286,6 +4347,24 @@ static const long_mul_row long_mul_table[] = { > { { LMK_MUL_LOLO, LMX_LO }, > { LMK_LOW_SUM, LMX_SHL_N } }, > NULL }, > + /* (xl*yl & mask) | (ladder_sum1 << N), > + ladder_sum1 as in the high ladder row above. */ > + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, > + { { LMK_MUL_LOLO, LMX_LO }, > + { LMK_LADDER_SUM1, LMX_SHL_N } }, > + NULL }, > + /* (xl*yl & mask) | (ladder_sum2 << N), > + ladder_sum2 as in the high ladder row above. */ > + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, > + { { LMK_MUL_LOLO, LMX_LO }, > + { LMK_LADDER_SUM2, LMX_SHL_N } }, > + NULL }, > + /* (xl*yl & mask) | (ladder_sum3 << N), > + ladder_sum3 as in the high ladder-long row above. */ > + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, > + { { LMK_MUL_LOLO, LMX_LO }, > + { LMK_LADDER_SUM3, LMX_SHL_N } }, > + NULL }, > }; > > /* If a multi-used inner addition (sharing the chain's outer code) blocked > -- > 2.55.0 >
