[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 #26 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:aac02c9666184d19334a0527ec444b5e55fbd113

commit r17-3443-gaac02c9666184d19334a0527ec444b5e55fbd113
Author: Konstantinos Eleftheriou <[email protected]>
Date:   Thu Jul 9 02:22:54 2026 -0700

    widening_mul: Lower long-multiply chains to inline longhand

    The forwprop long-multiply recognizer canonicalizes longhand
    high-part multiplies into

      lhs = (N) (((2N) op1 * (2N) op2) >> N)

    When the target cannot expand the wide form, lower the chain back to
    a longhand at N precision: (N/2)x(N/2)->N WIDEN_MULT_EXPR partial
    products where the optab exists, plain N-bit MULT_EXPR otherwise
    (value-equivalent, the halves being < 2^(N/2)).  No 2N value is
    materialized in gimple, so the lowering also covers modes with no
    expansion path at all (e.g. the high 128 bits of a 128x128 product
    with OImode in the mode table but no scalar OImode support).

    The longhand is built at narrow precision and converted once to the
    outer convert's lhs type, which conversion merging may have combined
    with a later user cast ((u64) mulh128 (x, y)); value-preserving for
    any integral lhs as the high part is < 2^N.

    An operand wider than N bits (a shared wide product, a sign-extended
    cast) is split into N-bit halves rather than truncated.  The split
    recurses through a chained wide product, reads a widening cast's
    halves from its source, and resolves a 2N value shifted down by N to
    the high half of what was shifted.  An operand that provably fits N
    bits yields a zero high half.  An operand PHI (left by PRE hoisting
    a (T_2N) cast) is split through its arguments and re-merged with two
    new PHIs; one split is shared by all chains reaching the PHI
    (PR126642).

    A 2N product also read outside the chain survives the split.  If
    every use takes only its low N bits it is narrowed to
    (2N) ((N) a * (N) b); a product surviving every lowering is rewritten
    by a closing sweep into the halves its uses read, the high one
    synthesized in longhand (PR126642).  Multiplies for which the target
    has a widening or high-part multiply are left to
    convert_mult_to_widen / convert_mult_to_highpart.

    The recognizer's HIGH_PART emit is gated on
    optimize_widening_mul_active_p, so the chain is emitted only when
    this pass will run to lower an unsupported 2N form; this replaces the
    recognizer's test for an expandable 2N multiply and extends the fold
    to targets without one.  The predicate is false for optimize_debug:
    -Og runs no widening_mul pass.

    Bootstrapped and regression-tested on AArch64, x86-64, i686, ARM and
    PowerPC.

            PR tree-optimization/107090
            PR tree-optimization/126642

    gcc/ChangeLog:

            * match.pd (long_mul_high_chain): New atom for the emitted
high-part chain.
            * tree-ssa-forwprop.cc (long_mul_classify_match): Gate the
            HIGH_PART wide-chain emit on optimize_widening_mul_active_p
            rather than on the target having a 2N multiply.
            * 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.
            (struct long_mul_halves): New; the halves an operand PHI was
            split into.
            (struct long_mul_arg_split): New; an argument of an operand PHI
            with the statements that split it.
            (long_mul_split_phi): New; splits an operand PHI by splitting its
            arguments and merging the halves with two new PHIs. Record the
            halves and reuse them for the next consumer of the same PHI.
            (long_mul_high_half_uses): New; collects the `>> N' uses forming
            a product's high half.
            (long_mul_only_low_half_used_p): New.
            (unexpandable_long_mul_p): New; true for a 2N multiply in a mode
            the target cannot multiply.
            (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.
            (finish_long_mul_low_half): New; narrows or removes a 2N mult
            whose high half is synthesized elsewhere.
            (narrow_long_mul_halves): New; rewrites a 2N multiply into the
            N-bit halves its uses read.
            (gimple_long_mul_high_chain): Declare.
            (lower_long_mul_high_chain): New; lowers the high-part chain to a
            longhand at narrow precision. Split each operand into N-bit
            halves and combine, handling an operand wider than narrow_prec
            instead of rejecting it. Narrow or drop the residual 2N mult via
            the helpers and recurse into its operands.
            (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.
            (pass_optimize_widening_mul::execute): Sweep the function for
            multiplies left in a mode the target cannot expand. Scope the
            record of split operand PHIs to one run of the pass.
            * tree-ssa-math-opts.h (optimize_widening_mul_active_p): Declare.

    gcc/testsuite/ChangeLog:

            * gcc.dg/torture/long-mul-64-run.c: Add near-miss variants of the
            idiom, cross-checked against their literal meaning.
            * gcc.dg/tree-ssa/long-mul-carry.c: Add scans for the high-part
            chain lowering and its dump message. Exclude sparc/hppa from
            the chain-lowering scan.
            * gcc.dg/tree-ssa/long-mul-ladder.c: Likewise.
            * lib/target-supports.exp (check_effective_target_oi_mode): New;
            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/tree-ssa/long-mul-chain-cse-128.c: New test.
            * gcc.dg/tree-ssa/long-mul-chain-trunc-128.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-phi-split.c: New test.
            * gcc.target/i386/long-mul-sweep.c: New test.
            * gcc.target/i386/widen_mult_high_chain.c: New test.

    Co-authored-by: Philipp Tomsich <[email protected]>