On Thu, May 28, 2026 at 12:09 AM Konstantinos Eleftheriou <[email protected]> wrote: > > Recognize longhand wide-multiplication idioms and fold them into > MULT_HIGHPART_EXPR (or a widening multiply followed by a right shift) > for the high part, and a plain MULT_EXPR for the low part. > > Based on LLVM's approach: > https://github.com/llvm/llvm-project/pull/168396 > > The decomposed patterns differ in how they propagate the carry from > the cross-product addition: > > - carry: single overflow comparison on the cross-sum > - carry-long: cross-carry with separate high/low accumulation > - two-carry: both cross-carry and low-carry as separate comparisons > - ladder: sequential accumulation without explicit carry comparison > - ladder-long: ladder with separate high/low accumulation > - low-plus: low part as a direct sum of partial products > > Atom-level pattern recognition is implemented via match patterns in > match.pd (mul_hi, mul_lo, mul_hilo, mul_cross_sum, mul_carry_*, ...). > The composite recognition that ties atoms into a long-multiplication > chain is performed in forwprop by match_long_mul: it linearises 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. > > Folding is gated on a new m_long_mul_fold_p pass parameter, enabled > from forwprop2 onwards. This keeps the fold out of the pre-IPA > forwprop1, where target capability queries are unsafe under offload > compilation, without adding a runtime predicate. At emission, the > target's support for the lowered form is verified via > can_mult_highpart_p before MULT_HIGHPART_EXPR is produced.
The idea of this new gate here is wrong. I think we should be able to produce decent code without mult high part optabs. Let widdening_multiply pass generate MULT_HIGHPART_EXPR from the code if needed. Basically don't add that part of the optimization in forward prop. If we need to improve widdening_multiply to do the right thing; let's do it there. Thanks, Andrea > > 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] > > Sealcrypto shows a 25% improvement on Neoverse-N1 and 59% on Zen4. > > Bootstrapped/regtested on AArch64, x86-64 and PowerPC. > > PR tree-optimization/107090 > > gcc/ChangeLog: > > * match.pd: Add atom match patterns for long-multiply > recognition (mul_hi, mul_lo, mul_hilo, mul_lolo, mul_hihi, > mul_cross_sum, mul_low_sum, mul_low_accum, mul_carry_low, > mul_carry_low_sum, mul_carry_cross_sum, mul_ladder_sum1/2/3, > mul_ladder_part_sum). > * passes.def: Pass the new m_long_mul_fold_p parameter to > pass_forwprop instances from forwprop2 onwards. > * tree-ssa-forwprop.cc (pass_forwprop): Add m_long_mul_fold_p > pass parameter. > (create_mul_high_seq): New, emits MULT_HIGHPART_EXPR after > can_mult_highpart_p check. > (create_mul_low_seq): New, emits MULT_EXPR. > (match_long_mul): New, top-level entry: linearises 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. > (long_mul_table): New table of long-multiply variants. > (pass_forwprop::execute): Call match_long_mul when > m_long_mul_fold_p is set, on PLUS_EXPR and BIT_IOR_EXPR > statements. > > gcc/testsuite/ChangeLog: > > * gcc.dg/tree-ssa/long-mul-carry.c: New test. > * gcc.dg/tree-ssa/long-mul-ladder.c: New test. > * gcc.dg/tree-ssa/long-mul-low-plus.c: New test. > * gcc.dg/tree-ssa/long-mul-two-carry.c: New test. > * gcc.dg/tree-ssa/long-mul-partial.c: New test. > * gcc.dg/tree-ssa/long-mul-boundary.c: New test. > * gcc.dg/tree-ssa/long-mul-boundary-64.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]> > --- > > Changes in v4: > - 1/2: > - Rebuild the guard with per-conjunct reasoning: require both > INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type) and > INTEGRAL_TYPE_P (TREE_TYPE (@0)) && TYPE_UNSIGNED (TREE_TYPE (@0)). > The v3 swap of TYPE_UNSIGNED (type) for TYPE_UNSIGNED > (TREE_TYPE (@0)) had let signed result types with @3 == INT_MIN > slip through into a shift-by-(-1). > - Drop the "carry diamond" CFG-shape nickname. Describe the > transform in terms of the data shape it operates on (conditional > carry-add) rather than CFG topology. Rename the profitability > helper to fold_cond_carry_add_profitable_p; rename phiopt > regression tests to test_cond_carry_add*. > - 2/2: > - Pass-parameter gating: pass_forwprop takes a new > m_long_mul_fold_p, set true for forwprop2 onwards. This keeps > the fold out of pre-IPA forwprop1, where target capability > queries are unsafe under offload compilation, without adding a > runtime predicate. > - Lower the high-part to MULT_HIGHPART_EXPR and rely on RTL > expansion to pick native umul_highpart, a widening multiply, or > a synthesised sequence. Emission is gated on > can_mult_highpart_p. > - Structural redesign: per-variant fold_mul_* functions > consolidated into a single linearise + classify + table-lookup > framework (long_mul_table, match_long_mul, > long_mul_classify_summand, long_mul_check_consistency). Each > variant is now a row in long_mul_table; consistency checks are > shared across rows. > - Fast-fail prefilters in match_long_mul: LHS-type prefilter at > entry (no legitimate long-mul leaf has a signed / pointer / > float / odd-width type) and a can_mult_highpart_p probe before > the row loop to skip HIGH_PART rows on unsupported targets. > - Bound long_mul_linearize_chain mid-walk by LONG_MUL_MAX_SUMMANDS > so an overlong addition / BIT_IOR chain bails immediately rather > than after a full traversal. > - Emit a dump-file hint pointing at the shared inner addition when > long-mul folding rejects a chain because of a multi-used > intermediate (caching the partial sum into a single-use SSA > name normally enables the fold). > > Changes in v3: > - Moved carry-diamond flattening from forwprop to match.pd, > replacing ~460 lines of C++ with a 17-line match.pd pattern. > - Two-carry test scans forwprop3 (the first forwprop after phiopt2, > since early phiopt restricts which tree codes are allowed). > - Set location for new sequences. > - Updated mul_carry_low pattern. > - Added the `mul_low_plus` pattern. > - Fixed formatting issues. > > Changes in v2: > - Fixed the testcases by separating the high part's fold count for > 32-bit and 64-bit targets. > > gcc/match.pd | 152 +++ > gcc/passes.def | 8 +- > gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c | 1 + > .../gcc.dg/tree-ssa/long-mul-boundary-64.c | 276 ++++++ > .../gcc.dg/tree-ssa/long-mul-boundary.c | 272 ++++++ > .../gcc.dg/tree-ssa/long-mul-carry.c | 310 ++++++ > .../gcc.dg/tree-ssa/long-mul-ladder.c | 328 +++++++ > .../gcc.dg/tree-ssa/long-mul-low-plus.c | 54 ++ > .../gcc.dg/tree-ssa/long-mul-partial.c | 119 +++ > .../gcc.dg/tree-ssa/long-mul-two-carry.c | 113 +++ > gcc/testsuite/gcc.target/aarch64/long_mul.c | 100 ++ > gcc/testsuite/gcc.target/i386/long_mul.c | 100 ++ > gcc/tree-ssa-forwprop.cc | 904 +++++++++++++++++- > 13 files changed, 2728 insertions(+), 9 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-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 cb7cbf9971c7..510046a7872b 100644 > --- a/gcc/match.pd > +++ b/gcc/match.pd > @@ -11826,6 +11826,158 @@ and, > && compare_tree_int (@c16, 16) == 0 > && compare_tree_int (@c32, 32) == 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 (check_hilo_and_ops). */ > +(match (mul_cross_sum @mul_hilo0 @mul_hilo1) > + (plus:c @mul_hilo0 @mul_hilo1)) > +/* Low sum: cross_sum + (xl*yl >> N). */ > +(match (mul_low_sum @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (mul_cross_sum @mul_hilo0 @mul_hilo1) > + (mul_hi > + (mul_lolo @op0 @op1 INTEGER_CST@1) > + INTEGER_CST@0))) > +/* Carry from low-sum overflow: (cast?) (hilo > low_sum) << N. > + No explicit type/width guard needed: mul_low_sum delegates to > + mul_cross_sum + mul_hi + mul_lolo, which provide deep structural > + constraints, and @0 ties the shift amount to the inner constants. */ > +(match (mul_carry_low_sum @op0 @op1 @mul_hilo0 @mul_hilo1 @mul_hilo2 @0 @1) > + (lshift > + (convert? (gt > + @mul_hilo0 > + (mul_low_sum @op0 @op1 @mul_hilo1 @mul_hilo2 INTEGER_CST@0 > + INTEGER_CST@1))) > + INTEGER_CST@0)) > +/* 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)))) > +/* Carry from addition overflow: (cast?) (a > a + b). > + :c on gt also matches the LT form: (cast?) (a + b < a). */ > +(match (mul_carry_low @0 @1) > + (convert? > + (gt:c @0 (plus:c @1 @0))) > + (with { tree op_type = TREE_TYPE (@0); } > + (if (INTEGRAL_TYPE_P (op_type) && TYPE_UNSIGNED (op_type))))) > +/* 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))) > +/* Ladder sum form 1: (hilo0 & mask) + hilo1 + (xl*yl >> N). > + First variant: @mul_hilo1 is inside the inner plus:c alongside > + (mul_lo ...). */ > +(match (mul_ladder_sum1 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (plus:c > + (mul_lo > + @mul_hilo0 > + INTEGER_CST@0) > + @mul_hilo1) > + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1))) > +/* Second variant: @mul_hilo1 is the outermost addend and could match > + anything, so guard that its definition is a MULT_EXPR. */ > +(match (mul_ladder_sum1 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (plus:c > + (mul_lo @mul_hilo0 INTEGER_CST@0) > + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1)) > + @mul_hilo1) > + (with { > + tree_code mul_hilo_code = TREE_CODE (@mul_hilo1); > + tree_code rhs_code = ERROR_MARK; > + if (mul_hilo_code == SSA_NAME) > + { > + gimple *def = SSA_NAME_DEF_STMT (@mul_hilo1); > + if (def && gimple_code (def) == GIMPLE_ASSIGN) > + rhs_code = gimple_assign_rhs_code (def); > + } } > + (if (rhs_code == MULT_EXPR)))) > +/* Partial ladder sum: (xl*yl >> N) + hilo. */ > +(match (mul_ladder_part_sum @op0 @op1 @mul_hilo0 @0 @1) > + (plus:c > + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1) > + @mul_hilo0)) > +/* Ladder sum form 2: (ladder_part_sum & mask) + hilo. */ > +(match (mul_ladder_sum2 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (mul_lo > + (mul_ladder_part_sum @op0 @op1 @mul_hilo0 INTEGER_CST@0 INTEGER_CST@1) > + INTEGER_CST@0) > + @mul_hilo1)) > +/* Ladder sum form 3: (hilo0 & mask) + (hilo1 & mask) + (xl*yl >> N). */ > +(match (mul_ladder_sum3 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (plus:c > + (mul_lo @mul_hilo0 INTEGER_CST@0) > + (mul_lo @mul_hilo1 INTEGER_CST@0)) > + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1))) > +(match (mul_ladder_sum3 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) > + (plus:c > + (plus:c > + (mul_lo @mul_hilo0 INTEGER_CST@0) > + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1)) > + (mul_lo @mul_hilo1 INTEGER_CST@0))) > +#endif > + > /* Floatint point/integer comparison and integer->integer > or floating point -> float point conversion. */ > (match (cond_expr_convert_p @0 @2 @3 @6) > diff --git a/gcc/passes.def b/gcc/passes.def > index cdddb87302f6..0bfd63d6d3df 100644 > --- a/gcc/passes.def > +++ b/gcc/passes.def > @@ -226,7 +226,7 @@ along with GCC; see the file COPYING3. If not see > NEXT_PASS (pass_complete_unrolli); > NEXT_PASS (pass_backprop); > NEXT_PASS (pass_phiprop); > - NEXT_PASS (pass_forwprop, /*full_walk=*/true); > + NEXT_PASS (pass_forwprop, /*full_walk=*/true, /*last=*/false, > /*long_mul_fold_p=*/true); > /* pass_build_alias is a dummy pass that ensures that we > execute TODO_rebuild_alias at this point. */ > NEXT_PASS (pass_build_alias); > @@ -266,7 +266,7 @@ along with GCC; see the file COPYING3. If not see > NEXT_PASS (pass_isolate_erroneous_paths); > NEXT_PASS (pass_reassoc, true /* early_p */); > NEXT_PASS (pass_dce); > - NEXT_PASS (pass_forwprop); > + NEXT_PASS (pass_forwprop, /*full_walk=*/false, /*last=*/false, > /*long_mul_fold_p=*/true); > NEXT_PASS (pass_phiopt, false /* early_p */); > NEXT_PASS (pass_ccp, true /* nonzero_p */); > /* After CCP we rewrite no longer addressed locals into SSA > @@ -368,7 +368,7 @@ along with GCC; see the file COPYING3. If not see > NEXT_PASS (pass_dce, true /* update_address_taken_p */, true /* > remove_unused_locals */); > /* After late DCE we rewrite no longer addressed locals into SSA > form if possible. */ > - NEXT_PASS (pass_forwprop, /*full_walk=*/false, /*last=*/true); > + NEXT_PASS (pass_forwprop, /*full_walk=*/false, /*last=*/true, > /*long_mul_fold_p=*/true); > NEXT_PASS (pass_sink_code, true /* unsplit edges */); > NEXT_PASS (pass_phiopt, false /* early_p */); > NEXT_PASS (pass_optimize_widening_mul); > @@ -408,7 +408,7 @@ along with GCC; see the file COPYING3. If not see > NEXT_PASS (pass_object_sizes); > NEXT_PASS (pass_strlen); > /* Fold remaining builtins. */ > - NEXT_PASS (pass_forwprop, /*full_walk=*/false, /*last=*/true); > + NEXT_PASS (pass_forwprop, /*full_walk=*/false, /*last=*/true, > /*long_mul_fold_p=*/true); > NEXT_PASS (pass_dce); > /* Profile count may overflow as a result of inlinining very large > loop nests. This pass should run before any late pass that makes > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > index 0d9e91697cdd..365eab9c5459 100644 > --- a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > @@ -1,5 +1,6 @@ > /* { dg-do compile } */ > /* { dg-options "-O2 -fdump-tree-phiopt2" } */ > +/* { dg-require-effective-target lp64 } */ > > /* Test that phiopt flattens a conditional carry-add > sum = a + b; if (b > sum) result = base + 1; > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c > b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c > new file mode 100644 > index 000000000000..b086d7f75788 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c > @@ -0,0 +1,276 @@ > +/* { dg-do run } */ > +/* { dg-require-effective-target int128 } */ > +/* { dg-options "-O3" } */ > + > +typedef __UINT64_TYPE__ uint64_t; > +typedef unsigned __int128 uint128_t; > + > +/* Reference: high part of 64x64 -> 128 multiply. */ > +__attribute__((noipa)) > +uint64_t mulh_ref (uint64_t x, uint64_t y) > +{ > + return (uint64_t)(((uint128_t)x * y) >> 64); > +} > + > +/* Carry pattern for high part. */ > +__attribute__((noipa)) > +uint64_t mulh_carry (uint64_t x, uint64_t y) > +{ > + uint64_t x_hi = x >> 32; > + uint64_t x_lo = x & 0xFFFFFFFFUL; > + uint64_t y_hi = y >> 32; > + uint64_t y_lo = y & 0xFFFFFFFFUL; > + uint64_t mulhilo = x_hi * y_lo; > + uint64_t mullohi = x_lo * y_hi; > + uint64_t cross_sum = mulhilo + mullohi; > + uint64_t mullolo = x_lo * y_lo; > + uint64_t shrlolo = mullolo >> 32; > + uint64_t add_cross_sum = cross_sum + shrlolo; > + int carry = add_cross_sum < mulhilo; > + uint64_t cond = ((uint64_t) carry << 32) + x_hi * y_hi; > + uint64_t add = cond + (add_cross_sum >> 32); > + > + return add; > +} > + > +/* Ladder pattern for high part. */ > +__attribute__((noipa)) > +uint64_t mulh_ladder (uint64_t x, uint64_t y) > +{ > + uint64_t x_lo = x & 0xFFFFFFFFUL; > + uint64_t y_lo = y & 0xFFFFFFFFUL; > + uint64_t x_hi = x >> 32; > + uint64_t y_hi = y >> 32; > + uint64_t t0 = y_lo * x_lo; > + uint64_t t1 = y_lo * x_hi; > + uint64_t t2 = y_hi * x_lo; > + uint64_t t3 = y_hi * x_hi; > + uint64_t t0_hi = t0 >> 32; > + uint64_t u0 = t0_hi + t1; > + uint64_t u0_lo = u0 & 0xFFFFFFFFUL; > + uint64_t u0_hi = u0 >> 32; > + uint64_t u1 = u0_lo + t2; > + uint64_t u1_hi = u1 >> 32; > + uint64_t u2 = u0_hi + t3; > + uint64_t hw = u2 + u1_hi; > + > + return hw; > +} > + > +/* Ladder-long full multiply (both high and low parts). */ > +__attribute__((noipa)) > +void full_mul (uint64_t x, uint64_t y, uint64_t *p) > +{ > + uint64_t xl = x & 0xFFFFFFFFUL; > + uint64_t xh = x >> 32; > + uint64_t yl = y & 0xFFFFFFFFUL; > + uint64_t yh = y >> 32; > + uint64_t mulll = xl * yl; > + uint64_t mullh = xl * yh; > + uint64_t mulhl = xh * yl; > + uint64_t mulhh = xh * yh; > + uint64_t shr8 = mulll >> 32; > + uint64_t conv10 = mullh & 0xFFFFFFFFUL; > + uint64_t add = shr8 + conv10; > + uint64_t conv12 = mulhl & 0xFFFFFFFFUL; > + uint64_t add13 = add + conv12; > + uint64_t shr14 = add13 >> 32; > + uint64_t shr15 = mullh >> 32; > + uint64_t add16 = mulhh + shr15; > + uint64_t shr17 = mulhl >> 32; > + uint64_t add18 = add16 + shr17; > + uint64_t add19 = add18 + shr14; > + p[1] = add19; > + uint64_t add_13_shl = add13 << 32; > + uint64_t and17 = mulll & 0xFFFFFFFFUL; > + uint64_t or_val = add_13_shl | and17; > + p[0] = or_val; > +} > + > +/* Two-carry pattern for high part. */ > +__attribute__((noipa)) > +uint64_t mulh_two_carry (uint64_t x, uint64_t y) > +{ > + uint64_t x_hi = x >> 32; > + uint64_t x_lo = x & 0xFFFFFFFFUL; > + uint64_t y_hi = y >> 32; > + uint64_t y_lo = y & 0xFFFFFFFFUL; > + > + uint64_t lolo = x_lo * y_lo; > + uint64_t hilo = x_hi * y_lo; > + uint64_t lohi = x_lo * y_hi; > + uint64_t hihi = x_hi * y_hi; > + > + uint64_t cross_sum = hilo + lohi; > + uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32; > + > + uint64_t cross_shifted = cross_sum << 32; > + uint64_t low_result = lolo + cross_shifted; > + uint64_t low_carry = (uint64_t)(low_result < cross_shifted); > + > + uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry; > + > + return high; > +} > + > +/* Two-carry full multiply (both high and low parts). */ > +__attribute__((noipa)) > +void full_mul_two_carry (uint64_t x, uint64_t y, uint64_t *p) > +{ > + uint64_t x_hi = x >> 32; > + uint64_t x_lo = x & 0xFFFFFFFFUL; > + uint64_t y_hi = y >> 32; > + uint64_t y_lo = y & 0xFFFFFFFFUL; > + > + uint64_t lolo = x_lo * y_lo; > + uint64_t hilo = x_hi * y_lo; > + uint64_t lohi = x_lo * y_hi; > + uint64_t hihi = x_hi * y_hi; > + > + uint64_t cross_sum = hilo + lohi; > + uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32; > + > + uint64_t cross_shifted = cross_sum << 32; > + uint64_t low_result = lolo + cross_shifted; > + uint64_t low_carry = (uint64_t)(low_result < cross_shifted); > + > + uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry; > + > + p[0] = low_result; > + p[1] = high; > +} > + > +/* Carry-long pattern for high part. */ > +__attribute__((noipa)) > +uint64_t mulh_carry_long (uint64_t x, uint64_t y) > +{ > + uint64_t x_lo = x & 0xFFFFFFFFUL; > + uint64_t x_hi = x >> 32; > + uint64_t y_lo = y & 0xFFFFFFFFUL; > + 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 & 0xFFFFFFFFUL; > + 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; > +} > + > +/* Carry-long full multiply (both high and low parts). */ > +__attribute__((noipa)) > +void full_mul_carry_long (uint64_t x, uint64_t y, uint64_t *p) > +{ > + uint64_t x_lo = x & 0xFFFFFFFFUL; > + uint64_t x_hi = x >> 32; > + uint64_t y_lo = y & 0xFFFFFFFFUL; > + 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 & 0xFFFFFFFFUL; > + 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; > + p[1] = upper_mid_with_cross + low_accum_hi; > + uint64_t low_accum_shifted = low_accum << 32; > + uint64_t y_lo_x_lo_lo = y_lo_x_lo & 0xFFFFFFFFUL; > + p[0] = low_accum_shifted | y_lo_x_lo_lo; > +} > + > +/* Ladder-long pattern for high part. */ > +__attribute__((noipa)) > +uint64_t mulh_ladder_long (uint64_t x, uint64_t y) > +{ > + uint64_t xl = x & 0xFFFFFFFFUL; > + uint64_t xh = x >> 32; > + uint64_t yl = y & 0xFFFFFFFFUL; > + uint64_t yh = y >> 32; > + uint64_t mulll = xl * yl; > + uint64_t mullh = xl * yh; > + uint64_t mulhl = xh * yl; > + uint64_t mulhh = xh * yh; > + uint64_t shr8 = mulll >> 32; > + uint64_t conv10 = mullh & 0xFFFFFFFFUL; > + uint64_t add = shr8 + conv10; > + uint64_t conv12 = mulhl & 0xFFFFFFFFUL; > + uint64_t add13 = add + conv12; > + uint64_t shr14 = add13 >> 32; > + uint64_t shr15 = mullh >> 32; > + uint64_t add16 = mulhh + shr15; > + uint64_t shr17 = mulhl >> 32; > + uint64_t add18 = add16 + shr17; > + return add18 + shr14; > +} > + > +int main () > +{ > + /* Boundary inputs: zero, one, half-word mask, half-word+1, signed max, > + unsigned max. */ > + uint64_t vals[] = { > + 0, 1, 0xFFFFFFFFUL, 0x100000000ULL, > + 0x7FFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL > + }; > + int n = sizeof (vals) / sizeof (vals[0]); > + > + for (int i = 0; i < n; i++) > + for (int j = 0; j < n; j++) > + { > + uint64_t x = vals[i], y = vals[j]; > + uint64_t expected_hi = mulh_ref (x, y); > + uint64_t expected_lo = x * y; > + > + if (mulh_carry (x, y) != expected_hi) > + __builtin_abort (); > + > + if (mulh_ladder (x, y) != expected_hi) > + __builtin_abort (); > + > + if (mulh_two_carry (x, y) != expected_hi) > + __builtin_abort (); > + > + uint64_t p[2]; > + full_mul (x, y, p); > + if (p[1] != expected_hi) > + __builtin_abort (); > + if (p[0] != expected_lo) > + __builtin_abort (); > + > + uint64_t q[2]; > + full_mul_two_carry (x, y, q); > + if (q[1] != expected_hi) > + __builtin_abort (); > + if (q[0] != expected_lo) > + __builtin_abort (); > + > + if (mulh_carry_long (x, y) != expected_hi) > + __builtin_abort (); > + > + if (mulh_ladder_long (x, y) != expected_hi) > + __builtin_abort (); > + > + uint64_t r[2]; > + full_mul_carry_long (x, y, r); > + if (r[1] != expected_hi) > + __builtin_abort (); > + if (r[0] != expected_lo) > + __builtin_abort (); > + } > + > + return 0; > +} > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c > b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c > new file mode 100644 > index 000000000000..926acaddeade > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c > @@ -0,0 +1,272 @@ > +/* { dg-do run } */ > +/* { dg-options "-O3" } */ > + > +typedef __UINT32_TYPE__ uint32_t; > +typedef __UINT64_TYPE__ uint64_t; > + > +/* Reference: high part of 32x32 -> 64 multiply. */ > +__attribute__((noipa)) > +uint32_t mulh_ref (uint32_t x, uint32_t y) > +{ > + return (uint32_t)(((uint64_t)x * y) >> 32); > +} > + > +/* Carry pattern for high part. */ > +__attribute__((noipa)) > +uint32_t mulh_carry (uint32_t x, uint32_t y) > +{ > + uint32_t x_hi = x >> 16; > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_hi = y >> 16; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t mulhilo = x_hi * y_lo; > + uint32_t mullohi = x_lo * y_hi; > + uint32_t cross_sum = mulhilo + mullohi; > + uint32_t mullolo = x_lo * y_lo; > + uint32_t shrlolo = mullolo >> 16; > + uint32_t add_cross_sum = cross_sum + shrlolo; > + int carry = add_cross_sum < mulhilo; > + uint32_t cond = ((uint32_t) carry << 16) + x_hi * y_hi; > + uint32_t add = cond + (add_cross_sum >> 16); > + > + return add; > +} > + > +/* Ladder pattern for high part. */ > +__attribute__((noipa)) > +uint32_t mulh_ladder (uint32_t x, uint32_t y) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = y_hi * x_lo; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_lo = u0 & 0xFFFF; > + uint32_t u0_hi = u0 >> 16; > + uint32_t u1 = u0_lo + t2; > + uint32_t u1_hi = u1 >> 16; > + uint32_t u2 = u0_hi + t3; > + uint32_t hw = u2 + u1_hi; > + > + return hw; > +} > + > +/* Ladder-long pattern for full multiplication (both high and low parts). */ > +__attribute__((noipa)) > +void full_mul (uint32_t x, uint32_t y, uint32_t *p) > +{ > + uint32_t xl = x & 0xFFFF; > + uint32_t xh = x >> 16; > + uint32_t yl = y & 0xFFFF; > + uint32_t yh = y >> 16; > + uint32_t mulll = xl * yl; > + uint32_t mullh = xl * yh; > + uint32_t mulhl = xh * yl; > + uint32_t mulhh = xh * yh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mullh & 0xFFFF; > + uint32_t add = shr8 + conv10; > + uint32_t conv12 = mulhl & 0xFFFF; > + uint32_t add13 = add + conv12; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mullh >> 16; > + uint32_t add16 = mulhh + shr15; > + uint32_t shr17 = mulhl >> 16; > + uint32_t add18 = add16 + shr17; > + uint32_t add19 = add18 + shr14; > + p[1] = add19; > + uint32_t add_13_shl = add13 << 16; > + uint32_t and17 = mulll & 0xFFFF; > + uint32_t or_val = add_13_shl | and17; > + p[0] = or_val; > +} > + > +/* Two-carry pattern for high part (32-bit). */ > +__attribute__((noipa)) > +uint32_t mulh_two_carry (uint32_t x, uint32_t y) > +{ > + uint32_t x_hi = x >> 16; > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_hi = y >> 16; > + uint32_t y_lo = y & 0xFFFF; > + > + uint32_t lolo = x_lo * y_lo; > + uint32_t hilo = x_hi * y_lo; > + uint32_t lohi = x_lo * y_hi; > + uint32_t hihi = x_hi * y_hi; > + > + uint32_t cross_sum = hilo + lohi; > + uint32_t cross_carry = (uint32_t)(cross_sum < hilo) << 16; > + > + uint32_t cross_shifted = cross_sum << 16; > + uint32_t low_result = lolo + cross_shifted; > + uint32_t low_carry = (uint32_t)(low_result < cross_shifted); > + > + uint32_t high = hihi + (cross_sum >> 16) + cross_carry + low_carry; > + > + return high; > +} > + > +/* Two-carry full multiply (32-bit, both high and low parts). */ > +__attribute__((noipa)) > +void full_mul_two_carry (uint32_t x, uint32_t y, uint32_t *p) > +{ > + uint32_t x_hi = x >> 16; > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_hi = y >> 16; > + uint32_t y_lo = y & 0xFFFF; > + > + uint32_t lolo = x_lo * y_lo; > + uint32_t hilo = x_hi * y_lo; > + uint32_t lohi = x_lo * y_hi; > + uint32_t hihi = x_hi * y_hi; > + > + uint32_t cross_sum = hilo + lohi; > + uint32_t cross_carry = (uint32_t)(cross_sum < hilo) << 16; > + > + uint32_t cross_shifted = cross_sum << 16; > + uint32_t low_result = lolo + cross_shifted; > + uint32_t low_carry = (uint32_t)(low_result < cross_shifted); > + > + uint32_t high = hihi + (cross_sum >> 16) + cross_carry + low_carry; > + > + p[0] = low_result; > + p[1] = high; > +} > + > +/* Carry-long pattern for high part. */ > +__attribute__((noipa)) > +uint32_t mulh_carry_long (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; > +} > + > +/* Carry-long full multiply (both high and low parts). */ > +__attribute__((noipa)) > +void full_mul_carry_long (uint32_t x, uint32_t y, uint32_t *p) > +{ > + 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 upper_mid = y_hi_x_hi + carry; > + uint32_t low_accum_hi = low_accum >> 16; > + uint32_t upper_mid_with_cross = upper_mid + cross_sum_hi; > + p[1] = upper_mid_with_cross + low_accum_hi; > + uint32_t low_accum_shifted = low_accum << 16; > + uint32_t y_lo_x_lo_lo = y_lo_x_lo & 0xFFFF; > + p[0] = low_accum_shifted | y_lo_x_lo_lo; > +} > + > +/* Ladder-long pattern for high part. */ > +__attribute__((noipa)) > +uint32_t mulh_ladder_long (uint32_t x, uint32_t y) > +{ > + uint32_t xl = x & 0xFFFF; > + uint32_t xh = x >> 16; > + uint32_t yl = y & 0xFFFF; > + uint32_t yh = y >> 16; > + uint32_t mulll = xl * yl; > + uint32_t mullh = xl * yh; > + uint32_t mulhl = xh * yl; > + uint32_t mulhh = xh * yh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mullh & 0xFFFF; > + uint32_t add = shr8 + conv10; > + uint32_t conv12 = mulhl & 0xFFFF; > + uint32_t add13 = add + conv12; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mullh >> 16; > + uint32_t add16 = mulhh + shr15; > + uint32_t shr17 = mulhl >> 16; > + uint32_t add18 = add16 + shr17; > + return add18 + shr14; > +} > + > +int main () > +{ > + /* Boundary inputs: zero, one, half-word mask, half-word+1, signed max, > + unsigned max. */ > + uint32_t vals[] = { 0, 1, 0xFFFF, 0x10000, 0x7FFFFFFFU, 0xFFFFFFFFU }; > + int n = sizeof (vals) / sizeof (vals[0]); > + > + for (int i = 0; i < n; i++) > + for (int j = 0; j < n; j++) > + { > + uint32_t x = vals[i], y = vals[j]; > + uint32_t expected_hi = mulh_ref (x, y); > + uint32_t expected_lo = x * y; > + > + if (mulh_carry (x, y) != expected_hi) > + __builtin_abort (); > + > + if (mulh_ladder (x, y) != expected_hi) > + __builtin_abort (); > + > + if (mulh_two_carry (x, y) != expected_hi) > + __builtin_abort (); > + > + uint32_t p[2]; > + full_mul (x, y, p); > + if (p[1] != expected_hi) > + __builtin_abort (); > + if (p[0] != expected_lo) > + __builtin_abort (); > + > + uint32_t q[2]; > + full_mul_two_carry (x, y, q); > + if (q[1] != expected_hi) > + __builtin_abort (); > + if (q[0] != expected_lo) > + __builtin_abort (); > + > + if (mulh_carry_long (x, y) != expected_hi) > + __builtin_abort (); > + > + if (mulh_ladder_long (x, y) != expected_hi) > + __builtin_abort (); > + > + uint32_t r[2]; > + full_mul_carry_long (x, y, r); > + if (r[1] != expected_hi) > + __builtin_abort (); > + if (r[0] != expected_lo) > + __builtin_abort (); > + } > + > + return 0; > +} > 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..c8c449596879 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c > @@ -0,0 +1,310 @@ > +/* { 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; > + > +uint32_t mulh_carry (uint32_t x, uint32_t y) > +{ > + uint32_t x_hi = x >> 16; > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_hi = y >> 16; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t mulhilo = x_hi * y_lo; > + uint32_t mullohi = x_lo * y_hi; > + uint32_t cross_sum = mulhilo + mullohi; > + uint32_t mullolo = x_lo * y_lo; > + uint32_t shrlolo = mullolo >> 16; > + uint32_t add_cross_sum = cross_sum + shrlolo; > + int carry = add_cross_sum < mulhilo; > + uint32_t cond = ((uint32_t) carry << 16) + x_hi * y_hi; > + uint32_t add = cond + (add_cross_sum >> 16); > + > + return add; > +} > + > +void full_mul_carry (uint32_t x, uint32_t y, uint32_t* p) > +{ > + uint32_t x_hi = x >> 16; > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_hi = y >> 16; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t mulhilo = x_hi * y_lo; > + uint32_t mullohi = x_lo * y_hi; > + uint32_t cross_sum = mulhilo + mullohi; > + uint32_t mullolo = x_lo * y_lo; > + uint32_t shrlolo = mullolo >> 16; > + uint32_t add_cross_sum = cross_sum + shrlolo; > + int carry = add_cross_sum < mulhilo; > + uint32_t cond = ((uint32_t) carry << 16) + x_hi * y_hi; > + uint32_t add = cond + (add_cross_sum >> 16); > + p[1] = add; > + uint32_t add_cross_sum_shr = add_cross_sum << 16; > + uint32_t mullololo = mullolo & 0xFFFF; > + uint32_t low = add_cross_sum_shr | mullololo; > + p[0] = low; > +} > + > +uint32_t mulh_carry_comm (uint32_t x, uint32_t y) > +{ > + uint32_t x_hi = x >> 16; > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_hi = y >> 16; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t mulhilo = y_lo * x_hi; > + uint32_t mullohi = y_hi * x_lo; > + uint32_t cross_sum = mullohi + mulhilo; > + uint32_t mullolo = x_lo * y_lo; > + uint32_t shrlolo = mullolo >> 16; > + uint32_t add_cross_sum = shrlolo + cross_sum; > + int carry = add_cross_sum < mulhilo; > + uint32_t cond = ((uint32_t) carry << 16) + x_hi * y_hi; > + uint32_t add = cond + (add_cross_sum >> 16); > + > + return add; > +} > + > +uint32_t mulh_carry_lohi (uint32_t x, uint32_t y) { > + uint32_t x_hi = x >> 16; > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_hi = y >> 16; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t mulhilo = x_hi * y_lo; > + uint32_t mullohi = x_lo * y_hi; > + uint32_t cross_sum = mulhilo + mullohi; > + uint32_t mullolo = x_lo * y_lo; > + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); > + int carry_occurred = (add_cross_sum < mullohi); > + uint32_t cond = (uint32_t) carry_occurred << 16; > + uint32_t add = x_hi * y_hi + cond + (add_cross_sum >> 16); > + > + return add; > +} > + > +/* The 128-bit variant will fail during the high sequence generation > + (no target provides a 256-bit multiply) and is excluded from the > + expected fold counts below. */ > +#ifdef __SIZEOF_INT128__ > +__uint128_t mulh_carry_128 (__uint128_t x, __uint128_t y) > +{ > + __uint128_t x_hi = x >> 64; > + __uint128_t x_lo = x & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t y_hi = y >> 64; > + __uint128_t y_lo = y & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t mulhilo = x_hi * y_lo; > + __uint128_t mullohi = x_lo * y_hi; > + __uint128_t cross_sum = mulhilo + mullohi; > + __uint128_t mullolo = x_lo * y_lo; > + __uint128_t shrlolo = mullolo >> 64; > + __uint128_t add_cross_sum = cross_sum + shrlolo; > + int carry = add_cross_sum < mulhilo; > + __uint128_t cond = ((__uint128_t) carry << 64) + x_hi * y_hi; > + __uint128_t add = cond + (add_cross_sum >> 64); > + > + return add; > +} > +#endif > + > +/* 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_hi = x.v[i] >> 16; > + uint32_t x_lo = x.v[i] & 0xFFFF; > + uint32_t y_hi = y.v[i] >> 16; > + uint32_t y_lo = y.v[i] & 0xFFFF; > + uint32_t mulhilo = x_hi * y_lo; > + uint32_t mullohi = x_lo * y_hi; > + uint32_t cross_sum = mulhilo + mullohi; > + uint32_t mullolo = x_lo * y_lo; > + uint32_t shrlolo = mullolo >> 16; > + uint32_t add_cross_sum = cross_sum + shrlolo; > + int carry = add_cross_sum < mulhilo; > + uint32_t cond = ((uint32_t) carry << 16) + x_hi * y_hi; > + uint32_t add = cond + (add_cross_sum >> 16); > + result.v[i] = add; > + } > + > + return result; > +} > + > +/* Carry-long variants: hi-part sum uses the long form > + (xh*yh + carry + cross_hi + low_accum_hi). */ > + > +uint64_t mulh_carry_long (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_long_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_long_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 will fail during the high sequence generation > + (no target provides a 256-bit multiply) and is excluded from the > + expected fold counts below. */ > +#ifdef __SIZEOF_INT128__ > +__uint128_t mulh_carry_long_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_long (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_long_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." > 10 "forwprop2" { target lp64 } } } */ > +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." > 7 "forwprop2" { target { ! lp64 } } } } */ > +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." > 2 "forwprop2" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c > b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c > new file mode 100644 > index 000000000000..1fc85efbfeb5 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c > @@ -0,0 +1,328 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -fdump-tree-forwprop-details" } */ > + > +typedef __UINT32_TYPE__ uint32_t; > +typedef __UINT64_TYPE__ uint64_t; > +typedef struct { uint32_t v[2]; } v2i32; > +typedef struct { uint64_t v[2]; } v2i64; > + > +uint64_t mulh_ladder (uint64_t x, uint64_t y) > +{ > + uint64_t x_lo = x & 0xFFFFFFFF; > + uint64_t y_lo = y & 0xFFFFFFFF; > + uint64_t x_hi = x >> 32; > + uint64_t y_hi = y >> 32; > + uint64_t t0 = y_lo * x_lo; > + uint64_t t1 = y_lo * x_hi; > + uint64_t t2 = y_hi * x_lo; > + uint64_t t3 = y_hi * x_hi; > + uint64_t t0_hi = t0 >> 32; > + uint64_t u0 = t0_hi + t1; > + uint64_t u0_lo = u0 & 0xFFFFFFFF; > + uint64_t u0_hi = u0 >> 32; > + uint64_t u1 = u0_lo + t2; > + uint64_t u1_hi = u1 >> 32; > + uint64_t u2 = u0_hi + t3; > + uint64_t hw64 = u2 + u1_hi; > + > + return hw64; > +} > + > +uint64_t mulh_ladder_comm (uint64_t x, uint64_t y) > +{ > + uint64_t x_lo = x & 0xFFFFFFFF; > + uint64_t y_lo = y & 0xFFFFFFFF; > + uint64_t x_hi = x >> 32; > + uint64_t y_hi = y >> 32; > + uint64_t t0 = x_lo * y_lo; > + uint64_t t1 = x_lo * y_hi; > + uint64_t t2 = x_hi * y_lo; > + uint64_t t3 = x_hi * y_hi; > + uint64_t t0_hi = t0 >> 32; > + uint64_t u0 = t1 + t0_hi; > + uint64_t u0_lo = u0 & 0xFFFFFFFF; > + uint64_t u0_hi = u0 >> 32; > + uint64_t u1 = t2 + u0_lo; > + uint64_t u1_hi = u1 >> 32; > + uint64_t u2 = u1_hi + u0_hi; > + uint64_t hw64 = t3 + u2; > + > + return hw64; > +} > + > +uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = y_hi * x_lo; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_lo = u0 & 0xFFFF; > + uint32_t u0_hi = u0 >> 16; > + uint32_t u1 = u0_lo + t2; > + uint32_t u1_hi = u1 >> 16; > + uint32_t u2 = u0_hi + t3; > + uint32_t hw64 = u2 + u1_hi; > + > + return hw64; > +} > + > +/* The 128-bit variant will fail during the high sequence generation > + (no target provides a 256-bit multiply) and is excluded from the > + expected fold counts below. */ > +#ifdef __SIZEOF_INT128__ > +__uint128_t umulh_variant_i128 (__uint128_t x, __uint128_t y) > +{ > + __uint128_t x_lo = x & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t y_lo = y & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t x_hi = x >> 64; > + __uint128_t y_hi = y >> 64; > + __uint128_t t0 = y_lo * x_lo; > + __uint128_t t1 = y_lo * x_hi; > + __uint128_t t2 = y_hi * x_lo; > + __uint128_t t3 = y_hi * x_hi; > + __uint128_t t0_hi = t0 >> 64; > + __uint128_t u0 = t0_hi + t1; > + __uint128_t u0_lo = u0 & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t u0_hi = u0 >> 64; > + __uint128_t u1 = u0_lo + t2; > + __uint128_t u1_hi = u1 >> 64; > + __uint128_t u2 = u0_hi + t3; > + __uint128_t hw64 = u2 + u1_hi; > + > + return hw64; > +} > +#endif > + > +v2i64 full_mul_ladder (uint64_t x, uint64_t y) > +{ > + uint64_t and_x = x & 0xFFFFFFFF; > + uint64_t and_y = y & 0xFFFFFFFF; > + uint64_t mul_i = and_y * and_x; > + uint64_t shr_x = x >> 32; > + uint64_t mul_i27 = and_y * shr_x; > + uint64_t shr_y = y >> 32; > + uint64_t mul_i28 = shr_y * and_x; > + uint64_t mul_i29 = shr_y * shr_x; > + uint64_t shr10 = mul_i >> 32; > + uint64_t and11 = mul_i27 & 0xFFFFFFFF; > + uint64_t add = and11 + mul_i28; > + uint64_t add12 = add + shr10; > + uint64_t shr13 = mul_i27 >> 32; > + uint64_t shr14 = add12 >> 32; > + uint64_t add15 = shr13 + mul_i29; > + uint64_t add16 = add15 + shr14; > + uint64_t shl = add12 << 32; > + uint64_t and17 = mul_i & 0xFFFFFFFF; > + uint64_t or_val = shl | and17; > + v2i64 result; > + result.v[0] = or_val; > + result.v[1] = add16; > + return result; > +} > + > +/* This will be optimized during the second forwprop run. > + Disable SLP so the expected fold count is target-independent. */ > +__attribute__((optimize("no-tree-slp-vectorize"))) > +v2i32 mulh_ladder_v2i32 (v2i32 x, v2i32 y) > +{ > + v2i32 result; > + for(int i=0; i<2; ++i) > + { > + uint32_t x_lo = x.v[i] & 0xFFFF; > + uint32_t y_lo = y.v[i] & 0xFFFF; > + uint32_t x_hi = x.v[i] >> 16; > + uint32_t y_hi = y.v[i] >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = y_hi * x_lo; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_lo = u0 & 0xFFFF; > + uint32_t u0_hi = u0 >> 16; > + uint32_t u1 = u0_lo + t2; > + uint32_t u1_hi = u1 >> 16; > + uint32_t u2 = u0_hi + t3; > + result.v[i] = u2 + u1_hi; > + } > + > + return result; > +} > + > +/* Ladder-long variants: hi-part sum uses the long form > + (xh*yh + cross_hi_a + cross_hi_b + mid_hi). */ > + > +uint32_t mulh_ladder_long (uint32_t x, uint32_t y) > +{ > + uint32_t xl = x & 0xFFFF; > + uint32_t xh = x >> 16; > + uint32_t yl = y & 0xFFFF; > + uint32_t yh = y >> 16; > + uint32_t mulll = xl * yl; > + uint32_t mullh = xl * yh; > + uint32_t mulhl = xh * yl; > + uint32_t mulhh = xh * yh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mullh & 0xFFFF; > + uint32_t add = shr8 + conv10; > + uint32_t conv12 = mulhl & 0xFFFF; > + uint32_t add13 = add + conv12; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mullh >> 16; > + uint32_t add16 = mulhh + shr15; > + uint32_t shr17 = mulhl >> 16; > + uint32_t add18 = add16 + shr17; > + uint32_t add19 = add18 + shr14; > + > + return add19; > +} > + > +void full_mul_ladder_long (uint32_t x, uint32_t y, uint32_t *p) > +{ > + uint32_t xl = x & 0xFFFF; > + uint32_t xh = x >> 16; > + uint32_t yl = y & 0xFFFF; > + uint32_t yh = y >> 16; > + uint32_t mulll = xl * yl; > + uint32_t mullh = xl * yh; > + uint32_t mulhl = xh * yl; > + uint32_t mulhh = xh * yh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mullh & 0xFFFF; > + uint32_t add = shr8 + conv10; > + uint32_t conv12 = mulhl & 0xFFFF; > + uint32_t add13 = add + conv12; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mullh >> 16; > + uint32_t add16 = mulhh + shr15; > + uint32_t shr17 = mulhl >> 16; > + uint32_t add18 = add16 + shr17; > + uint32_t add19 = add18 + shr14; > + p[1] = add19; > + uint32_t add_13_shl = add13 << 16; > + uint32_t and17 = mulll & 0xFFFF; > + uint32_t or_val = add_13_shl | and17; > + p[0] = or_val; > +} > + > +uint32_t mulh_ladder_long_comm (uint32_t x, uint32_t y) > +{ > + uint32_t xl = x & 0xFFFF; > + uint32_t xh = x >> 16; > + uint32_t yl = y & 0xFFFF; > + uint32_t yh = y >> 16; > + uint32_t mulll = yl * xl; > + uint32_t mullh = yh * xl; > + uint32_t mulhl = yl * xh; > + uint32_t mulhh = yh * xh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mullh & 0xFFFF; > + uint32_t add = conv10 + shr8; > + uint32_t conv12 = mulhl & 0xFFFF; > + uint32_t add13 = conv12 + add; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mullh >> 16; > + uint32_t shr17 = mulhl >> 16; > + uint32_t add16 = shr14 + shr17; > + uint32_t add18 = add16 + shr15; > + uint32_t add19 = mulhh + add18; > + > + return add19; > +} > + > +/* The 128-bit variant will fail during the high sequence generation > + (no target provides a 256-bit multiply) and is excluded from the > + expected fold counts below. */ > +#ifdef __SIZEOF_INT128__ > +__uint128_t mulh_ladder_long_128 (__uint128_t x, __uint128_t y) > +{ > + __uint128_t xl = x & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t xh = x >> 64; > + __uint128_t yl = y & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t yh = y >> 64; > + __uint128_t mulll = xl * yl; > + __uint128_t mullh = xl * yh; > + __uint128_t mulhl = xh * yl; > + __uint128_t mulhh = xh * yh; > + __uint128_t shr8 = mulll >> 64; > + __uint128_t conv10 = mullh & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t add = shr8 + conv10; > + __uint128_t conv12 = mulhl & (__uint128_t)0xFFFFFFFFFFFFFFFF; > + __uint128_t add13 = add + conv12; > + __uint128_t shr14 = add13 >> 64; > + __uint128_t shr15 = mullh >> 64; > + __uint128_t add16 = mulhh + shr15; > + __uint128_t shr17 = mulhl >> 64; > + __uint128_t add18 = add16 + shr17; > + __uint128_t add19 = add18 + shr14; > + > + return add19; > +} > +#endif > + > +uint32_t mulh_ladder_long_hllh (uint32_t x, uint32_t y) > +{ > + uint32_t xl = x & 0xFFFF; > + uint32_t xh = x >> 16; > + uint32_t yl = y & 0xFFFF; > + uint32_t yh = y >> 16; > + uint32_t mulll = xl * yl; > + uint32_t mullh = xl * yh; > + uint32_t mulhl = xh * yl; > + uint32_t mulhh = xh * yh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mulhl & 0xFFFF; > + uint32_t add = shr8 + conv10; > + uint32_t conv12 = mullh & 0xFFFF; > + uint32_t add13 = add + conv12; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mulhl >> 16; > + uint32_t add16 = mulhh + shr15; > + uint32_t shr17 = mullh >> 16; > + uint32_t add18 = add16 + shr17; > + uint32_t add19 = add18 + shr14; > + > + return add19; > +} > + > +/* This will be optimized during the second forwprop run. > + Disable SLP so the expected fold count is target-independent. */ > +__attribute__((optimize("no-tree-slp-vectorize"))) > +v2i32 mul_ladder_long_v2i32 (v2i32 x, v2i32 y) > +{ > + v2i32 result; > + for (int i = 0; i < 2; i++) > + { > + uint32_t xl = x.v[i] & 0xFFFF; > + uint32_t xh = x.v[i] >> 16; > + uint32_t yl = y.v[i] & 0xFFFF; > + uint32_t yh = y.v[i] >> 16; > + uint32_t mulll = xl * yl; > + uint32_t mullh = xl * yh; > + uint32_t mulhl = xh * yl; > + uint32_t mulhh = xh * yh; > + uint32_t shr8 = mulll >> 16; > + uint32_t conv10 = mullh & 0xFFFF; > + uint32_t add = shr8 + conv10; > + uint32_t conv12 = mulhl & 0xFFFF; > + uint32_t add13 = add + conv12; > + uint32_t shr14 = add13 >> 16; > + uint32_t shr15 = mullh >> 16; > + uint32_t add16 = mulhh + shr15; > + uint32_t shr17 = mulhl >> 16; > + uint32_t add18 = add16 + shr17; > + result.v[i] = add18 + shr14; > + } > + > + return result; > +} > + > +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." > 10 "forwprop2" { target lp64 } } } */ > +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." > 7 "forwprop2" { target { ! lp64 } } } } */ > +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." > 2 "forwprop2" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c > b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c > new file mode 100644 > index 000000000000..381c0a768f05 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c > @@ -0,0 +1,54 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -fdump-tree-forwprop-details" } */ > + > +typedef __UINT32_TYPE__ uint32_t; > +typedef __UINT64_TYPE__ uint64_t; > + > +/* Low part via PLUS form: lolo + (cross_sum << halfwidth). > + No GT/LT comparison on the result, so fold_mul_low_plus > + should fold without deferring. */ > +uint32_t mul_low_plus_32 (uint32_t x, uint32_t y) > +{ > + uint32_t x_hi = x >> 16; > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_hi = y >> 16; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t lolo = x_lo * y_lo; > + uint32_t hilo = x_hi * y_lo; > + uint32_t lohi = x_lo * y_hi; > + uint32_t cross_sum = hilo + lohi; > + uint32_t cross_shifted = cross_sum << 16; > + return lolo + cross_shifted; > +} > + > +/* 64-bit variant. */ > +uint64_t mul_low_plus_64 (uint64_t x, uint64_t y) > +{ > + uint64_t x_hi = x >> 32; > + uint64_t x_lo = x & 0xFFFFFFFFUL; > + uint64_t y_hi = y >> 32; > + uint64_t y_lo = y & 0xFFFFFFFFUL; > + uint64_t lolo = x_lo * y_lo; > + uint64_t hilo = x_hi * y_lo; > + uint64_t lohi = x_lo * y_hi; > + uint64_t cross_sum = hilo + lohi; > + uint64_t cross_shifted = cross_sum << 32; > + return lolo + cross_shifted; > +} > + > +/* Commuted operand order. */ > +uint32_t mul_low_plus_comm (uint32_t x, uint32_t y) > +{ > + uint32_t x_hi = x >> 16; > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_hi = y >> 16; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t lolo = y_lo * x_lo; > + uint32_t hilo = y_lo * x_hi; > + uint32_t lohi = y_hi * x_lo; > + uint32_t cross_sum = lohi + hilo; > + uint32_t cross_shifted = cross_sum << 16; > + return cross_shifted + lolo; > +} > + > +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." > 3 "forwprop2" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c > b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c > new file mode 100644 > index 000000000000..0b187b4949b2 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c > @@ -0,0 +1,119 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -fdump-tree-optimized" } */ > + > +typedef __UINT32_TYPE__ uint32_t; > + > +/* Only one cross-product (xh*yl), missing xl*yh. > + Should NOT be folded. */ > +uint32_t partial_one_cross (uint32_t x, uint32_t y) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_hi = u0 >> 16; > + return t3 + u0_hi; > +} > + > +/* Only xl*yl and xh*yh, no cross-products at all. > + Should NOT be folded. */ > +uint32_t partial_no_cross (uint32_t x, uint32_t y) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t3 = y_hi * x_hi; > + return t3 + (t0 >> 16); > +} > + > +/* Only cross-products, missing xl*yl and xh*yh. > + Should NOT be folded. */ > +uint32_t partial_only_cross (uint32_t x, uint32_t y) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = y_hi * x_lo; > + return (t1 + t2) >> 16; > +} > + > +/* Full ladder structure but one cross-product uses z instead of y. > + check_hilo_and_ops should reject the mismatched operand. > + Should NOT be folded. */ > +uint32_t partial_mismatched_op (uint32_t x, uint32_t y, uint32_t z) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t z_lo = z & 0xFFFF; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = z_lo * x_lo; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_lo = u0 & 0xFFFF; > + uint32_t u0_hi = u0 >> 16; > + uint32_t u1 = u0_lo + t2; > + uint32_t u1_hi = u1 >> 16; > + uint32_t u2 = u0_hi + t3; > + return u2 + u1_hi; > +} > + > +/* Uses conditionals in the computation. > + Should NOT be folded. */ > +unsigned mulhu_conditional (unsigned u, unsigned v) { > + unsigned a, b, c, d, p, q, rlow, rhigh; > + > + a = u >> 16; > + b = u & 0xFFFF; > + c = v >> 16; > + d = v & 0xFFFF; > + > + p = a*c; > + q = b*d; > + rlow = (-a + b)*(c - d); > + rhigh = (int)((-a + b)^(c - d)) >> 31; > + if (rlow == 0) rhigh = 0; > + > + q = q + (q >> 16); > + rlow = rlow + p; > + if (rlow < p) rhigh = rhigh + 1; > + rlow = rlow + q; > + if (rlow < q) rhigh = rhigh + 1; > + > + return p + (rlow >> 16) + (rhigh << 16); > +} > + > +/* Signed operands. > + Should NOT be folded. */ > +int mulhs_signed (int u, int v) { > + unsigned u0, v0, w0; > + int u1, v1, w1, w2, t; > + > + u0 = u & 0xFFFF; > + u1 = u >> 16; > + v0 = v & 0xFFFF; > + v1 = v >> 16; > + w0 = u0*v0; > + t = u1*v0 + (w0 >> 16); > + w1 = t & 0xFFFF; > + w2 = t >> 16; > + w1 = u0*v1 + w1; > + return u1*v1 + w2 + (w1 >> 16); > +} > + > +/* Verify no fold in any forwprop pass by checking the optimized IR > + for MULT_HIGHPART_EXPR (h*) and WIDEN_MULT_EXPR (w*). */ > +/* { dg-final { scan-tree-dump-not " h\\* " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not " w\\* " "optimized" } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c > b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c > new file mode 100644 > index 000000000000..19aeb5215bd8 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c > @@ -0,0 +1,113 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -fdump-tree-forwprop-details" } */ > + > +typedef __UINT32_TYPE__ uint32_t; > +typedef __UINT64_TYPE__ uint64_t; > + > +/* High part using two separate carries (cross carry + low carry). */ > +uint64_t mulh_two_carry (uint64_t x, uint64_t y) > +{ > + uint64_t x_hi = x >> 32; > + uint64_t x_lo = x & 0xFFFFFFFFUL; > + uint64_t y_hi = y >> 32; > + uint64_t y_lo = y & 0xFFFFFFFFUL; > + > + uint64_t lolo = x_lo * y_lo; > + uint64_t hilo = x_hi * y_lo; > + uint64_t lohi = x_lo * y_hi; > + uint64_t hihi = x_hi * y_hi; > + > + uint64_t cross_sum = hilo + lohi; > + uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32; > + > + uint64_t cross_shifted = cross_sum << 32; > + uint64_t low_result = lolo + cross_shifted; > + uint64_t low_carry = (uint64_t)(low_result < cross_shifted); > + > + uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry; > + > + return high; > +} > + > +/* Commuted operand order. */ > +uint64_t mulh_two_carry_comm (uint64_t x, uint64_t y) > +{ > + uint64_t x_hi = x >> 32; > + uint64_t x_lo = x & 0xFFFFFFFFUL; > + uint64_t y_hi = y >> 32; > + uint64_t y_lo = y & 0xFFFFFFFFUL; > + > + uint64_t lolo = x_lo * y_lo; > + uint64_t lohi = x_lo * y_hi; > + uint64_t hilo = x_hi * y_lo; > + uint64_t hihi = x_hi * y_hi; > + > + uint64_t cross_sum = lohi + hilo; > + uint64_t cross_carry = (uint64_t)(cross_sum < lohi) << 32; > + > + uint64_t cross_shifted = cross_sum << 32; > + uint64_t low_result = cross_shifted + lolo; > + uint64_t low_carry = (uint64_t)(low_result < lolo); > + > + uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry; > + > + return high; > +} > + > +/* 32-bit variant. */ > +uint32_t mulh_two_carry_32 (uint32_t x, uint32_t y) > +{ > + uint32_t x_hi = x >> 16; > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_hi = y >> 16; > + uint32_t y_lo = y & 0xFFFF; > + > + uint32_t lolo = x_lo * y_lo; > + uint32_t hilo = x_hi * y_lo; > + uint32_t lohi = x_lo * y_hi; > + uint32_t hihi = x_hi * y_hi; > + > + uint32_t cross_sum = hilo + lohi; > + uint32_t cross_carry = (uint32_t)(cross_sum < hilo) << 16; > + > + uint32_t cross_shifted = cross_sum << 16; > + uint32_t low_result = lolo + cross_shifted; > + uint32_t low_carry = (uint32_t)(low_result < cross_shifted); > + > + uint32_t high = hihi + (cross_sum >> 16) + cross_carry + low_carry; > + > + return high; > +} > + > +/* Full multiply: both high and low parts. */ > +uint64_t full_mul_two_carry (uint64_t x, uint64_t y, uint64_t *lo) > +{ > + uint64_t x_hi = x >> 32; > + uint64_t x_lo = x & 0xFFFFFFFFUL; > + uint64_t y_hi = y >> 32; > + uint64_t y_lo = y & 0xFFFFFFFFUL; > + > + uint64_t lolo = x_lo * y_lo; > + uint64_t hilo = x_hi * y_lo; > + uint64_t lohi = x_lo * y_hi; > + uint64_t hihi = x_hi * y_hi; > + > + uint64_t cross_sum = hilo + lohi; > + uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32; > + > + uint64_t cross_shifted = cross_sum << 32; > + uint64_t low_result = lolo + cross_shifted; > + uint64_t low_carry = (uint64_t)(low_result < cross_shifted); > + > + uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry; > + > + *lo = low_result; > + return high; > +} > + > +/* The high/low split across forwprop3/forwprop4 is intentional: see > + long_mul_check_low_plus_defer in tree-ssa-forwprop.cc. */ > +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." > 4 "forwprop3" { target lp64 } } } */ > +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." > 1 "forwprop3" { target { ! lp64 } } } } */ > +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." > 1 "forwprop4" { target lp64 } } } */ > +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." > 1 "forwprop4" { target { ! lp64 } } } } */ > 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..f9c765380d8c > --- /dev/null > +++ b/gcc/testsuite/gcc.target/aarch64/long_mul.c > @@ -0,0 +1,100 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3" } */ > + > +typedef __UINT32_TYPE__ uint32_t; > +typedef __UINT64_TYPE__ uint64_t; > + > +/* 64-bit ladder pattern for high part. */ > +uint64_t mulh_ladder (uint64_t x, uint64_t y) > +{ > + uint64_t x_lo = x & 0xFFFFFFFF; > + uint64_t y_lo = y & 0xFFFFFFFF; > + uint64_t x_hi = x >> 32; > + uint64_t y_hi = y >> 32; > + uint64_t t0 = y_lo * x_lo; > + uint64_t t1 = y_lo * x_hi; > + uint64_t t2 = y_hi * x_lo; > + uint64_t t3 = y_hi * x_hi; > + uint64_t t0_hi = t0 >> 32; > + uint64_t u0 = t0_hi + t1; > + uint64_t u0_lo = u0 & 0xFFFFFFFF; > + uint64_t u0_hi = u0 >> 32; > + uint64_t u1 = u0_lo + t2; > + uint64_t u1_hi = u1 >> 32; > + uint64_t u2 = u0_hi + t3; > + return u2 + u1_hi; > +} > + > +/* 64-bit carry pattern for high part. */ > +uint64_t mulh_carry (uint64_t x, uint64_t y) > +{ > + 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 ladder pattern for high part. */ > +uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = y_hi * x_lo; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_lo = u0 & 0xFFFF; > + uint32_t u0_hi = u0 >> 16; > + uint32_t u1 = u0_lo + t2; > + uint32_t u1_hi = u1 >> 16; > + uint32_t u2 = u0_hi + t3; > + return u2 + u1_hi; > +} > + > +/* 32-bit carry pattern for high part. */ > +uint32_t mulh_carry_32 (uint32_t x, uint32_t y) > +{ > + 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 patterns should emit umulh. */ > +/* { dg-final { scan-assembler-times "umulh\t" 2 } } */ > +/* 32-bit patterns should emit umull (32x32->64 widening multiply). */ > +/* { dg-final { scan-assembler-times "umull\t" 2 } } */ > diff --git a/gcc/testsuite/gcc.target/i386/long_mul.c > b/gcc/testsuite/gcc.target/i386/long_mul.c > new file mode 100644 > index 000000000000..d4b03ed1beda > --- /dev/null > +++ b/gcc/testsuite/gcc.target/i386/long_mul.c > @@ -0,0 +1,100 @@ > +/* { dg-do compile { target { ! ia32 } } } */ > +/* { dg-options "-O3" } */ > + > +typedef __UINT32_TYPE__ uint32_t; > +typedef __UINT64_TYPE__ uint64_t; > + > +/* 64-bit ladder pattern for high part. */ > +uint64_t mulh_ladder (uint64_t x, uint64_t y) > +{ > + uint64_t x_lo = x & 0xFFFFFFFF; > + uint64_t y_lo = y & 0xFFFFFFFF; > + uint64_t x_hi = x >> 32; > + uint64_t y_hi = y >> 32; > + uint64_t t0 = y_lo * x_lo; > + uint64_t t1 = y_lo * x_hi; > + uint64_t t2 = y_hi * x_lo; > + uint64_t t3 = y_hi * x_hi; > + uint64_t t0_hi = t0 >> 32; > + uint64_t u0 = t0_hi + t1; > + uint64_t u0_lo = u0 & 0xFFFFFFFF; > + uint64_t u0_hi = u0 >> 32; > + uint64_t u1 = u0_lo + t2; > + uint64_t u1_hi = u1 >> 32; > + uint64_t u2 = u0_hi + t3; > + return u2 + u1_hi; > +} > + > +/* 64-bit carry pattern for high part. */ > +uint64_t mulh_carry (uint64_t x, uint64_t y) > +{ > + 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 ladder pattern for high part. */ > +uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) > +{ > + uint32_t x_lo = x & 0xFFFF; > + uint32_t y_lo = y & 0xFFFF; > + uint32_t x_hi = x >> 16; > + uint32_t y_hi = y >> 16; > + uint32_t t0 = y_lo * x_lo; > + uint32_t t1 = y_lo * x_hi; > + uint32_t t2 = y_hi * x_lo; > + uint32_t t3 = y_hi * x_hi; > + uint32_t t0_hi = t0 >> 16; > + uint32_t u0 = t0_hi + t1; > + uint32_t u0_lo = u0 & 0xFFFF; > + uint32_t u0_hi = u0 >> 16; > + uint32_t u1 = u0_lo + t2; > + uint32_t u1_hi = u1 >> 16; > + uint32_t u2 = u0_hi + t3; > + return u2 + u1_hi; > +} > + > +/* 32-bit carry pattern for high part. */ > +uint32_t mulh_carry_32 (uint32_t x, uint32_t y) > +{ > + 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 patterns should emit mulq (unsigned 64x64->128 multiply). */ > +/* { dg-final { scan-assembler-times "\tmulq" 2 } } */ > +/* 32-bit patterns should emit imulq (64-bit multiply of zero-extended > operands). */ > +/* { dg-final { scan-assembler-times "\timulq" 2 } } */ > diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc > index 06eb81b9a28d..1613b2fdc5d9 100644 > --- a/gcc/tree-ssa-forwprop.cc > +++ b/gcc/tree-ssa-forwprop.cc > @@ -3576,6 +3576,885 @@ 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_low_sum (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_carry_cross_sum (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_carry_low_sum (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_low_accum (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_cross_sum (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_ladder_part_sum (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_ladder_sum1 (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_ladder_sum2 (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_ladder_sum3 (tree, tree *, tree (*)(tree)); > +extern bool gimple_mul_carry_low (tree, tree *, tree (*)(tree)); > + > +/* Replace STMT with a high-part multiply of OP1 and OP2. The single > + MULT_HIGHPART_EXPR is lowered by RTL expansion to native umul_highpart, > + to a widening multiply + shift, or to a synthesised sequence, whichever > + the target supports. Return false (no replacement) if the target > + cannot do any of these (libcall fallback is slower than the original > + longhand). */ > + > +static bool > +create_mul_high_seq (tree op1, tree op2, gimple *stmt) > +{ > + tree op_type = TREE_TYPE (op1); > + scalar_int_mode op_mode; > + if (!is_a<scalar_int_mode> (TYPE_MODE (op_type), &op_mode)) > + return false; > + > + if (!can_mult_highpart_p (op_mode, TYPE_UNSIGNED (op_type))) > + return false; > + > + gimple *prod = gimple_build_assign (gimple_get_lhs (stmt), > + MULT_HIGHPART_EXPR, op1, op2); > + gimple_set_location (prod, gimple_location (stmt)); > + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); > + gsi_replace (&gsi, prod, true); > + return 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_carry_low_sum) takes 7 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_LOW_SUM, > + LMK_LADDER_SUM1, > + LMK_LADDER_SUM2, > + LMK_LADDER_SUM3, > + LMK_LADDER_PART_SUM, > + LMK_CARRY_LOW, > + LMK_CARRY_CROSS_SUM, > + LMK_CARRY_LOW_SUM, > +}; > + > +/* 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; > + tree carry_a, carry_b; > + 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, auto_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 ()) > + { > + 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: > + case LMK_LOW_SUM: > + case LMK_LADDER_SUM1: > + case LMK_LADDER_SUM2: > + case LMK_LADDER_SUM3: > + n_ops = 2; > + n_hilos = 2; > + break; > + case LMK_LADDER_PART_SUM: > + n_ops = 2; > + n_hilos = 1; > + break; > + case LMK_CARRY_CROSS_SUM: > + n_hilos = 3; > + shift_idx = 3; > + break; > + case LMK_CARRY_LOW_SUM: > + n_ops = 2; > + n_hilos = 3; > + shift_idx = 5; > + break; > + case LMK_CARRY_LOW: > + info->carry_a = res_ops[0]; > + info->carry_b = res_ops[1]; > + return; > + } > + 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 / mul_carry_low_sum, so they're 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]; > + /* mul_carry_low_sum's inner is constrained to mul_low_sum (cross_sum > + + mul_hi(mul_lolo)); mul_carry_cross_sum's inner is just > + mul_cross_sum (any plus); mul_carry_low matches gt:c (@0, plus(@0, > + @1)) without a baked-in shift. Most specific first, so the > + less-constrained pattern doesn't shadow the more-constrained one. */ > + if (gimple_mul_carry_low_sum (leaf, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_CARRY_LOW_SUM, res_ops); > + return true; > + } > + if (gimple_mul_carry_cross_sum (leaf, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_CARRY_CROSS_SUM, res_ops); > + return true; > + } > + if (gimple_mul_carry_low (leaf, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_CARRY_LOW, res_ops); > + return true; > + } > + return false; > +} > + > +/* Classify INNER -- already unwrapped from an outer (X >> SHIFT) -- as > + a high-half-extracted summand. Tries the more-specific atoms before > + the generic mul_cross_sum (which matches any plus). */ > + > +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; > + /* mul_hilo (mult-shape) is orthogonal to the plus-based kinds; try > + it first. For the plus-based kinds, more-specific atoms must come > + before less-specific ones: mul_low_sum's first arm is any plus, so > + mul_ladder_sum1/3 (which constrain that arm to a plus containing a > + mul_lo) and mul_low_accum (which constrains both arms) shadow it; > + ladder_part_sum is the least specific (one arm unconstrained); and > + mul_cross_sum (any plus) is the fallback. */ > + if (gimple_mul_hilo (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_MUL_HILO, res_ops); > + return true; > + } > + if (gimple_mul_low_accum (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LOW_ACCUM, res_ops); > + return true; > + } > + if (gimple_mul_ladder_sum3 (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_SUM3, res_ops); > + return true; > + } > + if (gimple_mul_ladder_sum1 (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_SUM1, res_ops); > + return true; > + } > + if (gimple_mul_low_sum (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LOW_SUM, res_ops); > + return true; > + } > + if (gimple_mul_ladder_sum2 (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_SUM2, res_ops); > + return true; > + } > + if (gimple_mul_ladder_part_sum (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_PART_SUM, res_ops); > + return true; > + } > + if (gimple_mul_cross_sum (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_CROSS_SUM, res_ops); > + 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. Same specificity ordering as the high-half > + branch. */ > + > +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 (gimple_mul_low_accum (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LOW_ACCUM, res_ops); > + return true; > + } > + if (gimple_mul_ladder_sum3 (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_SUM3, res_ops); > + return true; > + } > + if (gimple_mul_ladder_sum1 (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_SUM1, res_ops); > + return true; > + } > + if (gimple_mul_low_sum (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LOW_SUM, res_ops); > + return true; > + } > + if (gimple_mul_ladder_sum2 (inner, res_ops, NULL)) > + { > + long_mul_set_summand (info, LMK_LADDER_SUM2, res_ops); > + return true; > + } > + 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. SIG[0..COUNT-1] are the > + meaningful summand signatures (4 covers the largest variant); any > + trailing entries are aggregate-init padding and not a sentinel -- > + long_mul_signature_matches reads only the first COUNT. */ > + > +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 auto_vec<long_mul_summand> &, gimple *); > +}; > + > +/* True iff (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 iff H is a cross-half product of (OP0, OP1) -- gimple_mul_hilo > + recognises 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); > +} > + > +/* 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 auto_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; > +} > + > +/* Return the first summand in SUMMANDS whose kind matches KIND, or NULL. */ > + > +static const long_mul_summand * > +long_mul_find_summand (const auto_vec<long_mul_summand> &summands, > + long_mul_kind kind) > +{ > + for (const long_mul_summand &s : summands) > + if (s.kind == kind) > + return &s; > + return NULL; > +} > + > +/* 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, and every captured hilo is a true cross-half product > + of (op0, op1). */ > + > +static bool > +long_mul_check_consistency (const auto_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; > + > + 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; > + } > + > + *op0_out = op0; > + *op1_out = op1; > + return true; > +} > + > +/* Compare the (already-sorted) SUMMANDS multiset against ROW.sig. */ > + > +static bool > +long_mul_signature_matches (const auto_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; > +} > + > +/* Extra check for the two-carries high-part row: the LMK_CARRY_LOW summand's > + two operands (carry_a, carry_b) must be a (cross_shifted, mul_lolo) pair > + consistent with the multiset's canonical (op0, op1). */ > + > +static bool > +long_mul_check_two_carries (const auto_vec<long_mul_summand> &summands, > + gimple *) > +{ > + tree op0, op1; > + if (!long_mul_canonical_ops (summands, &op0, &op1)) > + return false; > + unsigned int halfwidth = TYPE_PRECISION (TREE_TYPE (op0)) / 2; > + > + const long_mul_summand *cl = long_mul_find_summand (summands, > LMK_CARRY_LOW); > + if (!cl) > + return false; > + > + /* The two carry_low operands must be (cross_shifted, mul_lolo) in either > + order. cross_shifted = LSHIFT_EXPR (mul_cross_sum, halfwidth). */ > + tree cs = cl->carry_a, lolo = cl->carry_b; > + tree inner; > + unsigned HOST_WIDE_INT shift; > + if (!long_mul_is_lshift_def (cs, &inner, &shift)) > + { > + std::swap (cs, lolo); > + if (!long_mul_is_lshift_def (cs, &inner, &shift)) > + return false; > + } > + if (shift != halfwidth) > + return false; > + > + tree scratch[LONG_MUL_MAX_CAPTURES]; > + if (!gimple_mul_cross_sum (inner, scratch, NULL)) > + return false; > + for (int i = 0; i < 2; i++) > + if (!long_mul_is_cross_half (scratch[i], op0, op1)) > + return false; > + if (!gimple_mul_lolo (lolo, scratch, NULL) > + || !long_mul_same_ops (scratch[0], scratch[1], op0, op1)) > + return false; > + > + return true; > +} > + > +/* The lolo + cross_shifted shape is also the low half of a two-carry > + long-multiply, where an unsigned overflow compare against one of > + the PLUS operands is the low-carry term consumed by the matching > + high-part fold. Folding to mul_lo here destroys cross_shifted, > + which both the compare and the high-part match still need; defer > + so the high-part fold runs first. After it does, the compare is > + dead and the surviving lolo + cross_shifted is picked up by this > + row in the next forwprop instance. Returns false to defer. */ > + > +static bool > +long_mul_check_low_plus_defer (const auto_vec<long_mul_summand> &, gimple > *stmt) > +{ > + tree lhs = gimple_assign_lhs (stmt); > + tree rhs1 = gimple_assign_rhs1 (stmt); > + tree rhs2 = gimple_assign_rhs2 (stmt); > + > + imm_use_iterator iter; > + gimple *use_stmt; > + FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) > + { > + tree cmp_op1 = NULL_TREE, cmp_op2 = NULL_TREE; > + enum tree_code use_code = ERROR_MARK; > + if (is_gimple_assign (use_stmt)) > + { > + use_code = gimple_assign_rhs_code (use_stmt); > + cmp_op1 = gimple_assign_rhs1 (use_stmt); > + cmp_op2 = gimple_assign_rhs2 (use_stmt); > + } > + else if (gcond *cond = dyn_cast<gcond *> (use_stmt)) > + { > + use_code = gimple_cond_code (cond); > + cmp_op1 = gimple_cond_lhs (cond); > + cmp_op2 = gimple_cond_rhs (cond); > + } > + if (use_code == GT_EXPR || use_code == LT_EXPR > + || use_code == GE_EXPR || use_code == LE_EXPR) > + { > + tree other = (cmp_op1 == lhs) ? cmp_op2 > + : (cmp_op2 == lhs) ? cmp_op1 : NULL_TREE; > + if (other && (other == rhs1 || other == rhs2)) > + 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 the same comparator used on the input summands, so a > + plain element-wise compare suffices for matching. > + > + Scope: all rows describe unsigned schoolbook expansions on an > + even-width 2N-bit type, split at half-width N. Six HIGH_PART rows > + recover xh*yh + the carries/cross-half reductions that produce the > + upper 2N bits; six LOW_PART rows recover the lower 2N bits assembled > + from mul_lolo plus a shifted cross sum or ladder term. > + > + Adding a row: pick PART (HIGH_PART or LOW_PART) and OUTER > + (PLUS_EXPR or BIT_IOR_EXPR). Set COUNT to the number of meaningful > + SIG entries and list them in canonical order (the order > + long_mul_summand_compare produces). EXTRA_CHECK is for invariants > + the (kind, extract) signature cannot express: cross-summand operand > + shapes (e.g. long_mul_check_two_carries) or ordering decisions > + between rows that would otherwise clash (e.g. > + long_mul_check_low_plus_defer). */ > + > +static const long_mul_row long_mul_table[] = { > + /* HIGH-PART folds. 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_sum >> N) + ((hilo > low_sum) << N), > + low_sum = cross_sum + (xl*yl >> N). */ > + { long_mul_row::HIGH_PART, PLUS_EXPR, 3, > + { { LMK_MUL_HIHI, LMX_NONE }, > + { LMK_LOW_SUM, LMX_HI }, > + { LMK_CARRY_LOW_SUM, LMX_NONE } }, > + NULL }, > + /* 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 }, > + /* xh*yh + (cross_sum >> N) + carry_low + ((hilo > cross_sum) << N), > + carry_low = (xl*yl + (cross_sum << N)) < (cross_sum << N). */ > + { long_mul_row::HIGH_PART, PLUS_EXPR, 4, > + { { LMK_MUL_HIHI, LMX_NONE }, > + { LMK_CROSS_SUM, LMX_HI }, > + { LMK_CARRY_LOW, LMX_NONE }, > + { LMK_CARRY_CROSS_SUM, LMX_NONE } }, > + long_mul_check_two_carries }, > + /* xh*yh + (hilo >> N) + (ladder_sum1 >> N), > + ladder_sum1 = (hilo & mask) + hilo' + (xl*yl >> N), > + hilo, hilo' the two cross-half products. */ > + { long_mul_row::HIGH_PART, PLUS_EXPR, 3, > + { { LMK_MUL_HIHI, LMX_NONE }, > + { LMK_MUL_HILO, LMX_HI }, > + { LMK_LADDER_SUM1, LMX_HI } }, > + NULL }, > + /* xh*yh + (ladder_sum2 >> N) + (ladder_part_sum >> N), > + ladder_part_sum = (xl*yl >> N) + hilo, > + ladder_sum2 = (ladder_part_sum & mask) + hilo'. */ > + { long_mul_row::HIGH_PART, PLUS_EXPR, 3, > + { { LMK_MUL_HIHI, LMX_NONE }, > + { LMK_LADDER_SUM2, LMX_HI }, > + { LMK_LADDER_PART_SUM, LMX_HI } }, > + NULL }, > + /* xh*yh + (hilo >> N) + (hilo' >> N) + (ladder_sum3 >> N), > + ladder_sum3 = (hilo & mask) + (hilo' & mask) + (xl*yl >> N). */ > + { long_mul_row::HIGH_PART, PLUS_EXPR, 4, > + { { LMK_MUL_HIHI, LMX_NONE }, > + { LMK_MUL_HILO, LMX_HI }, > + { LMK_MUL_HILO, LMX_HI }, > + { LMK_LADDER_SUM3, LMX_HI } }, > + NULL }, > + /* LOW-PART folds. Recover the lower 2N bits from xl*yl plus a > + shifted cross-half term. Notation as for HIGH-PART rows above. */ > + /* xl*yl + (cross_sum << N). */ > + { long_mul_row::LOW_PART, PLUS_EXPR, 2, > + { { LMK_MUL_LOLO, LMX_NONE }, > + { LMK_CROSS_SUM, LMX_SHL_N } }, > + long_mul_check_low_plus_defer }, > + /* (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 }, > + /* (xl*yl & mask) | (low_sum << N), > + low_sum = cross_sum + (xl*yl >> N). */ > + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, > + { { LMK_MUL_LOLO, LMX_LO }, > + { LMK_LOW_SUM, LMX_SHL_N } }, > + NULL }, > + /* (xl*yl & mask) | (ladder_sum1 << N), > + ladder_sum1 as in the high ladder row above. */ > + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, > + { { LMK_MUL_LOLO, LMX_LO }, > + { LMK_LADDER_SUM1, LMX_SHL_N } }, > + NULL }, > + /* (xl*yl & mask) | (ladder_sum2 << N), > + ladder_sum2 as in the high ladder row above. */ > + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, > + { { LMK_MUL_LOLO, LMX_LO }, > + { LMK_LADDER_SUM2, LMX_SHL_N } }, > + NULL }, > + /* (xl*yl & mask) | (ladder_sum3 << N), > + ladder_sum3 as in the high ladder-long row above. */ > + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, > + { { LMK_MUL_LOLO, LMX_LO }, > + { LMK_LADDER_SUM3, LMX_SHL_N } }, > + NULL }, > +}; > + > +/* If a multi-used inner addition (sharing the chain's outer code) blocked > + linearization of a long-mul candidate, emit a dump-file hint pointing > + at it. Caching that partial sum into a single-use SSA name normally > + enables the fold. */ > + > +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 linearise/classify work on every other PLUS/IOR > + in the TU. */ > + 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> 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> summands; > + summands.reserve_exact (leaves.length ()); > + 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 need the target to support highpart multiply (directly > + or via widening multiply + shift); LOW_PART rows emit a plain > + MULT_EXPR and are always available. Probe once and use it to skip > + HIGH_PART rows on unsupported targets without burning the consistency > + check first. */ > + scalar_int_mode lhs_mode; > + bool can_high = is_a<scalar_int_mode> (TYPE_MODE (lhs_type), &lhs_mode) > + && can_mult_highpart_p (lhs_mode, true); > + > + for (const long_mul_row &row : long_mul_table) > + { > + if (row.outer != outer) > + continue; > + if (row.part == long_mul_row::HIGH_PART && !can_high) > + continue; > + if (!long_mul_signature_matches (summands, row)) > + continue; > + > + tree op0, op1; > + if (!long_mul_check_consistency (summands, &op0, &op1)) > + continue; > + > + if (row.extra_check && !row.extra_check (summands, stmt)) > + continue; > + > + if (row.part == long_mul_row::HIGH_PART) > + { > + if (!create_mul_high_seq (op0, op1, stmt)) > + return false; > + 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. */ > @@ -5212,6 +6091,9 @@ public: > case 1: > last_p = param; > break; > + case 2: > + m_long_mul_fold_p = param; > + break; > default: > gcc_unreachable(); > } > @@ -5225,6 +6107,12 @@ public: > > /* True if the aggregate props are doing a full walk or not. */ > bool m_full_walk = false; > + > + /* True if the pass instance should fold longhand wide-multiplication > + idioms. Skipped in the pre-IPA instance because the fold consults > + target optabs, which during offload compilation reflect the host > + target rather than the consuming target. */ > + bool m_long_mul_fold_p = false; > }; // class pass_forwprop > > /* Attemp to make the BB block of __builtin_unreachable unreachable by > changing > @@ -5829,11 +6717,17 @@ 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 = false; > + if (m_long_mul_fold_p) > + 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.52.0 >
