[COMMITTED PATCH v9 6/7] match.pd, forwprop: Recognize long-multiply carries written as 2-arg PHI
Konstantinos Eleftheriou <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
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]>
Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---
(no changes since v1)
gcc/match.pd | 25 ++
.../gcc.dg/tree-ssa/long-mul-boundary-64.c | 417 ++++++++++++++++++
.../gcc.dg/tree-ssa/long-mul-boundary.c | 394 +++++++++++++++++
.../gcc.dg/tree-ssa/long-mul-carry.c | 74 +++-
.../gcc.dg/tree-ssa/long-mul-partial.c | 193 ++++++++
.../gcc.dg/tree-ssa/long-mul-two-carry.c | 31 +-
gcc/tree-ssa-forwprop.cc | 149 ++++++-
7 files changed, 1270 insertions(+), 13 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c
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;
--
2.55.0