Recognize longhand wide-multiplication idioms and fold them into 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. HIGH_PART rows emit the canonical widening shape (N)(((2N) op1 * (2N) op2) >> N) which pass_optimize_widening_mul later lowers to a single WIDEN_MULT_EXPR or MULT_HIGHPART_EXPR on targets that support it. LOW_PART rows emit a plain MULT_EXPR. HIGH_PART rows are skipped when the target lacks the 2N scalar mode, so the canonical shape never survives to RTL expansion as a libcall. scalar_mode_supported_p is a static target property, invariant across forwprop instances, so the fold remains eligible in pre-IPA forwprop1. 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). * tree-ssa-forwprop.cc (create_mul_high_seq): New, emits (N)(((2N) op1 * (2N) op2) >> N). (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. Skips HIGH_PART rows when the 2N scalar mode is not supported by the target. (long_mul_table): New table of long-multiply variants. (pass_forwprop::execute): Call match_long_mul on PLUS_EXPR and BIT_IOR_EXPR statements. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/long-mul-carry.c: New test. * gcc.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 v5: - 1/2: - Replace the match.pd simplify on COND_EXPR with cond_carry_add / cond_carry_add_neg match recognizers (cond^), split by gcond polarity, plus a flatten_cond_carry_add driver in tree-ssa-forwprop.cc. The driver inverts the gcond's comparison for the _neg form. Modelled on match_saturation_add. - Remove fold_cond_carry_add_profitable_p and the tm_p.h / predict.h includes from gimple-match-head.cc. The width > MAX_FIXED_MODE_SIZE and width % 2 != 0 guards were prerequisites for the can_mult_highpart_p fallback path, not soundness checks. type_has_mode_precision_p subsumes them. - Retarget the test scans from phiopt2 to forwprop1. Add forwprop-46.c covering all four arm/comparison polarities. - forwprop-45.c uses __UINT64_TYPE__ instead of unsigned long and drops the lp64 restriction, covering the type > word_mode regime on 32-bit targets. - 2/2: - Lower the high-part as (N)(((2N) op1 * (2N) op2) >> N). pass_optimize_widening_mul rewrites this to WIDEN_MULT_EXPR / MULT_HIGHPART_EXPR on supporting targets. Removes can_mult_highpart_p queries from forwprop. - Replace the can_mult_highpart_p prefilter in match_long_mul with a targetm.scalar_mode_supported_p check on the 2N mode. Test scans select on int128, mirroring the gate, instead of lp64. - Drop the m_long_mul_fold_p pass parameter and its passes.def arguments. The long-mul fold runs in every forwprop instance. Test scans retargeted from forwprop2 to forwprop1. - Stop restricting forwprop-44.c to lp64. With the can_mult_highpart_p gating gone, the fold is target-independent and the test passes on ilp32 targets too. 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.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 | 311 ++++++ .../gcc.dg/tree-ssa/long-mul-ladder.c | 329 +++++++ .../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 | 116 +++ gcc/testsuite/gcc.target/aarch64/long_mul.c | 100 ++ gcc/testsuite/gcc.target/i386/long_mul.c | 100 ++ gcc/tree-ssa-forwprop.cc | 902 +++++++++++++++++- 11 files changed, 2726 insertions(+), 5 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 43d56e851172..cec8f9f8fa06 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -11870,6 +11870,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/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..ecffabb3eda0 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c @@ -0,0 +1,311 @@ +/* { 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." 8 "forwprop1" { target int128 } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 2 "forwprop2" { target int128 } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 5 "forwprop1" { target { ! int128 } } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 2 "forwprop1" } } */ 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..00b5cc0d937e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c @@ -0,0 +1,329 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-forwprop-details" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; +typedef struct { uint32_t v[2]; } v2i32; +typedef struct { uint64_t v[2]; } v2i64; + +uint64_t mulh_ladder (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t t0 = y_lo * x_lo; + uint64_t t1 = y_lo * x_hi; + uint64_t t2 = y_hi * x_lo; + uint64_t t3 = y_hi * x_hi; + uint64_t t0_hi = t0 >> 32; + uint64_t u0 = t0_hi + t1; + uint64_t u0_lo = u0 & 0xFFFFFFFF; + uint64_t u0_hi = u0 >> 32; + uint64_t u1 = u0_lo + t2; + uint64_t u1_hi = u1 >> 32; + uint64_t u2 = u0_hi + t3; + uint64_t hw64 = u2 + u1_hi; + + return hw64; +} + +uint64_t mulh_ladder_comm (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t t0 = x_lo * y_lo; + uint64_t t1 = x_lo * y_hi; + uint64_t t2 = x_hi * y_lo; + uint64_t t3 = x_hi * y_hi; + uint64_t t0_hi = t0 >> 32; + uint64_t u0 = t1 + t0_hi; + uint64_t u0_lo = u0 & 0xFFFFFFFF; + uint64_t u0_hi = u0 >> 32; + uint64_t u1 = t2 + u0_lo; + uint64_t u1_hi = u1 >> 32; + uint64_t u2 = u1_hi + u0_hi; + uint64_t hw64 = t3 + u2; + + return hw64; +} + +uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t y_lo = y & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_hi = y >> 16; + uint32_t t0 = y_lo * x_lo; + uint32_t t1 = y_lo * x_hi; + uint32_t t2 = y_hi * x_lo; + uint32_t t3 = y_hi * x_hi; + uint32_t t0_hi = t0 >> 16; + uint32_t u0 = t0_hi + t1; + uint32_t u0_lo = u0 & 0xFFFF; + uint32_t u0_hi = u0 >> 16; + uint32_t u1 = u0_lo + t2; + uint32_t u1_hi = u1 >> 16; + uint32_t u2 = u0_hi + t3; + uint32_t hw64 = u2 + u1_hi; + + return hw64; +} + +/* The 128-bit variant 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." 8 "forwprop1" { target int128 } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 2 "forwprop2" { target int128 } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 5 "forwprop1" { target { ! int128 } } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 2 "forwprop1" } } */ 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..b64fad8b964d --- /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 "forwprop1" } } */ 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..4307793d4c46 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c @@ -0,0 +1,116 @@ +/* { 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. On targets + without a native 2N scalar mode the HIGH fold is skipped, so the + paired LOW fold for full_mul_two_carry stays deferred and never + fires either. */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 4 "forwprop3" { target int128 } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 1 "forwprop3" { target { ! int128 } } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 1 "forwprop4" { target int128 } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 0 "forwprop4" { target { ! int128 } } } } */ 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 1e8f3aab48f4..7dbe3d7d4741 100644 --- a/gcc/tree-ssa-forwprop.cc +++ b/gcc/tree-ssa-forwprop.cc @@ -3641,6 +3641,894 @@ flatten_cond_carry_add (gphi *phi) 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, emitted as + (N)(((2N) op1 * (2N) op2) >> N). + pass_optimize_widening_mul's convert_mult_to_widen and + convert_mult_to_highpart later rewrite this to a single + WIDEN_MULT_EXPR or MULT_HIGHPART_EXPR when the target supports it, + otherwise the 2N multiply expands directly. Emitting the canonical + widening shape keeps target-capability decisions in the layer that + already owns them. */ + +static void +create_mul_high_seq (tree op1, tree op2, gimple *stmt) +{ + tree op_type = TREE_TYPE (op1); + unsigned int width = TYPE_PRECISION (op_type); + tree wide_type = build_nonstandard_integer_type (width * 2, 1); + + location_t loc = gimple_location (stmt); + gimple_seq seq = NULL; + + tree wide_a = gimple_convert (&seq, loc, wide_type, op1); + tree wide_b = gimple_convert (&seq, loc, wide_type, op2); + tree wide_prod = gimple_build (&seq, loc, MULT_EXPR, wide_type, + wide_a, wide_b); + tree hi = gimple_build (&seq, loc, RSHIFT_EXPR, wide_type, wide_prod, + build_int_cst (integer_type_node, width)); + + gimple *prod = gimple_build_assign (gimple_get_lhs (stmt), NOP_EXPR, hi); + gimple_set_location (prod, loc); + gimple_seq_add_stmt (&seq, prod); + + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gsi_replace_with_seq (&gsi, seq, true); +} + +/* Replace STMT with a low-part multiply of OP1 and OP2. */ + +static void +create_mul_low_seq (tree op1, tree op2, gimple *stmt) +{ + gimple *prod = gimple_build_assign (gimple_get_lhs (stmt), + MULT_EXPR, op1, op2); + gimple_set_location (prod, gimple_location (stmt)); + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gsi_replace (&gsi, prod, true); +} + +/* Long-multiply fold framework. + + Walks the outer addition or bit_ior chain on a candidate statement, + classifies each summand against the atom match patterns from + match.pd, and looks the resulting multiset of (kind, extract) tuples + up in a table. On a hit, three cross-summand consistency checks + decide whether the wide multiply is emitted. */ + +/* Widest match.pd atom (mul_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 emit a 2N-bit multiply (later lowered by + pass_optimize_widening_mul); LOW_PART rows emit a plain MULT_EXPR. + Skip HIGH_PART rows when the target lacks the 2N scalar mode, so + the multiply does not survive to RTL expansion as a libcall. + scalar_mode_supported_p is a static target property, invariant + across forwprop instances. */ + scalar_int_mode mode, wide_mode; + bool can_emit_high + = is_a <scalar_int_mode> (TYPE_MODE (lhs_type), &mode) + && GET_MODE_2XWIDER_MODE (mode).exists (&wide_mode) + && targetm.scalar_mode_supported_p (wide_mode); + + for (const long_mul_row &row : long_mul_table) + { + if (row.outer != outer + || (row.part == long_mul_row::HIGH_PART && !can_emit_high) + || !long_mul_signature_matches (summands, row)) + continue; + + tree op0, op1; + if (!long_mul_check_consistency (summands, &op0, &op1)) + continue; + + if (row.extra_check && !row.extra_check (summands, stmt)) + continue; + + if (row.part == long_mul_row::HIGH_PART) + { + create_mul_high_seq (op0, op1, stmt); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Long multiplication high part folded.\n"); + return true; + } + create_mul_low_seq (op0, op1, stmt); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Long multiplication low part folded.\n"); + return true; + } + + long_mul_hint_shared_intermediate (shared_def); + return false; +} + /* Determine whether applying the 2 permutations (mask1 then mask2) gives back one of the input. */ @@ -5904,11 +6792,15 @@ pass_forwprop::execute (function *fun) } else if (TREE_CODE_CLASS (code) == tcc_comparison) changed |= forward_propagate_into_comparison (&gsi); - else if ((code == PLUS_EXPR - || code == BIT_IOR_EXPR - || code == BIT_XOR_EXPR) - && simplify_rotate (&gsi)) - changed = true; + else if ((code == PLUS_EXPR || code == BIT_IOR_EXPR)) + { + bool folded = match_long_mul (stmt); + if (!folded) + folded = simplify_rotate (&gsi); + changed |= folded; + } + else if (code == BIT_XOR_EXPR) + changed |= simplify_rotate (&gsi); else if (code == VEC_PERM_EXPR) changed |= simplify_permutation (&gsi); else if (code == CONSTRUCTOR -- 2.52.0
