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