[PATCH v8 7/7] widening_mul: Lower long-multiply chains to inline longhand
Konstantinos Eleftheriou <[email protected]> Mon, 3 Aug 2026 08:41:41 -0700
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
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