Andrea, Agreed, staging this into a series will go a long way towards making it more reviewable. We'll resubmit a restructured series.
Proposed split: 1. The single flat carry form: a top-level '+' chain of the four 32x32 partial products plus one overflow-compare carry. This is what multiply_uint64_hw64_generic lowers to (and has been a separate commit in our tree anyway). 2.[n]. One decomposition variant per patch: carry-long, two-carry, ladder, ladder-long, low-plusl; each with the matching test. 3. The 2-arg-PHI carry form (`if (overflow) hi += 1;`). This is strictly additive on top of the earlier. The bulk of the "complexity" is due to the same longhand written several different ways across sealcrypto and the Hacker's Delight variants. The mid-end hands us several canonical forms. Regarding "worrying about the target": we gate the high-part emit on the 2N scalar mode existing because on a target without a native wide multiply, we'd turn a working hand-rolled longhand into a __multi3-style libgcc call. I'd recommend to keep that check. Most of the +3300 lines is testsuite; the logic is ~1.2k. The split above should make each patch individually digestible in a single sitting. Thanks, Philipp On Thu, 25 Jun 2026 at 01:05, Andrea Pinski <[email protected]> wrote: > > On Wed, Jun 24, 2026 at 2:09 PM Philipp Tomsich > <[email protected]> wrote: > > > > 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 > > I have a big question. Why is it much more complex than LLVM's implementation? > Can we start with a simple implementation and add more things to it? > Also each revision seems to get even more complex and adds much more things. > So let's start with assuming no basic block changes needed. > And then we can add the second case. > Also start with not worrying about what the target has, that can be > lowered during expand and/or during widen_multiply. > > This will allow it easier to review this huge patch. Because it seems > like each time it is getting bigger and bigger. > > Thanks, > Andrea > > > > > > > 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
