[COMMITTED PATCH v9 0/7] Recognize and fold longhand wide-multiplication idioms [PR107090]
Konstantinos Eleftheriou <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
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.
An operand PHI is split through its arguments. A closing sweep
rewrites any 2N product that no lowering claimed into the N-bit
halves its uses read. 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, i686, ARM and PowerPC.
Changes in v9:
- New narrow_long_mul_halves: a sweep after the widening_mul walk that
rewrites a 2N multiply no lowering claimed into the N-bit halves its
uses read. Fixes the ICE building libbid on i686 (PR126642).
- New long_mul_split_phi: split an operand PHI through its arguments.
A PHI merging a zero-extended with a sign-extended value fits N bits
on neither arm, so the split refused it and the multiply reached
expand again. Fixes the rest of PR126642, bid128_sqrt.c on i686.
- Add testcases for the two ICE fixes.
- Drop long_mul_summand's mask field from 1/7. The mul_lo atom only
matches the half-width mask, so nothing ever read it back. Its
parameter and the tree_to_uhwi that fed it go with it.
- Fix the formatting of the `with` blocks in the match.pd
long-multiply atoms.
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 | 193 +++
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.target/i386/long-mul-phi-split.c | 50 +
.../gcc.target/i386/long-mul-sweep.c | 30 +
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 | 1192 ++++++++++++++++-
gcc/tree-ssa-math-opts.cc | 714 +++++++++-
gcc/tree-ssa-math-opts.h | 2 +
25 files changed, 4982 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-phi-split.c
create mode 100644 gcc/testsuite/gcc.target/i386/long-mul-sweep.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