[PATCH v8 1/7] forwprop: Match and fold the long-multiply carry form [PR107090]
Konstantinos Eleftheriou <[email protected]> Mon, 3 Aug 2026 08:41:35 -0700
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
Recognize the longhand wide-multiplication carry idiom and fold it to a widening multiply followed by a right shift for the high part, and a plain MULT_EXPR for the low part. The carry idiom is the schoolbook expansion of a 2N-bit unsigned multiply written as a top-level + chain of four NxN partial products plus one overflow-compare carry: xh*yh + (cross_sum >> N) + (low_accum >> N) + ((hilo > cross_sum) << N) cross_sum = xh*yl + xl*yh low_accum = (xl*yl >> N) + (cross_sum & mask) For example, this AArch64 sequence from SPEC2026's 750.sealcrypto_r: lsr x4, x0, 32 lsr x6, x1, 32 umull x3, w0, w1 umull x1, w1, w4 and x5, x3, 4294967295 umaddl x0, w0, w6, x1 cmp x1, x0 and x1, x0, 4294967295 lsr x0, x0, 32 add x3, x1, x3, lsr 32 cset x1, hi orr x5, x5, x3, lsl 32 umaddl x4, w4, w6, x0 extr x0, x1, x3, 32 add x0, x0, x4 stp x5, x0, [x2] can be transformed to: umulh x3, x1, x0 mul x0, x0, x1 stp x0, x3, [x2] Atom-level pattern recognition is implemented via match patterns in match.pd (mul_hi, mul_lo, mul_hilo, mul_lolo, mul_hihi, mul_cross_sum, mul_low_accum, mul_carry_cross_sum). The composite recognition that ties atoms into a long-multiplication chain is performed in forwprop. match_long_mul is the entry point; long_mul_classify_chain linearizes the outer add/ior chain into a multiset of summands, classifies each summand via the match.pd atoms, and hands the multiset to long_mul_classify_match, which looks it 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. build_mul_high_seq emits the wide product into a caller-supplied destination. The three helpers are split out so a second entry point can reuse them. The HIGH_PART row emits the canonical widening shape (N)(((2N) op1 * (2N) op2) >> N) which pass_optimize_widening_mul later lowers to a single WIDEN_MULT_EXPR or MULT_HIGHPART_EXPR on targets that support it. The LOW_PART row emits a plain MULT_EXPR. HIGH_PART is emitted only when the 2N mode is present in the mode table. Matching starts only at the end of a chain: when a statement's result feeds another same-code statement in the same block, that consumer's own attempt linearizes through it and sees the whole chain, so starting at interior statements is redundant work. A consumer in another block does not count: folding at the later use could sink a loop-invariant multiply into a loop. Leaves that classify as no long-multiply summand do not fail the match. They are set aside (up to LONG_MUL_MAX_EXTRAS) and re-applied on top of the folded multiply under the chain's own operation. This keeps the chain-end restriction from regressing chains whose fold result feeds a wider sum, and covers chains where reassociation merged unrelated addends into the long-multiply sum, such as an accumulator `acc += mulh (x, y)`. A leaf that does classify is always consumed by the multiset: if the resulting signature misses every row the match fails rather than retrying with the leaf demoted to an extra, since a subset search would be exponential. PR tree-optimization/107090 gcc/ChangeLog: * match.pd: Add atom match recognizers for long-multiply (mul_hi, mul_lo, mul_hilo, mul_lolo, mul_hihi, mul_cross_sum, mul_low_accum, mul_carry_cross_sum). * tree-ssa-forwprop.cc (gimple_mul_hi): Declare. (gimple_mul_lo): Likewise. (gimple_mul_hilo): Likewise. (gimple_mul_lolo): Likewise. (gimple_mul_hihi): Likewise. (gimple_mul_cross_sum): Likewise. (gimple_mul_low_accum): Likewise. (gimple_mul_carry_cross_sum): Likewise. (build_mul_high_seq): New, emits (N)(((2N) op1 * (2N) op2) >> N) into a caller-supplied destination. (long_mul_apply_extras): New, combines the preserved addends back on top of the folded multiply. (create_mul_high_seq): New, replaces the statement with the high-part multiply plus any extras. (create_mul_low_seq): New, likewise for the low part. (enum long_mul_kind): New. (enum long_mul_extract): New. (struct long_mul_summand): New. (long_mul_linearize_chain): New, walks the outer add/ior chain into a multiset of leaves. (long_mul_is_lshift_def): New. (long_mul_set_summand): New. (long_mul_classify_carry): New. (long_mul_classify_plus_kinds): New. (long_mul_classify_hi_extract): New. (long_mul_classify_lo_extract): New. (long_mul_classify_shl_extract): New. (long_mul_classify_bare): New. (long_mul_classify_summand): New, classify each summand via the match.pd atoms. (long_mul_summand_compare): New. (struct long_mul_row): New. (long_mul_same_ops): New. (long_mul_is_cross_half): New. (long_mul_hilo_orientation): New, orientation of a mul_hilo capture relative to (op0, op1). (long_mul_canonical_ops): New. (long_mul_check_consistency): New, cross-summand consistency check (operand pairing, half-width shifts, hilo cross-half). (long_mul_signature_matches): New. (long_mul_hint_shared_intermediate): New, dump-file hint pointing at a shared inner addition. (long_mul_classify_match): New, looks a summand multiset up in long_mul_table and runs the per-row checks. (long_mul_classify_chain): New, linearize plus classify plus table lookup; sets aside leaves that classify as no summand. (match_long_mul): New, top-level entry: starts only at a chain end, classifies the chain, and dispatches to create_mul_high_seq / create_mul_low_seq with any preserved addends. (pass_forwprop::execute): Call match_long_mul on PLUS_EXPR and BIT_IOR_EXPR statements. gcc/testsuite/ChangeLog: * gcc.dg/torture/long-mul-64-run.c: New test. * gcc.dg/tree-ssa/long-mul-carry.c: New test. * gcc.dg/tree-ssa/long-mul-extra-addend.c: New test. * gcc.target/aarch64/long_mul.c: New test. * gcc.target/i386/long_mul.c: New test. Co-authored-by: Philipp Tomsich <[email protected]> Signed-off-by: Konstantinos Eleftheriou <[email protected]> --- (no changes since v1) gcc/match.pd | 73 ++ .../gcc.dg/torture/long-mul-64-run.c | 79 ++ .../gcc.dg/tree-ssa/long-mul-carry.c | 181 ++++ .../gcc.dg/tree-ssa/long-mul-extra-addend.c | 63 ++ gcc/testsuite/gcc.target/aarch64/long_mul.c | 58 ++ gcc/testsuite/gcc.target/i386/long_mul.c | 58 ++ gcc/tree-ssa-forwprop.cc | 804 +++++++++++++++++- 7 files changed, 1310 insertions(+), 6 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/torture/long-mul-64-run.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-extra-addend.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 017b1362b7e4..7374d7a27182 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -12183,6 +12183,79 @@ and, INTEGER_CST@2) INTEGER_CST@3) (if (compare_tree_int (@sub1, 1) == 0))) +#if GIMPLE +/* Match low and high parts of longhand multiplication. + Given a 2N-bit unsigned type, x = xh*2^N + xl and y = yh*2^N + yl, + where xh, xl, yh, yl are N-bit halves extracted via shifts and masks. */ + +/* High half: op >> N. */ +(match (mul_hi @op @0) + (rshift @op INTEGER_CST@0) + (with { + tree op_type = TREE_TYPE (@op); } + (if (INTEGRAL_TYPE_P (op_type) + && TYPE_UNSIGNED (op_type) + && TYPE_PRECISION (op_type) % 2 == 0 + && tree_fits_uhwi_p (@0) + && tree_to_uhwi (@0) == TYPE_PRECISION (op_type) / 2)))) +/* Low half: op & mask. */ +(match (mul_lo @op @0) + (bit_and @op INTEGER_CST@0) + (with { + tree op_type = TREE_TYPE (@op); } + (if (INTEGRAL_TYPE_P (op_type) + && TYPE_UNSIGNED (op_type) + && TYPE_PRECISION (op_type) % 2 == 0 + && tree_fits_uhwi_p (@0) + && tree_to_uhwi (@0) == wi::mask ( + TYPE_PRECISION (op_type) / 2, + false, + TYPE_PRECISION (op_type)))))) +/* Cross product: high(op0) * low(op1). */ +(match (mul_hilo @op0 @op1 @0 @1) + (mult:c + (mul_hi @op0 INTEGER_CST@0) + (mul_lo @op1 INTEGER_CST@1))) +/* Low-low product: low(op0) * low(op1). */ +(match (mul_lolo @op0 @op1 @0) + (mult:c + (mul_lo @op0 INTEGER_CST@0) + (mul_lo @op1 INTEGER_CST@0))) +/* High-high product: high(op0) * high(op1). */ +(match (mul_hihi @op0 @op1 @0) + (mult:c + (mul_hi @op0 INTEGER_CST@0) + (mul_hi @op1 INTEGER_CST@0))) +/* Cross sum: xh*yl + xl*yh. + Note: matches any PLUS; operands are validated as actual cross + products by the forwprop consumer (long_mul_check_consistency). */ +(match (mul_cross_sum @mul_hilo0 @mul_hilo1) + (plus:c @mul_hilo0 @mul_hilo1)) +/* Carry from cross-sum overflow: (cast?) (hilo > cross_sum) << N. + Explicit guard required because mul_cross_sum is just (plus:c @0 @1) + with no inherent type or halfwidth constraint. */ +(match (mul_carry_cross_sum @mul_hilo0 @mul_hilo1 @mul_hilo2 @0) + (lshift + (convert? (gt + @mul_hilo0 + (mul_cross_sum @mul_hilo1 @mul_hilo2))) + INTEGER_CST@0) + (with { + tree op_type = TREE_TYPE (@mul_hilo0); } + (if (INTEGRAL_TYPE_P (op_type) + && TYPE_UNSIGNED (op_type) + && TYPE_PRECISION (op_type) % 2 == 0 + && tree_fits_uhwi_p (@0) + && tree_to_uhwi (@0) == TYPE_PRECISION (op_type) / 2)))) +/* Low accumulate: (xl*yl >> N) + (cross_sum & mask). */ +(match (mul_low_accum @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) + (plus:c + (mul_hi + (mul_lolo @op0 @op1 INTEGER_CST@0) + INTEGER_CST@1) + (mul_lo (mul_cross_sum @mul_hilo0 @mul_hilo1) INTEGER_CST@0))) +#endif + /* Floatint point/integer comparison and integer->integer or floating point -> float point conversion. */ (match (cond_expr_convert_p @0 @2 @3 @6) diff --git a/gcc/testsuite/gcc.dg/torture/long-mul-64-run.c b/gcc/testsuite/gcc.dg/torture/long-mul-64-run.c new file mode 100644 index 000000000000..8546573d91cf --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/long-mul-64-run.c @@ -0,0 +1,79 @@ +/* { dg-do run { target int128 } } */ + +/* Runtime behavior of the recognizer on the longhand 64x64 high-part + idiom, checked against a 128-bit reference multiply. Covers chains + carrying an extra addend, where the folded form must keep the addend + on top of the wide multiply. */ + +typedef __UINT64_TYPE__ uint64_t; +typedef unsigned __int128 uint128_t; + +/* The genuine idiom. */ +__attribute__((noipa)) uint64_t +mulh_good (uint64_t x, uint64_t y) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + uint64_t carry = (uint64_t) (hilo > low_sum) << 32; + return xh * yh + (low_sum >> 32) + carry; +} + +/* Extra addend appended after the full chain. */ +__attribute__((noipa)) uint64_t +mulh_acc (uint64_t x, uint64_t y, uint64_t acc) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + int carry_out = hilo > low_sum; + uint64_t carry = (uint64_t) carry_out << 32; + return xh * yh + (low_sum >> 32) + carry + acc; +} + +/* Extra addend interleaved into the middle of the chain. */ +__attribute__((noipa)) uint64_t +mulh_acc_interleaved (uint64_t x, uint64_t y, uint64_t acc) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + int carry_out = hilo > low_sum; + uint64_t carry = (uint64_t) carry_out << 32; + return ((xh * yh + acc) + (low_sum >> 32)) + carry; +} + +int +main (void) +{ + static const uint64_t vals[] = { + 0, 1, 0xFFFFFFFFULL, 0x100000000ULL, 0xFFFFFFFFFFFFFFFFULL, + 0xDEADBEEFCAFEBABEULL, 0x8000000080000000ULL, 0x00000001FFFFFFFFULL + }; + const 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], z = vals[(i + j) % n]; + uint64_t hi = (uint64_t) (((uint128_t) x * y) >> 64); + if (mulh_good (x, y) != hi) + __builtin_abort (); + if (mulh_acc (x, y, z) != hi + z) + __builtin_abort (); + if (mulh_acc_interleaved (x, y, z) != hi + z) + __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..bbdbc63ac0bb --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c @@ -0,0 +1,181 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-forwprop-details" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; +typedef struct { uint32_t v[2]; } v2i32; + +/* High part follows the long form + xh*yh + carry + (cross_sum >> N) + (low_accum >> N). */ + +uint64_t mulh_carry (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = cross_sum < y_lo_x_hi; + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint64_t interm = cross_sum_hi + y_hi_x_hi; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t interm_plus_carry = interm + carry; + uint64_t hw64 = interm_plus_carry + low_accum_hi; + + return hw64; +} + +uint64_t mulh_carry_comm (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = x_hi * y_lo; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = x_lo * y_hi; + uint64_t y_lo_x_lo = x_lo * y_lo; + uint64_t cross_sum = y_lo_x_hi + y_hi_x_lo; + int carry_out = (cross_sum < y_lo_x_hi); + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = y_lo_x_lo_hi + cross_sum_lo; + uint64_t inter = y_hi_x_hi + cross_sum_hi; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t interm_plus_carry = carry + inter; + uint64_t hw64 = low_accum_hi + interm_plus_carry; + + return hw64; +} + +uint32_t mulh_carry_32 (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo_x_hi = y_lo * x_hi; + uint32_t y_hi_x_hi = y_hi * x_hi; + uint32_t y_hi_x_lo = y_hi * x_lo; + uint32_t y_lo_x_lo = y_lo * x_lo; + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint32_t carry = (uint32_t) carry_out << 16; + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16; + uint32_t cross_sum_lo = cross_sum & 0xFFFF; + uint32_t cross_sum_hi = cross_sum >> 16; + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint32_t interm = cross_sum_hi + y_hi_x_hi; + uint32_t low_accum_hi = low_accum >> 16; + uint32_t interm_plus_carry = interm + carry; + uint32_t hw64 = interm_plus_carry + low_accum_hi; + + return hw64; +} + +/* The 128-bit variant lowers to longhand in pass_optimize_widening_mul; + no target provides a 256-bit multiply. */ +#ifdef __SIZEOF_INT128__ +__uint128_t mulh_carry_128 (__uint128_t x, __uint128_t y) +{ + __uint128_t x_lo = x & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t x_hi = x >> 64; + __uint128_t y_lo = y & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t y_hi = y >> 64; + __uint128_t y_lo_x_hi = y_lo * x_hi; + __uint128_t y_hi_x_hi = y_hi * x_hi; + __uint128_t y_hi_x_lo = y_hi * x_lo; + __uint128_t y_lo_x_lo = y_lo * x_lo; + __uint128_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = cross_sum < y_lo_x_hi; + __uint128_t carry = (__uint128_t) carry_out << 64; + __uint128_t y_lo_x_lo_hi = y_lo_x_lo >> 64; + __uint128_t cross_sum_lo = cross_sum & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t cross_sum_hi = cross_sum >> 64; + __uint128_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + __uint128_t interm = cross_sum_hi + y_hi_x_hi; + __uint128_t low_accum_hi = low_accum >> 64; + __uint128_t interm_plus_carry = interm + carry; + __uint128_t hw64 = interm_plus_carry + low_accum_hi; + + return hw64; +} +#endif + +void full_mul_carry (uint64_t x, uint64_t y, uint64_t* p) { + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint64_t upper_mid = y_hi_x_hi + carry; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t upper_mid_with_cross = upper_mid + cross_sum_hi; + uint64_t hw64 = upper_mid_with_cross + low_accum_hi; + p[1] = hw64; + uint64_t low_accum_shifted = low_accum << 32; + uint64_t y_lo_x_lo_lo = y_lo_x_lo & 0xFFFFFFFF; + uint64_t lw64 = low_accum_shifted | y_lo_x_lo_lo; + p[0] = lw64; +} + +/* This will be optimized during the second forwprop run. + Disable SLP so the expected fold count is target-independent. */ +__attribute__((optimize("no-tree-slp-vectorize"))) +v2i32 mulh_carry_v2i32 (v2i32 x, v2i32 y) +{ + v2i32 result; + for (int i = 0; i < 2; i++) + { + uint32_t x_lo = x.v[i] & 0xFFFF; + uint32_t y_lo = y.v[i] & 0xFFFF; + uint32_t x_hi = x.v[i] >> 16; + uint32_t y_hi = y.v[i] >> 16; + + uint32_t y_lo_x_hi = y_lo * x_hi; + uint32_t y_hi_x_hi = y_hi * x_hi; + uint32_t y_hi_x_lo = y_hi * x_lo; + uint32_t y_lo_x_lo = y_lo * x_lo; + + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = cross_sum < y_lo_x_hi; + uint32_t carry = (uint32_t) carry_out << 16; + + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16; + uint32_t cross_sum_lo = cross_sum & 0xFFFF; + uint32_t cross_sum_hi = cross_sum >> 16; + + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint32_t interm = cross_sum_hi + y_hi_x_hi; + uint32_t low_accum_hi = low_accum >> 16; + uint32_t interm_plus_carry = interm + carry; + + result.v[i] = interm_plus_carry + low_accum_hi; + } + + return result; +} + +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 4 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 1 "forwprop2" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 1 "forwprop1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-extra-addend.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-extra-addend.c new file mode 100644 index 000000000000..5e36a1592ec2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-extra-addend.c @@ -0,0 +1,63 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-forwprop-details" } */ + +/* Chains carrying addends that are not part of the long-multiply idiom + (an accumulator merged in by reassociation, a foreign shifted term) + must still fold, with the extra addends preserved on top of the wide + multiply. A leaf that classifies as a long-mul summand but breaks + operand consistency kills the match instead (no subset retry). */ + +typedef __UINT64_TYPE__ uint64_t; + +/* Extra addend appended after the full high-part chain. Folds. */ +uint64_t +mulh_acc (uint64_t x, uint64_t y, uint64_t acc) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + int carry_out = hilo > low_sum; + uint64_t carry = (uint64_t) carry_out << 32; + return xh * yh + (low_sum >> 32) + carry + acc; +} + +/* Extra addend interleaved into the middle of the chain. Folds. */ +uint64_t +mulh_acc_interleaved (uint64_t x, uint64_t y, uint64_t acc) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + int carry_out = hilo > low_sum; + uint64_t carry = (uint64_t) carry_out << 32; + return ((xh * yh + acc) + (low_sum >> 32)) + carry; +} + +/* Foreign leaf that classifies as a summand (a second high-high + product of different operands): consumed by the multiset, operand + consistency fails, no fold. */ +uint64_t +mulh_foreign_hihi (uint64_t x, uint64_t y, uint64_t a, uint64_t b) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t ah = a >> 32, bh = b >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + int carry_out = hilo > low_sum; + uint64_t carry = (uint64_t) carry_out << 32; + return xh * yh + (low_sum >> 32) + carry + ah * bh; +} + +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded" 2 "forwprop1" } } */ diff --git a/gcc/testsuite/gcc.target/aarch64/long_mul.c b/gcc/testsuite/gcc.target/aarch64/long_mul.c new file mode 100644 index 000000000000..2a4709ecbfd0 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/long_mul.c @@ -0,0 +1,58 @@ +/* { dg-do compile } */ +/* { dg-options "-O3" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; + +/* 64-bit carry pattern for high part. */ +uint64_t mulh_carry (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = cross_sum < y_lo_x_hi; + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint64_t interm = cross_sum_hi + y_hi_x_hi; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t interm_plus_carry = interm + carry; + return interm_plus_carry + low_accum_hi; +} + +/* 32-bit carry pattern for high part. */ +uint32_t mulh_carry_32 (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo_x_hi = y_lo * x_hi; + uint32_t y_hi_x_hi = y_hi * x_hi; + uint32_t y_hi_x_lo = y_hi * x_lo; + uint32_t y_lo_x_lo = y_lo * x_lo; + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint32_t carry = (uint32_t) carry_out << 16; + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16; + uint32_t cross_sum_lo = cross_sum & 0xFFFF; + uint32_t cross_sum_hi = cross_sum >> 16; + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint32_t interm = cross_sum_hi + y_hi_x_hi; + uint32_t low_accum_hi = low_accum >> 16; + uint32_t interm_plus_carry = interm + carry; + return interm_plus_carry + low_accum_hi; +} + +/* 64-bit pattern should emit umulh. */ +/* { dg-final { scan-assembler-times "umulh\t" 1 } } */ +/* 32-bit pattern should emit umull (32x32->64 widening multiply). */ +/* { dg-final { scan-assembler-times "umull\t" 1 } } */ diff --git a/gcc/testsuite/gcc.target/i386/long_mul.c b/gcc/testsuite/gcc.target/i386/long_mul.c new file mode 100644 index 000000000000..6ec87eb8dd21 --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/long_mul.c @@ -0,0 +1,58 @@ +/* { dg-do compile { target { ! ia32 } } } */ +/* { dg-options "-O3" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; + +/* 64-bit carry pattern for high part. */ +uint64_t mulh_carry (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = cross_sum < y_lo_x_hi; + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint64_t interm = cross_sum_hi + y_hi_x_hi; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t interm_plus_carry = interm + carry; + return interm_plus_carry + low_accum_hi; +} + +/* 32-bit carry pattern for high part. */ +uint32_t mulh_carry_32 (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo_x_hi = y_lo * x_hi; + uint32_t y_hi_x_hi = y_hi * x_hi; + uint32_t y_hi_x_lo = y_hi * x_lo; + uint32_t y_lo_x_lo = y_lo * x_lo; + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint32_t carry = (uint32_t) carry_out << 16; + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16; + uint32_t cross_sum_lo = cross_sum & 0xFFFF; + uint32_t cross_sum_hi = cross_sum >> 16; + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint32_t interm = cross_sum_hi + y_hi_x_hi; + uint32_t low_accum_hi = low_accum >> 16; + uint32_t interm_plus_carry = interm + carry; + return interm_plus_carry + low_accum_hi; +} + +/* 64-bit pattern should emit mulq (unsigned 64x64->128 multiply). */ +/* { dg-final { scan-assembler-times "\tmulq" 1 } } */ +/* 32-bit pattern should emit imulq (64-bit multiply of zero-extended operands). */ +/* { dg-final { scan-assembler-times "\timulq" 1 } } */ diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc index 12c07c99c9bd..b8700f571fc6 100644 --- a/gcc/tree-ssa-forwprop.cc +++ b/gcc/tree-ssa-forwprop.cc @@ -3592,6 +3592,791 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) return 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. */ + +/* Match.pd functions to match long multiplication. */ + +extern bool gimple_mul_hi (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_lo (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_hilo (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_lolo (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_hihi (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_cross_sum (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_low_accum (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_carry_cross_sum (tree, tree *, tree (*)(tree)); + +/* Append to SEQ statements assigning DEST the 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 +build_mul_high_seq (tree op1, tree op2, tree dest, location_t loc, + gimple_seq *seq) +{ + tree op_type = TREE_TYPE (op1); + unsigned int width = TYPE_PRECISION (op_type); + tree wide_type = build_nonstandard_integer_type (width * 2, 1); + + 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 (dest, NOP_EXPR, hi); + gimple_set_location (prod, loc); + gimple_seq_add_stmt (seq, prod); +} + +/* Append to SEQ statements combining ACC with each of EXTRAS under + OUTER, the last one assigning to STMT's lhs. EXTRAS are leaves of + STMT's own chain, so any combining order is valid. */ + +static void +long_mul_apply_extras (tree acc, const vec<tree> &extras, tree_code outer, + gassign *stmt, gimple_seq *seq) +{ + location_t loc = gimple_location (stmt); + tree lhs = gimple_assign_lhs (stmt); + for (unsigned i = 0; i + 1 < extras.length (); i++) + acc = gimple_build (seq, loc, outer, TREE_TYPE (lhs), acc, extras[i]); + gimple *last = gimple_build_assign (lhs, outer, acc, extras.last ()); + gimple_set_location (last, loc); + gimple_seq_add_stmt (seq, last); +} + +/* Replace STMT with a high-part multiply of OP1 and OP2, combining any + EXTRAS back on top under OUTER. */ + +static void +create_mul_high_seq (tree op1, tree op2, gassign *stmt, + const vec<tree> &extras, tree_code outer) +{ + gimple_seq seq = NULL; + tree lhs = gimple_assign_lhs (stmt); + tree dest = extras.is_empty () ? lhs : make_ssa_name (TREE_TYPE (lhs)); + build_mul_high_seq (op1, op2, dest, gimple_location (stmt), &seq); + if (!extras.is_empty ()) + long_mul_apply_extras (dest, extras, outer, stmt, &seq); + 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, combining any + EXTRAS back on top under OUTER. */ + +static void +create_mul_low_seq (tree op1, tree op2, gassign *stmt, + const vec<tree> &extras, tree_code outer) +{ + gimple_seq seq = NULL; + tree lhs = gimple_assign_lhs (stmt); + tree dest = extras.is_empty () ? lhs : make_ssa_name (TREE_TYPE (lhs)); + gimple *prod = gimple_build_assign (dest, MULT_EXPR, op1, op2); + gimple_set_location (prod, gimple_location (stmt)); + gimple_seq_add_stmt (&seq, prod); + if (!extras.is_empty ()) + long_mul_apply_extras (dest, extras, outer, stmt, &seq); + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gsi_replace_with_seq (&gsi, seq, true); +} + +/* Widest match.pd atom (mul_low_accum) takes 6 captures; round up + to 8 for the scratch buffers below. */ +static constexpr unsigned LONG_MUL_MAX_CAPTURES = 8; + +/* Longest variant in long_mul_table has 4 summands. */ +static constexpr unsigned LONG_MUL_MAX_SUMMANDS = 4; + +/* Cap on the leaves set aside as not part of the idiom, so an + arbitrarily long unrelated chain still bails early. */ +static constexpr unsigned LONG_MUL_MAX_EXTRAS = 4; + +enum long_mul_kind { + LMK_MUL_HIHI, + LMK_MUL_LOLO, + LMK_MUL_HILO, + LMK_CROSS_SUM, + LMK_LOW_ACCUM, + LMK_CARRY_CROSS_SUM, +}; + +/* How the leaf wraps its inner kind. Carry kinds use LMX_NONE: their + match.pd pattern bakes the lshift in, so the leaf is already the + complete carry expression. */ + +enum long_mul_extract { + LMX_NONE, + LMX_HI, + LMX_LO, + LMX_SHL_N, +}; + +struct long_mul_summand { + long_mul_kind kind; + long_mul_extract extract; + tree op0, op1; + tree hilo0, hilo1, hilo2; + unsigned HOST_WIDE_INT shift; + unsigned HOST_WIDE_INT mask; +}; + +/* Walk the OUTER addition or BIT_IOR chain rooted at STMT and collect + the leaf operands into LEAVES. Descends through single-use + intermediate stmts of the same code. Returns false once the leaf + count exceeds LONG_MUL_MAX_SUMMANDS + LONG_MUL_MAX_EXTRAS, 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 + LONG_MUL_MAX_EXTRAS) + return false; + } + return !leaves.is_empty (); +} + +/* If EXPR is defined by LSHIFT_EXPR with a uhwi-valued amount, return + the shifted input via *INNER_OUT and the amount via *SHIFT_OUT. */ + +static bool +long_mul_is_lshift_def (tree expr, tree *inner_out, + unsigned HOST_WIDE_INT *shift_out) +{ + if (TREE_CODE (expr) != SSA_NAME) + return false; + gimple *def = SSA_NAME_DEF_STMT (expr); + if (!def || !is_gimple_assign (def) + || gimple_assign_rhs_code (def) != LSHIFT_EXPR) + return false; + tree amount = gimple_assign_rhs2 (def); + if (!tree_fits_uhwi_p (amount)) + return false; + *inner_out = gimple_assign_rhs1 (def); + *shift_out = tree_to_uhwi (amount); + return true; +} + +/* Fill INFO's kind plus the captures from RES_OPS that the kind requires. + The kind itself determines how many (op0, op1) and hilo captures to + pick up from RES_OPS, and whether a baked-in shift is present. */ + +static void +long_mul_set_summand (long_mul_summand *info, long_mul_kind kind, + const tree *res_ops) +{ + info->kind = kind; + unsigned n_ops = 0; + unsigned n_hilos = 0; + int shift_idx = -1; + switch (kind) + { + case LMK_MUL_HIHI: + case LMK_MUL_LOLO: + case LMK_MUL_HILO: + n_ops = 2; + break; + case LMK_CROSS_SUM: + n_hilos = 2; + break; + case LMK_LOW_ACCUM: + n_ops = 2; + n_hilos = 2; + break; + case LMK_CARRY_CROSS_SUM: + n_hilos = 3; + shift_idx = 3; + break; + } + if (n_ops >= 1) + info->op0 = res_ops[0]; + if (n_ops >= 2) + info->op1 = res_ops[1]; + if (n_hilos >= 1) + info->hilo0 = res_ops[n_ops]; + if (n_hilos >= 2) + info->hilo1 = res_ops[n_ops + 1]; + if (n_hilos >= 3) + info->hilo2 = res_ops[n_ops + 2]; + if (shift_idx >= 0) + /* The carry atoms (mul_carry_cross_sum, mul_carry_low_sum) capture the + shift as an INTEGER_CST already checked with tree_fits_uhwi_p, so this + cannot overflow. */ + info->shift = tree_to_uhwi (res_ops[shift_idx]); +} + +/* Classify LEAF as a carry-kind summand. The lshift amount is baked + into mul_carry_cross_sum, so it's tried before any branch that looks + for a generic (X >> N) or (X << N) wrapper. */ + +static bool +long_mul_classify_carry (tree leaf, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + if (gimple_mul_carry_cross_sum (leaf, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_CARRY_CROSS_SUM, res_ops); + return true; + } + return false; +} + +/* Plus-based summand kinds shared by the (X >> SHIFT) and (X << SHIFT) + classifiers. */ + +static bool +long_mul_classify_plus_kinds (tree inner, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + if (gimple_mul_low_accum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LOW_ACCUM, res_ops); + return true; + } + return false; +} + +/* Classify INNER -- already unwrapped from an outer (X >> SHIFT) -- as + a high-half-extracted summand. mul_hilo (mult-shape) is orthogonal + to the plus-based kinds and is tried first; mul_cross_sum (any plus) + is the fallback after the shared plus-based kinds. */ + +static bool +long_mul_classify_hi_extract (tree inner, unsigned HOST_WIDE_INT shift, + long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + info->extract = LMX_HI; + info->shift = shift; + if (gimple_mul_hilo (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_HILO, res_ops); + return true; + } + if (long_mul_classify_plus_kinds (inner, info)) + return true; + if (gimple_mul_cross_sum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_CROSS_SUM, res_ops); + return true; + } + return false; +} + +/* Classify INNER -- already unwrapped from an outer (X & MASK) -- as + a low-half-masked summand. */ + +static bool +long_mul_classify_lo_extract (tree inner, unsigned HOST_WIDE_INT mask, + long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + info->extract = LMX_LO; + info->mask = mask; + if (gimple_mul_lolo (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_LOLO, res_ops); + return true; + } + return false; +} + +/* Classify INNER -- already unwrapped from an outer (X << SHIFT) -- as + a left-shifted summand. No mul_hilo here -- that shape appears only + under (X >> SHIFT). */ + +static bool +long_mul_classify_shl_extract (tree inner, unsigned HOST_WIDE_INT shift, + long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + info->extract = LMX_SHL_N; + info->shift = shift; + if (long_mul_classify_plus_kinds (inner, info)) + return true; + if (gimple_mul_cross_sum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_CROSS_SUM, res_ops); + return true; + } + return false; +} + +/* Classify LEAF as one of the bare-kind summands (no extraction + wrapper): mul_hihi or mul_lolo standing on their own. */ + +static bool +long_mul_classify_bare (tree leaf, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + if (gimple_mul_hihi (leaf, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_HIHI, res_ops); + return true; + } + if (gimple_mul_lolo (leaf, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_LOLO, res_ops); + return true; + } + return false; +} + +/* Classify LEAF as one of the long-multiply summand shapes. On success, + fill *INFO with the kind, extract, captured operands and shift/mask. + Dispatches to per-extract helpers; the order matters because the + carry kinds bake an lshift into the pattern and would otherwise be + misread by the (X << N) branch. */ + +static bool +long_mul_classify_summand (tree leaf, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + *info = {}; + + if (long_mul_classify_carry (leaf, info)) + return true; + + if (gimple_mul_hi (leaf, res_ops, NULL)) + return long_mul_classify_hi_extract (res_ops[0], + tree_to_uhwi (res_ops[1]), info); + + if (gimple_mul_lo (leaf, res_ops, NULL)) + return long_mul_classify_lo_extract (res_ops[0], + tree_to_uhwi (res_ops[1]), info); + + tree inner; + unsigned HOST_WIDE_INT shift; + if (long_mul_is_lshift_def (leaf, &inner, &shift)) + return long_mul_classify_shl_extract (inner, shift, info); + + return long_mul_classify_bare (leaf, info); +} + +/* qsort comparator: sort summands by (kind, extract) to put a multiset + into canonical order for table lookup. Unstable sort within a tie is + harmless: no row in long_mul_table pairs distinct subterms under the + same (kind, extract), and long_mul_check_consistency cross-validates + that matching summands share one canonical (op0, op1). */ + +static int +long_mul_summand_compare (const void *a, const void *b) +{ + const long_mul_summand *sa = (const long_mul_summand *) a; + const long_mul_summand *sb = (const long_mul_summand *) b; + if (sa->kind != sb->kind) + return (int) sa->kind - (int) sb->kind; + return (int) sa->extract - (int) sb->extract; +} + +/* One row of the long-multiply variant table. COUNT is how many entries + of SIG carry the row's signature (2 to LONG_MUL_MAX_SUMMANDS); a row + with fewer summands leaves the remaining SIG entries zero-initialized. + Those zeros are not a terminator -- {LMK_MUL_HIHI, LMX_NONE} is itself a + valid signature -- so long_mul_signature_matches is bounded by COUNT, + never by a sentinel entry. */ + +struct long_mul_row { + enum long_mul_row_part { HIGH_PART, LOW_PART } part; + tree_code outer; + unsigned char count; + struct { + long_mul_kind kind; + long_mul_extract extract; + } sig[LONG_MUL_MAX_SUMMANDS]; + bool (*extra_check) (const vec<long_mul_summand> &, gimple *); +}; + +/* True if (A, B) is the same pair as (OP0, OP1) in either order. */ + +static inline bool +long_mul_same_ops (tree a, tree b, tree op0, tree op1) +{ + return (a == op0 && b == op1) || (a == op1 && b == op0); +} + +/* True if H is a cross-half product of (OP0, OP1) -- gimple_mul_hilo + recognizes it and its captured operands match the pair. */ + +static bool +long_mul_is_cross_half (tree h, tree op0, tree op1) +{ + tree scratch[LONG_MUL_MAX_CAPTURES]; + return gimple_mul_hilo (h, scratch, NULL) + && long_mul_same_ops (scratch[0], scratch[1], op0, op1); +} + +/* Orientation of the mul_hilo capture H relative to (OP0, OP1): + returns 0 for high(OP0)*low(OP1), 1 for high(OP1)*low(OP0), or -1 + if H does not decompose that way. A cross-sum of two mul_hilos must + see one of each orientation -- otherwise a doubled factor would fold + to the wrong value. (In a self-multiply the two orientations + coincide; see the OP0 == OP1 bypass in long_mul_check_consistency.) */ + +static int +long_mul_hilo_orientation (tree h, tree op0, tree op1) +{ + tree scratch[LONG_MUL_MAX_CAPTURES]; + if (!gimple_mul_hilo (h, scratch, NULL)) + return -1; + if (scratch[0] == op0 && scratch[1] == op1) + return 0; + if (scratch[0] == op1 && scratch[1] == op0) + return 1; + return -1; +} + +/* Find the first summand that carries operand captures, and return its + (op0, op1) pair in *OP0_OUT / *OP1_OUT. Returns false if no summand + provides them. */ + +static bool +long_mul_canonical_ops (const vec<long_mul_summand> &summands, + tree *op0_out, tree *op1_out) +{ + for (const long_mul_summand &s : summands) + if (s.op0) + { + *op0_out = s.op0; + *op1_out = s.op1; + return true; + } + return false; +} + +/* Run the cross-summand validation invariants and return the canonical + (op0, op1). Returns false unless all summands that carry operands use + the same (op0, op1) pair (in either order), every LMX_HI/LMX_SHL_N shift + equals halfwidth, every captured hilo is a true cross-half product of + (op0, op1), and every cross-half pair (both those inside a single + mul_cross_sum-bearing summand and those spread across separate + LMK_MUL_HILO summands) contains one of each orientation. */ + +static bool +long_mul_check_consistency (const vec<long_mul_summand> &summands, + tree *op0_out, tree *op1_out) +{ + tree op0, op1; + if (!long_mul_canonical_ops (summands, &op0, &op1)) + return false; + + tree op_type = TREE_TYPE (op0); + if (!INTEGRAL_TYPE_P (op_type) + || TYPE_PRECISION (op_type) % 2 != 0) + return false; + unsigned int halfwidth = TYPE_PRECISION (op_type) / 2; + + /* Self-multiply (x*x) collapses the two cross-halves onto one value, + so the complementarity constraint is a trivial no-op there. */ + bool need_orient = op0 != op1; + int mul_hilo_orient[2] = { 0, 0 }; + + for (const long_mul_summand &s : summands) + { + if (s.op0 && !long_mul_same_ops (s.op0, s.op1, op0, op1)) + return false; + if ((s.extract == LMX_HI || s.extract == LMX_SHL_N) + && s.shift != halfwidth) + return false; + tree hilos[3] = { s.hilo0, s.hilo1, s.hilo2 }; + for (tree h : hilos) + if (h && !long_mul_is_cross_half (h, op0, op1)) + return false; + + if (!need_orient) + continue; + + /* The two cross-sum operands are the last two non-null hilos: + (hilo1, hilo2) for the CARRY_*_SUM kinds, (hilo0, hilo1) for + the CROSS_SUM / SUM / ACCUM / LADDER_SUM kinds, none for the + rest. */ + tree a = NULL_TREE; + tree b = NULL_TREE; + if (s.hilo2) + { + a = s.hilo1; + b = s.hilo2; + } + else if (s.hilo1) + { + a = s.hilo0; + b = s.hilo1; + } + if (a && b + && (long_mul_hilo_orientation (a, op0, op1) + == long_mul_hilo_orientation (b, op0, op1))) + return false; + + /* Two LMK_MUL_HILO summands (the two-hilos ladder form) stand for + the two cross-halves separately; count orientations and require + the pair to be complementary. s.op0/op1 is already validated to + match (op0, op1) in some order above. */ + if (s.kind == LMK_MUL_HILO && s.op0) + mul_hilo_orient[s.op0 == op1]++; + } + + if (mul_hilo_orient[0] + mul_hilo_orient[1] >= 2 + && (mul_hilo_orient[0] == 0 || mul_hilo_orient[1] == 0)) + return false; + + *op0_out = op0; + *op1_out = op1; + return true; +} + +/* Compare the (already-sorted) SUMMANDS multiset against ROW.sig. */ + +static bool +long_mul_signature_matches (const vec<long_mul_summand> &summands, + const long_mul_row &row) +{ + if (row.count != summands.length ()) + return false; + for (unsigned i = 0; i < row.count; i++) + if (summands[i].kind != row.sig[i].kind + || summands[i].extract != row.sig[i].extract) + return false; + return true; +} + +/* Long-multiply variant table. Each row enumerates the multiset of + (kind, extract) summands that compose one long-multiply form. Rows + are sorted by long_mul_summand_compare, matching the input summands' + sort order, so a plain element-wise compare suffices. Rows describe + unsigned schoolbook expansions on an even-width 2N-bit type split at + half-width N; EXTRA_CHECK carries invariants the (kind, extract) + signature cannot express. */ + +static const long_mul_row long_mul_table[] = { + /* HIGH-PART fold. Notation: xh, xl, yh, yl are the half-width pieces + of x and y; N is the half-width. cross_sum = xh*yl + xl*yh; hilo is + either xh*yl or xl*yh (consumers validate the operand shape). */ + /* xh*yh + (low_accum >> N) + (cross_sum >> N) + + ((hilo > cross_sum) << N), + low_accum = (xl*yl >> N) + (cross_sum & mask). */ + { long_mul_row::HIGH_PART, PLUS_EXPR, 4, + { { LMK_MUL_HIHI, LMX_NONE }, + { LMK_CROSS_SUM, LMX_HI }, + { LMK_LOW_ACCUM, LMX_HI }, + { LMK_CARRY_CROSS_SUM, LMX_NONE } }, + NULL }, + /* LOW-PART fold. Recover the lower 2N bits from xl*yl plus a + shifted cross-half term. Notation as for the HIGH-PART row above. */ + /* (xl*yl & mask) | (low_accum << N), + low_accum = (xl*yl >> N) + (cross_sum & mask). */ + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, + { { LMK_MUL_LOLO, LMX_LO }, + { LMK_LOW_ACCUM, LMX_SHL_N } }, + NULL }, +}; + +/* If a multi-used inner addition (sharing the chain's outer code) blocked + linearization of a long-mul candidate, emit a dump-file hint pointing + at it. */ + +static void +long_mul_hint_shared_intermediate (gimple *shared_def) +{ + if (!shared_def || !dump_file || !(dump_flags & TDF_DETAILS)) + return; + fprintf (dump_file, "long-mul fold rejected: shared intermediate at "); + print_gimple_stmt (dump_file, shared_def, 0, TDF_SLIM); +} + +/* Search long_mul_table for a row whose multiset matches SUMMANDS for + outer kind OUTER on a result of type LHS_TYPE. CANDIDATE_STMT is + passed to per-row extra_check predicates. On a hit, returns the + matching row and writes the half-width operands via OUT_OP0/OUT_OP1. + No IR mutation. */ + +static const long_mul_row * +long_mul_classify_match (const vec<long_mul_summand> &summands, + tree lhs_type, tree_code outer, + gimple *candidate_stmt, + tree *out_op0, tree *out_op1) +{ + /* HIGH_PART rows emit a 2N-bit multiply that is consumed by + pass_optimize_widening_mul (WIDEN_MULT_EXPR conversion or + longhand re-synthesis) or by expand (supported 2N mode); + LOW_PART rows emit a plain MULT_EXPR. Emission needs only a 2N + mode to exist in the mode table -- capability is settled on the + lowering side. */ + scalar_int_mode mode, wide_mode; + bool can_emit_high + = is_a <scalar_int_mode> (TYPE_MODE (lhs_type), &mode) + && GET_MODE_2XWIDER_MODE (mode).exists (&wide_mode); + + for (const long_mul_row &row : long_mul_table) + { + if (row.outer != outer + || (row.part == long_mul_row::HIGH_PART && !can_emit_high) + || !long_mul_signature_matches (summands, row)) + continue; + + tree op0, op1; + if (!long_mul_check_consistency (summands, &op0, &op1)) + continue; + + /* Do not emit the wide chain when an operand is subject to + abnormal coalescing: the widening_mul-side consumers refuse + such operands (see convert_mult_to_widen), which would leave + the chain without a consumer. */ + if (row.part == long_mul_row::HIGH_PART + && ((TREE_CODE (op0) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)) + || (TREE_CODE (op1) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)))) + continue; + + if (row.extra_check && !row.extra_check (summands, candidate_stmt)) + continue; + + *out_op0 = op0; + *out_op1 = op1; + return &row; + } + return NULL; +} + +/* Walk STMT's outer chain (kind OUTER), classify each leaf as a + long-multiply summand, and look the multiset up in long_mul_table + for a result of type LHS_TYPE. CANDIDATE is passed to per-row + extra_check predicates. + + If EXTRAS_OUT is non-NULL, leaves matching no summand are set aside + there instead of failing the match, and the caller must re-apply + them on top of the folded multiply. A leaf that does match is + always consumed: if that makes the signature miss every row the + match fails, rather than retrying with the leaf demoted to an extra + (subset search would be exponential). + + Returns the matched row and the half-width operands via + OUT_OP0/OUT_OP1, or NULL on a miss. No IR mutation. */ + +static const long_mul_row * +long_mul_classify_chain (gimple *stmt, tree_code outer, tree lhs_type, + gimple *candidate, vec<tree> *extras_out, + tree *out_op0, tree *out_op1) +{ + auto_vec<tree, LONG_MUL_MAX_SUMMANDS + LONG_MUL_MAX_EXTRAS> leaves; + gimple *shared_def = NULL; + if (!long_mul_linearize_chain (stmt, outer, leaves, &shared_def)) + return NULL; + + auto_vec<long_mul_summand, + LONG_MUL_MAX_SUMMANDS + LONG_MUL_MAX_EXTRAS + 1> summands; + for (tree leaf : leaves) + { + long_mul_summand s; + if (long_mul_classify_summand (leaf, &s)) + summands.quick_push (s); + else if (extras_out && extras_out->length () < LONG_MUL_MAX_EXTRAS) + extras_out->safe_push (leaf); + else + { + long_mul_hint_shared_intermediate (shared_def); + return NULL; + } + } + if (summands.length () < 2 + || summands.length () > LONG_MUL_MAX_SUMMANDS) + return NULL; + summands.qsort (long_mul_summand_compare); + + const long_mul_row *row + = long_mul_classify_match (summands, lhs_type, outer, candidate, + out_op0, out_op1); + if (!row) + long_mul_hint_shared_intermediate (shared_def); + return row; +} + +/* 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 (gassign *stmt) +{ + tree_code outer = gimple_assign_rhs_code (stmt); + if (outer != PLUS_EXPR && outer != BIT_IOR_EXPR) + return false; + + /* Skip non-candidate adds (signed, pointer, odd-width) before walking the + chain. No legitimate long-mul leaf has a type the atoms would reject. + This just avoids the linearize/classify work on every other PLUS/IOR. */ + tree lhs_type = TREE_TYPE (gimple_get_lhs (stmt)); + if (!INTEGRAL_TYPE_P (lhs_type) + || !TYPE_UNSIGNED (lhs_type) + || TYPE_PRECISION (lhs_type) % 2 != 0) + return false; + + auto_vec<tree, LONG_MUL_MAX_EXTRAS> extras; + tree op0, op1; + const long_mul_row *row + = long_mul_classify_chain (stmt, outer, lhs_type, stmt, &extras, + &op0, &op1); + if (!row) + return false; + + if (row->part == long_mul_row::HIGH_PART) + { + create_mul_high_seq (op0, op1, stmt, extras, outer); + 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, extras, outer); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Long multiplication low part folded.\n"); + return true; +} /* Determine whether applying the 2 permutations (mask1 then mask2) gives back one of the input. */ @@ -5378,7 +6163,10 @@ pass_forwprop::execute (function *fun) } } - /* Record degenerate PHIs in the lattice. */ + /* Fold PHI-form long-multiply carries and record degenerate + PHIs in the lattice. Iterator advanced up front so a folded + PHI can be removed in-flight; a long-mul carry PHI is never + degenerate, so the two cases are disjoint. */ for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) { @@ -5851,11 +6639,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 (as_a <gassign *> (stmt)); + if (!folded) + folded = simplify_rotate (&gsi); + changed |= folded; + } + else if (code == BIT_XOR_EXPR) + changed |= simplify_rotate (&gsi); else if (code == VEC_PERM_EXPR) changed |= simplify_permutation (&gsi); else if (code == CONSTRUCTOR -- 2.55.0