The existing long-multiply fold walks a top-level + statement to find
its summands. 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, leaving the existing matcher nothing
to walk.
Add a PHI-driven entry. Two match.pd recognizers cond_carry_add and
cond_carry_add_neg match the PHI<base + pow2, base> shape guarded by
an unsigned compare on (a, sum) in either polarity.
match_long_mul_phi in tree-ssa-forwprop.cc classifies the captured
sum into a CARRY_LOW / CARRY_CROSS_SUM / CARRY_LOW_SUM summand,
linearizes base for the remaining high-part summands, and runs
long_mul_table. On a match it emits a 2N-bit multiply with PHI_RES
as its LHS and removes the PHI; only HIGH_PART rows are reachable
(LOW_PART rows are BIT_IOR-shaped and never produce a carry PHI).
Factor long_mul_classify_match and build_mul_high_seq out of
match_long_mul and create_mul_high_seq, and add long_mul_classify_chain
wrapping the linearize + classify + sort + match block, so the PHI
entry reuses the table search and wide-multiply emit.
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.
(build_mul_high_seq): New seq-producing wide-multiply build.
(create_mul_high_seq): Use build_mul_high_seq.
(long_mul_classify_match): New classify-only entry to the
long_mul_table.
(long_mul_classify_chain): New shared helper wrapping
linearize + classify + sort + table lookup.
(match_long_mul): Use long_mul_classify_chain.
(match_long_mul_phi): New PHI-driven entry; recognizes a
cond_carry_add(_neg) PHI and folds the long-multiply shape
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 | 302 ++++++++++---
7 files changed, 1366 insertions(+), 70 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 ca6d57814776..063315d398c0 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -6411,6 +6411,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..b63e077e7aa4 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, recognised 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 30f3a0310d0f..95f83e60f25d 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -3592,6 +3592,14 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)
return true;
}
+/* 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));
@@ -3620,26 +3628,31 @@ extern bool gimple_mul_ladder_part_sum (tree, tree *,
tree (*)(tree));
already owns them. */
static void
-create_mul_high_seq (tree op1, tree op2, gimple *stmt)
+build_mul_high_seq (tree op1, tree op2, tree dest, location_t loc,
+ gimple_seq *seq)
{
tree op_type = TREE_TYPE (op1);
unsigned int width = TYPE_PRECISION (op_type);
tree wide_type = build_nonstandard_integer_type (width * 2, 1);
- location_t loc = gimple_location (stmt);
- gimple_seq seq = NULL;
-
- tree wide_a = gimple_convert (&seq, loc, wide_type, op1);
- tree wide_b = gimple_convert (&seq, loc, wide_type, op2);
- tree wide_prod = gimple_build (&seq, loc, MULT_EXPR, wide_type,
+ tree wide_a = gimple_convert (seq, loc, wide_type, op1);
+ tree wide_b = gimple_convert (seq, loc, wide_type, op2);
+ tree wide_prod = gimple_build (seq, loc, MULT_EXPR, wide_type,
wide_a, wide_b);
- tree hi = gimple_build (&seq, loc, RSHIFT_EXPR, wide_type, wide_prod,
+ tree hi = gimple_build (seq, loc, RSHIFT_EXPR, wide_type, wide_prod,
build_int_cst (integer_type_node, width));
- gimple *prod = gimple_build_assign (gimple_get_lhs (stmt), NOP_EXPR, hi);
+ gimple *prod = gimple_build_assign (dest, NOP_EXPR, hi);
gimple_set_location (prod, loc);
- gimple_seq_add_stmt (&seq, prod);
+ gimple_seq_add_stmt (seq, prod);
+}
+static void
+create_mul_high_seq (tree op1, tree op2, gimple *stmt)
+{
+ gimple_seq seq = NULL;
+ build_mul_high_seq (op1, op2, gimple_get_lhs (stmt),
+ gimple_location (stmt), &seq);
gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
gsi_replace_with_seq (&gsi, seq, true);
}
@@ -4284,6 +4297,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;
@@ -4434,49 +4451,18 @@ long_mul_hint_shared_intermediate (gimple *shared_def)
print_gimple_stmt (dump_file, shared_def, 0, TDF_SLIM);
}
-/* Top-level entry for long-multiply folding. Walks STMT's outer
- addition or BIT_IOR chain, classifies the summands, and dispatches
- to create_mul_high_seq / create_mul_low_seq if the multiset matches
- a known long-multiply form. Returns true on success. */
-
-static bool
-match_long_mul (gimple *stmt)
+/* Search long_mul_table for a row whose multiset matches SUMMANDS for
+ outer kind OUTER on a result of type LHS_TYPE. CANDIDATE_STMT is
+ passed to per-row extra_check predicates. On a hit, returns the
+ matching row and writes the half-width operands via OUT_OP0/OUT_OP1.
+ No IR mutation. */
+
+static const long_mul_row *
+long_mul_classify_match (const vec<long_mul_summand> &summands,
+ tree lhs_type, tree_code outer,
+ gimple *candidate_stmt,
+ tree *out_op0, tree *out_op1)
{
- if (!is_gimple_assign (stmt))
- return false;
- tree_code outer = gimple_assign_rhs_code (stmt);
- if (outer != PLUS_EXPR && outer != BIT_IOR_EXPR)
- return false;
-
- /* Skip non-candidate adds (signed, pointer, odd-width) before walking the
- chain. No legitimate long-mul leaf has a type the atoms would reject;
- this just avoids the linearize/classify work on every other PLUS/IOR. */
- tree lhs_type = TREE_TYPE (gimple_get_lhs (stmt));
- if (!INTEGRAL_TYPE_P (lhs_type)
- || !TYPE_UNSIGNED (lhs_type)
- || TYPE_PRECISION (lhs_type) % 2 != 0)
- return false;
-
- auto_vec<tree, LONG_MUL_MAX_SUMMANDS + 1> leaves;
- gimple *shared_def = NULL;
- if (!long_mul_linearize_chain (stmt, outer, leaves, &shared_def))
- return false;
- if (leaves.length () < 2)
- return false;
-
- auto_vec<long_mul_summand, LONG_MUL_MAX_SUMMANDS> summands;
- for (tree leaf : leaves)
- {
- long_mul_summand s;
- if (!long_mul_classify_summand (leaf, &s))
- {
- long_mul_hint_shared_intermediate (shared_def);
- return false;
- }
- summands.quick_push (s);
- }
- summands.qsort (long_mul_summand_compare);
-
/* HIGH_PART rows emit a 2N-bit multiply that is consumed by
pass_optimize_widening_mul (WIDEN_MULT_EXPR conversion or
longhand re-synthesis) or by expand (supported 2N mode);
@@ -4510,24 +4496,205 @@ match_long_mul (gimple *stmt)
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
continue;
- if (row.extra_check && !row.extra_check (summands, stmt))
+ if (row.extra_check && !row.extra_check (summands, candidate_stmt))
continue;
- if (row.part == long_mul_row::HIGH_PART)
+ *out_op0 = op0;
+ *out_op1 = op1;
+ return &row;
+ }
+ return NULL;
+}
+
+/* Walk STMT's outer chain (kind OUTER), classify each leaf as a
+ long-multiply summand, optionally append EXTRA as an additional
+ pre-classified summand, sort the multiset, and look it up in
+ long_mul_table on a result of type LHS_TYPE. CANDIDATE is passed
+ to per-row extra_check predicates. On a hit, returns the matched
+ row and writes the half-width operands via OUT_OP0/OUT_OP1; on a
+ miss returns NULL and emits a shared-intermediate hint to the
+ dump file when one blocked linearization. No IR mutation. */
+
+static const long_mul_row *
+long_mul_classify_chain (gimple *stmt, tree_code outer, tree lhs_type,
+ gimple *candidate, const long_mul_summand *extra,
+ tree *out_op0, tree *out_op1)
+{
+ auto_vec<tree, LONG_MUL_MAX_SUMMANDS + 1> leaves;
+ gimple *shared_def = NULL;
+ if (!long_mul_linearize_chain (stmt, outer, leaves, &shared_def))
+ return NULL;
+ unsigned total = leaves.length () + (extra ? 1 : 0);
+ if (total < 2 || total > LONG_MUL_MAX_SUMMANDS)
+ return NULL;
+
+ auto_vec<long_mul_summand, LONG_MUL_MAX_SUMMANDS> summands;
+ for (tree leaf : leaves)
+ {
+ long_mul_summand s;
+ if (!long_mul_classify_summand (leaf, &s))
{
- create_mul_high_seq (op0, op1, stmt);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Long multiplication high part folded.\n");
- return true;
+ long_mul_hint_shared_intermediate (shared_def);
+ return NULL;
}
- create_mul_low_seq (op0, op1, stmt);
+ summands.quick_push (s);
+ }
+ if (extra)
+ summands.quick_push (*extra);
+ summands.qsort (long_mul_summand_compare);
+
+ const long_mul_row *row
+ = long_mul_classify_match (summands, lhs_type, outer, candidate,
+ out_op0, out_op1);
+ if (!row)
+ long_mul_hint_shared_intermediate (shared_def);
+ return row;
+}
+
+/* Top-level entry for long-multiply folding. Walks STMT's outer
+ addition or BIT_IOR chain, classifies the summands, and dispatches
+ to create_mul_high_seq / create_mul_low_seq if the multiset matches
+ a known long-multiply form. Returns true on success. */
+
+static bool
+match_long_mul (gimple *stmt)
+{
+ if (!is_gimple_assign (stmt))
+ return false;
+ tree_code outer = gimple_assign_rhs_code (stmt);
+ if (outer != PLUS_EXPR && outer != BIT_IOR_EXPR)
+ return false;
+
+ /* Skip non-candidate adds (signed, pointer, odd-width) before walking the
+ chain. No legitimate long-mul leaf has a type the atoms would reject;
+ this just avoids the linearize/classify work on every other PLUS/IOR. */
+ tree lhs_type = TREE_TYPE (gimple_get_lhs (stmt));
+ if (!INTEGRAL_TYPE_P (lhs_type)
+ || !TYPE_UNSIGNED (lhs_type)
+ || TYPE_PRECISION (lhs_type) % 2 != 0)
+ return false;
+
+ tree op0, op1;
+ const long_mul_row *row
+ = long_mul_classify_chain (stmt, outer, lhs_type, stmt, NULL,
+ &op0, &op1);
+ if (!row)
+ return false;
+
+ if (row->part == long_mul_row::HIGH_PART)
+ {
+ create_mul_high_seq (op0, op1, stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Long multiplication low part folded.\n");
+ fprintf (dump_file, "Long multiplication high part folded.\n");
return true;
}
+ create_mul_low_seq (op0, op1, stmt);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Long multiplication low part folded.\n");
+ return true;
+}
- long_mul_hint_shared_intermediate (shared_def);
- return false;
+/* 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,
+ &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)
@@ -6315,14 +6482,19 @@ pass_forwprop::execute (function *fun)
}
}
- /* Record degenerate PHIs in the lattice. */
- for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
- gsi_next (&si))
+ /* Fold PHI-form long-multiply carries and record degenerate
+ PHIs in the lattice. Iterator advanced up front so a folded
+ PHI can be removed in-flight; a long-mul carry PHI is never
+ degenerate, so the two cases are disjoint. */
+ for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);)
{
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
