Re: [PATCH v8 0/7] Recognize and fold longhand wide-multiplication idioms [PR107090]

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?

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