[PATCH v9 7/7] widening_mul: Lower long-multiply chains to inline longhand
Konstantinos Eleftheriou <[email protected]> Thu, 6 Aug 2026 23:36:34 -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. An operand can also be a PHI, left behind when PRE hoists a (T_2N) cast onto a shared slot. Fitting N bits and splitting are different tests: a PHI merging a zero-extended with a sign-extended value fits on neither arm, though the cast case splits either argument on its own. So `long_mul_split_phi` splits the arguments and merges the halves with two new PHIs. Several chains can reach one operand PHI, so a split is recorded against it and shared with the rest. 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. A product can also survive every lowering. The chain lowering rewrites the cast reading its high half but retires the shift only once nothing reads it, so a second recognized product taking that high half as an operand keeps it live, and the product is then read through a shift that `narrow_long_mul_low_half' does not take. `narrow_long_mul_halves' sweeps the function after the walk and rewrites such a product into the halves its uses read, the high one synthesized in longhand with each shift becoming a widening cast of it. Running last, what it sees is what nothing else claimed. 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. (struct long_mul_halves): New; the halves an operand PHI was split into. (struct long_mul_arg_split): New; an argument of an operand PHI with the statements that split it. (long_mul_split_phi): New; splits an operand PHI by splitting its arguments and merging the halves with two new PHIs. Record the halves and reuse them for the next consumer of the same PHI. (long_mul_high_half_uses): New; collects the `>> N' uses forming a product's high half. (long_mul_only_low_half_used_p): New. (unexpandable_long_mul_p): New; true for a 2N multiply in a mode the target cannot multiply. (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. (finish_long_mul_low_half): New; narrows or removes a 2N mult whose high half is synthesized elsewhere. (narrow_long_mul_halves): New; rewrites a 2N multiply into the N-bit halves its uses read. (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. (pass_optimize_widening_mul::execute): Sweep the function for multiplies left in a mode the target cannot expand. Scope the record of split operand PHIs to one run of the pass. * 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/long-mul-phi-split.c: New test. * gcc.target/i386/long-mul-sweep.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 v9: - New narrow_long_mul_halves: a sweep after the widening_mul walk that rewrites a 2N multiply no lowering claimed into the N-bit halves its uses read. Fixes the ICE building libbid on i686 (PR126642). - New long_mul_split_phi: split an operand PHI through its arguments. A PHI merging a zero-extended with a sign-extended value fits N bits on neither arm, so the split refused it and the multiply reached expand again. Fixes the rest of PR126642, bid128_sqrt.c on i686. - Add testcases for the two ICE fixes. - Drop long_mul_summand's mask field from 1/7. The mul_lo atom only matches the half-width mask, so nothing ever read it back. Its parameter and the tree_to_uhwi that fed it go with it. - Fix the formatting of the `with` blocks in the match.pd long-multiply atoms. 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 | 20 + 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/long-mul-phi-split.c | 50 ++ .../gcc.target/i386/long-mul-sweep.c | 30 + .../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 | 714 +++++++++++++++++- gcc/tree-ssa-math-opts.h | 2 + 17 files changed, 1399 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/long-mul-phi-split.c create mode 100644 gcc/testsuite/gcc.target/i386/long-mul-sweep.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 90ee6f4981d4..9cdca1757ab0 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -12464,6 +12464,26 @@ 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/long-mul-phi-split.c b/gcc/testsuite/gcc.target/i386/long-mul-phi-split.c new file mode 100644 index 000000000000..036e34ffd229 --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/long-mul-phi-split.c @@ -0,0 +1,50 @@ +/* { dg-do compile { target ia32 } } */ +/* { dg-options "-O2 -fdump-tree-widening_mul-details" } */ + +/* The product has an operand PHI carrying a sign-extended value, which only + long_mul_split_phi splits. */ + +typedef unsigned long long u64; +typedef unsigned int u32; +typedef struct { u64 w[2]; } u128; + +u128 pCS, ES; +u64 ARS1, ES32, R64H, S1, S3; +int src, flag; + +void +f (void) +{ + ES.w[1] = src; /* Signed, so this sign-extends. */ + if (src < 0) + { + u64 PH; + if (flag) + ES.w[1]--; /* Leaves the operand a PHI. */ + u64 CXH = ES.w[1] >> 32, CXL = (u32) ES.w[1]; + u64 CYH = ARS1 >> 32, CYL = (u32) ARS1; + u64 PM = CXH * CYL; + PH = CXH * CYH; + u64 PL = CXL * CYL, PM2 = CXL * CYH; + PH += PM >> 32; + PM = (u32) PM + PM2 + (PL >> 32); + if (PH + (PM >> 32)) + R64H++; + S3 = R64H; + } + { + u64 PH; + u64 CXH = ES32 >> 32, CXL = (u32) ES32; + u64 CYH = ES.w[1] >> 32, CYL = (u32) ES.w[1]; + u64 PM = CXH * CYL; + PH = CXH * CYH; + u64 PL = CXL * CYL, PM2 = CXL * CYH; + PH += PM >> 32; + PM = (u32) PM + PM2 + (PL >> 32); + if (PH + (PM >> 32)) + S1 = S3; + } + pCS.w[1] = S1; +} + +/* { dg-final { scan-tree-dump "Split long-multiply operand PHI" "widening_mul" } } */ diff --git a/gcc/testsuite/gcc.target/i386/long-mul-sweep.c b/gcc/testsuite/gcc.target/i386/long-mul-sweep.c new file mode 100644 index 000000000000..e3d8f090e021 --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/long-mul-sweep.c @@ -0,0 +1,30 @@ +/* { dg-do compile { target ia32 } } */ +/* { dg-options "-O2 -fdump-tree-widening_mul-details" } */ + +/* The high half is also read by a second multiply, so the chain lowering + cannot retire the product and only the sweep rewrites it. */ + +typedef unsigned long long u64; +typedef unsigned int u32; + +u64 x, y, cond, PL, PM, PM2, res, hi; + +void +f (void) +{ + u64 PH; + u64 CXH = x >> 32, CXL = (u32) x; + u64 CYH = y >> 32, CYL = (u32) y; + PM = CXH * CYL; + PH = CXH * CYH; + PL = CXL * CYL; + PM2 = CXL * CYH; + PH += PM >> 32; + PM = (u32) PM + PM2 + (PL >> 32); + hi = PH + (PM >> 32); + if (cond) + /* Keeps the high half, and so the product, live. */ + res = (u32) hi * (PM >> 32); +} + +/* { dg-final { scan-tree-dump "Narrowed high half of long multiply" "widening_mul" } } */ 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 dafbebe84ca7..54cb788a8e0a 100644 --- a/gcc/testsuite/lib/target-supports.exp +++ b/gcc/testsuite/lib/target-supports.exp @@ -4983,6 +4983,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 abcbc24369bb..1a301e0070a5 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 @@ -4529,15 +4530,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 0df1909ebc43..c0a730308673 100644 --- a/gcc/tree-ssa-math-opts.cc +++ b/gcc/tree-ssa-math-opts.cc @@ -6541,6 +6541,689 @@ 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; +} + +static bool long_mul_split_operand (gimple_seq *, location_t, tree, tree, + tree *, tree *); + +struct long_mul_halves +{ + tree lo; + tree hi; +}; + +/* Halves recorded for one run of the pass, keyed on the PHI they came from. + Several chains can reach one operand PHI, and each that splits it again + leaves another redundant pair of half PHIs behind. */ + +static hash_map<tree, long_mul_halves> *long_mul_phi_halves; + +struct long_mul_arg_split +{ + gimple_seq seq; + tree lo; + tree hi; +}; + +/* Split the 2N-bit result of PHI into N-bit halves *LO and *HI, by splitting + each argument and merging the halves with two new PHIs. A split goes at + the end of its argument's incoming block, where the argument is available, + rather than on the edge, which could split a critical edge while the + dominator walk is still running. Returns false, having changed nothing, + when an argument cannot be split. A split that succeeds stands even if + the caller then gives up. */ + +static bool +long_mul_split_phi (gphi *phi, tree narrow_type, tree *lo, tree *hi) +{ + tree res = gimple_phi_result (phi); + if (long_mul_halves *prev = long_mul_phi_halves->get (res)) + { + /* Every operand reaching a split has the 2N type, so the width is + fixed by the PHI's own type. */ + gcc_checking_assert (types_compatible_p (TREE_TYPE (prev->lo), + narrow_type)); + *lo = prev->lo; + *hi = prev->hi; + return true; + } + + unsigned int n = gimple_phi_num_args (phi); + location_t loc = gimple_location (phi); + basic_block bb = gimple_bb (phi); + auto_vec<long_mul_arg_split, 4> args; + + for (unsigned int i = 0; i < n; i++) + { + edge e = gimple_phi_arg_edge (phi, i); + /* A back edge could lead back to PHI and recurse forever. The entry + block cannot hold a split. */ + if (dominated_by_p (CDI_DOMINATORS, e->src, bb) + || e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + return false; + + long_mul_arg_split arg = {}; + if (!long_mul_split_operand (&arg.seq, loc, gimple_phi_arg_def (phi, i), + narrow_type, &arg.lo, &arg.hi)) + return false; + + args.safe_push (arg); + } + + /* Every argument split, so the rewrite can be committed. */ + gphi *lo_phi = create_phi_node (make_ssa_name (narrow_type), bb); + gphi *hi_phi = create_phi_node (make_ssa_name (narrow_type), bb); + for (unsigned int i = 0; i < n; i++) + { + edge e = gimple_phi_arg_edge (phi, i); + if (args[i].seq) + { + gimple_stmt_iterator gsi = gsi_last_bb (e->src); + if (!gsi_end_p (gsi) && stmt_ends_bb_p (gsi_stmt (gsi))) + gsi_insert_seq_before (&gsi, args[i].seq, GSI_SAME_STMT); + else + gsi_insert_seq_after (&gsi, args[i].seq, GSI_CONTINUE_LINKING); + } + add_phi_arg (lo_phi, args[i].lo, e, UNKNOWN_LOCATION); + add_phi_arg (hi_phi, args[i].hi, e, UNKNOWN_LOCATION); + } + *lo = gimple_phi_result (lo_phi); + *hi = gimple_phi_result (hi_phi); + long_mul_phi_halves->put (res, { *lo, *hi }); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Split long-multiply operand PHI.\n"); + return true; +} + +/* 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. A PHI is split through its + arguments as a last resort. 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; + } + + /* A PHI that does not fit N bits can still be split through its arguments, + which is how a sign-extended value reaches the cast case above. */ + if (TREE_CODE (op) == SSA_NAME) + if (gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (op))) + return long_mul_split_phi (phi, narrow_type, lo, hi); + return false; +} + +/* Collect into HIGH_USES the uses of PROD forming its high half, + `PROD >> NARROW_PREC'. A use reading only the low NARROW_PREC bits is + accepted but not collected. Returns false on any other use. */ + +static bool +long_mul_high_half_uses (tree prod, unsigned int narrow_prec, + vec<gimple *> *high_uses) +{ + 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 (code == RSHIFT_EXPR + && gimple_assign_rhs1 (use_stmt) == prod + && tree_fits_uhwi_p (gimple_assign_rhs2 (use_stmt)) + && tree_to_uhwi (gimple_assign_rhs2 (use_stmt)) == narrow_prec) + high_uses->safe_push (use_stmt); + else 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; +} + +/* True when every use of PROD reads only its low NARROW_PREC bits. */ + +static bool +long_mul_only_low_half_used_p (tree prod, unsigned int narrow_prec) +{ + auto_vec<gimple *, 4> high_uses; + return (long_mul_high_half_uses (prod, narrow_prec, &high_uses) + && high_uses.is_empty ()); +} + +/* True when STMT is res = a * b whose unsigned 2N-bit result is in a mode the + target cannot multiply, having neither insn nor libcall, so that expand_mult + would abort; set *NARROW_TYPE to the N-bit unsigned type its halves are + built at. A mode the target does support is left to convert_mult_to_widen + and convert_mult_to_highpart. */ + +static bool +unexpandable_long_mul_p (gimple *stmt, tree *narrow_type) +{ + if (!is_gimple_assign (stmt) || gimple_assign_rhs_code (stmt) != MULT_EXPR) + return false; + + tree wide_type = TREE_TYPE (gimple_assign_lhs (stmt)); + 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; + + *narrow_type + = build_nonstandard_integer_type (TYPE_PRECISION (wide_type) / 2, 1); + 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 the + target cannot multiply 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. match.pd's shorten rule omits this for + MULT_EXPR. */ + +static bool +narrow_long_mul_low_half (gimple_stmt_iterator *gsi) +{ + gimple *stmt = gsi_stmt (*gsi); + tree narrow_type; + if (!unexpandable_long_mul_p (stmt, &narrow_type)) + return false; + + tree lhs = gimple_assign_lhs (stmt); + if (!long_mul_only_low_half_used_p (lhs, TYPE_PRECISION (narrow_type))) + return false; + + tree op1 = gimple_assign_rhs1 (stmt); + tree op2 = gimple_assign_rhs2 (stmt); + location_t loc = gimple_location (stmt); + 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; +} + +/* The 2N multiply at *GSI has had its high half synthesized elsewhere, so any + use left reads only its low half: narrow it in place, or remove it when it + has no use at all. Removing it drops a use of each operand, so a 2N + multiply defining one may become low-half-only. Narrow those operands. */ + +static void +finish_long_mul_low_half (gimple_stmt_iterator *gsi) +{ + gimple *stmt = gsi_stmt (*gsi); + + if (has_zero_uses (gimple_assign_lhs (stmt))) + { + tree op1 = gimple_assign_rhs1 (stmt); + tree op2 = gimple_assign_rhs2 (stmt); + gsi_remove (gsi, true); + release_defs (stmt); + narrow_long_mul_operands (op1, op2); + return; + } + + narrow_long_mul_low_half (gsi); +} + +/* Rewrite the multiply STMT into the N-bit halves its uses read, when the + target can neither multiply at 2N bits nor form an N-bit high part. + Returns true on a rewrite, which may remove STMT. + + Runs once lower_long_mul_high_chain has been applied to every statement: + both rewrite products with a high half, and this one, keyed on the + definition rather than on a consumer, would otherwise pre-empt it. What + reaches it is a product that lowering could not retire, its high half also + read as an operand of another product, or read alongside the low half. A + product read only for its low half is left to narrow_long_mul_low_half. */ + +static bool +narrow_long_mul_halves (gimple *stmt) +{ + tree narrow_type; + if (!unexpandable_long_mul_p (stmt, &narrow_type)) + return false; + + /* Only worth lowering where the target cannot form the N-bit high part. */ + scalar_int_mode narrow_mode; + if (!is_a <scalar_int_mode> (TYPE_MODE (narrow_type), &narrow_mode) + || can_mult_highpart_p (narrow_mode, true)) + return false; + + tree lhs = gimple_assign_lhs (stmt); + auto_vec<gimple *, 4> high_uses; + if (!long_mul_high_half_uses (lhs, TYPE_PRECISION (narrow_type), &high_uses) + || high_uses.is_empty ()) + return false; + + tree op1 = gimple_assign_rhs1 (stmt); + tree op2 = gimple_assign_rhs2 (stmt); + location_t loc = gimple_location (stmt); + gimple_seq seq = NULL; + tree l1, h1, l2, h2; + if (!long_mul_split_operand (&seq, loc, op1, narrow_type, &l1, &h1) + || !long_mul_split_operand (&seq, loc, op2, narrow_type, &l2, &h2)) + return false; + tree hi = combine_long_mul_halves (&seq, loc, l1, h1, l2, h2, narrow_type); + /* The high part is < 2^N, so widening it back to 2N leaves every use of a + shift, full width or truncated, reading the same value. */ + tree hi_wide = gimple_convert (&seq, loc, TREE_TYPE (lhs), hi); + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT); + + unsigned int i; + gimple *shift_stmt; + FOR_EACH_VEC_ELT (high_uses, i, shift_stmt) + { + gimple_stmt_iterator sgsi = gsi_for_stmt (shift_stmt); + gimple *conv = gimple_build_assign (gimple_assign_lhs (shift_stmt), + hi_wide); + gimple_set_location (conv, loc); + gsi_replace (&sgsi, conv, true); + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Narrowed high half of long multiply.\n"); + + finish_long_mul_low_half (&gsi); + 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. */ + gimple_stmt_iterator mgsi = gsi_for_stmt (mult_stmt); + finish_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 +7253,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 +7321,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 +7389,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:; @@ -6780,8 +7475,25 @@ pass_optimize_widening_mul::execute (function *fun) calculate_dominance_info (CDI_DOMINATORS); renumber_gimple_stmt_uids (cfun); + long_mul_phi_halves = new hash_map<tree, long_mul_halves>; + math_opts_dom_walker (&cfg_changed).walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + /* A 2N multiply the target cannot expand would abort expand_mult. Every + statement has been through the lowerings above, so one left here matched + none of them. */ + basic_block bb; + FOR_EACH_BB_FN (bb, fun) + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) + { + gimple *stmt = gsi_stmt (gsi); + gsi_next (&gsi); + narrow_long_mul_halves (stmt); + } + + delete long_mul_phi_halves; + long_mul_phi_halves = NULL; + statistics_counter_event (fun, "widening multiplications inserted", widen_mul_stats.widen_mults_inserted); statistics_counter_event (fun, "widening maccs inserted", 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