This patch series teaches GCC to recognize longhand 64x64->128
wide-multiplication idioms and replace them with native multiply
instructions (MULT_HIGHPART_EXPR / widening multiply for the high part,
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 match.pd: Flatten a power-of-two carry-add to a shifted compare
A conditional power-of-two add into a running sum --
sum = a + b;
if (cmp(a, sum)) result = base + pow2;
else result = base;
-- gets rewritten to branchless straight-line code:
result = base + ((type)(cmp(a, sum)) << log2(pow2));
Independently useful as a branch-elimination peephole; 2/2 is
one consumer (it needs the carry on a branch-free path to
classify it as the carry summand of a long-multiply variant).
2/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
Gated on a new m_long_mul_fold_p pass parameter (forwprop2
onwards) and on can_mult_highpart_p at emission time.
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 v4:
- 1/2:
- Rebuild the guard with per-conjunct reasoning: require both
INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type) and
INTEGRAL_TYPE_P (TREE_TYPE (@0)) && TYPE_UNSIGNED (TREE_TYPE (@0)).
The v3 swap of TYPE_UNSIGNED (type) for TYPE_UNSIGNED
(TREE_TYPE (@0)) had let signed result types with @3 == INT_MIN
slip through into a shift-by-(-1).
- Drop the "carry diamond" CFG-shape nickname. Describe the
transform in terms of the data shape it operates on (conditional
carry-add) rather than CFG topology. Rename the profitability
helper to fold_cond_carry_add_profitable_p; rename phiopt
regression tests to test_cond_carry_add*.
- 2/2:
- Pass-parameter gating: pass_forwprop takes a new
m_long_mul_fold_p, set true for forwprop2 onwards. This keeps
the fold out of pre-IPA forwprop1, where target capability
queries are unsafe under offload compilation, without adding a
runtime predicate.
- Lower the high-part to MULT_HIGHPART_EXPR and rely on 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):
match.pd: Flatten a power-of-two carry-add to a shifted compare
forwprop: Match and fold long-multiply patterns [PR107090]
gcc/gimple-match-head.cc | 23 +
gcc/match.pd | 174 ++++
gcc/passes.def | 8 +-
gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c | 21 +
gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c | 45 +
.../gcc.dg/tree-ssa/long-mul-boundary-64.c | 276 ++++++
.../gcc.dg/tree-ssa/long-mul-boundary.c | 272 ++++++
.../gcc.dg/tree-ssa/long-mul-carry.c | 310 ++++++
.../gcc.dg/tree-ssa/long-mul-ladder.c | 328 +++++++
.../gcc.dg/tree-ssa/long-mul-low-plus.c | 54 ++
.../gcc.dg/tree-ssa/long-mul-partial.c | 119 +++
.../gcc.dg/tree-ssa/long-mul-two-carry.c | 113 +++
gcc/testsuite/gcc.target/aarch64/long_mul.c | 100 ++
gcc/testsuite/gcc.target/i386/long_mul.c | 100 ++
gcc/tree-ssa-forwprop.cc | 904 +++++++++++++++++-
15 files changed, 2838 insertions(+), 9 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.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-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
