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).
An operand of the matched multiply need not itself fit N bits: the
atom binds each one through an optional convert, so a shared wide
product or a sign-extended cast can appear there. Truncating such an
operand would drop its high input bits, so `long_mul_split_operand`
splits it into N-bit halves instead and `combine_long_mul_halves`
assembles the high part from them. The split recurses through a
chained wide product, reads a widening cast's halves from its narrower
source, and resolves a value shifted down by N to the high half of what
was shifted, so no 2N multiply or shift is ever emitted. An
operand that provably fits N bits yields a zero high half, folding the
combine back to a plain N-bit high part.
The split covers a 2N product reached through the chain's operands, but
not one that other statements also read: those uses keep it live, so it
survives the rewrite and reaches expansion as a 2N multiply the target
cannot expand. When every use of such a product takes only its low N
bits, `narrow_long_mul_low_half` rewrites it to (2N) ((N) a * (N) b),
which preserves each use because the low half of a product depends only
on the low halves of its operands. It runs on every MULT_EXPR the pass
walks, not just on a lowered chain, and `narrow_long_mul_operands`
re-visits the operands of a multiply just narrowed or lowered, so a
chained product collapses from the outside in. The gate stays
target-aware: where a widening or high-part multiply exists the multiply
is left to convert_mult_to_widen / convert_mult_to_highpart.
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. The
predicate also returns false for optimize_debug: the -Og pipeline does
not contain pass_optimize_widening_mul at all, so without that, the
recognizer would emit a wide chain with no lowering pass behind it and
the unexpandable multiply would reach RTL expansion.
gcc/ChangeLog:
* match.pd (long_mul_high_chain): New atom for the chain shape.
* tree-ssa-forwprop.cc (long_mul_classify_match): Gate the
HIGH_PART wide-chain emit on optimize_widening_mul_active_p.
* tree-ssa-math-opts.cc (can_widen_to_narrow_p): New.
(build_long_mul_partials): New; emits the four partial products
using widening or plain multiplies.
(emit_long_mul_highpart): New; the high N bits of an N-bit
product, as a longhand over (N/2)-bit partials.
(combine_long_mul_halves): New; the high N bits of a product of
two 2N-bit values given as N-bit halves.
(long_mul_op_fits_p): New; true when an operand is provably
representable in narrow_prec unsigned bits.
(long_mul_split_operand): New; splits an operand into N-bit
halves using only N-bit operations.
(long_mul_only_low_half_used_p): New.
(narrow_long_mul_low_half): New; narrow a 2N low-half-only mult
the target cannot expand to an N-bit mult.
(narrow_long_mul_operands): New; recurse into chained wide
products after a narrowing/lowering.
(gimple_long_mul_high_chain): Declare.
(lower_long_mul_high_chain): New; lowers the high-part chain to a
longhand at narrow precision. Split each operand into N-bit
halves and combine, handling an operand wider than narrow_prec
instead of rejecting it. Narrow or drop the residual 2N mult via
the helpers and recurse into its operands.
(optimize_widening_mul_active_p): New; shared gate used by
pass_optimize_widening_mul::gate and by the forwprop long-multiply
recognizer. Return false when optimize_debug.
(math_opts_dom_walker::after_dom_children): Dispatch to
lower_long_mul_high_chain on the outer convert. Run
narrow_long_mul_low_half on MULT_EXPR before the widen/fma
conversion attempts.
* tree-ssa-math-opts.h (optimize_widening_mul_active_p): Declare.
gcc/testsuite/ChangeLog:
* gcc.dg/torture/long-mul-64-run.c: Add near-miss variants of the
idiom, cross-checked against their literal meaning.
* gcc.dg/tree-ssa/long-mul-carry.c: Add scans for the high-part
chain lowering and its dump message. Exclude sparc/hppa from
the chain-lowering scan.
* gcc.dg/tree-ssa/long-mul-ladder.c: Likewise.
* lib/target-supports.exp (check_effective_target_oi_mode): New;
enumerates targets whose mode table declares OImode.
* gcc.dg/long-mul-128-Og.c: New test.
* gcc.dg/torture/long-mul-128.c: New test.
* gcc.dg/tree-ssa/long-mul-chain-cse-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.
Co-authored-by: Philipp Tomsich <[email protected]>
Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---
Changes in v8:
- 1/7 starts matching only at chain ends and sets aside leaves that are
not long-multiply summands, re-applying them on top of the fold. The
two go together. Either alone regresses a foldable chain. Now folds
shapes such as `acc += mulh (x, y)`.
- 1/7 factors out build_mul_high_seq, long_mul_classify_match and
long_mul_classify_chain for the PHI entry in 6/7 to reuse, and takes
a gassign * in the matcher and the emitters.
- The long_mul_high_chain atom binds each mult operand through
`(convert? @X)`, so a PRE-hoisted cast into a PHI still matches. An
operand wider than N is now split into N-bit halves rather than
rejected, which previously left the 2N multiply for expansion.
- optimize_widening_mul_active_p returns false for optimize_debug: -Og
runs no widening_mul pass to lower the emitted chain, so the
unexpandable multiply reached expand.
- Add narrow_long_mul_low_half: when a 2N `res = a * b` has uses only in
its low N bits and the target cannot expand 2N, rewrite it to
`res = (2N) ((N)a * (N)b)`. The split-based lowering covers a chained
2N operand by recursing into it, but not a shared 2N product left with
only low-half uses, which is what ICEs libgo's p521_fiat64.go on ARM32.
- long_mul_split_operand resolves a 2N value shifted down by N to the
high half of what was shifted, instead of truncating the shift. The
truncation read the shift and so kept a chained product live past its
own lowering, aborting expand_mult on a target without a 2N multiply.
Reachable from Go on ARM32 as bits.Mul64 (bits.Mul64 (x, y), z), where
the unexpandable mode is TImode, and on aarch64 and x86-64 from a
chained __int128 longhand, where it is OImode.
- New coverage: near misses of the idiom, checked at runtime against
their literal meaning, a signed narrow-cast operand on Thumb-1, and
chained longhands through both halves on ARM32.
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 | 21 +
gcc/testsuite/gcc.dg/long-mul-128-Og.c | 26 +
gcc/testsuite/gcc.dg/torture/long-mul-128.c | 121 +++++
.../gcc.dg/torture/long-mul-64-run.c | 111 +++-
.../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 | 10 +-
.../gcc.target/arm/long-mul-thumb1-inline.c | 47 ++
gcc/testsuite/gcc.target/arm/long-mul-umull.c | 73 +++
.../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 | 492 +++++++++++++++++-
gcc/tree-ssa-math-opts.h | 2 +
15 files changed, 1098 insertions(+), 19 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/long-mul-128-Og.c
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 a0566788e28c..7d3792f26905 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -12358,6 +12358,27 @@ 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
+
+ `(convert? @X)` accepts a bare operand (PRE may hoist the (T_2N) cast
+ out into a PHI on a shared slot). The lowering splits an operand
+ wider than T_N into T_N halves rather than truncating it. Wide type
+ must be unsigned mode-precision integer of even width; 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 wide_type = TREE_TYPE (@3); }
+ (if (INTEGRAL_TYPE_P (wide_type)
+ && TYPE_UNSIGNED (wide_type)
+ && type_has_mode_precision_p (wide_type)
+ && TREE_CODE (wide_type) != BITINT_TYPE
+ && TYPE_PRECISION (wide_type) >= 8
+ && (TYPE_PRECISION (wide_type) & 3) == 0
+ && tree_fits_uhwi_p (@2)
+ && tree_to_uhwi (@2) * 2 == TYPE_PRECISION (wide_type)))))
#endif
/* Floatint point/integer comparison and integer->integer
diff --git a/gcc/testsuite/gcc.dg/long-mul-128-Og.c
b/gcc/testsuite/gcc.dg/long-mul-128-Og.c
new file mode 100644
index 000000000000..3a9bd703c116
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/long-mul-128-Og.c
@@ -0,0 +1,26 @@
+/* { dg-do compile { target int128 } } */
+/* { dg-options "-Og -fexpensive-optimizations" } */
+
+/* The -Og pipeline does not run pass_optimize_widening_mul, so the
+ long-multiply fold must not emit a 2N wide-multiply chain here:
+ nothing would lower it before expansion. */
+
+typedef __uint128_t u128;
+
+u128
+mulh (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);
+}
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..1be4dec1141c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/long-mul-128.c
@@ -0,0 +1,121 @@
+/* { 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);
+}
+
+/* One chain's high half feeding the next, first high part also live. After
+ recognition the second chain multiplies by the first product shifted down;
+ truncating that shift would leave the product live past its own lowering.
*/
+__attribute__((noipa)) u128
+mulh_chain_high (u128 x, u128 y, u128 z, u128 *first)
+{
+ u128 h1 = mulh_inline (x, y);
+ *first = h1;
+ return mulh_inline (h1, 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 ();
+ u128 first = 0;
+ u128 h1 = mulh_reference (x, y);
+ if (mulh_chain_high (x, y, z, &first) != mulh_reference (h1, z)
+ || first != h1)
+ __builtin_abort ();
+ }
+ if (mulh_square (x) != mulh_reference (x, x))
+ __builtin_abort ();
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/torture/long-mul-64-run.c
b/gcc/testsuite/gcc.dg/torture/long-mul-64-run.c
index 8546573d91cf..0824f453630a 100644
--- a/gcc/testsuite/gcc.dg/torture/long-mul-64-run.c
+++ b/gcc/testsuite/gcc.dg/torture/long-mul-64-run.c
@@ -1,9 +1,11 @@
/* { 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. */
+ idiom. Two groups: shapes that must fold, checked against a 128-bit
+ reference multiply, and near misses that must not fold (each violates
+ one recognizer guard: low mask value, carry shift tie, cross-half
+ orientation, operand consistency), checked against their literal
+ meaning computed behind volatiles. Either way a misfold aborts. */
typedef __UINT64_TYPE__ uint64_t;
typedef unsigned __int128 uint128_t;
@@ -23,7 +25,8 @@ mulh_good (uint64_t x, uint64_t y)
return xh * yh + (low_sum >> 32) + carry;
}
-/* Extra addend appended after the full chain. */
+/* The idiom with an extra addend appended after the full chain: the
+ folded form must keep the addend on top of the wide multiply. */
__attribute__((noipa)) uint64_t
mulh_acc (uint64_t x, uint64_t y, uint64_t acc)
{
@@ -39,7 +42,8 @@ mulh_acc (uint64_t x, uint64_t y, uint64_t acc)
return xh * yh + (low_sum >> 32) + carry + acc;
}
-/* Extra addend interleaved into the middle of the chain. */
+/* Same, with the 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)
{
@@ -55,6 +59,95 @@ mulh_acc_interleaved (uint64_t x, uint64_t y, uint64_t acc)
return ((xh * yh + acc) + (low_sum >> 32)) + carry;
}
+/* Wrong low mask (0xFFFF, not the half mask). */
+__attribute__((noipa)) uint64_t
+mulh_wrong_mask (uint64_t x, uint64_t y)
+{
+ uint64_t xl = x & 0xFFFF, xh = x >> 32;
+ uint64_t yl = y & 0xFFFF, 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;
+}
+
+/* Wrong carry position (<< 16, not the half width). */
+__attribute__((noipa)) uint64_t
+mulh_wrong_carry_shift (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) << 16;
+ return xh * yh + (low_sum >> 32) + carry;
+}
+
+/* Doubled cross term (hilo + hilo, same orientation). */
+__attribute__((noipa)) uint64_t
+mulh_doubled_cross (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 cross = hilo + hilo;
+ 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;
+}
+
+/* Third operand sneaks into one cross term. */
+__attribute__((noipa)) uint64_t
+mulh_mixed_ops (uint64_t x, uint64_t y, uint64_t z)
+{
+ uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32;
+ uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32;
+ uint64_t zh = z >> 32;
+ uint64_t hilo = xh * yl;
+ uint64_t lohi = xl * zh;
+ 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;
+}
+
+/* What each (mis)shaped source literally means, computed behind
+ volatiles so no folding applies. */
+__attribute__((noipa)) uint64_t
+ref_eval (uint64_t x, uint64_t y, uint64_t z, int variant)
+{
+ volatile uint64_t vx = x, vy = y, vz = z;
+ uint64_t xh = vx >> 32, yl0 = vy & 0xFFFFFFFF, yh = vy >> 32, zh = vz >> 32;
+ uint64_t xl, yl;
+ switch (variant)
+ {
+ case 1: xl = vx & 0xFFFF; yl = vy & 0xFFFF; break;
+ default: xl = vx & 0xFFFFFFFF; yl = yl0; break;
+ }
+ uint64_t hilo = xh * yl;
+ uint64_t lohi;
+ switch (variant)
+ {
+ case 3: lohi = hilo; break;
+ case 4: lohi = xl * zh; break;
+ default: lohi = xl * yh; break;
+ }
+ uint64_t cross = hilo + lohi;
+ uint64_t lolo = xl * yl;
+ uint64_t low_sum = cross + (lolo >> 32);
+ uint64_t shift = (variant == 2) ? 16 : 32;
+ uint64_t carry = (uint64_t) (hilo > low_sum) << shift;
+ return xh * yh + (low_sum >> 32) + carry;
+}
+
int
main (void)
{
@@ -74,6 +167,14 @@ main (void)
__builtin_abort ();
if (mulh_acc_interleaved (x, y, z) != hi + z)
__builtin_abort ();
+ if (mulh_wrong_mask (x, y) != ref_eval (x, y, z, 1))
+ __builtin_abort ();
+ if (mulh_wrong_carry_shift (x, y) != ref_eval (x, y, z, 2))
+ __builtin_abort ();
+ if (mulh_doubled_cross (x, y) != ref_eval (x, y, z, 3))
+ __builtin_abort ();
+ if (mulh_mixed_ops (x, y, z) != ref_eval (x, y, z, 4))
+ __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 657d118cb704..99165656918f 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 16bcd3fdab47..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;
@@ -323,7 +323,11 @@ v2i32 mul_ladder_long_v2i32 (v2i32 x, v2i32 y)
/* 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 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" } } */
+/* 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..f36b4739d3a6
--- /dev/null
+++ b/gcc/testsuite/gcc.target/arm/long-mul-thumb1-inline.c
@@ -0,0 +1,47 @@
+/* { 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 __INT32_TYPE__ i32;
+typedef __UINT32_TYPE__ u32;
+typedef __UINT64_TYPE__ u64;
+
+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);
+}
+
+/* Signed operands sign-extended into the unsigned wide type. The atom
+ accepts them via `(convert? @X)'; long_mul_split_operand must sign-
+ extend the narrow operand into the high half (arithmetic shift by
+ N-1 on the signed narrow) -- a broken sign-extend branch would
+ zero the high and miscompile any negative input. */
+u32 mulhs_split (i32 a, i32 b)
+{
+ return (u32) (((u64) a * (u64) b) >> 32);
+}
+
+/* Recognizer canonicalizes; widening_mul re-synthesizes the longhand. */
+/* { dg-final { scan-tree-dump "Long multiplication high part folded"
"forwprop1" } } */
+/* { dg-final { scan-tree-dump-times "Lowered long-mul high-part chain" 2
"widening_mul" } } */
+/* No multiplication libcall: the longhand stays inline. */
+/* { dg-final { scan-assembler-not "__aeabi_lmul" } } */
+/* Split's signed branch emits an arithmetic shift by narrow_prec-1 on
+ each signed narrow source of mulhs_split -- once per operand,
+ absent when broken. */
+/* { dg-final { scan-tree-dump-times "\\(D\\) >> 31" 2 "widening_mul" } } */
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..721b640f7b70
--- /dev/null
+++ b/gcc/testsuite/gcc.target/arm/long-mul-umull.c
@@ -0,0 +1,73 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target arm_arm_ok } */
+/* { dg-options "-O2 -marm -fdump-tree-widening_mul-details" } */
+
+/* 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);
+}
+
+/* Two longhands chained through the low half, with the first high part also
+ live. After recognition the second chain reads its operand off the first
+ product as a masked low half, so lowering both leaves a live TImode
+ multiply the target cannot expand. */
+
+u64 chain_low (u64 a, u64 b, u64 c, u64 *hi1)
+{
+ *hi1 = mulh64 (a, b);
+ return mulh64 (a * b, c);
+}
+
+/* The same through the high half: after recognition the second chain
+ multiplies by the first product shifted down, and truncating that shift
+ would leave the product live instead. */
+
+u64 chain_high (u64 a, u64 b, u64 c, u64 *hi1)
+{
+ u64 h1 = mulh64 (a, b);
+ *hi1 = h1;
+ return mulh64 (h1, c);
+}
+
+/* mulh32 collapses to one umull and mulh64 lowers to four; chain_low and
+ chain_high inline two longhands each, for nine and eight. */
+/* { dg-final { scan-assembler-times "\tumull\t" 22 } } */
+/* One lowering in mulh64 and two in each chain. mulh32 contributes none:
+ its DImode multiply is converted to a widening multiply instead. */
+/* { dg-final { scan-tree-dump-times "Lowered long-mul high-part chain" 5
"widening_mul" } } */
+/* { dg-final { scan-tree-dump "Narrowed low-half-only long multiply"
"widening_mul" } } */
+/* { 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 f43197779517..929ba0ef86c1 100644
--- a/gcc/testsuite/lib/target-supports.exp
+++ b/gcc/testsuite/lib/target-supports.exp
@@ -4979,6 +4979,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 919e7e2402f3..800a2f93cebc 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
@@ -4502,15 +4503,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..60508d57cd04 100644
--- a/gcc/tree-ssa-math-opts.cc
+++ b/gcc/tree-ssa-math-opts.cc
@@ -6541,6 +6541,484 @@ 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);
+}
+
+/* Emit into *SEQ the high N bits of the unsigned product A * B, where A and B
+ are NARROW_TYPE (N-bit) values, as a longhand over (N/2)-bit partials.
+ Returns the high-part SSA. */
+
+static tree
+emit_long_mul_highpart (gimple_seq *seq, location_t loc, tree a, tree b,
+ tree narrow_type)
+{
+ scalar_int_mode narrow_mode
+ = as_a <scalar_int_mode> (TYPE_MODE (narrow_type));
+ unsigned int half_width = GET_MODE_PRECISION (narrow_mode) / 2;
+ /* Prefer (N/2)-by-(N/2)->N 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);
+ tree half_type = build_nonstandard_integer_type (half_width, 1);
+ 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, a, b, 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);
+ return gimple_build (seq, loc, PLUS_EXPR, narrow_type, t2, cross_carry);
+}
+
+/* Emit into *SEQ the high N bits (NARROW_TYPE) of the unsigned product of two
+ 2N-bit values given as N-bit halves, x = L1 + H1*2^N and y = L2 + H2*2^N:
+ the high half of x*y is the high N bits of L1*L2, plus H1*L2 and L1*H2, all
+ mod 2^N. */
+
+static tree
+combine_long_mul_halves (gimple_seq *seq, location_t loc, tree l1, tree h1,
+ tree l2, tree h2, tree narrow_type)
+{
+ tree hh = emit_long_mul_highpart (seq, loc, l1, l2, narrow_type);
+ tree c1 = gimple_build (seq, loc, MULT_EXPR, narrow_type, h1, l2);
+ tree c2 = gimple_build (seq, loc, MULT_EXPR, narrow_type, l1, h2);
+ tree s = gimple_build (seq, loc, PLUS_EXPR, narrow_type, hh, c1);
+ return gimple_build (seq, loc, PLUS_EXPR, narrow_type, s, c2);
+}
+
+/* True when OP fits NARROW_PREC bits as an unsigned value. Looks
+ through widening casts and PHIs, falling back to `tree_nonzero_bits'
+ otherwise. PHI_SEEN guards against cycles. */
+
+static bool
+long_mul_op_fits_p (tree op, unsigned narrow_prec, bitmap phi_seen)
+{
+ if (!TYPE_UNSIGNED (TREE_TYPE (op)))
+ return false;
+ if (TYPE_PRECISION (TREE_TYPE (op)) <= narrow_prec)
+ return true;
+ if (TREE_CODE (op) == SSA_NAME)
+ {
+ gimple *def = SSA_NAME_DEF_STMT (op);
+ if (is_gimple_assign (def)
+ && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
+ return long_mul_op_fits_p (gimple_assign_rhs1 (def), narrow_prec,
+ phi_seen);
+ if (gphi *phi = dyn_cast <gphi *> (def))
+ if (bitmap_set_bit (phi_seen, SSA_NAME_VERSION (op)))
+ {
+ for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
+ if (!long_mul_op_fits_p (gimple_phi_arg_def (phi, i),
+ narrow_prec, phi_seen))
+ return false;
+ return true;
+ }
+ }
+ return wi::min_precision (tree_nonzero_bits (op), UNSIGNED) <= narrow_prec;
+}
+
+/* Split the 2N-bit unsigned value OP into its low and high N bits (*LO and
+ *HI, both NARROW_TYPE) using only N-bit operations, as the target has no 2N
+ multiply or shift. A 2N product recurses on its operands, its high half
+ coming from combine_long_mul_halves. A value shifted down by N recurses on
+ the shifted value and takes its high half, rather than reading the 2N shift.
+ A widening cast's low half is the truncated source and its high half is what
+ the cast extended with, zero or the source's replicated sign bit. A value
+ that provably fits N bits has a zero high half. Returns false otherwise.
*/
+
+static bool
+long_mul_split_operand (gimple_seq *seq, location_t loc, tree op,
+ tree narrow_type, tree *lo, tree *hi)
+{
+ unsigned int narrow_prec = TYPE_PRECISION (narrow_type);
+ if (TREE_CODE (op) == SSA_NAME)
+ {
+ gimple *def = SSA_NAME_DEF_STMT (op);
+ if (is_gimple_assign (def) && gimple_assign_rhs_code (def) == MULT_EXPR)
+ {
+ tree a_lo, a_hi, b_lo, b_hi;
+ if (!long_mul_split_operand (seq, loc, gimple_assign_rhs1 (def),
+ narrow_type, &a_lo, &a_hi)
+ || !long_mul_split_operand (seq, loc, gimple_assign_rhs2 (def),
+ narrow_type, &b_lo, &b_hi))
+ return false;
+ *lo = gimple_build (seq, loc, MULT_EXPR, narrow_type, a_lo, b_lo);
+ *hi = combine_long_mul_halves (seq, loc, a_lo, a_hi, b_lo, b_hi,
+ narrow_type);
+ return true;
+ }
+ /* A 2N value shifted down by N is its own high half: split the source
+ and use that half. Reading the shift instead leaves the 2N source
+ live, and the target cannot expand it. This has to come before the
+ widening-cast case below, which would take such a value as it
+ stands. */
+ if (is_gimple_assign (def)
+ && gimple_assign_rhs_code (def) == RSHIFT_EXPR
+ && tree_fits_uhwi_p (gimple_assign_rhs2 (def))
+ && tree_to_uhwi (gimple_assign_rhs2 (def)) == narrow_prec)
+ {
+ tree src_lo, src_hi;
+ if (!long_mul_split_operand (seq, loc, gimple_assign_rhs1 (def),
+ narrow_type, &src_lo, &src_hi))
+ return false;
+ *lo = src_hi;
+ *hi = build_zero_cst (narrow_type);
+ return true;
+ }
+ if (is_gimple_assign (def)
+ && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
+ {
+ tree src = gimple_assign_rhs1 (def);
+ tree src_type = TREE_TYPE (src);
+ if (INTEGRAL_TYPE_P (src_type)
+ && TYPE_PRECISION (src_type) <= narrow_prec)
+ {
+ *lo = gimple_convert (seq, loc, narrow_type, src);
+ if (TYPE_UNSIGNED (src_type))
+ *hi = build_zero_cst (narrow_type);
+ else
+ {
+ /* Sign extension: the high N bits replicate the sign bit. */
+ tree snarrow = signed_type_for (narrow_type);
+ tree s = gimple_convert (seq, loc, snarrow, *lo);
+ tree amt = build_int_cst (integer_type_node, narrow_prec - 1);
+ tree sh = gimple_build (seq, loc, RSHIFT_EXPR, snarrow, s,
+ amt);
+ *hi = gimple_convert (seq, loc, narrow_type, sh);
+ }
+ return true;
+ }
+ }
+ }
+
+ /* A value provably within N bits: its low half is the truncation to N bits
+ (a subreg, not a 2N shift), its high half is zero. */
+ auto_bitmap phi_seen;
+ if (long_mul_op_fits_p (op, narrow_prec, phi_seen))
+ {
+ *lo = gimple_convert (seq, loc, narrow_type, op);
+ *hi = build_zero_cst (narrow_type);
+ return true;
+ }
+ return false;
+}
+
+/* True when every use of PROD reads only its low NARROW_PREC bits -- a
+ truncation to at most NARROW_PREC bits, or an AND with a low-bit mask. */
+
+static bool
+long_mul_only_low_half_used_p (tree prod, unsigned int narrow_prec)
+{
+ imm_use_iterator iui;
+ gimple *use_stmt;
+ FOR_EACH_IMM_USE_STMT (use_stmt, iui, prod)
+ {
+ if (is_gimple_debug (use_stmt))
+ continue;
+ if (!is_gimple_assign (use_stmt))
+ return false;
+ tree_code code = gimple_assign_rhs_code (use_stmt);
+ if (CONVERT_EXPR_CODE_P (code))
+ {
+ tree t = TREE_TYPE (gimple_assign_lhs (use_stmt));
+ if (!INTEGRAL_TYPE_P (t) || TYPE_PRECISION (t) > narrow_prec)
+ return false;
+ }
+ else if (code == BIT_AND_EXPR
+ && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
+ {
+ if (wi::min_precision (wi::to_wide (gimple_assign_rhs2 (use_stmt)),
+ UNSIGNED) > narrow_prec)
+ return false;
+ }
+ else
+ return false;
+ }
+ return true;
+}
+
+static bool narrow_long_mul_low_half (gimple_stmt_iterator *);
+
+/* OP1 and OP2 are the operands of a 2N multiply just narrowed or lowered;
+ that rewrite now reads each through an N-bit low-half cast. An operand
+ defined by another 2N multiply can thereby become low-half-only -- narrow
+ it too, recursing through chained wide products such as (a*b)*c. */
+
+static void
+narrow_long_mul_operands (tree op1, tree op2)
+{
+ for (tree op : { op1, op2 })
+ if (TREE_CODE (op) == SSA_NAME)
+ {
+ gimple *def = SSA_NAME_DEF_STMT (op);
+ if (is_gimple_assign (def) && gimple_assign_rhs_code (def) == MULT_EXPR)
+ {
+ gimple_stmt_iterator dgsi = gsi_for_stmt (def);
+ narrow_long_mul_low_half (&dgsi);
+ }
+ }
+}
+
+/* If the statement at *GSI is res = a * b with a 2N-bit unsigned result
+ whose mode the target cannot multiply (no insn and no libcall, so it would
+ abort expand_mult), and every use reads only the low N bits, narrow it to
+ res = (2N) ((N) a * (N) b) and return true. The low N bits of a product
+ depend only on the low N bits of the operands, so this preserves every
+ use; the unused high half becomes zero. The gate keeps it target-aware:
+ where a wide or high-part multiply exists the mult is left for
+ convert_mult_to_widen / convert_mult_to_highpart, so this (which match.pd's
+ shorten rule omits for MULT_EXPR) does not pessimize it. */
+
+static bool
+narrow_long_mul_low_half (gimple_stmt_iterator *gsi)
+{
+ gimple *stmt = gsi_stmt (*gsi);
+ if (!is_gimple_assign (stmt) || gimple_assign_rhs_code (stmt) != MULT_EXPR)
+ return false;
+
+ tree lhs = gimple_assign_lhs (stmt);
+ tree wide_type = TREE_TYPE (lhs);
+ scalar_int_mode wide_mode;
+ if (!INTEGRAL_TYPE_P (wide_type)
+ || !TYPE_UNSIGNED (wide_type)
+ || !is_a <scalar_int_mode> (TYPE_MODE (wide_type), &wide_mode)
+ || targetm.scalar_mode_supported_p (wide_mode))
+ return false;
+
+ unsigned int narrow_prec = TYPE_PRECISION (wide_type) / 2;
+ if (!long_mul_only_low_half_used_p (lhs, narrow_prec))
+ return false;
+
+ tree op1 = gimple_assign_rhs1 (stmt);
+ tree op2 = gimple_assign_rhs2 (stmt);
+ location_t loc = gimple_location (stmt);
+ tree narrow_type = build_nonstandard_integer_type (narrow_prec, 1);
+ gimple_seq seq = NULL;
+ tree a = gimple_convert (&seq, loc, narrow_type, op1);
+ tree b = gimple_convert (&seq, loc, narrow_type, op2);
+ tree np = gimple_build (&seq, loc, MULT_EXPR, narrow_type, a, b);
+ gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
+ gimple *conv = gimple_build_assign (lhs, NOP_EXPR, np);
+ gimple_set_location (conv, loc);
+ gsi_replace (gsi, conv, true);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Narrowed low-half-only long multiply.\n");
+
+ narrow_long_mul_operands (op1, op2);
+ return true;
+}
+
+/* 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. 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). An operand
+ wider than T_N -- a shared wide product or a sign-extended cast -- is split
+ into T_N halves rather than truncated, so no high input bits are dropped.
+ 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;
+
+ /* Walk the matched chain back to the 2N multiply and take narrow_type at
+ half its precision. */
+ gimple *shift_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (trunc_stmt));
+ gimple *mult_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (shift_stmt));
+ unsigned int narrow_prec
+ = TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (mult_stmt))) / 2;
+ tree narrow_type = build_nonstandard_integer_type (narrow_prec, /*uns=*/1);
+ scalar_int_mode narrow_mode;
+ if (!is_a <scalar_int_mode> (TYPE_MODE (narrow_type), &narrow_mode))
+ return false;
+
+ /* Lower only when the target cannot form the N-bit high part itself. */
+ if (can_mult_highpart_p (narrow_mode, true))
+ return false;
+
+ location_t loc = gimple_location (trunc_stmt);
+ gimple_seq seq = NULL;
+
+ /* Split each operand into N-bit halves and combine. An operand that fits
+ N bits yields h == 0, so its cross term folds away; with both fitting
+ the combine is just a plain N-bit high part. */
+ tree l1, h1, l2, h2;
+ if (!long_mul_split_operand (&seq, loc, gimple_assign_rhs1 (mult_stmt),
+ narrow_type, &l1, &h1)
+ || !long_mul_split_operand (&seq, loc, gimple_assign_rhs2 (mult_stmt),
+ narrow_type, &l2, &h2))
+ return false;
+ tree hi = combine_long_mul_halves (&seq, loc, l1, h1, l2, h2, narrow_type);
+
+ /* Merging the chain's truncation with a later user cast can retarget the
+ outer convert to any integral type, so convert the narrow result once
+ here (the high part is < 2^N, so the conversion preserves it). */
+ 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, hi);
+ else
+ result_stmt = gimple_build_assign (narrow_lhs, NOP_EXPR, hi);
+ gimple_set_location (result_stmt, loc);
+ gimple_seq_add_stmt (&seq, result_stmt);
+
+ gsi_replace_with_seq (gsi, seq, true);
+
+ /* Clean up the shift and the 2N mult now -- LTRANS runs no DCE between
+ widening_mul and expand, and a dead 2N mult would abort expand_mult.
+ Dead upstream (T_2N) casts, if any, are harmless NOP_EXPRs and land
+ with normal DCE. */
+ if (has_zero_uses (gimple_assign_lhs (shift_stmt)))
+ {
+ gimple_stmt_iterator dgsi = gsi_for_stmt (shift_stmt);
+ gsi_remove (&dgsi, true);
+ release_defs (shift_stmt);
+ }
+
+ /* The mult is either dead (low half recomputed elsewhere) or now read only
+ for its low half -- narrow_long_mul_low_half rewrites it, recursing into
+ its operands. Removing a dead mult can leave a chained 2N mult that fed
+ it low-half-only, so narrow those operands on that path. */
+ gimple_stmt_iterator mgsi = gsi_for_stmt (mult_stmt);
+ if (has_zero_uses (gimple_assign_lhs (mult_stmt)))
+ {
+ tree op1 = gimple_assign_rhs1 (mult_stmt);
+ tree op2 = gimple_assign_rhs2 (mult_stmt);
+ gsi_remove (&mgsi, true);
+ release_defs (mult_stmt);
+ narrow_long_mul_operands (op1, op2);
+ }
+ else
+ narrow_long_mul_low_half (&mgsi);
+
+ 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.
+ The -Og pipeline (pass_all_optimizations_g) does not contain
+ pass_optimize_widening_mul at all, so -Og -fexpensive-optimizations
+ must not enable the emit: the unlowered 2N multiply would reach
+ expand as an unexpandable mode (e.g. OImode) and ICE.
+ -fdisable-tree-widening_mul is not observed. */
+
+bool
+optimize_widening_mul_active_p (void)
+{
+ return flag_expensive_optimizations && optimize && !optimize_debug;
+}
+
/* 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 +7048,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;
@@ -6638,6 +7116,8 @@ math_opts_dom_walker::after_dom_children (basic_block bb)
switch (code)
{
case MULT_EXPR:
+ if (narrow_long_mul_low_half (&gsi))
+ break;
if (!convert_mult_to_widen (stmt, &gsi)
&& !convert_expand_mult_copysign (stmt, &gsi)
&& convert_mult_to_fma (stmt,
@@ -6704,6 +7184,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
