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

On Tue, Aug 4, 2026 at 6:55=E2=80=AFAM Richard Biener
<[email protected]> wrote:
>
> On Mon, Aug 3, 2026 at 5:57=E2=80=AFPM 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 =3D OImode, which the mo=
de
> > 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 +=3D 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=3Dyes,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 +=3D 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 =3D a * b` has uses only=
 in
> >   its low N bits and the target cannot expand 2N, rewrite it to
> >   `res =3D (2N) ((N)a * (N)b)`. The split-based lowering covers a chain=
ed
> >   2N operand by recursing into it, but not a shared 2N product left wit=
h
> >   only low-half uses, which is what ICEs libgo's p521_fiat64.go on ARM3=
2.
> > - 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), wher=
e
> >   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 !=3D 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 !=3D 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 >=3D 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-12=
8.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