Re: [PATCH v7 1/7] forwprop: Match and fold the long-multiply carry form [PR107090]
Konstantinos Eleftheriou <[email protected]> Mon, 3 Aug 2026 19:03:04 +0300
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <CAAMozG9uSyfYVMDm5A7apw8kP0D__=W7X3FtobDXgPSrEss2eA@mail.gmail.com> |
Hi all, We sent a new version based on your suggestions. We had to update the widening_mul side too, as we hit some `expand_mult` ICEs on ARM. So, an operand wider than N is now split into N-bit halves and combined rather than rejected, narrow_long_mul_low_half rewrites a 2N product whose uses read only its low N bits to an N-bit multiply and a value holding a product's high N bits now comes from the product's own operands instead of the 2N shift. More details in the section for version's 8 changes. Thanks, Konstantinos On Fri, Jul 24, 2026 at 3:43 PM Richard Biener <[email protected]> wrote: > On Fri, Jul 24, 2026 at 9:19 AM Konstantinos Eleftheriou > <[email protected]> wrote: > > > > Hi Andrew, > > > > On Fri, Jul 24, 2026 at 3:53 AM Andrea Pinski < > [email protected]> wrote: > >> > >> 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? > > > > That's not a worklist. It's a one-shot linearization of a single > associative PLUS/OR > > into its summands. It runs once per root, holds at most 4 entries, and > doesn't revisit statements. > >> > >> Since you are looking backwards and forwprop will retry the statement > >> if returns changed. > > > > There are no intermediate changes. We're not folding anything until the > whole pattern > > matches. > >> > >> Do we need a worklist at all? > > > > We need the linearization. Recognition is a multiset lookup: we collect > all summands, sort them, > > and look the signature up in `long_mul_table`. A single summand (xh*yh, > a cross-sum) matches > > no row, so there's nothing to fold incrementally. > >> > >> Shouldn't we just do a simple matching for the leaf? and then handle > >> that case first and then retry? > > > > The chain is associativity/commutativity-variant. Flatten + sort lets > one table row cover every shape. > > Matching immediate operands only would push that into a combinatorial > set of patterns. > >> > >> 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. > > > > We could add a comment to clarify this. > > We could limit starts with sth similar to how BB vect limits analyzing > reductions: > > /* Should be the chain end. */ > && (!single_imm_use (gimple_assign_lhs (assign), > &use_p, &use_stmt) > || !is_gimple_assign (use_stmt) > || (gimple_assign_rhs_code (use_stmt) != code > && ((code != PLUS_EXPR && code != MINUS_EXPR) > || (gimple_assign_rhs_code (use_stmt) > != (code == PLUS_EXPR ? MINUS_EXPR : > PLUS_EXPR)))))) > > and "discard" irrelevant entries (preserving them, of course). > > Richard. > > > > > Thanks, > > Konstantinos > >> > >> > + 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 > >> > >