https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107090
--- Comment #19 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:f1ea3d58f0caf819042b0ca3981af1219a8fb461 commit r17-2952-gf1ea3d58f0caf819042b0ca3981af1219a8fb461 Author: Konstantinos Eleftheriou <[email protected]> Date: Wed Jul 8 06:58:21 2026 -0700 forwprop, widening_mul: Fold longhand wide-multiply idioms [PR107090] Portable code computing a 2N-bit product on an N-bit target splits the operands into N/2-bit halves, forms four partial products, and propagates the carries by hand. Fold that longhand back to a widening multiply plus shift for the high part and a MULT_EXPR for the low part: 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) match.pd atoms match the partial-product and carry shapes (including the PHI<base + pow2, base> carry form); forwprop linearizes the outer add/ior chain into a multiset of summands, looks it up in long_mul_table, and gates the rewrite on cross-summand consistency (one operand pair, N/2-bit shifts, hilo cross-half products) and a per-row extra check. Twelve rows cover six high-part and six low-part carry shapes. Emit (N)(((2N) op1 * (2N) op2) >> N), which pass_optimize_widening_mul lowers to WIDEN_MULT_EXPR or MULT_HIGHPART_EXPR; where 2N is unsupported (e.g. OImode for 128x128), lower_long_mul_high_chain resynthesizes the longhand at N precision so 2N is never materialized. 750.sealcrypto_r: +25% on AArch64 Neoverse-N1, +59% on x86-64 Zen4. Compile-time impact ~0.1% on gcc/*.cc, confined to forwprop. Bootstrapped and regression-tested (before squash) on AArch64, x86-64, ARM and PowerPC. 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_sum, mul_low_accum, mul_carry_cross_sum, mul_carry_low_sum, mul_carry_low, mul_ladder_sum1, mul_ladder_sum2, mul_ladder_sum3, mul_ladder_part_sum), the cond_carry_add and cond_carry_add_neg recognizers for the 2-arg PHI carry form, one per gcond polarity, and long_mul_high_chain for the emitted chain shape. * tree-ssa-forwprop.cc (gimple_cond_carry_add): Declare. (gimple_cond_carry_add_neg): Likewise. (gimple_mul_hi): Likewise. (gimple_mul_lo): Likewise. (gimple_mul_hilo): Likewise. (gimple_mul_lolo): Likewise. (gimple_mul_hihi): Likewise. (gimple_mul_cross_sum): Likewise. (gimple_mul_low_sum): Likewise. (gimple_mul_low_accum): Likewise. (gimple_mul_carry_cross_sum): Likewise. (gimple_mul_carry_low_sum): Likewise. (gimple_mul_carry_low): Likewise. (gimple_mul_ladder_sum1): Likewise. (gimple_mul_ladder_sum2): Likewise. (gimple_mul_ladder_sum3): Likewise. (gimple_mul_ladder_part_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, most-specific carry atom first. (long_mul_classify_plus_kinds): New, likewise by specificity. (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 a 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_find_summand): 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_check_two_carries): New extra check, validates the two-carry row's carry operands against the canonical (op0, op1). (long_mul_check_low_plus_defer): New extra check, defers the low-plus row while a GT/LT/GE/LE use shares an operand with the PLUS. (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, runs the per-row checks, and gates the high-part emit on optimize_widening_mul_active_p. (long_mul_classify_chain): New, linearize plus classify plus table lookup; sets aside leaves that classify as no summand and takes an optional pre-classified summand. (match_long_mul): New, top-level entry: starts only at a chain end and dispatches to create_mul_high_seq / create_mul_low_seq with any preserved addends. (match_long_mul_phi): New PHI-driven entry, recognizes a cond_carry_add(_neg) PHI and folds the long-multiply shape when the rest of the high-part chain matches. (pass_forwprop::execute): Call match_long_mul on PLUS_EXPR and BIT_IOR_EXPR statements, and match_long_mul_phi on each PHI in the degenerate-PHI walk. * tree-ssa-math-opts.cc (can_widen_to_narrow_p): New. (build_long_mul_partials): New, emits the four partial products using widening or plain multiplies. (emit_long_mul_highpart): New, the high N bits of an N-bit product, as a longhand over (N/2)-bit partials. (combine_long_mul_halves): New, the high N bits of a product of two 2N-bit values given as N-bit halves. (long_mul_op_fits_p): New, true when an operand is provably representable in narrow_prec unsigned bits. (long_mul_split_operand): New, splits an operand into N-bit halves using only N-bit operations. (long_mul_only_low_half_used_p): New. (narrow_long_mul_low_half): New, narrow a 2N low-half-only mult the target cannot expand to an N-bit mult. (narrow_long_mul_operands): New, recurse into chained wide products after a narrowing/lowering. (gimple_long_mul_high_chain): Declare. (lower_long_mul_high_chain): New, lowers the high-part chain to a longhand at narrow precision, splitting each operand into N-bit halves and combining them, then narrowing or dropping the residual 2N mult via the helpers. (optimize_widening_mul_active_p): New, shared gate used by pass_optimize_widening_mul::gate and by the forwprop long-multiply recognizer. Return false when optimize_debug. (math_opts_dom_walker::after_dom_children): Dispatch to lower_long_mul_high_chain on the outer convert. Run narrow_long_mul_low_half on MULT_EXPR before the widen/fma conversion attempts. * tree-ssa-math-opts.h (optimize_widening_mul_active_p): Declare. gcc/testsuite/ChangeLog: * lib/target-supports.exp: Add check_effective_target_oi_mode, which enumerates targets whose mode table declares OImode. * gcc.dg/long-mul-128-Og.c: New test. * gcc.dg/torture/long-mul-128.c: New test. * gcc.dg/torture/long-mul-64-run.c: New test. * gcc.dg/tree-ssa/long-mul-boundary-64.c: New test. * gcc.dg/tree-ssa/long-mul-boundary.c: New test. * gcc.dg/tree-ssa/long-mul-carry.c: New test. * gcc.dg/tree-ssa/long-mul-chain-cse-128.c: New test. * gcc.dg/tree-ssa/long-mul-chain-trunc-128.c: New test. * gcc.dg/tree-ssa/long-mul-extra-addend.c: New test. * gcc.dg/tree-ssa/long-mul-ladder.c: New test. * gcc.dg/tree-ssa/long-mul-low-plus.c: New test. * gcc.dg/tree-ssa/long-mul-partial.c: New test. * gcc.dg/tree-ssa/long-mul-two-carry.c: New test. * gcc.target/aarch64/long_mul.c: New test. * gcc.target/arm/long-mul-thumb1-inline.c: New test. * gcc.target/arm/long-mul-umull.c: New test. * gcc.target/i386/long_mul.c: New test. * gcc.target/i386/widen_mult_high_chain.c: New test. Co-authored-by: Philipp Tomsich <[email protected]>
