The forwprop long-multiply recognizer canonicalizes hand-written
longhand high-part multiplies into a cast+mult+shift+cast chain:
lhs = (N) (((2N) op1 * (2N) op2) >> N)
When the target lacks an expansion path for the wide form,
`lower_long_mul_high_chain' resynthesizes the longhand at N precision
with a carry-cross-sum recipe. The partial products use
(N/2)-by-(N/2)->N WIDEN_MULT_EXPR when the target has that optab, and
plain MULT_EXPR at N precision
otherwise (value-equivalent, as the halves are < 2^(N/2)). The
accumulator stays at narrow_type, so the chain never materializes 2N
in gimple -- necessary for shapes where the 2N mode has no expansion
path at all (e.g. the high 128 bits of a 128x128 product on a target
with OImode in the mode table but no scalar OImode support).
The lowering is type-adaptive on the outer convert's lhs type, since
conversion merging can combine the chain's final truncation with a
later user cast (e.g. `(u64) mulh128 (x, y)'): the longhand is built
at narrow precision and converted once to the actual lhs type, which
is value-preserving for any integral lhs (the high part is < 2^N).
The recognizer's HIGH_PART emit and the widening_mul pass's gate are
paired via `optimize_widening_mul_active_p', so a chain is emitted
only when the pass will run to rescue any unsupported 2N shape.
gcc/ChangeLog:
* match.pd (long_mul_high_chain): New atom for the chain
shape.
* tree-ssa-math-opts.h (optimize_widening_mul_active_p):
Declare.
* tree-ssa-math-opts.cc (optimize_widening_mul_active_p): New;
shared gate used by pass_optimize_widening_mul::gate and by
the forwprop long-multiply recognizer.
(can_widen_to_narrow_p): New.
(build_long_mul_partials): New; emits the four partial
products using widening or plain multiplies.
(gimple_long_mul_high_chain): Declare.
(lower_long_mul_high_chain): New; lowers the high-part chain
to a longhand at narrow precision.
(pass_optimize_widening_mul::gate): Delegate to
optimize_widening_mul_active_p.
(math_opts_dom_walker::after_dom_children): Dispatch to
lower_long_mul_high_chain on the outer convert.
* tree-ssa-forwprop.cc: Include tree-ssa-math-opts.h.
(long_mul_classify_match): Gate the HIGH_PART wide-chain
emit on optimize_widening_mul_active_p.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/long-mul-carry.c: Add scans for the
high-part chain lowering and its dump message.
* gcc.dg/tree-ssa/long-mul-ladder.c: Likewise.
* gcc.dg/tree-ssa/long-mul-chain-cse-128.c: New test.
* gcc.dg/torture/long-mul-128.c: New test.
* gcc.dg/tree-ssa/long-mul-chain-trunc-128.c: New test.
* gcc.target/arm/long-mul-thumb1-inline.c: New test.
* gcc.target/arm/long-mul-umull.c: New test.
* gcc.target/i386/widen_mult_high_chain.c: New test.
* lib/target-supports.exp (check_effective_target_oi_mode):
New; enumerates targets whose mode table declares OImode.
Co-authored-by: Philipp Tomsich <[email protected]>
Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---
Changes in v7:
- Split the single long-multiply fold (was 1/2) into five patches: a
base patch carrying the framework and the carry form, then one
patch each for the carry-low-sum, two-carry, ladder and low-plus
variants. Easier to review and to bisect a variant in isolation.
The PHI-form recognition follows as 6/7, unchanged from v6's 2/2.
- New 7/7: lower the emitted high-part chain to inline longhand at
narrow precision when the target has no expansion path for the 2N
form. v6 only emitted a HIGH_PART when the 2N scalar mode existed
and skipped it otherwise; v7 emits it and pairs the recognizer with
lower_long_mul_high_chain via optimize_widening_mul_active_p, so a
128x128 high part on a target whose mode table has OImode but no
scalar OImode support is now built from (N/2)-wide partial products
instead of a 2N multiply the target cannot expand.
- Refuse the HIGH_PART emit and the chain lowering for BITINT_TYPE,
keeping the recognizer and the lowering gate symmetric.
- Add per-variant tree-ssa tests, 128-bit torture and runtime tests,
arm thumb1 / umull inline tests, and a check_effective_target
_oi_mode helper.
Changes in v6:
- Reorder so the long-multiply fold (was 2/2) is now 1/2 and a new
PHI-form recognition pass is 2/2. Reverting 2/2 leaves a working
long-multiply fold for the flat-shifted-compare carry form.
- Drop v5's standalone flatten_cond_carry_add driver. The same
cond_carry_add / cond_carry_add_neg match.pd recognizers now feed
a match_long_mul_phi entry inside the long-multiply fold, so a
PHI-shaped carry folds straight to the wide-multiply output.
- Factor long_mul_classify_chain, long_mul_classify_match and
build_mul_high_seq for sharing between match_long_mul and the new
match_long_mul_phi.
- cond_carry_add_neg uses le / ge instead of gt / lt to encode the
carry condition strictly. v5 inverted the compare via
invert_tree_comparison in the flatten driver; v6 synthesises the
carry summand directly inside match_long_mul_phi and so requires
the recogniser to encode the strict form.
- Delete forwprop-44/45/46.c; add PHI-form coverage in
long-mul-carry.c, long-mul-two-carry.c, long-mul-boundary.c
and long-mul-boundary-64.c.
- Add PHI-form near-miss tests in long-mul-partial.c and
operand-swap polarity coverage in long-mul-boundary{,-64}.c.
- Refresh stale long-mul comment references (check_hilo_and_ops,
fold_mul_low_plus) and reword mul_carry_low's :c-on-gt note to
the correct LT form (a + b < a).
Changes in v5:
- 1/2:
- Replace the match.pd simplify on COND_EXPR with cond_carry_add
/ cond_carry_add_neg match recognizers (cond^), split by gcond
polarity, plus a flatten_cond_carry_add driver in
tree-ssa-forwprop.cc. The driver inverts the gcond's
comparison for the _neg form. Modelled on match_saturation_add.
- Remove fold_cond_carry_add_profitable_p and the tm_p.h /
predict.h includes from gimple-match-head.cc. The width >
MAX_FIXED_MODE_SIZE and width % 2 != 0 guards were
prerequisites for the can_mult_highpart_p fallback path, not
soundness checks. type_has_mode_precision_p subsumes them.
- Retarget the test scans from phiopt2 to forwprop1. Add
forwprop-46.c covering all four arm/comparison polarities.
- forwprop-45.c uses __UINT64_TYPE__ instead of unsigned long
and drops the lp64 restriction, covering the type > word_mode
regime on 32-bit targets.
- 2/2:
- Lower the high-part as (N)(((2N) op1 * (2N) op2) >> N).
pass_optimize_widening_mul rewrites this to WIDEN_MULT_EXPR /
MULT_HIGHPART_EXPR on supporting targets. Removes
can_mult_highpart_p queries from forwprop.
- Replace the can_mult_highpart_p prefilter in match_long_mul
with a targetm.scalar_mode_supported_p check on the 2N mode.
Test scans select on int128, mirroring the gate, instead of
lp64.
- Drop the m_long_mul_fold_p pass parameter and its passes.def
arguments. The long-mul fold runs in every forwprop instance.
Test scans retargeted from forwprop2 to forwprop1.
- Stop restricting forwprop-44.c to lp64. With the
can_mult_highpart_p gating gone, the fold is target-independent
and the test passes on ilp32 targets too.
Changes in v4:
- 1/2:
- Rebuild the guard with per-conjunct reasoning: require both
operands to be SSA names (drops degenerate one-side-constant
cases that fold trivially elsewhere), require the type to
have_mode_precision_p (excludes BITINT_TYPE precision != mode
and similar oddities), drop the explicit MAX_FIXED_MODE_SIZE
width cap (subsumed by have_mode_precision_p), and gate on the
flat optab via can_mult_highpart_p of the 2N mode.
- Retain BRANCH_COST >= 2: keep the flatten conditional on a
target where the branchless form is generally cheaper.
- Rewrite the cover letter to describe the gate as the
composition of these conjuncts and to clarify that the
transformation now only ever introduces a (mul_hi-like)
can_mult_highpart_p shape, not a libgcc multi-precision call.
- 2/2:
- Convert per-variant fold_mul_* functions into a
table-driven long_mul fold framework.
- Migrate each variant into a row in long_mul_table (six
HIGH_PART, six LOW_PART rows) keyed by (kind, extract).
- Add cross-summand consistency checks
(long_mul_check_consistency, long_mul_check_two_carries,
long_mul_check_low_plus_defer) shared across rows.
- Drop emission to a libgcc multi-precision call from RTL
expansion; defer to pass_optimize_widening_mul / RTL
expansion to pick native umul_highpart, a widening multiply, or
a synthesised sequence. Emission is gated on
can_mult_highpart_p.
- Structural redesign: per-variant fold_mul_* functions
consolidated into a single linearise + classify + table-lookup
framework (long_mul_table, match_long_mul,
long_mul_classify_summand, long_mul_check_consistency). Each
variant is now a row in long_mul_table; consistency checks are
shared across rows.
- Fast-fail prefilters in match_long_mul: LHS-type prefilter at
entry (no legitimate long-mul leaf has a signed / pointer /
float / odd-width type) and a can_mult_highpart_p probe before
the row loop to skip HIGH_PART rows on unsupported targets.
- Bound long_mul_linearize_chain mid-walk by LONG_MUL_MAX_SUMMANDS
so an overlong addition / BIT_IOR chain bails immediately rather
than after a full traversal.
- Emit a dump-file hint pointing at the shared inner addition when
long-mul folding rejects a chain because of a multi-used
intermediate (caching the partial sum into a single-use SSA
name normally enables the fold).
Changes in v3:
- Moved carry-diamond flattening from forwprop to match.pd,
replacing ~460 lines of C++ with a 17-line match.pd pattern.
- Two-carry test scans forwprop3 (the first forwprop after phiopt2,
since early phiopt restricts which tree codes are allowed).
- Set location for new sequences.
- Updated mul_carry_low pattern.
- Added the `mul_low_plus` pattern.
- Fixed formatting issues.
Changes in v2:
- Fixed the testcases by separating the high part's fold count for
32-bit and 64-bit targets.
gcc/match.pd | 25 ++
gcc/testsuite/gcc.dg/torture/long-mul-128.c | 105 ++++++++
.../gcc.dg/tree-ssa/long-mul-carry.c | 10 +-
.../gcc.dg/tree-ssa/long-mul-chain-cse-128.c | 52 ++++
.../tree-ssa/long-mul-chain-trunc-128.c | 80 ++++++
.../gcc.dg/tree-ssa/long-mul-ladder.c | 18 +-
.../gcc.target/arm/long-mul-thumb1-inline.c | 31 +++
gcc/testsuite/gcc.target/arm/long-mul-umull.c | 46 ++++
.../gcc.target/i386/widen_mult_high_chain.c | 32 +++
gcc/testsuite/lib/target-supports.exp | 20 ++
gcc/tree-ssa-forwprop.cc | 20 +-
gcc/tree-ssa-math-opts.cc | 244 +++++++++++++++++-
gcc/tree-ssa-math-opts.h | 2 +
13 files changed, 667 insertions(+), 18 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/torture/long-mul-128.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-cse-128.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-trunc-128.c
create mode 100644 gcc/testsuite/gcc.target/arm/long-mul-thumb1-inline.c
create mode 100644 gcc/testsuite/gcc.target/arm/long-mul-umull.c
create mode 100644 gcc/testsuite/gcc.target/i386/widen_mult_high_chain.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 063315d398c0..884ba608f385 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -12335,6 +12335,31 @@ and,
(mul_lo @mul_hilo0 INTEGER_CST@0)
(mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1))
(mul_lo @mul_hilo1 INTEGER_CST@0)))
+/* Long-multiply high-part emit chain produced by forwprop's recognizer:
+
+ (N) ((2N) op1 * (2N) op2) >> N
+
+ Captures the two N-bit operands. The outermost convert's result
+ type is unconstrained (conversion merging may retarget it).
+ Wide type must be unsigned; BITINT_TYPE is refused. */
+(match (long_mul_high_chain @0 @1)
+ (convert (rshift (mult:c@3 (convert @0) (convert @1)) INTEGER_CST@2))
+ (with {
+ tree narrow_type = TREE_TYPE (@0);
+ tree wide_type = TREE_TYPE (@3); }
+ (if (INTEGRAL_TYPE_P (narrow_type)
+ && TYPE_UNSIGNED (narrow_type)
+ && type_has_mode_precision_p (narrow_type)
+ && TYPE_PRECISION (narrow_type) >= 4
+ && (TYPE_PRECISION (narrow_type) & 1) == 0
+ && types_match (TREE_TYPE (@1), narrow_type)
+ && INTEGRAL_TYPE_P (wide_type)
+ && TYPE_UNSIGNED (wide_type)
+ && TREE_CODE (narrow_type) != BITINT_TYPE
+ && TREE_CODE (wide_type) != BITINT_TYPE
+ && TYPE_PRECISION (wide_type) == 2 * TYPE_PRECISION (narrow_type)
+ && tree_fits_uhwi_p (@2)
+ && tree_to_uhwi (@2) == TYPE_PRECISION (narrow_type)))))
#endif
/* Floatint point/integer comparison and integer->integer
diff --git a/gcc/testsuite/gcc.dg/torture/long-mul-128.c
b/gcc/testsuite/gcc.dg/torture/long-mul-128.c
new file mode 100644
index 000000000000..aa6f90707ec4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/long-mul-128.c
@@ -0,0 +1,105 @@
+/* { dg-do run { target int128 } } */
+
+/* Runtime correctness for the full 128-bit pipeline: forwprop folds the
+ longhand to (u256) x * (u256) y >> 128 and widening_mul lowers it back
+ to a 128-bit longhand. mulh_reference stays unfolded via volatiles. */
+
+typedef __uint128_t u128;
+
+/* The recognized longhand high-part multiply, shared by the callers below.
+ static inline so each caller inlines a copy, exposing its own chain to
+ forwprop. */
+static inline u128
+mulh_inline (u128 x, u128 y)
+{
+ u128 x_hi = x >> 64;
+ u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 y_hi = y >> 64;
+ u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 mulhilo = x_hi * y_lo;
+ u128 mullohi = x_lo * y_hi;
+ u128 cross_sum = mulhilo + mullohi;
+ u128 mullolo = x_lo * y_lo;
+ u128 shrlolo = mullolo >> 64;
+ u128 add_cross_sum = cross_sum + shrlolo;
+ int carry = add_cross_sum < mulhilo;
+ u128 cond = ((u128) carry << 64) + x_hi * y_hi;
+ return cond + (add_cross_sum >> 64);
+}
+
+/* Standalone folded instance (noipa keeps it distinct from the inline
+ copies), validated against the unfolded reference. */
+__attribute__((noipa)) u128
+mulh_folded (u128 x, u128 y)
+{
+ return mulh_inline (x, y);
+}
+
+__attribute__((noipa)) u128
+mulh_reference (u128 x, u128 y)
+{
+ volatile u128 x_hi = x >> 64;
+ volatile u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF;
+ volatile u128 y_hi = y >> 64;
+ volatile u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 mulhilo = x_hi * y_lo;
+ u128 mullohi = x_lo * y_hi;
+ u128 cross_sum = mulhilo + mullohi;
+ u128 mullolo = x_lo * y_lo;
+ u128 shrlolo = mullolo >> 64;
+ u128 add_cross_sum = cross_sum + shrlolo;
+ int carry = add_cross_sum < mulhilo;
+ u128 cond = ((u128) carry << 64) + x_hi * y_hi;
+ return cond + (add_cross_sum >> 64);
+}
+
+/* Two mulh calls sharing an operand: inlining exposes both chains and
+ VN CSEs the shared (u256) cast. Guard that lowering the first chain
+ does not free a cast the second still references. */
+__attribute__((noipa)) u128
+mulh_shared_xor (u128 x, u128 y, u128 z)
+{
+ return mulh_inline (x, y) ^ mulh_inline (x, z);
+}
+
+/* Squaring: VN CSEs the two (u256) casts of x, so lowering sees the
+ same stmt on both operand-cast slots. */
+__attribute__((noipa)) u128
+mulh_square (u128 x)
+{
+ return mulh_inline (x, x);
+}
+
+int
+main (void)
+{
+ static const u128 vals[] = {
+ 0,
+ 1,
+ (u128)0xFFFFFFFFFFFFFFFF, /* low half all-ones */
+ ((u128)1 << 64), /* 2^64 */
+ ((u128)1 << 127), /* high bit */
+ ~(u128)0, /* all-ones */
+ ((u128)0xDEADBEEFCAFEBABE << 64) | 0x0123456789ABCDEF,
+ ((u128)0x8000000000000001 << 64) | 0xFFFFFFFFFFFFFFFE,
+ };
+ const unsigned n = sizeof (vals) / sizeof (vals[0]);
+
+ for (unsigned i = 0; i < n; i++)
+ for (unsigned j = 0; j < n; j++)
+ {
+ u128 x = vals[i], y = vals[j];
+ if (mulh_folded (x, y) != mulh_reference (x, y))
+ __builtin_abort ();
+ for (unsigned k = 0; k < n; k++)
+ {
+ u128 z = vals[k];
+ u128 want = mulh_reference (x, y) ^ mulh_reference (x, z);
+ if (mulh_shared_xor (x, y, z) != want)
+ __builtin_abort ();
+ }
+ if (mulh_square (x) != mulh_reference (x, x))
+ __builtin_abort ();
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c
b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c
index b63e077e7aa4..304e8bfded15 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O3 -fdump-tree-forwprop-details" } */
+/* { dg-options "-O3 -fdump-tree-forwprop-details
-fdump-tree-widening_mul-details" } */
typedef __UINT32_TYPE__ uint32_t;
typedef __UINT64_TYPE__ uint64_t;
@@ -372,10 +372,14 @@ uint32_t mulh_carry_phi_neg (uint32_t x, uint32_t y)
/* On targets with __int128 support the two 128-bit highparts also
fold; without it they are elided by #ifdef and the count drops
by 2. */
-/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\."
10 "forwprop1" { target int128 } } } */
-/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\."
8 "forwprop1" { target { ! int128 } } } } */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\."
10 "forwprop1" { target { oi_mode && int128 } } } } */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\."
8 "forwprop1" { target { ! { oi_mode && int128 } } } } } */
/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\."
2 "forwprop2" } } */
/* { dg-final { scan-tree-dump-times "Long multiplication low part folded\\."
2 "forwprop1" } } */
/* Three PHI-form highparts, one per polarity pair (gt via mulh_carry_phi
and mulh_carry_long_phi, le via mulh_carry_phi_neg). */
/* { dg-final { scan-tree-dump-times "Long multiplication high part folded
\\(carry PHI\\)" 3 "forwprop1" } } */
+/* Only the two 128-bit (OImode) chains are lowered. sparc64 and hppa64
+ have OImode and __int128 but no native DImode high part, so their u64
+ chains lower too and the count would exceed 2; exclude them. */
+/* { dg-final { scan-tree-dump-times "Lowered long-mul high-part chain" 2
"widening_mul" { target { { oi_mode && int128 } && { ! { sparc*-*-* hppa*-*-* }
} } } } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-cse-128.c
b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-cse-128.c
new file mode 100644
index 000000000000..53b5eba9e2db
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-cse-128.c
@@ -0,0 +1,52 @@
+/* { dg-do compile { target { oi_mode && int128 } } } */
+/* { dg-options "-O3 -fdump-tree-forwprop1-details -fdump-tree-optimized" } */
+
+/* Two differently-spelled high-part longhands of the same 128x128
+ product both fold to the canonical (u256) x * (u256) y >> 128, so
+ value numbering proves them equal and the function folds to 0. */
+
+typedef __uint128_t u128;
+
+u128 both_spellings (u128 x, u128 y)
+{
+ /* Spelling 1: overflow-compare carry form. */
+ u128 x_hi = x >> 64;
+ u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 y_hi = y >> 64;
+ u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 mulhilo = x_hi * y_lo;
+ u128 mullohi = x_lo * y_hi;
+ u128 cross_sum = mulhilo + mullohi;
+ u128 mullolo = x_lo * y_lo;
+ u128 shrlolo = mullolo >> 64;
+ u128 add_cross_sum = cross_sum + shrlolo;
+ int carry = add_cross_sum < mulhilo;
+ u128 cond = ((u128) carry << 64) + x_hi * y_hi;
+ u128 h1 = cond + (add_cross_sum >> 64);
+
+ /* Spelling 2: ladder form. */
+ u128 a_lo = x & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 b_lo = y & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 a_hi = x >> 64;
+ u128 b_hi = y >> 64;
+ u128 t0 = b_lo * a_lo;
+ u128 t1 = b_lo * a_hi;
+ u128 t2 = b_hi * a_lo;
+ u128 t3 = b_hi * a_hi;
+ u128 t0_hi = t0 >> 64;
+ u128 u0 = t0_hi + t1;
+ u128 u0_lo = u0 & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 u0_hi = u0 >> 64;
+ u128 u1 = u0_lo + t2;
+ u128 u1_hi = u1 >> 64;
+ u128 u2 = u0_hi + t3;
+ u128 h2 = u2 + u1_hi;
+
+ return h1 ^ h2;
+}
+
+/* Both spellings are recognized. */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 2
"forwprop1" } } */
+/* Once canonical, VN proves them equal and the function folds to 0. */
+/* { dg-final { scan-tree-dump "return 0;" "optimized" } } */
+/* { dg-final { scan-tree-dump-not " \\* " "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-trunc-128.c
b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-trunc-128.c
new file mode 100644
index 000000000000..00f0338df5e2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-trunc-128.c
@@ -0,0 +1,80 @@
+/* { dg-do run { target int128 } } */
+/* { dg-options "-O3" } */
+
+/* A user cast of the recognized 128-bit high part merges with the
+ chain's final truncation, so widening_mul lowering sees an outermost
+ convert to a type narrower than 128 bits. Checks it builds the
+ longhand at narrow precision and converts to the lhs type. */
+
+typedef __uint128_t u128;
+typedef unsigned long long u64;
+typedef unsigned int u32;
+
+static inline u128
+mulh128 (u128 x, u128 y)
+{
+ u128 x_hi = x >> 64;
+ u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 y_hi = y >> 64;
+ u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 mulhilo = x_hi * y_lo;
+ u128 mullohi = x_lo * y_hi;
+ u128 cross_sum = mulhilo + mullohi;
+ u128 mullolo = x_lo * y_lo;
+ u128 shrlolo = mullolo >> 64;
+ u128 add_cross_sum = cross_sum + shrlolo;
+ int carry = add_cross_sum < mulhilo;
+ u128 cond = ((u128) carry << 64) + x_hi * y_hi;
+ return cond + (add_cross_sum >> 64);
+}
+
+__attribute__((noipa)) u64
+trunc64 (u128 x, u128 y) { return (u64) mulh128 (x, y); }
+
+__attribute__((noipa)) u32
+trunc32 (u128 x, u128 y) { return (u32) mulh128 (x, y); }
+
+__attribute__((noipa)) u128
+mulh_reference (u128 x, u128 y)
+{
+ volatile u128 x_hi = x >> 64;
+ volatile u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF;
+ volatile u128 y_hi = y >> 64;
+ volatile u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF;
+ u128 mulhilo = x_hi * y_lo;
+ u128 mullohi = x_lo * y_hi;
+ u128 cross_sum = mulhilo + mullohi;
+ u128 mullolo = x_lo * y_lo;
+ u128 shrlolo = mullolo >> 64;
+ u128 add_cross_sum = cross_sum + shrlolo;
+ int carry = add_cross_sum < mulhilo;
+ u128 cond = ((u128) carry << 64) + x_hi * y_hi;
+ return cond + (add_cross_sum >> 64);
+}
+
+int
+main (void)
+{
+ static const u128 vals[] = {
+ 0,
+ 1,
+ (u128)0xFFFFFFFFFFFFFFFF,
+ ((u128)1 << 64),
+ ((u128)1 << 127),
+ ~(u128)0,
+ ((u128)0xDEADBEEFCAFEBABE << 64) | 0x0123456789ABCDEF,
+ ((u128)0x8000000000000001 << 64) | 0xFFFFFFFFFFFFFFFE,
+ };
+ const unsigned n = sizeof (vals) / sizeof (vals[0]);
+
+ for (unsigned i = 0; i < n; i++)
+ for (unsigned j = 0; j < n; j++)
+ {
+ u128 ref = mulh_reference (vals[i], vals[j]);
+ if (trunc64 (vals[i], vals[j]) != (u64) ref)
+ __builtin_abort ();
+ if (trunc32 (vals[i], vals[j]) != (u32) ref)
+ __builtin_abort ();
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c
b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c
index 36eadd05aae1..7b7384d86455 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O3 -fdump-tree-forwprop-details" } */
+/* { dg-options "-O3 -fdump-tree-forwprop-details
-fdump-tree-widening_mul-details" } */
typedef __UINT32_TYPE__ uint32_t;
typedef __UINT64_TYPE__ uint64_t;
@@ -321,9 +321,13 @@ v2i32 mul_ladder_long_v2i32 (v2i32 x, v2i32 y)
return result;
}
-/* On LP64 the __int128-guarded highpart also folds; on non-LP64 it
- is elided by #ifdef and the count drops by 2. */
-/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 8
"forwprop1" { target lp64 } } } */
-/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 5
"forwprop1" { target { ! lp64 } } } } */
-/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 2
"forwprop2" } } */
-/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 2
"forwprop1" } } */
+/* On targets with __int128 support the 128-bit highpart also folds;
+ without it it is elided by #ifdef and the count drops by 2. */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\."
10 "forwprop1" { target { oi_mode && int128 } } } } */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\."
8 "forwprop1" { target { ! { oi_mode && int128 } } } } } */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\."
2 "forwprop2" } } */
+/* { dg-final { scan-tree-dump-times "Long multiplication low part folded\\."
2 "forwprop1" } } */
+/* Only the two 128-bit (OImode) chains are lowered. sparc64 and hppa64
+ have OImode and __int128 but no native DImode high part, so their u64
+ chains lower too and the count would exceed 2; exclude them. */
+/* { dg-final { scan-tree-dump-times "Lowered long-mul high-part chain" 2
"widening_mul" { target { { oi_mode && int128 } && { ! { sparc*-*-* hppa*-*-* }
} } } } } */
diff --git a/gcc/testsuite/gcc.target/arm/long-mul-thumb1-inline.c
b/gcc/testsuite/gcc.target/arm/long-mul-thumb1-inline.c
new file mode 100644
index 000000000000..56e3bd383d73
--- /dev/null
+++ b/gcc/testsuite/gcc.target/arm/long-mul-thumb1-inline.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target arm_thumb1_ok } */
+/* { dg-options "-O2 -mthumb -mcpu=cortex-m0 -fdump-tree-forwprop1-details
-fdump-tree-widening_mul-details" } */
+
+/* Thumb-1 (cortex-m0) has no umull and no DImode multiply, so a DImode
+ multiply would expand to the __aeabi_lmul libcall. widening_mul
+ re-synthesizes the recognized u32 high part from the HImode widening
+ multiply Thumb-1 does have, so no libcall is emitted. */
+
+typedef __UINT32_TYPE__ u32;
+
+u32 mulh32 (u32 x, u32 y)
+{
+ u32 x_hi = x >> 16, x_lo = x & 0xFFFF;
+ u32 y_hi = y >> 16, y_lo = y & 0xFFFF;
+ u32 mulhilo = x_hi * y_lo;
+ u32 mullohi = x_lo * y_hi;
+ u32 cross_sum = mulhilo + mullohi;
+ u32 mullolo = x_lo * y_lo;
+ u32 shrlolo = mullolo >> 16;
+ u32 acs = cross_sum + shrlolo;
+ int carry = acs < mulhilo;
+ u32 cond = ((u32) carry << 16) + x_hi * y_hi;
+ return cond + (acs >> 16);
+}
+
+/* Recognizer canonicalizes; widening_mul re-synthesizes the longhand. */
+/* { dg-final { scan-tree-dump "Long multiplication high part folded"
"forwprop1" } } */
+/* { dg-final { scan-tree-dump "Lowered long-mul high-part chain"
"widening_mul" } } */
+/* No multiplication libcall: the longhand stays inline. */
+/* { dg-final { scan-assembler-not "__aeabi_lmul" } } */
diff --git a/gcc/testsuite/gcc.target/arm/long-mul-umull.c
b/gcc/testsuite/gcc.target/arm/long-mul-umull.c
new file mode 100644
index 000000000000..7366e06bb789
--- /dev/null
+++ b/gcc/testsuite/gcc.target/arm/long-mul-umull.c
@@ -0,0 +1,46 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target arm_arm_ok } */
+/* { dg-options "-O2 -marm" } */
+
+/* With umull available, the recognizer folds the u32 high-part longhand
+ to a DImode multiply that becomes a single umull, while the u64
+ longhand becomes a TImode chain that widening_mul re-synthesizes as
+ four umull. No libcalls. */
+
+typedef __UINT64_TYPE__ u64;
+typedef __UINT32_TYPE__ u32;
+
+u32 mulh32 (u32 x, u32 y)
+{
+ u32 x_hi = x >> 16, x_lo = x & 0xFFFF;
+ u32 y_hi = y >> 16, y_lo = y & 0xFFFF;
+ u32 mulhilo = x_hi * y_lo;
+ u32 mullohi = x_lo * y_hi;
+ u32 cross_sum = mulhilo + mullohi;
+ u32 mullolo = x_lo * y_lo;
+ u32 shrlolo = mullolo >> 16;
+ u32 acs = cross_sum + shrlolo;
+ int carry = acs < mulhilo;
+ u32 cond = ((u32) carry << 16) + x_hi * y_hi;
+ return cond + (acs >> 16);
+}
+
+u64 mulh64 (u64 x, u64 y)
+{
+ u64 x_hi = x >> 32, x_lo = x & 0xFFFFFFFF;
+ u64 y_hi = y >> 32, y_lo = y & 0xFFFFFFFF;
+ u64 mulhilo = x_hi * y_lo;
+ u64 mullohi = x_lo * y_hi;
+ u64 cross_sum = mulhilo + mullohi;
+ u64 mullolo = x_lo * y_lo;
+ u64 shrlolo = mullolo >> 32;
+ u64 acs = cross_sum + shrlolo;
+ int carry = acs < mulhilo;
+ u64 cond = ((u64) carry << 32) + x_hi * y_hi;
+ return cond + (acs >> 32);
+}
+
+/* mulh32 collapses to one umull; mulh64 lowers to four. */
+/* { dg-final { scan-assembler-times "\tumull\t" 5 } } */
+/* { dg-final { scan-assembler-not "__aeabi_lmul" } } */
+/* { dg-final { scan-assembler-not "__multi3" } } */
diff --git a/gcc/testsuite/gcc.target/i386/widen_mult_high_chain.c
b/gcc/testsuite/gcc.target/i386/widen_mult_high_chain.c
new file mode 100644
index 000000000000..7cfa42c9b3a5
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/widen_mult_high_chain.c
@@ -0,0 +1,32 @@
+/* { dg-do compile { target { lp64 } } } */
+/* { dg-options "-O3" } */
+
+/* The high 128 bits of a 128 x 128 -> 256 product has no widening
+ multiply (no TI x TI -> OI) and no 256-bit expansion path. forwprop
+ folds the longhand to the canonical (uint256_t) a * (uint256_t) b
+ >> 128 shape, and widening_mul re-synthesizes it from four
+ 64 x 64 -> 128 multiplies (mulq). No __mulOI3 libcall. */
+
+__uint128_t
+mulh_carry_128 (__uint128_t x, __uint128_t y)
+{
+ __uint128_t x_hi = x >> 64;
+ __uint128_t x_lo = x & (__uint128_t) 0xFFFFFFFFFFFFFFFF;
+ __uint128_t y_hi = y >> 64;
+ __uint128_t y_lo = y & (__uint128_t) 0xFFFFFFFFFFFFFFFF;
+ __uint128_t mulhilo = x_hi * y_lo;
+ __uint128_t mullohi = x_lo * y_hi;
+ __uint128_t cross_sum = mulhilo + mullohi;
+ __uint128_t mullolo = x_lo * y_lo;
+ __uint128_t shrlolo = mullolo >> 64;
+ __uint128_t add_cross_sum = cross_sum + shrlolo;
+ int carry = add_cross_sum < mulhilo;
+ __uint128_t cond = ((__uint128_t) carry << 64) + x_hi * y_hi;
+ __uint128_t add = cond + (add_cross_sum >> 64);
+
+ return add;
+}
+
+/* { dg-final { scan-assembler-not "__multi3" } } */
+/* { dg-final { scan-assembler-not "__mulOI3" } } */
+/* { dg-final { scan-assembler-times "\tmulq" 4 } } */
diff --git a/gcc/testsuite/lib/target-supports.exp
b/gcc/testsuite/lib/target-supports.exp
index cab72c8a9e10..39e074c60073 100644
--- a/gcc/testsuite/lib/target-supports.exp
+++ b/gcc/testsuite/lib/target-supports.exp
@@ -4954,6 +4954,26 @@ proc check_effective_target_int128 { } {
}]
}
+# Return 1 if the target's mode table includes OImode (a 256-bit
+# scalar_int_mode). Enumerated from `INT_MODE (OI, 32)' declarations
+# in gcc/config/*/*-modes.def.
+
+proc check_effective_target_oi_mode { } {
+ return [check_cached_effective_target oi_mode {
+ expr { [istarget aarch64*-*-*]
+ || [istarget i?86-*-*]
+ || [istarget x86_64-*-*]
+ || [istarget riscv*-*-*]
+ || [istarget sparc*-*-*]
+ || [istarget s390*-*-*]
+ || [istarget loongarch*-*-*]
+ || [istarget arm*-*-*]
+ || [istarget alpha*-*-*]
+ || [istarget ia64-*-*]
+ || [istarget hppa*-*-*] }
+ }]
+}
+
# Return 1 if the target supports unsigned int->float conversion
#
diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
index 95f83e60f25d..8aeba51bf7f3 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -58,6 +58,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-ssa.h"
#include "gimple-range.h"
#include "tree-ssa-dce.h"
+#include "tree-ssa-math-opts.h"
/* This pass propagates the RHS of assignment statements into use
sites of the LHS of the assignment. It's basically a specialized
@@ -4463,15 +4464,20 @@ long_mul_classify_match (const vec<long_mul_summand>
&summands,
gimple *candidate_stmt,
tree *out_op0, tree *out_op1)
{
- /* 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. */
+ /* HIGH_PART rows emit a 2N-bit multiply that pass_optimize
+ _widening_mul consumes -- either via WIDEN_MULT_EXPR /
+ MULT_HIGHPART conversion when the target has a native 2N
+ multiply, or via lower_long_mul_high_chain when it does not.
+ LOW_PART rows emit a plain MULT_EXPR. Emission needs a 2N
+ mode to exist in the mode table AND the widening_mul pass to
+ be active: without the pass, the emit could reach RTL expand
+ as an unexpandable 2N multiply (e.g. OImode). BITINT_TYPE is
+ refused -- the long_mul_high_chain atom excludes it. */
scalar_int_mode mode, wide_mode;
bool can_emit_high
- = is_a <scalar_int_mode> (TYPE_MODE (lhs_type), &mode)
+ = optimize_widening_mul_active_p ()
+ && TREE_CODE (lhs_type) != BITINT_TYPE
+ && 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)
diff --git a/gcc/tree-ssa-math-opts.cc b/gcc/tree-ssa-math-opts.cc
index c4a1d7bcf0bd..fb0e068798d6 100644
--- a/gcc/tree-ssa-math-opts.cc
+++ b/gcc/tree-ssa-math-opts.cc
@@ -6541,6 +6541,238 @@ optimize_spaceship (gcond *stmt)
}
+/* Long-multiply inverse-lowering helper.
+
+ The forwprop long-multiply recognizer canonicalizes a hand-written
+ longhand high-part multiply into a cast+mult+shift+cast chain
+ `(N) ((2N) a * (2N) b) >> N'. When the target lacks an expansion
+ path for the wide form, `lower_long_mul_high_chain' resynthesizes
+ the longhand at narrow precision via `build_long_mul_partials'. */
+
+/* Test whether the target supports an (HALF)-by-(HALF)->NARROW unsigned
+ widening multiply. Returns true on success, with the half-width
+ scalar int mode placed in *HALF_MODE. */
+
+static bool
+can_widen_to_narrow_p (scalar_int_mode narrow_mode, unsigned int half_width,
+ scalar_int_mode *half_mode)
+{
+ if (!int_mode_for_size (half_width, 0).exists (half_mode))
+ return false;
+ return convert_optab_handler (umul_widen_optab, narrow_mode, *half_mode)
+ != CODE_FOR_nothing;
+}
+
+/* Append to *SEQ the operand split and partial products for an unsigned
+ long multiply of OP1 by OP2 at the precision of TREE_TYPE (OP1).
+ HALF_TYPE is the (N/2)-bit unsigned type; HALF_AMT is the integer-typed
+ shift constant equal to N/2.
+
+ Outputs the four partial products via *LOLO, *HILO, *LOHI, *HIHI.
+
+ USE_WIDEN selects the partial-product form:
+ true - cast halves to HALF_TYPE and use WIDEN_MULT_EXPR (needs
+ an (N/2)-by-(N/2)->N widening multiply optab).
+ false - mask/shift halves within the N-bit accumulator and use
+ plain MULT_EXPR; the halves fit in N/2 bits so the N-bit
+ low product is exact. */
+
+static void
+build_long_mul_partials (gimple_seq *seq, location_t loc, tree op1, tree op2,
+ tree half_type, tree half_amt,
+ tree *lolo, tree *hilo, tree *lohi, tree *hihi,
+ bool use_widen)
+{
+ tree acc_type = TREE_TYPE (op1);
+ tree op1_hi = gimple_build (seq, loc, RSHIFT_EXPR, acc_type, op1, half_amt);
+ tree op2_hi = gimple_build (seq, loc, RSHIFT_EXPR, acc_type, op2, half_amt);
+ tree op1_lo, op2_lo;
+ tree_code mul_code;
+
+ if (use_widen)
+ {
+ op1_lo = gimple_build (seq, loc, NOP_EXPR, half_type, op1);
+ op2_lo = gimple_build (seq, loc, NOP_EXPR, half_type, op2);
+ op1_hi = gimple_build (seq, loc, NOP_EXPR, half_type, op1_hi);
+ op2_hi = gimple_build (seq, loc, NOP_EXPR, half_type, op2_hi);
+ mul_code = WIDEN_MULT_EXPR;
+ }
+ else
+ {
+ tree mask = wide_int_to_tree (acc_type,
+ wi::mask (TYPE_PRECISION (half_type), false,
+ TYPE_PRECISION (acc_type)));
+ op1_lo = gimple_build (seq, loc, BIT_AND_EXPR, acc_type, op1, mask);
+ op2_lo = gimple_build (seq, loc, BIT_AND_EXPR, acc_type, op2, mask);
+ mul_code = MULT_EXPR;
+ }
+
+ *lolo = gimple_build (seq, loc, mul_code, acc_type, op1_lo, op2_lo);
+ *hilo = gimple_build (seq, loc, mul_code, acc_type, op1_hi, op2_lo);
+ *lohi = gimple_build (seq, loc, mul_code, acc_type, op1_lo, op2_hi);
+ *hihi = gimple_build (seq, loc, mul_code, acc_type, op1_hi, op2_hi);
+}
+
+/* Match.pd recognizer for the long-multiply recognizer's high-part
+ emit chain. */
+
+extern bool gimple_long_mul_high_chain (tree, tree *, tree (*)(tree));
+
+/* Rewrite the `long_mul_high_chain' whose tail is the statement at GSI
+
+ wide_a = (T_2N) op1
+ wide_b = (T_2N) op2
+ wide_prod = wide_a * wide_b
+ hi = wide_prod >> N
+ lhs = (convert) hi
+
+ to a longhand high-part synthesis at T_N precision via
+ `build_long_mul_partials'. Never materializes T_2N in gimple, so it
+ covers cases where the 2N mode has no expansion path (e.g. the high
+ 128 bits of a 128x128 product where 2N=OImode). Returns true on a
+ rewrite. */
+
+static bool
+lower_long_mul_high_chain (gimple_stmt_iterator *gsi)
+{
+ gimple *trunc_stmt = gsi_stmt (*gsi);
+ if (!is_gimple_assign (trunc_stmt))
+ return false;
+
+ tree narrow_lhs = gimple_assign_lhs (trunc_stmt);
+ tree ops[2];
+ if (!gimple_long_mul_high_chain (narrow_lhs, ops, NULL))
+ return false;
+ tree op1 = ops[0];
+ tree op2 = ops[1];
+
+ /* match.pd guarantees an integral, unsigned, mode-precision narrow
+ type with even precision >= 4 -- safe to drop straight into a
+ scalar_int_mode. */
+ tree narrow_type = TREE_TYPE (op1);
+ scalar_int_mode narrow_mode
+ = as_a <scalar_int_mode> (TYPE_MODE (narrow_type));
+
+ /* Lower only when the target cannot form the N-bit high part itself. */
+ if (can_mult_highpart_p (narrow_mode, true))
+ return false;
+
+ unsigned int half_width = GET_MODE_PRECISION (narrow_mode) / 2;
+
+ /* Prefer widening partials; fall back to plain MULT_EXPR when the
+ target lacks the widen optab. See `build_long_mul_partials'. */
+ scalar_int_mode half_mode;
+ bool use_widen = can_widen_to_narrow_p (narrow_mode, half_width, &half_mode);
+
+ /* Synthesize the high-part longhand at narrow precision:
+
+ a = a_h * 2^(N/2) + a_l (a_h, a_l are (N/2)-bit halves)
+ b = b_h * 2^(N/2) + b_l
+
+ lolo = a_l * b_l (N-bit result of an (N/2)*(N/2) product)
+ hilo = a_h * b_l
+ lohi = a_l * b_h
+ hihi = a_h * b_h
+
+ cross_sum = hilo + lohi
+ cross_carry = ((cross_sum < hilo) ? 1 : 0) << (N/2)
+ low_accum = (lolo >> (N/2)) + (cross_sum & mask)
+
+ result = hihi + (cross_sum >> (N/2)) + (low_accum >> (N/2))
+ + cross_carry. */
+ tree half_type = build_nonstandard_integer_type (half_width, 1);
+ location_t loc = gimple_location (trunc_stmt);
+ gimple_seq seq = NULL;
+ tree half_amt = build_int_cst (integer_type_node, half_width);
+ tree half_mask = wide_int_to_tree (narrow_type,
+ wi::mask (half_width, false,
+ TYPE_PRECISION (narrow_type)));
+
+ tree lolo, hilo, lohi, hihi;
+ build_long_mul_partials (&seq, loc, op1, op2, half_type, half_amt,
+ &lolo, &hilo, &lohi, &hihi, use_widen);
+
+ tree cross_sum = gimple_build (&seq, loc, PLUS_EXPR, narrow_type,
+ hilo, lohi);
+ tree cross_lt = gimple_build (&seq, loc, LT_EXPR, boolean_type_node,
+ cross_sum, hilo);
+ tree cross_lt_n = gimple_build (&seq, loc, NOP_EXPR, narrow_type,
+ cross_lt);
+ tree cross_carry = gimple_build (&seq, loc, LSHIFT_EXPR, narrow_type,
+ cross_lt_n, half_amt);
+
+ tree lolo_hi = gimple_build (&seq, loc, RSHIFT_EXPR, narrow_type,
+ lolo, half_amt);
+ tree cross_lo = gimple_build (&seq, loc, BIT_AND_EXPR, narrow_type,
+ cross_sum, half_mask);
+ tree low_accum = gimple_build (&seq, loc, PLUS_EXPR, narrow_type,
+ lolo_hi, cross_lo);
+ tree low_accum_hi = gimple_build (&seq, loc, RSHIFT_EXPR, narrow_type,
+ low_accum, half_amt);
+ tree cross_hi = gimple_build (&seq, loc, RSHIFT_EXPR, narrow_type,
+ cross_sum, half_amt);
+
+ tree t1 = gimple_build (&seq, loc, PLUS_EXPR, narrow_type, hihi, cross_hi);
+ tree t2 = gimple_build (&seq, loc, PLUS_EXPR, narrow_type, t1, low_accum_hi);
+
+ /* Conversion merging may have retargeted the outer convert to any
+ integral type, so build at narrow precision and convert once
+ (the high part is < 2^N, so zero-extending or truncating is
+ value-preserving). */
+ gimple *result_stmt;
+ tree lhs_type = TREE_TYPE (narrow_lhs);
+ if (useless_type_conversion_p (lhs_type, narrow_type))
+ result_stmt = gimple_build_assign (narrow_lhs, PLUS_EXPR, t2,
+ cross_carry);
+ else
+ {
+ tree res = gimple_build (&seq, loc, PLUS_EXPR, narrow_type, t2,
+ cross_carry);
+ result_stmt = gimple_build_assign (narrow_lhs, NOP_EXPR, res);
+ }
+ gimple_set_location (result_stmt, loc);
+ gimple_seq_add_stmt (&seq, result_stmt);
+
+ /* Delete each dead upstream stmt now -- LTRANS runs no DCE between
+ widening_mul and expand, and a dead 2N MULT would abort expand_mult.
+ VN can collapse the two inner (2N) casts into one stmt (x*x, or
+ cross-chain sharing between sibling chains), so guard removal on
+ the stmt still being in a BB before checking has_zero_uses. */
+ gimple *shift_stmt
+ = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (trunc_stmt));
+ gimple *mult_stmt
+ = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (shift_stmt));
+ gimple *cast_a_stmt
+ = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (mult_stmt));
+ gimple *cast_b_stmt
+ = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (mult_stmt));
+
+ gsi_replace_with_seq (gsi, seq, true);
+
+ for (gimple *s : { shift_stmt, mult_stmt, cast_a_stmt, cast_b_stmt })
+ if (gimple_bb (s) && has_zero_uses (gimple_assign_lhs (s)))
+ {
+ gimple_stmt_iterator dgsi = gsi_for_stmt (s);
+ gsi_remove (&dgsi, true);
+ release_defs (s);
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Lowered long-mul high-part chain.\n");
+ return true;
+}
+
+/* True when pass_optimize_widening_mul will run. Shared with the
+ forwprop long-multiply recognizer so its wide-chain emit stays
+ paired with the lowering that rescues an unsupported 2N shape.
+ -fdisable-tree-widening_mul is not observed. */
+
+bool
+optimize_widening_mul_active_p (void)
+{
+ return flag_expensive_optimizations && optimize;
+}
+
/* Find integer multiplications where the operands are extended from
smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR
or MULT_HIGHPART_EXPR where appropriate. */
@@ -6570,7 +6802,7 @@ public:
/* opt_pass methods: */
bool gate (function *) final override
{
- return flag_expensive_optimizations && optimize;
+ return optimize_widening_mul_active_p ();
}
unsigned int execute (function *) final override;
@@ -6704,6 +6936,16 @@ math_opts_dom_walker::after_dom_children (basic_block bb)
match_unsigned_saturation_mul (&gsi, as_a<gassign *> (stmt));
match_unsigned_saturation_trunc (&gsi, as_a<gassign *> (stmt));
match_saturation_add_with_assign (&gsi, as_a<gassign *> (stmt));
+ /* fall-through */
+ case CONVERT_EXPR:
+ /* The long-multiply recognizer's high-part emit ends in an
+ outer convert. If the trailing cast+mult+shift+cast
+ chain has no expansion strategy at the 2N width, lower
+ the whole chain to a longhand high-part at narrow
+ precision. */
+ if (gsi_stmt (gsi) == stmt
+ && lower_long_mul_high_chain (&gsi))
+ continue;
break;
default:;
diff --git a/gcc/tree-ssa-math-opts.h b/gcc/tree-ssa-math-opts.h
index f750b52b5936..5de1697ff678 100644
--- a/gcc/tree-ssa-math-opts.h
+++ b/gcc/tree-ssa-math-opts.h
@@ -23,4 +23,6 @@ along with GCC; see the file COPYING3. If not see
extern tree powi_as_mults (gimple_stmt_iterator *, location_t,
tree, HOST_WIDE_INT);
+extern bool optimize_widening_mul_active_p (void);
+
#endif /* GCC_TREE_SSA_MATH_OPTS_H */
--
2.55.0
