[gcc r17-3442] match.pd, forwprop: Recognize long-multiply carries written as 2-arg PHI
Philipp Tomsich via Gcc-cvs <[email protected]>
| Newsgroups | gmane.comp.gcc.cvs |
|---|---|
| Message-ID | <[email protected]> |
https://gcc.gnu.org/g:0502e6b1e7be3d3fe00727e2936d3c3a03537c4e commit r17-3442-g0502e6b1e7be3d3fe00727e2936d3c3a03537c4e Author: Konstantinos Eleftheriou <[email protected]> Date: Thu Jul 9 02:22:29 2026 -0700 match.pd, forwprop: Recognize long-multiply carries written as 2-arg PHI Hand-written long-multiply code commonly writes the carry as a 2-arg PHI if (mul_hilo0 > low_sum) result = result_partial + (1ULL << N); else result = result_partial; with no top-level + at the join for the chain walk to start from. Add a PHI-driven entry: cond_carry_add / cond_carry_add_neg match PHI<base + pow2, base> guarded by an unsigned compare on (a, sum) in either polarity; the captured sum is classified into a carry summand, base is linearized for the remaining summands, and on a match the 2N-bit multiply is emitted with the PHI result as its LHS. Only HIGH_PART rows are reachable; LOW_PART rows are BIT_IOR chains and never produce a carry PHI. PR tree-optimization/107090 gcc/ChangeLog: * match.pd: Add cond_carry_add and cond_carry_add_neg match recognizers for the 2-arg PHI form PHI<base + pow2, base>, one per gcond polarity. * tree-ssa-forwprop.cc (gimple_cond_carry_add): Declare. (gimple_cond_carry_add_neg): Likewise. (long_mul_check_low_plus_defer): Note that the PHI entry commits only to HIGH_PART rows. (long_mul_classify_match): Take the candidate statement for the per-row checks. (long_mul_classify_chain): Take an optional pre-classified extra summand, for the carry the PHI entry synthesizes. (match_long_mul): Adjust. (match_long_mul_phi): New PHI-driven entry; recognizes a cond_carry_add(_neg) PHI and folds the long-multiply when the rest of the high-part chain matches. (pass_forwprop::execute): Call match_long_mul_phi on each PHI in the degenerate-PHI walk. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/long-mul-carry.c: Add PHI-form CARRY_LOW_SUM, CARRY_CROSS_SUM, and negated-branch compile variants; split the forwprop1 high-part fold count into 10 on int128 and 8 on !int128. * gcc.dg/tree-ssa/long-mul-two-carry.c: Add the mulh_two_carry_low_phi function and its forwprop3 high-part (carry PHI) fold scan. * gcc.dg/tree-ssa/long-mul-boundary-64.c: New test. * gcc.dg/tree-ssa/long-mul-boundary.c: New test. * gcc.dg/tree-ssa/long-mul-partial.c: New test. Co-authored-by: Philipp Tomsich <[email protected]> Diff: --- gcc/match.pd | 25 ++ .../gcc.dg/tree-ssa/long-mul-boundary-64.c | 417 +++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c | 394 +++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c | 74 +++- gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c | 193 ++++++++++ gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c | 31 +- gcc/tree-ssa-forwprop.cc | 149 +++++++- 7 files changed, 1270 insertions(+), 13 deletions(-) diff --git a/gcc/match.pd b/gcc/match.pd index 86042b02beea..40cd19649727 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -6813,6 +6813,31 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (lshift (convert (bit_xor (convert:boolean_type_node @0) { boolean_true_node; })) { shift; }))))))) +/* Recognize a 2-arg PHI of the form + PHI<base + pow2, base> + guarded by an unsigned compare on (@0, @1). @1 is captured without + further structure; the long-mul fold in tree-ssa-forwprop.cc + classifies it to drive a PHI-form carry summand. The consumer + treats the carry as strict @0 > @1, so each polarity's compare + must encode that same condition: + cond_carry_add: true edge selects (base + pow2), so the + compare itself must be @0 > @1. + cond_carry_add_neg: true edge selects base, so the compare's + negation must be @0 > @1, i.e. the + compare itself must be @0 <= @1. + Matches the 2-arg PHI form via cond^. */ +(if (INTEGRAL_TYPE_P (type) + && TYPE_UNSIGNED (type) + && type_has_mode_precision_p (type)) + (match (cond_carry_add @0 @1 @2 @3) + (cond^ (gt @0 @1) (plus @2 integer_pow2p@3) @2)) + (match (cond_carry_add @0 @1 @2 @3) + (cond^ (lt @1 @0) (plus @2 integer_pow2p@3) @2)) + (match (cond_carry_add_neg @0 @1 @2 @3) + (cond^ (le @0 @1) @2 (plus @2 integer_pow2p@3))) + (match (cond_carry_add_neg @0 @1 @2 @3) + (cond^ (ge @1 @0) @2 (plus @2 integer_pow2p@3)))) + /* (a > 1) ? 0 : (cast)a is the same as (cast)(a == 1) for unsigned types. */ (simplify 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..d191f2217afb --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c @@ -0,0 +1,417 @@ +/* { 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; +} + +/* PHI-form, cond_carry_add (strict carry-on-true). */ +__attribute__((noipa)) +uint64_t mulh_carry_phi (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 add_cross_sum = cross_sum + (mullolo >> 32); + uint64_t add = x_hi * y_hi + (add_cross_sum >> 32); + if (add_cross_sum < mulhilo) + add += (uint64_t)1 << 32; + return add; +} + +/* PHI-form, cond_carry_add_neg (negated branch, carry-on-false). */ +__attribute__((noipa)) +uint64_t mulh_carry_phi_neg (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 add_cross_sum = cross_sum + (mullolo >> 32); + uint64_t add = x_hi * y_hi + (add_cross_sum >> 32); + if (add_cross_sum >= mulhilo) + ; + else + add += (uint64_t)1 << 32; + return add; +} + +/* PHI-form, cond_carry_add written as gt (operand-swapped from lt). */ +__attribute__((noipa)) +uint64_t mulh_carry_phi_gt (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 add_cross_sum = cross_sum + (mullolo >> 32); + uint64_t add = x_hi * y_hi + (add_cross_sum >> 32); + if (mulhilo > add_cross_sum) + add += (uint64_t)1 << 32; + return add; +} + +/* PHI-form, cond_carry_add_neg written as le (operand-swapped from ge). */ +__attribute__((noipa)) +uint64_t mulh_carry_phi_le (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 add_cross_sum = cross_sum + (mullolo >> 32); + uint64_t add = x_hi * y_hi + (add_cross_sum >> 32); + if (mulhilo <= add_cross_sum) + ; + else + add += (uint64_t)1 << 32; + return add; +} + +/* Low part via PLUS: lolo + (cross_sum << 32) with no comparison. */ +__attribute__((noipa)) +uint64_t mul_low_plus (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; +} + +/* PHI-form, two-carry shape with the low carry as the PHI + (LMK_CARRY_LOW path in match_long_mul_phi). */ +__attribute__((noipa)) +uint64_t mulh_two_carry_low_phi (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 high = hihi + (cross_sum >> 32) + cross_carry; + if (low_result < cross_shifted) + high += 1; + + return high; +} + +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 (); + + if (mulh_carry_phi (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_neg (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_gt (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_le (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_two_carry_low_phi (x, y) != expected_hi) + __builtin_abort (); + + if (mul_low_plus (x, y) != 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..498481a01932 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c @@ -0,0 +1,394 @@ +/* { 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; +} + +/* PHI-form, cond_carry_add (strict carry-on-true). */ +__attribute__((noipa)) +uint32_t mulh_carry_phi (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); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum < mulhilo) + add += (uint32_t)1 << 16; + return add; +} + +/* PHI-form, cond_carry_add_neg (negated branch, carry-on-false). */ +__attribute__((noipa)) +uint32_t mulh_carry_phi_neg (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); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum >= mulhilo) + ; + else + add += (uint32_t)1 << 16; + return add; +} + +/* PHI-form, cond_carry_add written as gt (operand-swapped from lt). */ +__attribute__((noipa)) +uint32_t mulh_carry_phi_gt (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); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (mulhilo > add_cross_sum) + add += (uint32_t)1 << 16; + return add; +} + +/* PHI-form, cond_carry_add_neg written as le (operand-swapped from ge). */ +__attribute__((noipa)) +uint32_t mulh_carry_phi_le (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); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (mulhilo <= add_cross_sum) + ; + else + add += (uint32_t)1 << 16; + return add; +} + +/* PHI-form, two-carry shape with the low carry as the PHI + (LMK_CARRY_LOW path in match_long_mul_phi). */ +__attribute__((noipa)) +uint32_t mulh_two_carry_low_phi (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 high = hihi + (cross_sum >> 16) + cross_carry; + if (low_result < cross_shifted) + high += 1; + + return high; +} + +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 (); + + if (mulh_carry_phi (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_neg (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_gt (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_le (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_two_carry_low_phi (x, y) != expected_hi) + __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 index fd190f09dde9..657d118cb704 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c @@ -308,6 +308,74 @@ v2i32 mulh_carry_low_sum_v2i32 (v2i32 x, v2i32 y) return result; } -/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 8 "forwprop1" } } */ -/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 2 "forwprop2" } } */ -/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 2 "forwprop1" } } */ +/* PHI-form coverage: the carry summand is the join of a 2-arg PHI + guarded by an unsigned compare, recognized by cond_carry_add / + cond_carry_add_neg and folded by match_long_mul_phi. */ + +uint32_t mulh_carry_phi (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); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum < mulhilo) + add += (uint32_t)1 << 16; + return add; +} + +uint64_t mulh_carry_long_phi (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; + 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 >> 32); + uint64_t hw64 = y_hi_x_hi + cross_sum_hi + (low_accum >> 32); + if (cross_sum < y_lo_x_hi) + hw64 += (uint64_t)1 << 32; + return hw64; +} + +/* PHI-form, cond_carry_add_neg (negated branch, carry-on-false). */ +uint32_t mulh_carry_phi_neg (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); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum >= mulhilo) + ; + else + add += (uint32_t)1 << 16; + return add; +} + +/* On targets with __int128 support the two 128-bit highparts also + fold; without it they are elided by #ifdef and the count drops + by 2. */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 10 "forwprop1" { target int128 } } } */ +/* { 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" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded\\." 2 "forwprop1" } } */ +/* Three PHI-form highparts, one per polarity pair (gt via mulh_carry_phi + and mulh_carry_long_phi, le via mulh_carry_phi_neg). */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded \\(carry PHI\\)" 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..7b239e2439e1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c @@ -0,0 +1,193 @@ +/* { 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); +} + +/* PHI-form near-miss: non-power-of-two carry increment. + match.pd rejects via integer_pow2p@3. + Should NOT be folded. */ +uint32_t partial_phi_nonpow2 (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16, x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16, 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); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum < mulhilo) + add += (uint32_t)3 << 16; + return add; +} + +/* PHI-form near-miss: carry increment shifted by less than halfwidth. + match_long_mul_phi rejects via shift_amt == halfwidth. + Should NOT be folded. */ +uint32_t partial_phi_wrong_shift (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16, x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16, 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); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum < mulhilo) + add += (uint32_t)1 << 15; + return add; +} + +/* PHI-form near-miss: equality compare in place of the strict carry + predicate. cond_carry_add and cond_carry_add_neg only encode + gt / lt / le / ge. + Should NOT be folded. */ +uint32_t partial_phi_wrong_compare (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16, x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16, 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); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum == mulhilo) + add += (uint32_t)1 << 16; + return add; +} + +/* PHI-form near-miss: one cross-product uses z instead of y. + long_mul_check_consistency rejects the inconsistent (op0, op1). + Should NOT be folded. */ +uint32_t partial_phi_wrong_cross (uint32_t x, uint32_t y, uint32_t z) +{ + uint32_t x_hi = x >> 16, x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16, y_lo = y & 0xFFFF; + uint32_t z_hi = z >> 16; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * z_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum < mulhilo) + add += (uint32_t)1 << 16; + return add; +} + +/* 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 index 662ad77748e5..effed8262469 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c @@ -105,9 +105,36 @@ uint64_t full_mul_two_carry (uint64_t x, uint64_t y, uint64_t *lo) return high; } +/* Low carry written as an if-branch + 2-arg PHI. Exercises + match_long_mul_phi's LMK_CARRY_LOW path (shift = 0). */ +uint64_t mulh_two_carry_low_phi (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 high = hihi + (cross_sum >> 32) + cross_carry; + if (low_result < cross_shifted) + high += 1; + + return high; +} + /* The LOW fold for full_mul_two_carry lands in forwprop4 because `lolo + cross_shifted' also feeds the HIGH fold's low-carry compare; long_mul_check_low_plus_defer holds it until the HIGH fold has consumed the compare. */ -/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 4 "forwprop3" } } */ -/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 1 "forwprop4" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 4 "forwprop3" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded \\(carry PHI\\)" 1 "forwprop3" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded\\." 1 "forwprop4" } } */ diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc index b8e24882c8d8..6e13244fa2d7 100644 --- a/gcc/tree-ssa-forwprop.cc +++ b/gcc/tree-ssa-forwprop.cc @@ -3613,6 +3613,14 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) up in a table. On a hit, three cross-summand consistency checks decide whether the wide multiply is emitted. */ +/* Match.pd recognizers for the conditional carry-add pattern. The + two names split the gcond polarity: cond_carry_add matches when + the true edge selects (base + pow2), cond_carry_add_neg when the + true edge selects base. */ + +extern bool gimple_cond_carry_add (tree, tree *, tree (*)(tree)); +extern bool gimple_cond_carry_add_neg (tree, tree *, tree (*)(tree)); + /* Match.pd functions to match long multiplication. */ extern bool gimple_mul_hi (tree, tree *, tree (*)(tree)); @@ -4337,6 +4345,10 @@ long_mul_check_two_carries (const vec<long_mul_summand> &summands, 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; @@ -4542,9 +4554,9 @@ long_mul_classify_match (const vec<long_mul_summand> &summands, } /* 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. + long-multiply summand, optionally add the already-classified EXTRA, + 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 @@ -4558,7 +4570,8 @@ long_mul_classify_match (const vec<long_mul_summand> &summands, static const long_mul_row * long_mul_classify_chain (gimple *stmt, tree_code outer, tree lhs_type, - gimple *candidate, vec<tree> *extras_out, + gimple *candidate, const long_mul_summand *extra, + vec<tree> *extras_out, tree *out_op0, tree *out_op1) { auto_vec<tree, LONG_MUL_MAX_SUMMANDS + LONG_MUL_MAX_EXTRAS> leaves; @@ -4581,6 +4594,8 @@ long_mul_classify_chain (gimple *stmt, tree_code outer, tree lhs_type, return NULL; } } + if (extra) + summands.quick_push (*extra); if (summands.length () < 2 || summands.length () > LONG_MUL_MAX_SUMMANDS) return NULL; @@ -4609,16 +4624,29 @@ match_long_mul (gassign *stmt) /* 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)); + tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt)); if (!INTEGRAL_TYPE_P (lhs_type) || !TYPE_UNSIGNED (lhs_type) || TYPE_PRECISION (lhs_type) % 2 != 0) return false; + /* Only start at the end of a chain: a consumer with the same code + linearizes through this statement anyway, so starting here is + redundant. A consumer in another block does not count -- folding + at the later use could sink a loop-invariant multiply into a + loop. */ + use_operand_p use_p; + gimple *use_stmt; + if (single_imm_use (gimple_assign_lhs (stmt), &use_p, &use_stmt) + && is_gimple_assign (use_stmt) + && gimple_assign_rhs_code (use_stmt) == outer + && gimple_bb (use_stmt) == gimple_bb (stmt)) + 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, + = long_mul_classify_chain (stmt, outer, lhs_type, stmt, NULL, &extras, &op0, &op1); if (!row) return false; @@ -4636,6 +4664,109 @@ match_long_mul (gassign *stmt) return true; } +/* PHI-driven entry for long-multiply folding. When PHI's value + flattens to base + (carry << N), probe sum to classify the carry + kind, linearize base for the remaining high-part summands, and run + the long-multiply table. On a hit, emit a 2N-bit multiply at the + top of the join block with PHI_RES as its LHS and remove the PHI. + Otherwise leave the IR untouched. Only HIGH_PART rows are + reachable. LOW_PART rows are BIT_IOR-shaped and never produce a + carry PHI. */ + +static bool +match_long_mul_phi (gphi *phi) +{ + tree phi_res = gimple_phi_result (phi); + tree lhs_type = TREE_TYPE (phi_res); + if (!INTEGRAL_TYPE_P (lhs_type) || !TYPE_UNSIGNED (lhs_type) + || TYPE_PRECISION (lhs_type) % 2 != 0) + return false; + + tree cca_ops[4]; + if (!gimple_cond_carry_add (phi_res, cca_ops, NULL) + && !gimple_cond_carry_add_neg (phi_res, cca_ops, NULL)) + return false; + tree cmp_lhs = cca_ops[0]; + tree sum = cca_ops[1]; + tree base = cca_ops[2]; + + /* Classify sum and populate the carry summand directly. Most + specific first, mirroring long_mul_classify_carry's order. */ + long_mul_summand carry = {}; + tree sum_ops[LONG_MUL_MAX_CAPTURES]; + unsigned HOST_WIDE_INT shift_amt + = wi::exact_log2 (wi::to_wide (cca_ops[3])); + unsigned HOST_WIDE_INT halfwidth = TYPE_PRECISION (lhs_type) / 2; + carry.shift = shift_amt; + + if (gimple_mul_low_sum (sum, sum_ops, NULL) + && shift_amt == halfwidth) + { + /* mul_carry_low_sum's flat form ties the outer lshift amount to + the inner mul_hi's INTEGER_CST@0 via match.pd capture re-use; + the PHI form has no such tie, so gate on shift_amt explicitly. */ + carry.kind = LMK_CARRY_LOW_SUM; + carry.op0 = sum_ops[0]; + carry.op1 = sum_ops[1]; + carry.hilo0 = cmp_lhs; + carry.hilo1 = sum_ops[2]; + carry.hilo2 = sum_ops[3]; + } + else if (gimple_mul_cross_sum (sum, sum_ops, NULL) + && shift_amt == halfwidth) + { + /* mul_cross_sum is just (plus:c @0 @1) with no half-width + constraint. Gate here to mirror mul_carry_cross_sum; + a mismatch falls through to the LMK_CARRY_LOW branch. */ + carry.kind = LMK_CARRY_CROSS_SUM; + carry.hilo0 = cmp_lhs; + carry.hilo1 = sum_ops[0]; + carry.hilo2 = sum_ops[1]; + } + else if (shift_amt == 0 && TREE_CODE (sum) == SSA_NAME) + { + gimple *def = SSA_NAME_DEF_STMT (sum); + if (!is_gimple_assign (def) + || gimple_assign_rhs_code (def) != PLUS_EXPR) + return false; + tree p1 = gimple_assign_rhs1 (def); + tree p2 = gimple_assign_rhs2 (def); + if (p1 != cmp_lhs && p2 != cmp_lhs) + return false; + carry.kind = LMK_CARRY_LOW; + carry.carry_a = cmp_lhs; + carry.carry_b = p1 == cmp_lhs ? p2 : p1; + } + else + return false; + + /* Linearize base, the rest of the high-part chain. */ + if (TREE_CODE (base) != SSA_NAME) + return false; + gimple *base_def = SSA_NAME_DEF_STMT (base); + if (!is_gimple_assign (base_def) + || gimple_assign_rhs_code (base_def) != PLUS_EXPR) + return false; + + tree op0, op1; + const long_mul_row *row + = long_mul_classify_chain (base_def, PLUS_EXPR, lhs_type, phi, &carry, + NULL, &op0, &op1); + if (!row || row->part != long_mul_row::HIGH_PART) + return false; + + gimple_seq seq = NULL; + build_mul_high_seq (op0, op1, phi_res, gimple_location (phi), &seq); + gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi)); + gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT); + gimple_stmt_iterator psi = gsi_for_stmt (phi); + remove_phi_node (&psi, false); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Long multiplication high part folded (carry PHI).\n"); + return true; +} + /* Determine whether applying the 2 permutations (mask1 then mask2) gives back one of the input. */ @@ -6424,13 +6555,15 @@ pass_forwprop::execute (function *fun) 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)) + for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);) { gphi *phi = si.phi (); + gsi_next (&si); tree res = gimple_phi_result (phi); if (virtual_operand_p (res)) continue; + if (match_long_mul_phi (phi)) + continue; tree first = NULL_TREE; bool all_same = true;