Recognize the longhand wide-multiplication carry idiom and fold it to a
widening multiply followed by a right shift for the high part, and a
plain MULT_EXPR for the low part.
The carry idiom is the schoolbook expansion of a 2N-bit unsigned
multiply written as a top-level + chain of four NxN partial products
plus one overflow-compare carry:
xh*yh + (cross_sum >> N) + (low_accum >> N) + ((hilo > cross_sum) << N)
cross_sum = xh*yl + xl*yh
low_accum = (xl*yl >> N) + (cross_sum & mask)
For example, this AArch64 sequence from SPEC2026's 750.sealcrypto_r:
lsr x4, x0, 32
lsr x6, x1, 32
umull x3, w0, w1
umull x1, w1, w4
and x5, x3, 4294967295
umaddl x0, w0, w6, x1
cmp x1, x0
and x1, x0, 4294967295
lsr x0, x0, 32
add x3, x1, x3, lsr 32
cset x1, hi
orr x5, x5, x3, lsl 32
umaddl x4, w4, w6, x0
extr x0, x1, x3, 32
add x0, x0, x4
stp x5, x0, [x2]
can be transformed to:
umulh x3, x1, x0
mul x0, x0, x1
stp x0, x3, [x2]
Atom-level pattern recognition is implemented via match patterns in
match.pd (mul_hi, mul_lo, mul_hilo, mul_lolo, mul_hihi, mul_cross_sum,
mul_low_accum, mul_carry_cross_sum). The composite recognition that
ties atoms into a long-multiplication chain is performed in forwprop
by match_long_mul: it linearizes the outer add/ior chain into a
multiset of summands, classifies each summand via the match.pd atoms,
and looks the multiset up in long_mul_table to identify the variant.
On a hit, three cross-summand consistency checks (one operand pair,
half-width shifts, hilo cross-half products) gate the rewrite.
The HIGH_PART row emits the canonical widening shape
(N)(((2N) op1 * (2N) op2) >> N)
which pass_optimize_widening_mul later lowers to a single
WIDEN_MULT_EXPR or MULT_HIGHPART_EXPR on targets that support it.
The LOW_PART row emits a plain MULT_EXPR. HIGH_PART is emitted only
when the 2N mode is present in the mode table.
Bootstrapped/regtested on AArch64, x86-64 and PowerPC.
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.
(create_mul_high_seq): New, emits (N)(((2N) op1 * (2N) op2) >> N).
(create_mul_low_seq): New, emits MULT_EXPR.
(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.
(match_long_mul): New, top-level entry: linearizes the outer
add/ior chain, classifies summands, looks the multiset up in
long_mul_table, runs cross-summand consistency checks, and
dispatches to create_mul_high_seq / create_mul_low_seq.
(pass_forwprop::execute): Call match_long_mul on PLUS_EXPR and
BIT_IOR_EXPR statements.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/long-mul-carry.c: New test.
* gcc.target/aarch64/long_mul.c: New test.
* gcc.target/i386/long_mul.c: New test.
Co-authored-by: Philipp Tomsich <[email protected]>
Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---
(no changes since v1)
gcc/match.pd | 73 ++
.../gcc.dg/tree-ssa/long-mul-carry.c | 181 +++++
gcc/testsuite/gcc.target/aarch64/long_mul.c | 58 ++
gcc/testsuite/gcc.target/i386/long_mul.c | 58 ++
gcc/tree-ssa-forwprop.cc | 701 +++++++++++++++++-
5 files changed, 1066 insertions(+), 5 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.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 9d4ab622fe57..5a4b1923b589 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -12160,6 +12160,79 @@ and,
INTEGER_CST@2) INTEGER_CST@3)
(if (compare_tree_int (@sub1, 1) == 0)))
+#if GIMPLE
+/* Match low and high parts of longhand multiplication.
+ Given a 2N-bit unsigned type, x = xh*2^N + xl and y = yh*2^N + yl,
+ where xh, xl, yh, yl are N-bit halves extracted via shifts and masks. */
+
+/* High half: op >> N. */
+(match (mul_hi @op @0)
+ (rshift @op INTEGER_CST@0)
+ (with {
+ tree op_type = TREE_TYPE (@op); }
+ (if (INTEGRAL_TYPE_P (op_type)
+ && TYPE_UNSIGNED (op_type)
+ && TYPE_PRECISION (op_type) % 2 == 0
+ && tree_fits_uhwi_p (@0)
+ && tree_to_uhwi (@0) == TYPE_PRECISION (op_type) / 2))))
+/* Low half: op & mask. */
+(match (mul_lo @op @0)
+ (bit_and @op INTEGER_CST@0)
+ (with {
+ tree op_type = TREE_TYPE (@op); }
+ (if (INTEGRAL_TYPE_P (op_type)
+ && TYPE_UNSIGNED (op_type)
+ && TYPE_PRECISION (op_type) % 2 == 0
+ && tree_fits_uhwi_p (@0)
+ && tree_to_uhwi (@0) == wi::mask (
+ TYPE_PRECISION (op_type) / 2,
+ false,
+ TYPE_PRECISION (op_type))))))
+/* Cross product: high(op0) * low(op1). */
+(match (mul_hilo @op0 @op1 @0 @1)
+ (mult:c
+ (mul_hi @op0 INTEGER_CST@0)
+ (mul_lo @op1 INTEGER_CST@1)))
+/* Low-low product: low(op0) * low(op1). */
+(match (mul_lolo @op0 @op1 @0)
+ (mult:c
+ (mul_lo @op0 INTEGER_CST@0)
+ (mul_lo @op1 INTEGER_CST@0)))
+/* High-high product: high(op0) * high(op1). */
+(match (mul_hihi @op0 @op1 @0)
+ (mult:c
+ (mul_hi @op0 INTEGER_CST@0)
+ (mul_hi @op1 INTEGER_CST@0)))
+/* Cross sum: xh*yl + xl*yh.
+ Note: matches any PLUS; operands are validated as actual cross
+ products by the forwprop consumer (long_mul_check_consistency). */
+(match (mul_cross_sum @mul_hilo0 @mul_hilo1)
+ (plus:c @mul_hilo0 @mul_hilo1))
+/* Carry from cross-sum overflow: (cast?) (hilo > cross_sum) << N.
+ Explicit guard required because mul_cross_sum is just (plus:c @0 @1)
+ with no inherent type or halfwidth constraint. */
+(match (mul_carry_cross_sum @mul_hilo0 @mul_hilo1 @mul_hilo2 @0)
+ (lshift
+ (convert? (gt
+ @mul_hilo0
+ (mul_cross_sum @mul_hilo1 @mul_hilo2)))
+ INTEGER_CST@0)
+ (with {
+ tree op_type = TREE_TYPE (@mul_hilo0); }
+ (if (INTEGRAL_TYPE_P (op_type)
+ && TYPE_UNSIGNED (op_type)
+ && TYPE_PRECISION (op_type) % 2 == 0
+ && tree_fits_uhwi_p (@0)
+ && tree_to_uhwi (@0) == TYPE_PRECISION (op_type) / 2))))
+/* Low accumulate: (xl*yl >> N) + (cross_sum & mask). */
+(match (mul_low_accum @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1)
+ (plus:c
+ (mul_hi
+ (mul_lolo @op0 @op1 INTEGER_CST@0)
+ INTEGER_CST@1)
+ (mul_lo (mul_cross_sum @mul_hilo0 @mul_hilo1) INTEGER_CST@0)))
+#endif
+
/* Floatint point/integer comparison and integer->integer
or floating point -> float point conversion. */
(match (cond_expr_convert_p @0 @2 @3 @6)
diff --git a/gcc/testsuite/gcc.dg/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.target/aarch64/long_mul.c
b/gcc/testsuite/gcc.target/aarch64/long_mul.c
new file mode 100644
index 000000000000..2a4709ecbfd0
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/long_mul.c
@@ -0,0 +1,58 @@
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+
+typedef __UINT32_TYPE__ uint32_t;
+typedef __UINT64_TYPE__ uint64_t;
+
+/* 64-bit carry pattern for high part. */
+uint64_t mulh_carry (uint64_t x, uint64_t y)
+{
+ uint64_t x_lo = x & 0xFFFFFFFF;
+ uint64_t x_hi = x >> 32;
+ uint64_t y_lo = y & 0xFFFFFFFF;
+ uint64_t y_hi = y >> 32;
+ uint64_t y_lo_x_hi = y_lo * x_hi;
+ uint64_t y_hi_x_hi = y_hi * x_hi;
+ uint64_t y_hi_x_lo = y_hi * x_lo;
+ uint64_t y_lo_x_lo = y_lo * x_lo;
+ uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi;
+ int carry_out = cross_sum < y_lo_x_hi;
+ uint64_t carry = (uint64_t) carry_out << 32;
+ uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32;
+ uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF;
+ uint64_t cross_sum_hi = cross_sum >> 32;
+ uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
+ uint64_t interm = cross_sum_hi + y_hi_x_hi;
+ uint64_t low_accum_hi = low_accum >> 32;
+ uint64_t interm_plus_carry = interm + carry;
+ return interm_plus_carry + low_accum_hi;
+}
+
+/* 32-bit carry pattern for high part. */
+uint32_t mulh_carry_32 (uint32_t x, uint32_t y)
+{
+ uint32_t x_lo = x & 0xFFFF;
+ uint32_t x_hi = x >> 16;
+ uint32_t y_lo = y & 0xFFFF;
+ uint32_t y_hi = y >> 16;
+ uint32_t y_lo_x_hi = y_lo * x_hi;
+ uint32_t y_hi_x_hi = y_hi * x_hi;
+ uint32_t y_hi_x_lo = y_hi * x_lo;
+ uint32_t y_lo_x_lo = y_lo * x_lo;
+ uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi;
+ int carry_out = (cross_sum < y_lo_x_hi);
+ uint32_t carry = (uint32_t) carry_out << 16;
+ uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16;
+ uint32_t cross_sum_lo = cross_sum & 0xFFFF;
+ uint32_t cross_sum_hi = cross_sum >> 16;
+ uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
+ uint32_t interm = cross_sum_hi + y_hi_x_hi;
+ uint32_t low_accum_hi = low_accum >> 16;
+ uint32_t interm_plus_carry = interm + carry;
+ return interm_plus_carry + low_accum_hi;
+}
+
+/* 64-bit pattern should emit umulh. */
+/* { dg-final { scan-assembler-times "umulh\t" 1 } } */
+/* 32-bit pattern should emit umull (32x32->64 widening multiply). */
+/* { dg-final { scan-assembler-times "umull\t" 1 } } */
diff --git a/gcc/testsuite/gcc.target/i386/long_mul.c
b/gcc/testsuite/gcc.target/i386/long_mul.c
new file mode 100644
index 000000000000..6ec87eb8dd21
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/long_mul.c
@@ -0,0 +1,58 @@
+/* { dg-do compile { target { ! ia32 } } } */
+/* { dg-options "-O3" } */
+
+typedef __UINT32_TYPE__ uint32_t;
+typedef __UINT64_TYPE__ uint64_t;
+
+/* 64-bit carry pattern for high part. */
+uint64_t mulh_carry (uint64_t x, uint64_t y)
+{
+ uint64_t x_lo = x & 0xFFFFFFFF;
+ uint64_t x_hi = x >> 32;
+ uint64_t y_lo = y & 0xFFFFFFFF;
+ uint64_t y_hi = y >> 32;
+ uint64_t y_lo_x_hi = y_lo * x_hi;
+ uint64_t y_hi_x_hi = y_hi * x_hi;
+ uint64_t y_hi_x_lo = y_hi * x_lo;
+ uint64_t y_lo_x_lo = y_lo * x_lo;
+ uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi;
+ int carry_out = cross_sum < y_lo_x_hi;
+ uint64_t carry = (uint64_t) carry_out << 32;
+ uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32;
+ uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF;
+ uint64_t cross_sum_hi = cross_sum >> 32;
+ uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
+ uint64_t interm = cross_sum_hi + y_hi_x_hi;
+ uint64_t low_accum_hi = low_accum >> 32;
+ uint64_t interm_plus_carry = interm + carry;
+ return interm_plus_carry + low_accum_hi;
+}
+
+/* 32-bit carry pattern for high part. */
+uint32_t mulh_carry_32 (uint32_t x, uint32_t y)
+{
+ uint32_t x_lo = x & 0xFFFF;
+ uint32_t x_hi = x >> 16;
+ uint32_t y_lo = y & 0xFFFF;
+ uint32_t y_hi = y >> 16;
+ uint32_t y_lo_x_hi = y_lo * x_hi;
+ uint32_t y_hi_x_hi = y_hi * x_hi;
+ uint32_t y_hi_x_lo = y_hi * x_lo;
+ uint32_t y_lo_x_lo = y_lo * x_lo;
+ uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi;
+ int carry_out = (cross_sum < y_lo_x_hi);
+ uint32_t carry = (uint32_t) carry_out << 16;
+ uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16;
+ uint32_t cross_sum_lo = cross_sum & 0xFFFF;
+ uint32_t cross_sum_hi = cross_sum >> 16;
+ uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi;
+ uint32_t interm = cross_sum_hi + y_hi_x_hi;
+ uint32_t low_accum_hi = low_accum >> 16;
+ uint32_t interm_plus_carry = interm + carry;
+ return interm_plus_carry + low_accum_hi;
+}
+
+/* 64-bit pattern should emit mulq (unsigned 64x64->128 multiply). */
+/* { dg-final { scan-assembler-times "\tmulq" 1 } } */
+/* 32-bit pattern should emit imulq (64-bit multiply of zero-extended
operands). */
+/* { dg-final { scan-assembler-times "\timulq" 1 } } */
diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
index 12c07c99c9bd..3870bf17c0e0 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -3592,6 +3592,693 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)
return true;
}
+/* 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));
+
+/* Replace STMT with a 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
+create_mul_high_seq (tree op1, tree op2, gimple *stmt)
+{
+ 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,
+ 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 (gimple_get_lhs (stmt), NOP_EXPR, hi);
+ gimple_set_location (prod, loc);
+ gimple_seq_add_stmt (&seq, prod);
+
+ 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. */
+
+static void
+create_mul_low_seq (tree op1, tree op2, gimple *stmt)
+{
+ gimple *prod = gimple_build_assign (gimple_get_lhs (stmt),
+ MULT_EXPR, op1, op2);
+ gimple_set_location (prod, gimple_location (stmt));
+ gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+ gsi_replace (&gsi, prod, 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. */
+
+/* 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;
+
+enum long_mul_kind {
+ LMK_MUL_HIHI,
+ LMK_MUL_LOLO,
+ LMK_MUL_HILO,
+ LMK_CROSS_SUM,
+ LMK_LOW_ACCUM,
+ LMK_CARRY_CROSS_SUM,
+};
+
+/* How the leaf wraps its inner kind. Carry kinds use LMX_NONE: their
+ match.pd pattern bakes the lshift in, so the leaf is already the
+ complete carry expression. */
+
+enum long_mul_extract {
+ LMX_NONE,
+ LMX_HI,
+ LMX_LO,
+ LMX_SHL_N,
+};
+
+struct long_mul_summand {
+ long_mul_kind kind;
+ long_mul_extract extract;
+ tree op0, op1;
+ tree hilo0, hilo1, hilo2;
+ unsigned HOST_WIDE_INT shift;
+ unsigned HOST_WIDE_INT mask;
+};
+
+/* Walk the OUTER addition or BIT_IOR chain rooted at STMT and collect
+ the leaf operands into LEAVES. Descends through single-use
+ intermediate stmts of the same code. Returns false once the leaf
+ count exceeds LONG_MUL_MAX_SUMMANDS, 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)
+ 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)
+ info->shift = tree_to_uhwi (res_ops[shift_idx]);
+}
+
+/* Classify LEAF as a carry-kind summand. The lshift amount is baked
+ into mul_carry_cross_sum, so it's tried before any branch that looks
+ for a generic (X >> N) or (X << N) wrapper. */
+
+static bool
+long_mul_classify_carry (tree leaf, long_mul_summand *info)
+{
+ tree res_ops[LONG_MUL_MAX_CAPTURES];
+ if (gimple_mul_carry_cross_sum (leaf, res_ops, NULL))
+ {
+ long_mul_set_summand (info, LMK_CARRY_CROSS_SUM, res_ops);
+ return true;
+ }
+ return false;
+}
+
+/* Plus-based summand kinds shared by the (X >> SHIFT) and (X << SHIFT)
+ classifiers. */
+
+static bool
+long_mul_classify_plus_kinds (tree inner, long_mul_summand *info)
+{
+ tree res_ops[LONG_MUL_MAX_CAPTURES];
+ if (gimple_mul_low_accum (inner, res_ops, NULL))
+ {
+ long_mul_set_summand (info, LMK_LOW_ACCUM, res_ops);
+ return true;
+ }
+ return false;
+}
+
+/* Classify INNER -- already unwrapped from an outer (X >> SHIFT) -- as
+ a high-half-extracted summand. mul_hilo (mult-shape) is orthogonal
+ to the plus-based kinds and is tried first; mul_cross_sum (any plus)
+ is the fallback after the shared plus-based kinds. */
+
+static bool
+long_mul_classify_hi_extract (tree inner, unsigned HOST_WIDE_INT shift,
+ long_mul_summand *info)
+{
+ tree res_ops[LONG_MUL_MAX_CAPTURES];
+ info->extract = LMX_HI;
+ info->shift = shift;
+ if (gimple_mul_hilo (inner, res_ops, NULL))
+ {
+ long_mul_set_summand (info, LMK_MUL_HILO, res_ops);
+ return true;
+ }
+ if (long_mul_classify_plus_kinds (inner, info))
+ return true;
+ if (gimple_mul_cross_sum (inner, res_ops, NULL))
+ {
+ long_mul_set_summand (info, LMK_CROSS_SUM, res_ops);
+ return true;
+ }
+ return false;
+}
+
+/* Classify INNER -- already unwrapped from an outer (X & MASK) -- as
+ a low-half-masked summand. */
+
+static bool
+long_mul_classify_lo_extract (tree inner, unsigned HOST_WIDE_INT mask,
+ long_mul_summand *info)
+{
+ tree res_ops[LONG_MUL_MAX_CAPTURES];
+ info->extract = LMX_LO;
+ info->mask = mask;
+ if (gimple_mul_lolo (inner, res_ops, NULL))
+ {
+ long_mul_set_summand (info, LMK_MUL_LOLO, res_ops);
+ return true;
+ }
+ return false;
+}
+
+/* Classify INNER -- already unwrapped from an outer (X << SHIFT) -- as
+ a left-shifted summand. No mul_hilo here -- that shape appears only
+ under (X >> SHIFT). */
+
+static bool
+long_mul_classify_shl_extract (tree inner, unsigned HOST_WIDE_INT shift,
+ long_mul_summand *info)
+{
+ tree res_ops[LONG_MUL_MAX_CAPTURES];
+ info->extract = LMX_SHL_N;
+ info->shift = shift;
+ if (long_mul_classify_plus_kinds (inner, info))
+ return true;
+ if (gimple_mul_cross_sum (inner, res_ops, NULL))
+ {
+ long_mul_set_summand (info, LMK_CROSS_SUM, res_ops);
+ return true;
+ }
+ return false;
+}
+
+/* Classify LEAF as one of the bare-kind summands (no extraction
+ wrapper): mul_hihi or mul_lolo standing on their own. */
+
+static bool
+long_mul_classify_bare (tree leaf, long_mul_summand *info)
+{
+ tree res_ops[LONG_MUL_MAX_CAPTURES];
+ if (gimple_mul_hihi (leaf, res_ops, NULL))
+ {
+ long_mul_set_summand (info, LMK_MUL_HIHI, res_ops);
+ return true;
+ }
+ if (gimple_mul_lolo (leaf, res_ops, NULL))
+ {
+ long_mul_set_summand (info, LMK_MUL_LOLO, res_ops);
+ return true;
+ }
+ return false;
+}
+
+/* Classify LEAF as one of the long-multiply summand shapes. On success,
+ fill *INFO with the kind, extract, captured operands and shift/mask.
+ Dispatches to per-extract helpers; the order matters because the
+ carry kinds bake an lshift into the pattern and would otherwise be
+ misread by the (X << N) branch. */
+
+static bool
+long_mul_classify_summand (tree leaf, long_mul_summand *info)
+{
+ tree res_ops[LONG_MUL_MAX_CAPTURES];
+ *info = {};
+
+ if (long_mul_classify_carry (leaf, info))
+ return true;
+
+ if (gimple_mul_hi (leaf, res_ops, NULL))
+ return long_mul_classify_hi_extract (res_ops[0],
+ tree_to_uhwi (res_ops[1]), info);
+
+ if (gimple_mul_lo (leaf, res_ops, NULL))
+ return long_mul_classify_lo_extract (res_ops[0],
+ tree_to_uhwi (res_ops[1]), info);
+
+ tree inner;
+ unsigned HOST_WIDE_INT shift;
+ if (long_mul_is_lshift_def (leaf, &inner, &shift))
+ return long_mul_classify_shl_extract (inner, shift, info);
+
+ return long_mul_classify_bare (leaf, info);
+}
+
+/* qsort comparator: sort summands by (kind, extract) to put a multiset
+ into canonical order for table lookup. Unstable sort within a tie is
+ harmless: no row in long_mul_table pairs distinct subterms under the
+ same (kind, extract), and long_mul_check_consistency cross-validates
+ that matching summands share one canonical (op0, op1). */
+
+static int
+long_mul_summand_compare (const void *a, const void *b)
+{
+ const long_mul_summand *sa = (const long_mul_summand *) a;
+ const long_mul_summand *sb = (const long_mul_summand *) b;
+ if (sa->kind != sb->kind)
+ return (int) sa->kind - (int) sb->kind;
+ return (int) sa->extract - (int) sb->extract;
+}
+
+/* One row of the long-multiply variant table. COUNT is how many entries
+ of SIG carry the row's signature (2 to LONG_MUL_MAX_SUMMANDS); a row
+ with fewer summands leaves the remaining SIG entries zero-initialized.
+ Those zeros are not a terminator -- {LMK_MUL_HIHI, LMX_NONE} is itself a
+ valid signature -- so long_mul_signature_matches is bounded by COUNT,
+ never by a sentinel entry. */
+
+struct long_mul_row {
+ enum long_mul_row_part { HIGH_PART, LOW_PART } part;
+ tree_code outer;
+ unsigned char count;
+ struct {
+ long_mul_kind kind;
+ long_mul_extract extract;
+ } sig[LONG_MUL_MAX_SUMMANDS];
+ bool (*extra_check) (const vec<long_mul_summand> &, gimple *);
+};
+
+/* True if (A, B) is the same pair as (OP0, OP1) in either order. */
+
+static inline bool
+long_mul_same_ops (tree a, tree b, tree op0, tree op1)
+{
+ return (a == op0 && b == op1) || (a == op1 && b == op0);
+}
+
+/* True if H is a cross-half product of (OP0, OP1) -- gimple_mul_hilo
+ recognizes it and its captured operands match the pair. */
+
+static bool
+long_mul_is_cross_half (tree h, tree op0, tree op1)
+{
+ tree scratch[LONG_MUL_MAX_CAPTURES];
+ return gimple_mul_hilo (h, scratch, NULL)
+ && long_mul_same_ops (scratch[0], scratch[1], op0, op1);
+}
+
+/* Orientation of the mul_hilo capture H relative to (OP0, OP1):
+ returns 0 for high(OP0)*low(OP1), 1 for high(OP1)*low(OP0), or -1
+ if H does not decompose that way. A cross-sum of two mul_hilos must
+ see one of each orientation -- otherwise a doubled factor would fold
+ to the wrong value. (In a self-multiply the two orientations
+ coincide; see the OP0 == OP1 bypass in long_mul_check_consistency.) */
+
+static int
+long_mul_hilo_orientation (tree h, tree op0, tree op1)
+{
+ tree scratch[LONG_MUL_MAX_CAPTURES];
+ if (!gimple_mul_hilo (h, scratch, NULL))
+ return -1;
+ if (scratch[0] == op0 && scratch[1] == op1)
+ return 0;
+ if (scratch[0] == op1 && scratch[1] == op0)
+ return 1;
+ return -1;
+}
+
+/* Find the first summand that carries operand captures, and return its
+ (op0, op1) pair in *OP0_OUT / *OP1_OUT. Returns false if no summand
+ provides them. */
+
+static bool
+long_mul_canonical_ops (const vec<long_mul_summand> &summands,
+ tree *op0_out, tree *op1_out)
+{
+ for (const long_mul_summand &s : summands)
+ if (s.op0)
+ {
+ *op0_out = s.op0;
+ *op1_out = s.op1;
+ return true;
+ }
+ return false;
+}
+
+/* Run the cross-summand validation invariants and return the canonical
+ (op0, op1). Returns false unless all summands that carry operands use
+ the same (op0, op1) pair (in either order), every LMX_HI/LMX_SHL_N shift
+ equals halfwidth, every captured hilo is a true cross-half product of
+ (op0, op1), and every cross-half pair (both those inside a single
+ mul_cross_sum-bearing summand and those spread across separate
+ LMK_MUL_HILO summands) contains one of each orientation. */
+
+static bool
+long_mul_check_consistency (const vec<long_mul_summand> &summands,
+ tree *op0_out, tree *op1_out)
+{
+ tree op0, op1;
+ if (!long_mul_canonical_ops (summands, &op0, &op1))
+ return false;
+
+ tree op_type = TREE_TYPE (op0);
+ if (!INTEGRAL_TYPE_P (op_type)
+ || TYPE_PRECISION (op_type) % 2 != 0)
+ return false;
+ unsigned int halfwidth = TYPE_PRECISION (op_type) / 2;
+
+ /* Self-multiply (x*x) collapses the two cross-halves onto one value,
+ so the complementarity constraint is a trivial no-op there. */
+ bool need_orient = op0 != op1;
+ int mul_hilo_orient[2] = { 0, 0 };
+
+ for (const long_mul_summand &s : summands)
+ {
+ if (s.op0 && !long_mul_same_ops (s.op0, s.op1, op0, op1))
+ return false;
+ if ((s.extract == LMX_HI || s.extract == LMX_SHL_N)
+ && s.shift != halfwidth)
+ return false;
+ tree hilos[3] = { s.hilo0, s.hilo1, s.hilo2 };
+ for (tree h : hilos)
+ if (h && !long_mul_is_cross_half (h, op0, op1))
+ return false;
+
+ if (!need_orient)
+ continue;
+
+ /* The two cross-sum operands are the last two non-null hilos:
+ (hilo1, hilo2) for the CARRY_*_SUM kinds, (hilo0, hilo1) for
+ the CROSS_SUM / SUM / ACCUM / LADDER_SUM kinds, none for the
+ rest. */
+ tree a = NULL_TREE;
+ tree b = NULL_TREE;
+ if (s.hilo2)
+ {
+ a = s.hilo1;
+ b = s.hilo2;
+ }
+ else if (s.hilo1)
+ {
+ a = s.hilo0;
+ b = s.hilo1;
+ }
+ if (a && b
+ && (long_mul_hilo_orientation (a, op0, op1)
+ == long_mul_hilo_orientation (b, op0, op1)))
+ return false;
+
+ /* Two LMK_MUL_HILO summands (the two-hilos ladder form) stand for
+ the two cross-halves separately; count orientations and require
+ the pair to be complementary. s.op0/op1 is already validated to
+ match (op0, op1) in some order above. */
+ if (s.kind == LMK_MUL_HILO && s.op0)
+ mul_hilo_orient[s.op0 == op1]++;
+ }
+
+ if (mul_hilo_orient[0] + mul_hilo_orient[1] >= 2
+ && (mul_hilo_orient[0] == 0 || mul_hilo_orient[1] == 0))
+ return false;
+
+ *op0_out = op0;
+ *op1_out = op1;
+ return true;
+}
+
+/* Compare the (already-sorted) SUMMANDS multiset against ROW.sig. */
+
+static bool
+long_mul_signature_matches (const vec<long_mul_summand> &summands,
+ const long_mul_row &row)
+{
+ if (row.count != summands.length ())
+ return false;
+ for (unsigned i = 0; i < row.count; i++)
+ if (summands[i].kind != row.sig[i].kind
+ || summands[i].extract != row.sig[i].extract)
+ return false;
+ return true;
+}
+
+/* Long-multiply variant table. Each row enumerates the multiset of
+ (kind, extract) summands that compose one long-multiply form. Rows
+ are sorted by long_mul_summand_compare, matching the input summands'
+ sort order, so a plain element-wise compare suffices. Rows describe
+ unsigned schoolbook expansions on an even-width 2N-bit type split at
+ half-width N; EXTRA_CHECK carries invariants the (kind, extract)
+ signature cannot express. */
+
+static const long_mul_row long_mul_table[] = {
+ /* HIGH-PART fold. Notation: xh, xl, yh, yl are the half-width pieces
+ of x and y; N is the half-width. cross_sum = xh*yl + xl*yh; hilo is
+ either xh*yl or xl*yh (consumers validate the operand shape). */
+ /* xh*yh + (low_accum >> N) + (cross_sum >> N)
+ + ((hilo > cross_sum) << N),
+ low_accum = (xl*yl >> N) + (cross_sum & mask). */
+ { long_mul_row::HIGH_PART, PLUS_EXPR, 4,
+ { { LMK_MUL_HIHI, LMX_NONE },
+ { LMK_CROSS_SUM, LMX_HI },
+ { LMK_LOW_ACCUM, LMX_HI },
+ { LMK_CARRY_CROSS_SUM, LMX_NONE } },
+ NULL },
+ /* LOW-PART fold. Recover the lower 2N bits from xl*yl plus a
+ shifted cross-half term. Notation as for the HIGH-PART row above. */
+ /* (xl*yl & mask) | (low_accum << N),
+ low_accum = (xl*yl >> N) + (cross_sum & mask). */
+ { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2,
+ { { LMK_MUL_LOLO, LMX_LO },
+ { LMK_LOW_ACCUM, LMX_SHL_N } },
+ NULL },
+};
+
+/* If a multi-used inner addition (sharing the chain's outer code) blocked
+ linearization of a long-mul candidate, emit a dump-file hint pointing
+ at it. */
+
+static void
+long_mul_hint_shared_intermediate (gimple *shared_def)
+{
+ if (!shared_def || !dump_file || !(dump_flags & TDF_DETAILS))
+ return;
+ fprintf (dump_file, "long-mul fold rejected: shared intermediate at ");
+ print_gimple_stmt (dump_file, shared_def, 0, TDF_SLIM);
+}
+
+/* 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;
+
+ 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);
+ LOW_PART rows emit a plain MULT_EXPR. Emission needs only a 2N
+ mode to exist in the mode table -- capability is settled on the
+ lowering side. */
+ scalar_int_mode mode, wide_mode;
+ bool can_emit_high
+ = is_a <scalar_int_mode> (TYPE_MODE (lhs_type), &mode)
+ && GET_MODE_2XWIDER_MODE (mode).exists (&wide_mode);
+
+ for (const long_mul_row &row : long_mul_table)
+ {
+ if (row.outer != outer
+ || (row.part == long_mul_row::HIGH_PART && !can_emit_high)
+ || !long_mul_signature_matches (summands, row))
+ continue;
+
+ tree op0, op1;
+ if (!long_mul_check_consistency (summands, &op0, &op1))
+ continue;
+
+ /* Do not emit the wide chain when an operand is subject to
+ abnormal coalescing: the widening_mul-side consumers refuse
+ such operands (see convert_mult_to_widen), which would leave
+ the chain without a consumer. */
+ if (row.part == long_mul_row::HIGH_PART
+ && ((TREE_CODE (op0) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
+ || (TREE_CODE (op1) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
+ continue;
+
+ if (row.extra_check && !row.extra_check (summands, stmt))
+ continue;
+
+ 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 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;
+}
/* Determine whether applying the 2 permutations (mask1 then mask2)
gives back one of the input. */
@@ -5851,11 +6538,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 (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
