[Bug tree-optimization/107090] [aarch64] sequence logic should be combined with mul and umulh

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]>