This patch series teaches forwprop 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 forwprop: Flatten carry-diamond patterns to straight-line code
A carry diamond implements unsigned overflow detection with
conditional carry propagation:
sum = a + b;
if (addend > sum) result = base + C;
This patch converts such conditional branches into branchless
straight-line code, exposing the carry as a comparison
expression. This is a prerequisite for the long-multiply
pattern matching, which expects carries in the form
(lshift (convert? (gt ...)) INTEGER_CST).
2/2 forwprop: Match and fold long-multiply patterns [PR107090]
Adds match.pd patterns that recognize six decomposed variants
of the longhand multiplication:
- 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
The actual folding is performed in forwprop after verifying
target support for umul_highpart or widening multiply.
On SPEC2026's 750.sealcrypto_r:
- AArch64 Neoverse-N1: 25% improvement
- x86-64 Zen4: 59% improvement
Konstantinos Eleftheriou (2):
forwprop: Flatten carry-diamond patterns to straight-line code
forwprop: Match and fold long-multiply patterns [PR107090]
gcc/match.pd | 221 +++
gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c | 21 +
gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c | 44 +
.../gcc.dg/tree-ssa/long-mul-boundary-64.c | 274 ++++
.../gcc.dg/tree-ssa/long-mul-boundary.c | 270 ++++
.../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 | 109 ++
gcc/testsuite/gcc.target/aarch64/long_mul.c | 100 ++
gcc/testsuite/gcc.target/i386/long_mul.c | 100 ++
gcc/tree-ssa-forwprop.cc | 1367 ++++++++++++++++-
13 files changed, 3312 insertions(+), 5 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
