On Tue, Jul 14, 2026 at 9:05 AM Konstantinos Eleftheriou
<[email protected]> wrote:
>
> Recognize the longhand wide-multiplication carry idiom and fold it to a
> widening multiply followed by a right shift for the high part, and a
> plain MULT_EXPR for the low part.
>
> The carry idiom is the schoolbook expansion of a 2N-bit unsigned
> multiply written as a top-level + chain of four NxN partial products
> plus one overflow-compare carry:
>
> xh*yh + (cross_sum >> N) + (low_accum >> N) + ((hilo > cross_sum) << N)
> cross_sum = xh*yl + xl*yh
> low_accum = (xl*yl >> N) + (cross_sum & mask)
>
> For example, this AArch64 sequence from SPEC2026's 750.sealcrypto_r:
>
> lsr x4, x0, 32
> lsr x6, x1, 32
> umull x3, w0, w1
> umull x1, w1, w4
> and x5, x3, 4294967295
> umaddl x0, w0, w6, x1
> cmp x1, x0
> and x1, x0, 4294967295
> lsr x0, x0, 32
> add x3, x1, x3, lsr 32
> cset x1, hi
> orr x5, x5, x3, lsl 32
> umaddl x4, w4, w6, x0
> extr x0, x1, x3, 32
> add x0, x0, x4
> stp x5, x0, [x2]
>
> can be transformed to:
>
> umulh x3, x1, x0
> mul x0, x0, x1
> stp x0, x3, [x2]
>
> Atom-level pattern recognition is implemented via match patterns in
> match.pd (mul_hi, mul_lo, mul_hilo, mul_lolo, mul_hihi, mul_cross_sum,
> mul_low_accum, mul_carry_cross_sum). The composite recognition that
> ties atoms into a long-multiplication chain is performed in forwprop
> by match_long_mul: it linearizes the outer add/ior chain into a
> multiset of summands, classifies each summand via the match.pd atoms,
> and looks the multiset up in long_mul_table to identify the variant.
> On a hit, three cross-summand consistency checks (one operand pair,
> half-width shifts, hilo cross-half products) gate the rewrite.
>
> The HIGH_PART row emits the canonical widening shape
>
> (N)(((2N) op1 * (2N) op2) >> N)
>
> which pass_optimize_widening_mul later lowers to a single
> WIDEN_MULT_EXPR or MULT_HIGHPART_EXPR on targets that support it.
> The LOW_PART row emits a plain MULT_EXPR. HIGH_PART is emitted only
> when the 2N mode is present in the mode table.
>
> Bootstrapped/regtested on AArch64, x86-64 and PowerPC.
>
> PR tree-optimization/107090
>
> gcc/ChangeLog:
>
> * match.pd: Add atom match recognizers for long-multiply
> (mul_hi, mul_lo, mul_hilo, mul_lolo, mul_hihi, mul_cross_sum,
> mul_low_accum, mul_carry_cross_sum).
> * tree-ssa-forwprop.cc (gimple_mul_hi): Declare.
> (gimple_mul_lo): Likewise.
> (gimple_mul_hilo): Likewise.
> (gimple_mul_lolo): Likewise.
> (gimple_mul_hihi): Likewise.
> (gimple_mul_cross_sum): Likewise.
> (gimple_mul_low_accum): Likewise.
> (gimple_mul_carry_cross_sum): Likewise.
> (create_mul_high_seq): New, emits (N)(((2N) op1 * (2N) op2) >> N).
> (create_mul_low_seq): New, emits MULT_EXPR.
> (enum long_mul_kind): New.
> (enum long_mul_extract): New.
> (struct long_mul_summand): New.
> (long_mul_linearize_chain): New, walks the outer add/ior chain
> into a multiset of leaves.
> (long_mul_is_lshift_def): New.
> (long_mul_set_summand): New.
> (long_mul_classify_carry): New.
> (long_mul_classify_plus_kinds): New.
> (long_mul_classify_hi_extract): New.
> (long_mul_classify_lo_extract): New.
> (long_mul_classify_shl_extract): New.
> (long_mul_classify_bare): New.
> (long_mul_classify_summand): New, classify each summand via the
> match.pd atoms.
> (long_mul_summand_compare): New.
> (struct long_mul_row): New.
> (long_mul_same_ops): New.
> (long_mul_is_cross_half): New.
> (long_mul_hilo_orientation): New, orientation of a mul_hilo
> capture relative to (op0, op1).
> (long_mul_canonical_ops): New.
> (long_mul_check_consistency): New, cross-summand consistency
> check (operand pairing, half-width shifts, hilo cross-half).
> (long_mul_signature_matches): New.
> (long_mul_hint_shared_intermediate): New, dump-file hint
> pointing at a shared inner addition.
> (match_long_mul): New, top-level entry: linearizes the outer
> add/ior chain, classifies summands, looks the multiset up in
> long_mul_table, runs cross-summand consistency checks, and
> dispatches to create_mul_high_seq / create_mul_low_seq.
> (pass_forwprop::execute): Call match_long_mul on PLUS_EXPR and
> BIT_IOR_EXPR statements.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/long-mul-carry.c: New test.
> * gcc.target/aarch64/long_mul.c: New test.
> * gcc.target/i386/long_mul.c: New test.
>
> Co-authored-by: Philipp Tomsich <[email protected]>
> Signed-off-by: Konstantinos Eleftheriou <[email protected]>
> ---
>
> (no changes since v1)
>
> gcc/match.pd | 73 ++
> .../gcc.dg/tree-ssa/long-mul-carry.c | 181 +++++
> gcc/testsuite/gcc.target/aarch64/long_mul.c | 58 ++
> gcc/testsuite/gcc.target/i386/long_mul.c | 58 ++
> gcc/tree-ssa-forwprop.cc | 701 +++++++++++++++++-
> 5 files changed, 1066 insertions(+), 5 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c
> create mode 100644 gcc/testsuite/gcc.target/aarch64/long_mul.c
> create mode 100644 gcc/testsuite/gcc.target/i386/long_mul.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 9d4ab622fe57..5a4b1923b589 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -12160,6 +12160,79 @@ and,
> INTEGER_CST@2) INTEGER_CST@3)
> (if (compare_tree_int (@sub1, 1) == 0)))
>
> +#if GIMPLE
> +/* Match low and high parts of longhand multiplication.
> + Given a 2N-bit unsigned type, x = xh*2^N + xl and y = yh*2^N + yl,
> + where xh, xl, yh, yl are N-bit halves extracted via shifts and masks. */
> +
> +/* High half: op >> N. */
> +(match (mul_hi @op @0)
> + (rshift @op INTEGER_CST@0)
> + (with {
> + tree op_type = TREE_TYPE (@op); }
> + (if (INTEGRAL_TYPE_P (op_type)
> + && TYPE_UNSIGNED (op_type)
> + && TYPE_PRECISION (op_type) % 2 == 0
> + && tree_fits_uhwi_p (@0)
> + && tree_to_uhwi (@0) == TYPE_PRECISION (op_type) / 2))))
> +/* Low half: op & mask. */
> +(match (mul_lo @op @0)
> + (bit_and @op INTEGER_CST@0)
> + (with {
> + tree op_type = TREE_TYPE (@op); }
> + (if (INTEGRAL_TYPE_P (op_type)
> + && TYPE_UNSIGNED (op_type)
> + && TYPE_PRECISION (op_type) % 2 == 0
> + && tree_fits_uhwi_p (@0)
> + && tree_to_uhwi (@0) == wi::mask (
> + TYPE_PRECISION (op_type) / 2,
> + false,
> + TYPE_PRECISION (op_type))))))
> +/* Cross product: high(op0) * low(op1). */
> +(match (mul_hilo @op0 @op1 @0 @1)
> + (mult:c
> + (mul_hi @op0 INTEGER_CST@0)
> + (mul_lo @op1 INTEGER_CST@1)))
> +/* Low-low product: low(op0) * low(op1). */
> +(match (mul_lolo @op0 @op1 @0)
> + (mult:c
> + (mul_lo @op0 INTEGER_CST@0)
> + (mul_lo @op1 INTEGER_CST@0)))
> +/* High-high product: high(op0) * high(op1). */
> +(match (mul_hihi @op0 @op1 @0)
> + (mult:c
> + (mul_hi @op0 INTEGER_CST@0)
> + (mul_hi @op1 INTEGER_CST@0)))
> +/* Cross sum: xh*yl + xl*yh.
> + Note: matches any PLUS; operands are validated as actual cross
> + products by the forwprop consumer (long_mul_check_consistency). */
> +(match (mul_cross_sum @mul_hilo0 @mul_hilo1)
> + (plus:c @mul_hilo0 @mul_hilo1))
> +/* Carry from cross-sum overflow: (cast?) (hilo > cross_sum) << N.
> + Explicit guard required because mul_cross_sum is just (plus:c @0 @1)
> + with no inherent type or halfwidth constraint. */
> +(match (mul_carry_cross_sum @mul_hilo0 @mul_hilo1 @mul_hilo2 @0)
> + (lshift
> + (convert? (gt
> + @mul_hilo0
> + (mul_cross_sum @mul_hilo1 @mul_hilo2)))
> + INTEGER_CST@0)
> + (with {
> + tree op_type = TREE_TYPE (@mul_hilo0); }
> + (if (INTEGRAL_TYPE_P (op_type)
> + && TYPE_UNSIGNED (op_type)
> + && TYPE_PRECISION (op_type) % 2 == 0
> + && tree_fits_uhwi_p (@0)
> + && tree_to_uhwi (@0) == TYPE_PRECISION (op_type) / 2))))
> +/* Low accumulate: (xl*yl >> N) + (cross_sum & mask). */
> +(match (mul_low_accum @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1)
> + (plus:c
> + (mul_hi
> + (mul_lolo @op0 @op1 INTEGER_CST@0)
> + INTEGER_CST@1)
> + (mul_lo (mul_cross_sum @mul_hilo0 @mul_hilo1) INTEGER_CST@0)))
> +#endif
> +
> /* Floatint point/integer comparison and integer->integer
> or floating point -> float point conversion. */
> (match (cond_expr_convert_p @0 @2 @3 @6)
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c
> b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c
> new file mode 100644
> index 000000000000..bbdbc63ac0bb
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c
> @@ -0,0 +1,181 @@
> +/* { 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;
> +
> +/* High part follows the long form
> + xh*yh + carry + (cross_sum >> N) + (low_accum >> N). */
> +
> +uint64_t mulh_carry (uint64_t x, uint64_t y)
> +{
> + uint64_t x_lo = x & 0xFFFFFFFF;
> + uint64_t x_hi = x >> 32;
> + uint64_t y_lo = y & 0xFFFFFFFF;
> + uint64_t y_hi = y >> 32;
> + uint64_t y_lo_x_hi = y_lo * x_hi;
> + uint64_t y_hi_x_hi = y_hi * x_hi;
> + uint64_t y_hi_x_lo = y_hi * x_lo;
> + uint64_t y_lo_x_lo = y_lo * x_lo;
> + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi;
> + int carry_out = cross_sum < y_lo_x_hi;
> + uint64_t carry = (uint64_t) carry_out << 32;
> + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32;
> + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF;
> + uint64_t cross_sum_hi = cross_sum >> 32;
> + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
> + uint64_t interm = cross_sum_hi + y_hi_x_hi;
> + uint64_t low_accum_hi = low_accum >> 32;
> + uint64_t interm_plus_carry = interm + carry;
> + uint64_t hw64 = interm_plus_carry + low_accum_hi;
> +
> + return hw64;
> +}
> +
> +uint64_t mulh_carry_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 y_lo_x_hi = x_hi * y_lo;
> + uint64_t y_hi_x_hi = y_hi * x_hi;
> + uint64_t y_hi_x_lo = x_lo * y_hi;
> + uint64_t y_lo_x_lo = x_lo * y_lo;
> + uint64_t cross_sum = y_lo_x_hi + y_hi_x_lo;
> + int carry_out = (cross_sum < y_lo_x_hi);
> + uint64_t carry = (uint64_t) carry_out << 32;
> + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32;
> + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF;
> + uint64_t cross_sum_hi = cross_sum >> 32;
> + uint64_t low_accum = y_lo_x_lo_hi + cross_sum_lo;
> + uint64_t inter = y_hi_x_hi + cross_sum_hi;
> + uint64_t low_accum_hi = low_accum >> 32;
> + uint64_t interm_plus_carry = carry + inter;
> + uint64_t hw64 = low_accum_hi + interm_plus_carry;
> +
> + return hw64;
> +}
> +
> +uint32_t mulh_carry_32 (uint32_t x, uint32_t y)
> +{
> + uint32_t x_lo = x & 0xFFFF;
> + uint32_t x_hi = x >> 16;
> + uint32_t y_lo = y & 0xFFFF;
> + uint32_t y_hi = y >> 16;
> + uint32_t y_lo_x_hi = y_lo * x_hi;
> + uint32_t y_hi_x_hi = y_hi * x_hi;
> + uint32_t y_hi_x_lo = y_hi * x_lo;
> + uint32_t y_lo_x_lo = y_lo * x_lo;
> + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi;
> + int carry_out = (cross_sum < y_lo_x_hi);
> + uint32_t carry = (uint32_t) carry_out << 16;
> + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16;
> + uint32_t cross_sum_lo = cross_sum & 0xFFFF;
> + uint32_t cross_sum_hi = cross_sum >> 16;
> + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
> + uint32_t interm = cross_sum_hi + y_hi_x_hi;
> + uint32_t low_accum_hi = low_accum >> 16;
> + uint32_t interm_plus_carry = interm + carry;
> + uint32_t hw64 = interm_plus_carry + low_accum_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 mulh_carry_128 (__uint128_t x, __uint128_t y)
> +{
> + __uint128_t x_lo = x & (__uint128_t)0xFFFFFFFFFFFFFFFF;
> + __uint128_t x_hi = x >> 64;
> + __uint128_t y_lo = y & (__uint128_t)0xFFFFFFFFFFFFFFFF;
> + __uint128_t y_hi = y >> 64;
> + __uint128_t y_lo_x_hi = y_lo * x_hi;
> + __uint128_t y_hi_x_hi = y_hi * x_hi;
> + __uint128_t y_hi_x_lo = y_hi * x_lo;
> + __uint128_t y_lo_x_lo = y_lo * x_lo;
> + __uint128_t cross_sum = y_hi_x_lo + y_lo_x_hi;
> + int carry_out = cross_sum < y_lo_x_hi;
> + __uint128_t carry = (__uint128_t) carry_out << 64;
> + __uint128_t y_lo_x_lo_hi = y_lo_x_lo >> 64;
> + __uint128_t cross_sum_lo = cross_sum & (__uint128_t)0xFFFFFFFFFFFFFFFF;
> + __uint128_t cross_sum_hi = cross_sum >> 64;
> + __uint128_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
> + __uint128_t interm = cross_sum_hi + y_hi_x_hi;
> + __uint128_t low_accum_hi = low_accum >> 64;
> + __uint128_t interm_plus_carry = interm + carry;
> + __uint128_t hw64 = interm_plus_carry + low_accum_hi;
> +
> + return hw64;
> +}
> +#endif
> +
> +void full_mul_carry (uint64_t x, uint64_t y, uint64_t* p) {
> + 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 y_lo_x_hi = y_lo * x_hi;
> + uint64_t y_hi_x_hi = y_hi * x_hi;
> + uint64_t y_hi_x_lo = y_hi * x_lo;
> + uint64_t y_lo_x_lo = y_lo * x_lo;
> + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi;
> + int carry_out = (cross_sum < y_lo_x_hi);
> + uint64_t carry = (uint64_t) carry_out << 32;
> + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32;
> + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF;
> + uint64_t cross_sum_hi = cross_sum >> 32;
> + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
> + uint64_t upper_mid = y_hi_x_hi + carry;
> + uint64_t low_accum_hi = low_accum >> 32;
> + uint64_t upper_mid_with_cross = upper_mid + cross_sum_hi;
> + uint64_t hw64 = upper_mid_with_cross + low_accum_hi;
> + p[1] = hw64;
> + uint64_t low_accum_shifted = low_accum << 32;
> + uint64_t y_lo_x_lo_lo = y_lo_x_lo & 0xFFFFFFFF;
> + uint64_t lw64 = low_accum_shifted | y_lo_x_lo_lo;
> + p[0] = lw64;
> +}
> +
> +/* 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_carry_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 y_lo_x_hi = y_lo * x_hi;
> + uint32_t y_hi_x_hi = y_hi * x_hi;
> + uint32_t y_hi_x_lo = y_hi * x_lo;
> + uint32_t y_lo_x_lo = y_lo * x_lo;
> +
> + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi;
> + int carry_out = cross_sum < y_lo_x_hi;
> + uint32_t carry = (uint32_t) carry_out << 16;
> +
> + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16;
> + uint32_t cross_sum_lo = cross_sum & 0xFFFF;
> + uint32_t cross_sum_hi = cross_sum >> 16;
> +
> + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
> + uint32_t interm = cross_sum_hi + y_hi_x_hi;
> + uint32_t low_accum_hi = low_accum >> 16;
> + uint32_t interm_plus_carry = interm + carry;
> +
> + result.v[i] = interm_plus_carry + low_accum_hi;
> + }
> +
> + return result;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded."
> 4 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded."
> 1 "forwprop2" } } */
> +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded."
> 1 "forwprop1" } } */
> diff --git a/gcc/testsuite/gcc.target/aarch64/long_mul.c
> b/gcc/testsuite/gcc.target/aarch64/long_mul.c
> new file mode 100644
> index 000000000000..2a4709ecbfd0
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/long_mul.c
> @@ -0,0 +1,58 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3" } */
> +
> +typedef __UINT32_TYPE__ uint32_t;
> +typedef __UINT64_TYPE__ uint64_t;
> +
> +/* 64-bit carry pattern for high part. */
> +uint64_t mulh_carry (uint64_t x, uint64_t y)
> +{
> + uint64_t x_lo = x & 0xFFFFFFFF;
> + uint64_t x_hi = x >> 32;
> + uint64_t y_lo = y & 0xFFFFFFFF;
> + uint64_t y_hi = y >> 32;
> + uint64_t y_lo_x_hi = y_lo * x_hi;
> + uint64_t y_hi_x_hi = y_hi * x_hi;
> + uint64_t y_hi_x_lo = y_hi * x_lo;
> + uint64_t y_lo_x_lo = y_lo * x_lo;
> + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi;
> + int carry_out = cross_sum < y_lo_x_hi;
> + uint64_t carry = (uint64_t) carry_out << 32;
> + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32;
> + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF;
> + uint64_t cross_sum_hi = cross_sum >> 32;
> + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
> + uint64_t interm = cross_sum_hi + y_hi_x_hi;
> + uint64_t low_accum_hi = low_accum >> 32;
> + uint64_t interm_plus_carry = interm + carry;
> + return interm_plus_carry + low_accum_hi;
> +}
> +
> +/* 32-bit carry pattern for high part. */
> +uint32_t mulh_carry_32 (uint32_t x, uint32_t y)
> +{
> + uint32_t x_lo = x & 0xFFFF;
> + uint32_t x_hi = x >> 16;
> + uint32_t y_lo = y & 0xFFFF;
> + uint32_t y_hi = y >> 16;
> + uint32_t y_lo_x_hi = y_lo * x_hi;
> + uint32_t y_hi_x_hi = y_hi * x_hi;
> + uint32_t y_hi_x_lo = y_hi * x_lo;
> + uint32_t y_lo_x_lo = y_lo * x_lo;
> + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi;
> + int carry_out = (cross_sum < y_lo_x_hi);
> + uint32_t carry = (uint32_t) carry_out << 16;
> + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16;
> + uint32_t cross_sum_lo = cross_sum & 0xFFFF;
> + uint32_t cross_sum_hi = cross_sum >> 16;
> + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
> + uint32_t interm = cross_sum_hi + y_hi_x_hi;
> + uint32_t low_accum_hi = low_accum >> 16;
> + uint32_t interm_plus_carry = interm + carry;
> + 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 } } */
> diff --git a/gcc/testsuite/gcc.target/i386/long_mul.c
> b/gcc/testsuite/gcc.target/i386/long_mul.c
> new file mode 100644
> index 000000000000..6ec87eb8dd21
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/i386/long_mul.c
> @@ -0,0 +1,58 @@
> +/* { dg-do compile { target { ! ia32 } } } */
> +/* { dg-options "-O3" } */
> +
> +typedef __UINT32_TYPE__ uint32_t;
> +typedef __UINT64_TYPE__ uint64_t;
> +
> +/* 64-bit carry pattern for high part. */
> +uint64_t mulh_carry (uint64_t x, uint64_t y)
> +{
> + uint64_t x_lo = x & 0xFFFFFFFF;
> + uint64_t x_hi = x >> 32;
> + uint64_t y_lo = y & 0xFFFFFFFF;
> + uint64_t y_hi = y >> 32;
> + uint64_t y_lo_x_hi = y_lo * x_hi;
> + uint64_t y_hi_x_hi = y_hi * x_hi;
> + uint64_t y_hi_x_lo = y_hi * x_lo;
> + uint64_t y_lo_x_lo = y_lo * x_lo;
> + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi;
> + int carry_out = cross_sum < y_lo_x_hi;
> + uint64_t carry = (uint64_t) carry_out << 32;
> + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32;
> + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF;
> + uint64_t cross_sum_hi = cross_sum >> 32;
> + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
> + uint64_t interm = cross_sum_hi + y_hi_x_hi;
> + uint64_t low_accum_hi = low_accum >> 32;
> + uint64_t interm_plus_carry = interm + carry;
> + return interm_plus_carry + low_accum_hi;
> +}
> +
> +/* 32-bit carry pattern for high part. */
> +uint32_t mulh_carry_32 (uint32_t x, uint32_t y)
> +{
> + uint32_t x_lo = x & 0xFFFF;
> + uint32_t x_hi = x >> 16;
> + uint32_t y_lo = y & 0xFFFF;
> + uint32_t y_hi = y >> 16;
> + uint32_t y_lo_x_hi = y_lo * x_hi;
> + uint32_t y_hi_x_hi = y_hi * x_hi;
> + uint32_t y_hi_x_lo = y_hi * x_lo;
> + uint32_t y_lo_x_lo = y_lo * x_lo;
> + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi;
> + int carry_out = (cross_sum < y_lo_x_hi);
> + uint32_t carry = (uint32_t) carry_out << 16;
> + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16;
> + uint32_t cross_sum_lo = cross_sum & 0xFFFF;
> + uint32_t cross_sum_hi = cross_sum >> 16;
> + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
> + uint32_t interm = cross_sum_hi + y_hi_x_hi;
> + uint32_t low_accum_hi = low_accum >> 16;
> + uint32_t interm_plus_carry = interm + carry;
> + 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 } } */
> diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
> index 12c07c99c9bd..3870bf17c0e0 100644
> --- a/gcc/tree-ssa-forwprop.cc
> +++ b/gcc/tree-ssa-forwprop.cc
> @@ -3592,6 +3592,693 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)
> return true;
> }
>
> +/* Match.pd functions to match long multiplication. */
> +
> +extern bool gimple_mul_hi (tree, tree *, tree (*)(tree));
> +extern bool gimple_mul_lo (tree, tree *, tree (*)(tree));
> +extern bool gimple_mul_hilo (tree, tree *, tree (*)(tree));
> +extern bool gimple_mul_lolo (tree, tree *, tree (*)(tree));
> +extern bool gimple_mul_hihi (tree, tree *, tree (*)(tree));
> +extern bool gimple_mul_cross_sum (tree, tree *, tree (*)(tree));
> +extern bool gimple_mul_low_accum (tree, tree *, tree (*)(tree));
> +extern bool gimple_mul_carry_cross_sum (tree, tree *, tree (*)(tree));
> +
> +/* Replace STMT with a high-part multiply of OP1 and OP2, emitted as
> + (N)(((2N) op1 * (2N) op2) >> N).
> + pass_optimize_widening_mul's convert_mult_to_widen and
> + convert_mult_to_highpart later rewrite this to a single
> + WIDEN_MULT_EXPR or MULT_HIGHPART_EXPR when the target supports it,
> + otherwise the 2N multiply expands directly. Emitting the canonical
> + widening shape keeps target-capability decisions in the layer that
> + already owns them. */
> +
> +static void
> +create_mul_high_seq (tree op1, tree op2, gimple *stmt)
> +{
> + tree op_type = TREE_TYPE (op1);
> + unsigned int width = TYPE_PRECISION (op_type);
> + tree wide_type = build_nonstandard_integer_type (width * 2, 1);
> +
> + location_t loc = gimple_location (stmt);
> + gimple_seq seq = NULL;
> +
> + tree wide_a = gimple_convert (&seq, loc, wide_type, op1);
> + tree wide_b = gimple_convert (&seq, loc, wide_type, op2);
> + tree wide_prod = gimple_build (&seq, loc, MULT_EXPR, wide_type,
> + wide_a, wide_b);
> + tree hi = gimple_build (&seq, loc, RSHIFT_EXPR, wide_type, wide_prod,
> + build_int_cst (integer_type_node, width));
> +
> + gimple *prod = gimple_build_assign (gimple_get_lhs (stmt), NOP_EXPR, hi);
> + gimple_set_location (prod, loc);
> + gimple_seq_add_stmt (&seq, prod);
> +
> + gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
> + gsi_replace_with_seq (&gsi, seq, true);
> +}
> +
> +/* Replace STMT with a low-part multiply of OP1 and OP2. */
> +
> +static void
> +create_mul_low_seq (tree op1, tree op2, gimple *stmt)
> +{
> + gimple *prod = gimple_build_assign (gimple_get_lhs (stmt),
> + MULT_EXPR, op1, op2);
> + gimple_set_location (prod, gimple_location (stmt));
> + gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
> + gsi_replace (&gsi, prod, true);
> +}
> +
> +/* Long-multiply fold framework.
> +
> + Walks the outer addition or bit_ior chain on a candidate statement,
> + classifies each summand against the atom match patterns from
> + match.pd, and looks the resulting multiset of (kind, extract) tuples
> + up in a table. On a hit, three cross-summand consistency checks
> + decide whether the wide multiply is emitted. */
> +
> +/* Widest match.pd atom (mul_low_accum) takes 6 captures; round up
> + to 8 for the scratch buffers below. */
> +static constexpr unsigned LONG_MUL_MAX_CAPTURES = 8;
> +
> +/* Longest variant in long_mul_table has 4 summands. */
> +static constexpr unsigned LONG_MUL_MAX_SUMMANDS = 4;
> +
> +enum long_mul_kind {
> + LMK_MUL_HIHI,
> + LMK_MUL_LOLO,
> + LMK_MUL_HILO,
> + LMK_CROSS_SUM,
> + LMK_LOW_ACCUM,
> + LMK_CARRY_CROSS_SUM,
> +};
> +
> +/* How the leaf wraps its inner kind. Carry kinds use LMX_NONE: their
> + match.pd pattern bakes the lshift in, so the leaf is already the
> + complete carry expression. */
> +
> +enum long_mul_extract {
> + LMX_NONE,
> + LMX_HI,
> + LMX_LO,
> + LMX_SHL_N,
> +};
> +
> +struct long_mul_summand {
> + long_mul_kind kind;
> + long_mul_extract extract;
> + tree op0, op1;
> + tree hilo0, hilo1, hilo2;
> + unsigned HOST_WIDE_INT shift;
> + unsigned HOST_WIDE_INT mask;
> +};
> +
> +/* Walk the OUTER addition or BIT_IOR chain rooted at STMT and collect
> + the leaf operands into LEAVES. Descends through single-use
> + intermediate stmts of the same code. Returns false once the leaf
> + count exceeds LONG_MUL_MAX_SUMMANDS, so an overlong chain bails
> + mid-walk instead of after a full traversal.
> +
> + If SHARED_DEF_OUT is non-NULL, record there the first inner stmt that
> + shares the outer code but has more than one use -- descending into it
> + would change semantics, so it stays as a leaf. Such a leaf often
> + classifies as something no row matches, silently disabling the fold;
> + the caller surfaces this as a dump-file hint. */
> +
> +static bool
> +long_mul_linearize_chain (gimple *stmt, tree_code outer, vec<tree> &leaves,
> + gimple **shared_def_out = NULL)
> +{
> + auto_vec<tree, 8> stack;
> + stack.safe_push (gimple_assign_rhs2 (stmt));
> + stack.safe_push (gimple_assign_rhs1 (stmt));
> +
> + while (!stack.is_empty ())
> + {
The biggest problem I have with this patch is why do you need a worklist here?
Since you are looking backwards and forwprop will retry the statement
if returns changed.
Do we need a worklist at all?
Shouldn't we just do a simple matching for the leaf? and then handle
that case first and then retry?
This has been my biggest concern for even the original patch which is
why I wanted to see it split up to see if you could remove it.
> + tree t = stack.pop ();
> + if (TREE_CODE (t) == SSA_NAME)
> + {
> + gimple *def = SSA_NAME_DEF_STMT (t);
> + if (def
> + && is_gimple_assign (def)
> + && gimple_assign_rhs_code (def) == outer)
> + {
> + if (has_single_use (t))
> + {
> + stack.safe_push (gimple_assign_rhs2 (def));
> + stack.safe_push (gimple_assign_rhs1 (def));
> + continue;
> + }
> + if (shared_def_out && !*shared_def_out)
> + *shared_def_out = def;
> + }
> + }
> + leaves.safe_push (t);
> + if (leaves.length () > LONG_MUL_MAX_SUMMANDS)
> + return false;
> + }
> + return !leaves.is_empty ();
> +}
> +
> +/* If EXPR is defined by LSHIFT_EXPR with a uhwi-valued amount, return
> + the shifted input via *INNER_OUT and the amount via *SHIFT_OUT. */
> +
> +static bool
> +long_mul_is_lshift_def (tree expr, tree *inner_out,
> + unsigned HOST_WIDE_INT *shift_out)
> +{
> + if (TREE_CODE (expr) != SSA_NAME)
> + return false;
> + gimple *def = SSA_NAME_DEF_STMT (expr);
> + if (!def || !is_gimple_assign (def)
> + || gimple_assign_rhs_code (def) != LSHIFT_EXPR)
> + return false;
> + tree amount = gimple_assign_rhs2 (def);
> + if (!tree_fits_uhwi_p (amount))
> + return false;
> + *inner_out = gimple_assign_rhs1 (def);
> + *shift_out = tree_to_uhwi (amount);
> + return true;
> +}
> +
> +/* Fill INFO's kind plus the captures from RES_OPS that the kind requires.
> + The kind itself determines how many (op0, op1) and hilo captures to
> + pick up from RES_OPS, and whether a baked-in shift is present. */
> +
> +static void
> +long_mul_set_summand (long_mul_summand *info, long_mul_kind kind,
> + const tree *res_ops)
> +{
> + info->kind = kind;
> + unsigned n_ops = 0;
> + unsigned n_hilos = 0;
> + int shift_idx = -1;
> + switch (kind)
> + {
> + case LMK_MUL_HIHI:
> + case LMK_MUL_LOLO:
> + case LMK_MUL_HILO:
> + n_ops = 2;
> + break;
> + case LMK_CROSS_SUM:
> + n_hilos = 2;
> + break;
> + case LMK_LOW_ACCUM:
> + n_ops = 2;
> + n_hilos = 2;
> + break;
> + case LMK_CARRY_CROSS_SUM:
> + n_hilos = 3;
> + shift_idx = 3;
> + break;
> + }
> + if (n_ops >= 1)
> + info->op0 = res_ops[0];
> + if (n_ops >= 2)
> + info->op1 = res_ops[1];
> + if (n_hilos >= 1)
> + info->hilo0 = res_ops[n_ops];
> + if (n_hilos >= 2)
> + info->hilo1 = res_ops[n_ops + 1];
> + if (n_hilos >= 3)
> + info->hilo2 = res_ops[n_ops + 2];
> + if (shift_idx >= 0)
> + info->shift = tree_to_uhwi (res_ops[shift_idx]);
> +}
> +
> +/* Classify LEAF as a carry-kind summand. The lshift amount is baked
> + into mul_carry_cross_sum, so it's tried before any branch that looks
> + for a generic (X >> N) or (X << N) wrapper. */
> +
> +static bool
> +long_mul_classify_carry (tree leaf, long_mul_summand *info)
> +{
> + tree res_ops[LONG_MUL_MAX_CAPTURES];
> + if (gimple_mul_carry_cross_sum (leaf, res_ops, NULL))
> + {
> + long_mul_set_summand (info, LMK_CARRY_CROSS_SUM, res_ops);
> + return true;
> + }
> + return false;
> +}
> +
> +/* Plus-based summand kinds shared by the (X >> SHIFT) and (X << SHIFT)
> + classifiers. */
> +
> +static bool
> +long_mul_classify_plus_kinds (tree inner, long_mul_summand *info)
> +{
> + tree res_ops[LONG_MUL_MAX_CAPTURES];
> + if (gimple_mul_low_accum (inner, res_ops, NULL))
> + {
> + long_mul_set_summand (info, LMK_LOW_ACCUM, 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. */
> +
> +static bool
> +long_mul_classify_hi_extract (tree inner, unsigned HOST_WIDE_INT shift,
> + long_mul_summand *info)
> +{
> + tree res_ops[LONG_MUL_MAX_CAPTURES];
> + info->extract = LMX_HI;
> + info->shift = shift;
> + if (gimple_mul_hilo (inner, res_ops, NULL))
> + {
> + long_mul_set_summand (info, LMK_MUL_HILO, res_ops);
> + return true;
> + }
> + if (long_mul_classify_plus_kinds (inner, info))
> + return true;
> + if (gimple_mul_cross_sum (inner, res_ops, NULL))
> + {
> + long_mul_set_summand (info, LMK_CROSS_SUM, res_ops);
> + return true;
> + }
> + return false;
> +}
> +
> +/* Classify INNER -- already unwrapped from an outer (X & MASK) -- as
> + a low-half-masked summand. */
> +
> +static bool
> +long_mul_classify_lo_extract (tree inner, unsigned HOST_WIDE_INT mask,
> + long_mul_summand *info)
> +{
> + tree res_ops[LONG_MUL_MAX_CAPTURES];
> + info->extract = LMX_LO;
> + info->mask = mask;
> + if (gimple_mul_lolo (inner, res_ops, NULL))
> + {
> + long_mul_set_summand (info, LMK_MUL_LOLO, res_ops);
> + return true;
> + }
> + return false;
> +}
> +
> +/* 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). */
> +
> +static bool
> +long_mul_classify_shl_extract (tree inner, unsigned HOST_WIDE_INT shift,
> + long_mul_summand *info)
> +{
> + tree res_ops[LONG_MUL_MAX_CAPTURES];
> + info->extract = LMX_SHL_N;
> + info->shift = shift;
> + if (long_mul_classify_plus_kinds (inner, info))
> + return true;
> + if (gimple_mul_cross_sum (inner, res_ops, NULL))
> + {
> + long_mul_set_summand (info, LMK_CROSS_SUM, res_ops);
> + return true;
> + }
> + return false;
> +}
> +
> +/* Classify LEAF as one of the bare-kind summands (no extraction
> + wrapper): mul_hihi or mul_lolo standing on their own. */
> +
> +static bool
> +long_mul_classify_bare (tree leaf, long_mul_summand *info)
> +{
> + tree res_ops[LONG_MUL_MAX_CAPTURES];
> + if (gimple_mul_hihi (leaf, res_ops, NULL))
> + {
> + long_mul_set_summand (info, LMK_MUL_HIHI, res_ops);
> + return true;
> + }
> + if (gimple_mul_lolo (leaf, res_ops, NULL))
> + {
> + long_mul_set_summand (info, LMK_MUL_LOLO, res_ops);
> + return true;
> + }
> + return false;
> +}
> +
> +/* Classify LEAF as one of the long-multiply summand shapes. On success,
> + fill *INFO with the kind, extract, captured operands and shift/mask.
> + Dispatches to per-extract helpers; the order matters because the
> + carry kinds bake an lshift into the pattern and would otherwise be
> + misread by the (X << N) branch. */
> +
> +static bool
> +long_mul_classify_summand (tree leaf, long_mul_summand *info)
> +{
> + tree res_ops[LONG_MUL_MAX_CAPTURES];
> + *info = {};
> +
> + if (long_mul_classify_carry (leaf, info))
> + return true;
> +
> + if (gimple_mul_hi (leaf, res_ops, NULL))
> + return long_mul_classify_hi_extract (res_ops[0],
> + tree_to_uhwi (res_ops[1]), info);
> +
> + if (gimple_mul_lo (leaf, res_ops, NULL))
> + return long_mul_classify_lo_extract (res_ops[0],
> + tree_to_uhwi (res_ops[1]), info);
> +
> + tree inner;
> + unsigned HOST_WIDE_INT shift;
> + if (long_mul_is_lshift_def (leaf, &inner, &shift))
> + return long_mul_classify_shl_extract (inner, shift, info);
> +
> + return long_mul_classify_bare (leaf, info);
> +}
> +
> +/* qsort comparator: sort summands by (kind, extract) to put a multiset
> + into canonical order for table lookup. Unstable sort within a tie is
> + harmless: no row in long_mul_table pairs distinct subterms under the
> + same (kind, extract), and long_mul_check_consistency cross-validates
> + that matching summands share one canonical (op0, op1). */
> +
> +static int
> +long_mul_summand_compare (const void *a, const void *b)
> +{
> + const long_mul_summand *sa = (const long_mul_summand *) a;
> + const long_mul_summand *sb = (const long_mul_summand *) b;
> + if (sa->kind != sb->kind)
> + return (int) sa->kind - (int) sb->kind;
> + return (int) sa->extract - (int) sb->extract;
> +}
> +
> +/* One row of the long-multiply variant table. COUNT is how many entries
> + of SIG carry the row's signature (2 to LONG_MUL_MAX_SUMMANDS); a row
> + with fewer summands leaves the remaining SIG entries zero-initialized.
> + Those zeros are not a terminator -- {LMK_MUL_HIHI, LMX_NONE} is itself a
> + valid signature -- so long_mul_signature_matches is bounded by COUNT,
> + never by a sentinel entry. */
> +
> +struct long_mul_row {
> + enum long_mul_row_part { HIGH_PART, LOW_PART } part;
> + tree_code outer;
> + unsigned char count;
> + struct {
> + long_mul_kind kind;
> + long_mul_extract extract;
> + } sig[LONG_MUL_MAX_SUMMANDS];
> + bool (*extra_check) (const vec<long_mul_summand> &, gimple *);
> +};
> +
> +/* True if (A, B) is the same pair as (OP0, OP1) in either order. */
> +
> +static inline bool
> +long_mul_same_ops (tree a, tree b, tree op0, tree op1)
> +{
> + return (a == op0 && b == op1) || (a == op1 && b == op0);
> +}
> +
> +/* True if H is a cross-half product of (OP0, OP1) -- gimple_mul_hilo
> + recognizes it and its captured operands match the pair. */
> +
> +static bool
> +long_mul_is_cross_half (tree h, tree op0, tree op1)
> +{
> + tree scratch[LONG_MUL_MAX_CAPTURES];
> + return gimple_mul_hilo (h, scratch, NULL)
> + && long_mul_same_ops (scratch[0], scratch[1], op0, op1);
> +}
> +
> +/* Orientation of the mul_hilo capture H relative to (OP0, OP1):
> + returns 0 for high(OP0)*low(OP1), 1 for high(OP1)*low(OP0), or -1
> + if H does not decompose that way. A cross-sum of two mul_hilos must
> + see one of each orientation -- otherwise a doubled factor would fold
> + to the wrong value. (In a self-multiply the two orientations
> + coincide; see the OP0 == OP1 bypass in long_mul_check_consistency.) */
> +
> +static int
> +long_mul_hilo_orientation (tree h, tree op0, tree op1)
> +{
> + tree scratch[LONG_MUL_MAX_CAPTURES];
> + if (!gimple_mul_hilo (h, scratch, NULL))
> + return -1;
> + if (scratch[0] == op0 && scratch[1] == op1)
> + return 0;
> + if (scratch[0] == op1 && scratch[1] == op0)
> + return 1;
> + return -1;
> +}
> +
> +/* Find the first summand that carries operand captures, and return its
> + (op0, op1) pair in *OP0_OUT / *OP1_OUT. Returns false if no summand
> + provides them. */
> +
> +static bool
> +long_mul_canonical_ops (const vec<long_mul_summand> &summands,
> + tree *op0_out, tree *op1_out)
> +{
> + for (const long_mul_summand &s : summands)
> + if (s.op0)
> + {
> + *op0_out = s.op0;
> + *op1_out = s.op1;
> + return true;
> + }
> + return false;
> +}
> +
> +/* Run the cross-summand validation invariants and return the canonical
> + (op0, op1). Returns false unless all summands that carry operands use
> + the same (op0, op1) pair (in either order), every LMX_HI/LMX_SHL_N shift
> + equals halfwidth, every captured hilo is a true cross-half product of
> + (op0, op1), and every cross-half pair (both those inside a single
> + mul_cross_sum-bearing summand and those spread across separate
> + LMK_MUL_HILO summands) contains one of each orientation. */
> +
> +static bool
> +long_mul_check_consistency (const vec<long_mul_summand> &summands,
> + tree *op0_out, tree *op1_out)
> +{
> + tree op0, op1;
> + if (!long_mul_canonical_ops (summands, &op0, &op1))
> + return false;
> +
> + tree op_type = TREE_TYPE (op0);
> + if (!INTEGRAL_TYPE_P (op_type)
> + || TYPE_PRECISION (op_type) % 2 != 0)
> + return false;
> + unsigned int halfwidth = TYPE_PRECISION (op_type) / 2;
> +
> + /* Self-multiply (x*x) collapses the two cross-halves onto one value,
> + so the complementarity constraint is a trivial no-op there. */
> + bool need_orient = op0 != op1;
> + int mul_hilo_orient[2] = { 0, 0 };
> +
> + for (const long_mul_summand &s : summands)
> + {
> + if (s.op0 && !long_mul_same_ops (s.op0, s.op1, op0, op1))
> + return false;
> + if ((s.extract == LMX_HI || s.extract == LMX_SHL_N)
> + && s.shift != halfwidth)
> + return false;
> + tree hilos[3] = { s.hilo0, s.hilo1, s.hilo2 };
> + for (tree h : hilos)
> + if (h && !long_mul_is_cross_half (h, op0, op1))
> + return false;
> +
> + if (!need_orient)
> + continue;
> +
> + /* The two cross-sum operands are the last two non-null hilos:
> + (hilo1, hilo2) for the CARRY_*_SUM kinds, (hilo0, hilo1) for
> + the CROSS_SUM / SUM / ACCUM / LADDER_SUM kinds, none for the
> + rest. */
> + tree a = NULL_TREE;
> + tree b = NULL_TREE;
> + if (s.hilo2)
> + {
> + a = s.hilo1;
> + b = s.hilo2;
> + }
> + else if (s.hilo1)
> + {
> + a = s.hilo0;
> + b = s.hilo1;
> + }
> + if (a && b
> + && (long_mul_hilo_orientation (a, op0, op1)
> + == long_mul_hilo_orientation (b, op0, op1)))
> + return false;
> +
> + /* Two LMK_MUL_HILO summands (the two-hilos ladder form) stand for
> + the two cross-halves separately; count orientations and require
> + the pair to be complementary. s.op0/op1 is already validated to
> + match (op0, op1) in some order above. */
> + if (s.kind == LMK_MUL_HILO && s.op0)
> + mul_hilo_orient[s.op0 == op1]++;
> + }
> +
> + if (mul_hilo_orient[0] + mul_hilo_orient[1] >= 2
> + && (mul_hilo_orient[0] == 0 || mul_hilo_orient[1] == 0))
> + return false;
> +
> + *op0_out = op0;
> + *op1_out = op1;
> + return true;
> +}
> +
> +/* Compare the (already-sorted) SUMMANDS multiset against ROW.sig. */
> +
> +static bool
> +long_mul_signature_matches (const vec<long_mul_summand> &summands,
> + const long_mul_row &row)
> +{
> + if (row.count != summands.length ())
> + return false;
> + for (unsigned i = 0; i < row.count; i++)
> + if (summands[i].kind != row.sig[i].kind
> + || summands[i].extract != row.sig[i].extract)
> + return false;
> + return true;
> +}
> +
> +/* Long-multiply variant table. Each row enumerates the multiset of
> + (kind, extract) summands that compose one long-multiply form. Rows
> + are sorted by long_mul_summand_compare, matching the input summands'
> + sort order, so a plain element-wise compare suffices. Rows describe
> + unsigned schoolbook expansions on an even-width 2N-bit type split at
> + half-width N; EXTRA_CHECK carries invariants the (kind, extract)
> + signature cannot express. */
> +
> +static const long_mul_row long_mul_table[] = {
> + /* HIGH-PART fold. Notation: xh, xl, yh, yl are the half-width pieces
> + of x and y; N is the half-width. cross_sum = xh*yl + xl*yh; hilo is
> + either xh*yl or xl*yh (consumers validate the operand shape). */
> + /* xh*yh + (low_accum >> N) + (cross_sum >> N)
> + + ((hilo > cross_sum) << N),
> + low_accum = (xl*yl >> N) + (cross_sum & mask). */
> + { long_mul_row::HIGH_PART, PLUS_EXPR, 4,
> + { { LMK_MUL_HIHI, LMX_NONE },
> + { LMK_CROSS_SUM, LMX_HI },
> + { LMK_LOW_ACCUM, LMX_HI },
> + { LMK_CARRY_CROSS_SUM, LMX_NONE } },
> + NULL },
> + /* LOW-PART fold. Recover the lower 2N bits from xl*yl plus a
> + shifted cross-half term. Notation as for the HIGH-PART row above. */
> + /* (xl*yl & mask) | (low_accum << N),
> + low_accum = (xl*yl >> N) + (cross_sum & mask). */
> + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2,
> + { { LMK_MUL_LOLO, LMX_LO },
> + { LMK_LOW_ACCUM, LMX_SHL_N } },
> + NULL },
> +};
> +
> +/* If a multi-used inner addition (sharing the chain's outer code) blocked
> + linearization of a long-mul candidate, emit a dump-file hint pointing
> + at it. */
> +
> +static void
> +long_mul_hint_shared_intermediate (gimple *shared_def)
> +{
> + if (!shared_def || !dump_file || !(dump_flags & TDF_DETAILS))
> + return;
> + fprintf (dump_file, "long-mul fold rejected: shared intermediate at ");
> + print_gimple_stmt (dump_file, shared_def, 0, TDF_SLIM);
> +}
> +
> +/* Top-level entry for long-multiply folding. Walks STMT's outer
> + addition or BIT_IOR chain, classifies the summands, and dispatches
> + to create_mul_high_seq / create_mul_low_seq if the multiset matches
> + a known long-multiply form. Returns true on success. */
> +
> +static bool
> +match_long_mul (gimple *stmt)
> +{
> + if (!is_gimple_assign (stmt))
> + return false;
> + tree_code outer = gimple_assign_rhs_code (stmt);
> + if (outer != PLUS_EXPR && outer != BIT_IOR_EXPR)
> + return false;
> +
> + /* Skip non-candidate adds (signed, pointer, odd-width) before walking the
> + chain. No legitimate long-mul leaf has a type the atoms would reject;
> + this just avoids the linearize/classify work on every other PLUS/IOR.
> */
> + tree lhs_type = TREE_TYPE (gimple_get_lhs (stmt));
> + if (!INTEGRAL_TYPE_P (lhs_type)
> + || !TYPE_UNSIGNED (lhs_type)
> + || TYPE_PRECISION (lhs_type) % 2 != 0)
> + return false;
> +
> + auto_vec<tree, LONG_MUL_MAX_SUMMANDS + 1> leaves;
> + gimple *shared_def = NULL;
> + if (!long_mul_linearize_chain (stmt, outer, leaves, &shared_def))
> + return false;
> + if (leaves.length () < 2)
> + return false;
> +
> + auto_vec<long_mul_summand, LONG_MUL_MAX_SUMMANDS> summands;
> + for (tree leaf : leaves)
> + {
> + long_mul_summand s;
> + if (!long_mul_classify_summand (leaf, &s))
> + {
> + long_mul_hint_shared_intermediate (shared_def);
> + return false;
> + }
> + summands.quick_push (s);
> + }
> + summands.qsort (long_mul_summand_compare);
> +
> + /* HIGH_PART rows emit a 2N-bit multiply that is consumed by
> + pass_optimize_widening_mul (WIDEN_MULT_EXPR conversion or
> + longhand re-synthesis) or by expand (supported 2N mode);
> + LOW_PART rows emit a plain MULT_EXPR. Emission needs only a 2N
> + mode to exist in the mode table -- capability is settled on the
> + lowering side. */
> + scalar_int_mode mode, wide_mode;
> + bool can_emit_high
> + = is_a <scalar_int_mode> (TYPE_MODE (lhs_type), &mode)
> + && GET_MODE_2XWIDER_MODE (mode).exists (&wide_mode);
> +
> + for (const long_mul_row &row : long_mul_table)
> + {
> + if (row.outer != outer
> + || (row.part == long_mul_row::HIGH_PART && !can_emit_high)
> + || !long_mul_signature_matches (summands, row))
> + continue;
> +
> + tree op0, op1;
> + if (!long_mul_check_consistency (summands, &op0, &op1))
> + continue;
> +
> + /* Do not emit the wide chain when an operand is subject to
> + abnormal coalescing: the widening_mul-side consumers refuse
> + such operands (see convert_mult_to_widen), which would leave
> + the chain without a consumer. */
> + if (row.part == long_mul_row::HIGH_PART
> + && ((TREE_CODE (op0) == SSA_NAME
> + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
> + || (TREE_CODE (op1) == SSA_NAME
> + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
> + continue;
> +
> + if (row.extra_check && !row.extra_check (summands, stmt))
> + continue;
> +
> + if (row.part == long_mul_row::HIGH_PART)
> + {
> + create_mul_high_seq (op0, op1, stmt);
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + fprintf (dump_file, "Long multiplication high part folded.\n");
> + return true;
> + }
> + create_mul_low_seq (op0, op1, stmt);
> + if (dump_file && (dump_flags & TDF_DETAILS))
> + fprintf (dump_file, "Long multiplication low part folded.\n");
> + return true;
> + }
> +
> + long_mul_hint_shared_intermediate (shared_def);
> + return false;
> +}
>
> /* Determine whether applying the 2 permutations (mask1 then mask2)
> gives back one of the input. */
> @@ -5851,11 +6538,15 @@ pass_forwprop::execute (function *fun)
> }
> else if (TREE_CODE_CLASS (code) == tcc_comparison)
> changed |= forward_propagate_into_comparison (&gsi);
> - else if ((code == PLUS_EXPR
> - || code == BIT_IOR_EXPR
> - || code == BIT_XOR_EXPR)
> - && simplify_rotate (&gsi))
> - changed = true;
> + else if ((code == PLUS_EXPR || code == BIT_IOR_EXPR))
> + {
> + bool folded = match_long_mul (stmt);
> + if (!folded)
> + folded = simplify_rotate (&gsi);
> + changed |= folded;
> + }
> + else if (code == BIT_XOR_EXPR)
> + changed |= simplify_rotate (&gsi);
> else if (code == VEC_PERM_EXPR)
> changed |= simplify_permutation (&gsi);
> else if (code == CONSTRUCTOR
> --
> 2.55.0
>
