We submitted a new version with the ICE fixes: https://gcc.gnu.org/pipermail/gcc-patches/2026-August/726676.html
Thanks, Konstantinos On Wed, Aug 5, 2026 at 11:20 PM Andrea Pinski < [email protected]> wrote: > On Wed, Aug 5, 2026 at 3:48 AM Philipp Tomsich <[email protected]> > wrote: > > > > Turn out that bootstrap on x86-64 worked, but -m32 was broken… is -m32 > > now part of the required x86-64 bootstrap+regtest coverage we should > > add in the future? > > m32 Multilib support for x86_64 bootstrap has always been a requirement > .... > I am confused how you think m32 multilib support was not a requirement > for x86_64; it is a standard part of the compiler. > > > > > Thanks, > > Philipp. > > > > > > On Tue, 4 Aug 2026 at 19:00, Andrea Pinski > > <[email protected]> wrote: > > > > > > On Tue, Aug 4, 2026 at 6:55 AM Richard Biener > > > <[email protected]> wrote: > > > > > > > > On Mon, Aug 3, 2026 at 5:57 PM 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 a 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 recognizer emits the canonical widening shape > > > > > > > > > > (N)(((2N) a * (2N) b) >> N) > > > > > > > > > > for the high part and a plain MULT_EXPR for the low part. The high > > > > > part is emitted as a shift of the wide product, not as a bare > > > > > (2N) a * (2N) b: the `>> N' form is the MULT_HIGHPART idiom, so > > > > > pass_optimize_widening_mul rewrites it to the target's native > high-part > > > > > multiply (e.g. umulh) without ever forming the full 2N product. A > bare > > > > > widening product would also compute the unwanted low half, and > where 2N > > > > > has no native multiply -- the 128x128 case, 2N = OImode, which the > mode > > > > > table carries but the target cannot expand -- there is no way to > form > > > > > it at all. For that case the final patch resynthesizes the > longhand at > > > > > narrow precision from (N/2)-wide partial products, so the fold > never > > > > > depends on a 2N multiply the target lacks. > > > > > > > > > > The series is split into seven patches: > > > > > > > > > > 1/7 forwprop: Match and fold the long-multiply carry form > > > > > [PR107090] > > > > > > > > > > Adds the match.pd atom patterns and the forwprop framework: > > > > > linearize the outer add/ior chain, classify each summand, > and > > > > > match the multiset against a table of decomposed variants. > > > > > Carries the base carry form, a single overflow comparison on > > > > > the cross-sum. Matching starts only at the end of a chain, > and > > > > > leaves that are not long-multiply summands are preserved and > > > > > re-applied on top of the fold, so a chain that mixes the > idiom > > > > > with unrelated addends still folds. > > > > > > > > > > 2/7 - 5/7 Add the remaining recognized variants: carry-low-sum, > > > > > two-carry, ladder, and low-plus. > > > > > > > > > > 6/7 match.pd, forwprop: Recognize long-multiply carries written > as > > > > > 2-arg PHI > > > > > > > > > > Hand-written code often writes the carry as a 2-arg PHI > > > > > (`if (overflow) result += pow2;`) with no top-level + at the > > > > > result. Adds cond_carry_add / cond_carry_add_neg recognizers > > > > > for that shape and a match_long_mul_phi entry that > synthesizes > > > > > the carry summand from the PHI bindings and reuses the table > > > > > walk and emit path. > > > > > > > > > > 7/7 widening_mul: Lower long-multiply chains to inline longhand > > > > > > > > > > Lowers the high-part chain to a longhand high-part at narrow > > > > > precision when the target has no expansion path for the 2N > > > > > form, using (N/2)-by-(N/2)->N widening multiplies where the > > > > > optab exists and plain N-bit multiplies otherwise. Operands > > > > > that are themselves wider than N are split into N-bit halves > > > > > rather than truncated, and a 2N product left with only > low-half > > > > > uses is narrowed to an N-bit multiply rather than reaching > > > > > expansion. When an operand holds a product's high N bits, > those > > > > > come from the product's own operands instead of the 2N > shift. > > > > > Paired with pass_optimize_widening_mul so the chain is > emitted > > > > > only when the pass will run to rescue an unsupported 2N > shape. > > > > > > > > > > On SPEC2026's 750.sealcrypto_r: > > > > > > > > > > - AArch64 Neoverse-N1: 25% improvement > > > > > - x86-64 Zen4: 59% improvement > > > > > > > > > > Compile-time impact is negligible: recompiling gcc/*.cc > > > > > (checking=yes,extra) with the series compiler versus its base adds > > > > > about 0.1% overall, confined to forwprop, where the recognizer runs > > > > > and grows the pass by a few percent. > > > > > > > > > > Bootstrapped/regtested on AArch64, x86-64, ARM and PowerPC. > > > > > > > > This is OK. Please squash the series before pushing, there seems to > > > > be unused code in earlier parts of the series and possibly failing > > > > testcases. > > > > > > Note this would mean the series was not created correctly in the first > > > place. And it means it was not tested correctly. > > > Also I would have liked the series not squashed and actually fixed up > > > such that it was separated out for many different reasons. Including > > > but not limited to that it was complex to review in the first place. > > > Plus now bootstrap is broken on x86_64. > > > > > > > > > > > > > > Thanks, > > > > Richard. > > > > > > > > > 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. > > > > > > > > > > Konstantinos Eleftheriou (7): > > > > > forwprop: Match and fold the long-multiply carry form [PR107090] > > > > > forwprop: Add long-multiply carry-low-sum variant > > > > > forwprop: Add long-multiply two-carry variant > > > > > forwprop: Add long-multiply ladder variants > > > > > forwprop: Add long-multiply low-plus variant > > > > > match.pd, forwprop: Recognize long-multiply carries written as > 2-arg > > > > > PHI > > > > > widening_mul: Lower long-multiply chains to inline longhand > > > > > > > > > > gcc/match.pd | 198 +++ > > > > > 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 | 180 +++ > > > > > .../gcc.dg/tree-ssa/long-mul-boundary-64.c | 417 ++++++ > > > > > .../gcc.dg/tree-ssa/long-mul-boundary.c | 394 ++++++ > > > > > .../gcc.dg/tree-ssa/long-mul-carry.c | 385 ++++++ > > > > > .../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-extra-addend.c | 63 + > > > > > .../gcc.dg/tree-ssa/long-mul-ladder.c | 333 +++++ > > > > > .../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 | 140 ++ > > > > > gcc/testsuite/gcc.target/aarch64/long_mul.c | 100 ++ > > > > > .../gcc.target/arm/long-mul-thumb1-inline.c | 47 + > > > > > gcc/testsuite/gcc.target/arm/long-mul-umull.c | 73 + > > > > > gcc/testsuite/gcc.target/i386/long_mul.c | 100 ++ > > > > > .../gcc.target/i386/widen_mult_high_chain.c | 32 + > > > > > gcc/testsuite/lib/target-supports.exp | 20 + > > > > > gcc/tree-ssa-forwprop.cc | 1197 > ++++++++++++++++- > > > > > gcc/tree-ssa-math-opts.cc | 492 ++++++- > > > > > gcc/tree-ssa-math-opts.h | 2 + > > > > > 23 files changed, 4690 insertions(+), 9 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/torture/long-mul-64-run.c > > > > > 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-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.dg/tree-ssa/long-mul-extra-addend.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/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.c > > > > > create mode 100644 > gcc/testsuite/gcc.target/i386/widen_mult_high_chain.c > > > > > > > > > > -- > > > > > 2.55.0 >
