https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107090
--- Comment #20 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Philipp Tomsich <[email protected]>: https://gcc.gnu.org/g:806feb8e017b243de37e4502a6fc01fb76dd1529 commit r17-3437-g806feb8e017b243de37e4502a6fc01fb76dd1529 Author: Konstantinos Eleftheriou <[email protected]> Date: Wed Jul 8 06:58:21 2026 -0700 forwprop: Match and fold the long-multiply carry form [PR107090] Recognize the schoolbook expansion of a 2N-bit unsigned multiply -- four NxN partial products plus one overflow-compare carry, summed in a top-level + chain: xh*yh + (cross_sum >> N) + (low_accum >> N) + ((hilo > cross_sum) << N) cross_sum = xh*yl + xl*yh low_accum = (xl*yl >> N) + (cross_sum & mask) and fold it to a widening multiply plus right shift for the high part and a plain MULT_EXPR for the low part. On AArch64 this reduces the 16-instruction longhand in SPEC2026's 750.sealcrypto_r to umulh + mul + stp. The summands are matched by match.pd atoms; forwprop linearizes the outer chain, classifies each summand and looks the multiset up in a table of variants, guarded by cross-summand consistency checks (one operand pair, half-width shifts, hilo cross-half products). The high part is emitted as (N)(((2N) op1 * (2N) op2) >> N), for pass_optimize_widening_mul to lower to WIDEN_MULT_EXPR or MULT_HIGHPART_EXPR, and only when the target can multiply at 2N bits. The low part is a plain MULT_EXPR. Matching starts only at the end of a chain; folding at a use in another block could sink a loop-invariant multiply into a loop. Up to LONG_MUL_MAX_EXTRAS leaves that are no long-multiply summand are set aside and re-applied on top of the fold, so a chain feeding a wider sum (acc += mulh (x, y)) still folds. A leaf that does classify is always consumed; a subset search would be exponential. PR tree-optimization/107090 gcc/ChangeLog: * match.pd: Add atom match recognizers for long-multiply (mul_hi, mul_lo, mul_hilo, mul_lolo, mul_hihi, mul_cross_sum, mul_low_accum, mul_carry_cross_sum). * tree-ssa-forwprop.cc (gimple_mul_hi): Declare. (gimple_mul_lo): Likewise. (gimple_mul_hilo): Likewise. (gimple_mul_lolo): Likewise. (gimple_mul_hihi): Likewise. (gimple_mul_cross_sum): Likewise. (gimple_mul_low_accum): Likewise. (gimple_mul_carry_cross_sum): Likewise. (build_mul_high_seq): New, emits (N)(((2N) op1 * (2N) op2) >> N) into a caller-supplied destination. (long_mul_apply_extras): New, combines the preserved addends back on top of the folded multiply. (create_mul_high_seq): New, replaces the statement with the high-part multiply plus any extras. (create_mul_low_seq): New, likewise for the low part. (enum long_mul_kind): New. (enum long_mul_extract): New. (struct long_mul_summand): New. (long_mul_linearize_chain): New, walks the outer add/ior chain into a multiset of leaves. (long_mul_is_lshift_def): New. (long_mul_set_summand): New. (long_mul_classify_carry): New. (long_mul_classify_plus_kinds): New. (long_mul_classify_hi_extract): New. (long_mul_classify_lo_extract): New. (long_mul_classify_shl_extract): New. (long_mul_classify_bare): New. (long_mul_classify_summand): New, classify each summand via the match.pd atoms. (long_mul_summand_compare): New. (struct long_mul_row): New. (long_mul_same_ops): New. (long_mul_is_cross_half): New. (long_mul_hilo_orientation): New, orientation of a mul_hilo capture relative to (op0, op1). (long_mul_canonical_ops): New. (long_mul_check_consistency): New, cross-summand consistency check (operand pairing, half-width shifts, hilo cross-half). (long_mul_signature_matches): New. (long_mul_hint_shared_intermediate): New, dump-file hint pointing at a shared inner addition. (long_mul_classify_match): New, looks a summand multiset up in long_mul_table and runs the per-row checks. (long_mul_classify_chain): New, linearize plus classify plus table lookup; sets aside leaves that classify as no summand. (match_long_mul): New, top-level entry: starts only at a chain end, classifies the chain, and dispatches to create_mul_high_seq / create_mul_low_seq with any preserved addends. (pass_forwprop::execute): Call match_long_mul on PLUS_EXPR and BIT_IOR_EXPR statements. gcc/testsuite/ChangeLog: * gcc.dg/torture/long-mul-64-run.c: New test. * gcc.dg/tree-ssa/long-mul-carry.c: New test. * gcc.dg/tree-ssa/long-mul-extra-addend.c: New test. * gcc.target/aarch64/long_mul.c: New test. * gcc.target/i386/long_mul.c: New test. Co-authored-by: Philipp Tomsich <[email protected]>
