Hi Andrea, New version in https://gcc.gnu.org/pipermail/gcc-patches/2026-July/723920.html.
The key difference to your proposal is that instead of inverse-lowering `((2N) op1 * (2N) op2)` we do it for `(N) (((2N) op1 * (2N) op2) >> N)`. For the simple multiplication without the shift, `convert_mult_to_widen` already tries to generate a WIDEN_MULT_EXPR whenever the N->2N widen optab exists and bails otherwise. Fixing this there would be more complicated and risk regressions. In our implementation we inverse-lower the high part, so when a 2N has no native multiply (the 128×128 case, where 2N is OImode), `lower_long_mul_high_chain rebuilds` just the high N bits from (N/2)-wide partial products, so we never rely on the 2N product the target can't form. Thanks, Konstantinos On Thu, Jun 25, 2026 at 1:25 PM Andrea Pinski < [email protected]> wrote: > On Thu, Jun 25, 2026 at 1:38 AM Philipp Tomsich > <[email protected]> wrote: > > > > 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. > > Why not implement the opposite flow in say widenning_multiply when the > target does not have a widening multiply? > This will allow for when someone say just wrote > ((__int128)long_var1)*((__int128)long_var2) in the first place. > and then canonical form during gimple is one thing? > > Thanks, > Andrea > > > > > 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 >
