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 recognisers for long-multiply (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, mul_ladder_sum2, mul_ladder_sum3, mul_ladder_part_sum). * tree-ssa-forwprop.cc (gimple_mul_hi): Declare. (gimple_mul_lo): Likewise. (gimple_mul_hilo): Likewise. (gimple_mul_lolo): Likewise. (gimple_mul_hihi): Likewise. (gimple_mul_low_sum): Likewise. (gimple_mul_carry_cross_sum): Likewise. (gimple_mul_carry_low_sum): Likewise. (gimple_mul_low_accum): Likewise. (gimple_mul_cross_sum): Likewise. (gimple_mul_ladder_part_sum): Likewise. (gimple_mul_ladder_sum1): Likewise. (gimple_mul_ladder_sum2): Likewise. (gimple_mul_ladder_sum3): Likewise. (gimple_mul_carry_low): Likewise. (create_mul_high_seq): New, emits (N)(((2N) op1 * (2N) op2) >> N). (create_mul_low_seq): New, emits MULT_EXPR. (enum long_mul_kind): New. (enum long_mul_extract): New. (struct long_mul_summand): New. (long_mul_linearize_chain): New, walks the outer add/ior chain into a multiset of leaves. (long_mul_is_lshift_def): New. (long_mul_set_summand): New. (long_mul_classify_carry): New. (long_mul_classify_plus_kinds): New. (long_mul_classify_hi_extract): New. (long_mul_classify_lo_extract): New. (long_mul_classify_shl_extract): New. (long_mul_classify_bare): New. (long_mul_classify_summand): New, classify each summand via the match.pd atoms. (long_mul_summand_compare): New. (struct long_mul_row): New. (long_mul_same_ops): New. (long_mul_is_cross_half): New. (long_mul_canonical_ops): New. (long_mul_find_summand): New. (long_mul_check_consistency): New, cross-summand consistency check (operand pairing, half-width shifts, hilo cross-half). (long_mul_signature_matches): New. (long_mul_check_two_carries): New. (long_mul_check_low_plus_defer): New. (long_mul_hint_shared_intermediate): New, dump-file hint pointing at a shared inner addition. (long_mul_table): New table of long-multiply variants. (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. (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]> --- (no changes since v1) 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 | 895 +++++++++++++++++- 11 files changed, 2719 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 475939a0b638..d58b3721a576 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -11887,6 +11887,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 (long_mul_check_consistency). */ +(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..37c0193ece09 --- /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 long_mul_check_low_plus_defer + 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..0c022094a379 --- /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. + long_mul_check_consistency 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 9bb001d2f63b..cfe2709e63ab 100644 --- a/gcc/tree-ssa-forwprop.cc +++ b/gcc/tree-ssa-forwprop.cc @@ -3569,6 +3569,887 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) } +/* 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, 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; +} + +/* Plus-based summand kinds shared by the (X >> SHIFT) and (X << SHIFT) + classifiers. Order is by specificity: mul_low_sum's first arm is any + plus, so mul_ladder_sum1/3 (which constrain that arm to a plus + containing a mul_lo) and mul_low_accum (which constrains both arms) + shadow it and must come first. */ + +static bool +long_mul_classify_plus_kinds (tree inner, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + if (gimple_mul_low_accum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LOW_ACCUM, res_ops); + return true; + } + if (gimple_mul_ladder_sum3 (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LADDER_SUM3, res_ops); + return true; + } + if (gimple_mul_ladder_sum1 (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LADDER_SUM1, res_ops); + return true; + } + if (gimple_mul_low_sum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LOW_SUM, res_ops); + return true; + } + if (gimple_mul_ladder_sum2 (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LADDER_SUM2, res_ops); + return true; + } + return false; +} + +/* Classify INNER -- already unwrapped from an outer (X >> SHIFT) -- as + a high-half-extracted summand. mul_hilo (mult-shape) is orthogonal + to the plus-based kinds and is tried first; ladder_part_sum (one arm + unconstrained) and mul_cross_sum (any plus) are the fallbacks after + the shared plus-based ladder. */ + +static bool +long_mul_classify_hi_extract (tree inner, unsigned HOST_WIDE_INT shift, + long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + info->extract = LMX_HI; + info->shift = shift; + if (gimple_mul_hilo (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_HILO, res_ops); + return true; + } + if (long_mul_classify_plus_kinds (inner, info)) + return true; + if (gimple_mul_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. No mul_hilo / ladder_part_sum here -- those + shapes appear only under (X >> SHIFT). */ + +static bool +long_mul_classify_shl_extract (tree inner, unsigned HOST_WIDE_INT shift, + long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + info->extract = LMX_SHL_N; + info->shift = shift; + if (long_mul_classify_plus_kinds (inner, info)) + return true; + if (gimple_mul_cross_sum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_CROSS_SUM, res_ops); + return true; + } + return false; +} + +/* Classify LEAF as one of the bare-kind summands (no extraction + wrapper): mul_hihi or mul_lolo standing on their own. */ + +static bool +long_mul_classify_bare (tree leaf, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + if (gimple_mul_hihi (leaf, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_HIHI, res_ops); + return true; + } + if (gimple_mul_lolo (leaf, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_LOLO, res_ops); + return true; + } + return false; +} + +/* Classify LEAF as one of the long-multiply summand shapes. On success, + fill *INFO with the kind, extract, captured operands and shift/mask. + Dispatches to per-extract helpers; the order matters because the + carry kinds bake an lshift into the pattern and would otherwise be + misread by the (X << N) branch. */ + +static bool +long_mul_classify_summand (tree leaf, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + *info = {}; + + if (long_mul_classify_carry (leaf, info)) + return true; + + if (gimple_mul_hi (leaf, res_ops, NULL)) + return long_mul_classify_hi_extract (res_ops[0], + tree_to_uhwi (res_ops[1]), info); + + if (gimple_mul_lo (leaf, res_ops, NULL)) + return long_mul_classify_lo_extract (res_ops[0], + tree_to_uhwi (res_ops[1]), info); + + tree inner; + unsigned HOST_WIDE_INT shift; + if (long_mul_is_lshift_def (leaf, &inner, &shift)) + return long_mul_classify_shl_extract (inner, shift, info); + + return long_mul_classify_bare (leaf, info); +} + +/* qsort comparator: sort summands by (kind, extract) to put a multiset + into canonical order for table lookup. Unstable sort within a tie is + harmless: no row in long_mul_table pairs distinct subterms under the + same (kind, extract), and long_mul_check_consistency cross-validates + that matching summands share one canonical (op0, op1). */ + +static int +long_mul_summand_compare (const void *a, const void *b) +{ + const long_mul_summand *sa = (const long_mul_summand *) a; + const long_mul_summand *sb = (const long_mul_summand *) b; + if (sa->kind != sb->kind) + return (int) sa->kind - (int) sb->kind; + return (int) sa->extract - (int) sb->extract; +} + +/* One row of the long-multiply variant table. 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 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 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 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 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 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 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 vec<long_mul_summand> &, gimple *stmt) +{ + /* The PHI entry passes its gphi as the candidate but commits only to + HIGH_PART rows, so a LOW_PART row never folds from there. Guard the + gimple_assign accessors regardless, so this stays correct if a future + PLUS-shaped row reachable from the PHI path uses it. */ + if (!is_gimple_assign (stmt)) + return false; + + 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, LONG_MUL_MAX_SUMMANDS + 1> leaves; + gimple *shared_def = NULL; + if (!long_mul_linearize_chain (stmt, outer, leaves, &shared_def)) + return false; + if (leaves.length () < 2) + return false; + + auto_vec<long_mul_summand, LONG_MUL_MAX_SUMMANDS> summands; + for (tree leaf : leaves) + { + long_mul_summand s; + if (!long_mul_classify_summand (leaf, &s)) + { + long_mul_hint_shared_intermediate (shared_def); + return false; + } + summands.quick_push (s); + } + summands.qsort (long_mul_summand_compare); + + /* HIGH_PART rows emit a 2N-bit multiply (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. */ @@ -5827,11 +6708,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
