Also, this restores feature-parity with LLVM. The equivalent support was added in late November to LLVM: https://github.com/llvm/llvm-project/pull/168396
On Wed, 24 Jun 2026 at 16:14, Konstantinos Eleftheriou <[email protected]> wrote: > > > This patch series teaches GCC to recognize longhand 64x64->128 > wide-multiplication idioms and replace them with native multiply > instructions: a widening multiply followed by a right shift for the > high part, and plain MULT_EXPR for the low part. > > Portable C/C++ code that needs a 128-bit product on a 64-bit target > often resorts to a longhand decomposition: split operands into 32-bit > halves, compute four partial products, and propagate carries manually. > This pattern appears in a number of real-world codebases, including > SPEC2026's 750.sealcrypto_r (seal/util/uintarith.h) and several > examples from Hacker's Delight. Targets like AArch64 (mul/umulh) and > x86-64 can compute the full 128-bit product in one or two instructions, > but GCC does not currently fold the longhand sequence back to these. > > The series is split into two patches: > > 1/2 forwprop: Match and fold long-multiply patterns [PR107090] > > Adds match.pd atom patterns plus a forwprop framework that > linearises the outer add/ior chain, classifies summands, and > matches the multiset against a table of six decomposed > variants: > > - carry: single overflow comparison on the cross-sum > - carry-long: cross-carry with separate high/low accumulation > - two-carry: both cross-carry and low-carry as separate > comparisons > - ladder: sequential accumulation without explicit carry > comparison > - ladder-long: ladder with separate high/low accumulation > - low-plus: low part as a direct sum of partial products > > Emits the canonical widening shape > > (N)(((2N) a * (2N) b) >> N) > > for high parts. pass_optimize_widening_mul later lowers this > to WIDEN_MULT_EXPR / MULT_HIGHPART_EXPR on supporting targets. > Skipped when the target lacks the 2N scalar mode. > > 2/2 match.pd, forwprop: Recognise long-multiply carries written as > 2-arg PHI > > The 1/2 fold's entry walks a top-level + statement. Hand- > written long-multiply code often writes the carry as a 2-arg > PHI (`if (overflow) result += pow2;`) instead, with no > top-level + at the result. 2/2 adds cond_carry_add and > cond_carry_add_neg match.pd recognizers for that PHI shape > and a match_long_mul_phi entry that linearises the no-carry > arm, synthesises the carry summand from the PHI bindings, > and reuses 1/2's table walk and emit path. > > On SPEC2026's 750.sealcrypto_r: > > - AArch64 Neoverse-N1: 25% improvement > - x86-64 Zen4: 59% improvement > > Compile-time impact: single-threaded recompile of gcc/*.cc with each > branch's stage3 cc1plus (checking=yes,extra) takes 87:05 on master vs > 87:55 on this series -- ~1% overhead. > > Bootstrapped/regtested on AArch64, x86-64 and PowerPC. > > 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. > > Konstantinos Eleftheriou (2): > forwprop: Match and fold long-multiply patterns [PR107090] > match.pd, forwprop: Recognise long-multiply carries written as 2-arg > PHI > > gcc/match.pd | 177 +++ > .../gcc.dg/tree-ssa/long-mul-boundary-64.c | 398 ++++++ > .../gcc.dg/tree-ssa/long-mul-boundary.c | 394 ++++++ > .../gcc.dg/tree-ssa/long-mul-carry.c | 373 ++++++ > .../gcc.dg/tree-ssa/long-mul-ladder.c | 329 +++++ > .../gcc.dg/tree-ssa/long-mul-low-plus.c | 54 + > .../gcc.dg/tree-ssa/long-mul-partial.c | 193 +++ > .../gcc.dg/tree-ssa/long-mul-two-carry.c | 142 +++ > gcc/testsuite/gcc.target/aarch64/long_mul.c | 100 ++ > gcc/testsuite/gcc.target/i386/long_mul.c | 100 ++ > gcc/tree-ssa-forwprop.cc | 1066 ++++++++++++++++- > 11 files changed, 3318 insertions(+), 8 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c > create mode 100644 gcc/testsuite/gcc.target/aarch64/long_mul.c > create mode 100644 gcc/testsuite/gcc.target/i386/long_mul.c > > -- > 2.52.0
