[gcc r17-2952] forwprop, widening_mul: Fold longhand wide-multiply idioms [PR107090]
Philipp Tomsich via Gcc-cvs <[email protected]> Tue, 4 Aug 2026 15:37:00 +0000 (GMT)
| Newsgroups | gmane.comp.gcc.cvs |
|---|---|
| Message-ID | <[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]> Diff: --- gcc/match.pd | 198 ++++ gcc/testsuite/gcc.dg/long-mul-128-Og.c | 26 + gcc/testsuite/gcc.dg/torture/long-mul-128.c | 121 ++ gcc/testsuite/gcc.dg/torture/long-mul-64-run.c | 180 +++ .../gcc.dg/tree-ssa/long-mul-boundary-64.c | 417 +++++++ gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c | 394 +++++++ gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c | 385 +++++++ .../gcc.dg/tree-ssa/long-mul-chain-cse-128.c | 52 + .../gcc.dg/tree-ssa/long-mul-chain-trunc-128.c | 80 ++ .../gcc.dg/tree-ssa/long-mul-extra-addend.c | 63 ++ gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c | 333 ++++++ gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c | 54 + gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c | 193 ++++ gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c | 140 +++ gcc/testsuite/gcc.target/aarch64/long_mul.c | 100 ++ .../gcc.target/arm/long-mul-thumb1-inline.c | 47 + gcc/testsuite/gcc.target/arm/long-mul-umull.c | 73 ++ gcc/testsuite/gcc.target/i386/long_mul.c | 100 ++ .../gcc.target/i386/widen_mult_high_chain.c | 32 + gcc/testsuite/lib/target-supports.exp | 20 + gcc/tree-ssa-forwprop.cc | 1197 +++++++++++++++++++- gcc/tree-ssa-math-opts.cc | 492 +++++++- gcc/tree-ssa-math-opts.h | 2 + 23 files changed, 4690 insertions(+), 9 deletions(-) diff --git a/gcc/match.pd b/gcc/match.pd index 344883d6ea4c..4d47317b95e2 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -6450,6 +6450,31 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (lshift (convert (bit_xor (convert:boolean_type_node @0) { boolean_true_node; })) { shift; }))))))) +/* Recognize a 2-arg PHI of the form + PHI<base + pow2, base> + guarded by an unsigned compare on (@0, @1). @1 is captured without + further structure; the long-mul fold in tree-ssa-forwprop.cc + classifies it to drive a PHI-form carry summand. The consumer + treats the carry as strict @0 > @1, so each polarity's compare + must encode that same condition: + cond_carry_add: true edge selects (base + pow2), so the + compare itself must be @0 > @1. + cond_carry_add_neg: true edge selects base, so the compare's + negation must be @0 > @1, i.e. the + compare itself must be @0 <= @1. + Matches the 2-arg PHI form via cond^. */ +(if (INTEGRAL_TYPE_P (type) + && TYPE_UNSIGNED (type) + && type_has_mode_precision_p (type)) + (match (cond_carry_add @0 @1 @2 @3) + (cond^ (gt @0 @1) (plus @2 integer_pow2p@3) @2)) + (match (cond_carry_add @0 @1 @2 @3) + (cond^ (lt @1 @0) (plus @2 integer_pow2p@3) @2)) + (match (cond_carry_add_neg @0 @1 @2 @3) + (cond^ (le @0 @1) @2 (plus @2 integer_pow2p@3))) + (match (cond_carry_add_neg @0 @1 @2 @3) + (cond^ (ge @1 @0) @2 (plus @2 integer_pow2p@3)))) + /* (a > 1) ? 0 : (cast)a is the same as (cast)(a == 1) for unsigned types. */ (simplify @@ -12247,6 +12272,179 @@ and, INTEGER_CST@2) INTEGER_CST@3) (if (compare_tree_int (@sub1, 1) == 0))) +#if GIMPLE +/* Match low and high parts of longhand multiplication. + Given a 2N-bit unsigned type, x = xh*2^N + xl and y = yh*2^N + yl, + where xh, xl, yh, yl are N-bit halves extracted via shifts and masks. */ + +/* High half: op >> N. */ +(match (mul_hi @op @0) + (rshift @op INTEGER_CST@0) + (with { + tree op_type = TREE_TYPE (@op); } + (if (INTEGRAL_TYPE_P (op_type) + && TYPE_UNSIGNED (op_type) + && TYPE_PRECISION (op_type) % 2 == 0 + && tree_fits_uhwi_p (@0) + && tree_to_uhwi (@0) == TYPE_PRECISION (op_type) / 2)))) +/* Low half: op & mask. */ +(match (mul_lo @op @0) + (bit_and @op INTEGER_CST@0) + (with { + tree op_type = TREE_TYPE (@op); } + (if (INTEGRAL_TYPE_P (op_type) + && TYPE_UNSIGNED (op_type) + && TYPE_PRECISION (op_type) % 2 == 0 + && tree_fits_uhwi_p (@0) + && tree_to_uhwi (@0) == wi::mask ( + TYPE_PRECISION (op_type) / 2, + false, + TYPE_PRECISION (op_type)))))) +/* Cross product: high(op0) * low(op1). */ +(match (mul_hilo @op0 @op1 @0 @1) + (mult:c + (mul_hi @op0 INTEGER_CST@0) + (mul_lo @op1 INTEGER_CST@1))) +/* Low-low product: low(op0) * low(op1). */ +(match (mul_lolo @op0 @op1 @0) + (mult:c + (mul_lo @op0 INTEGER_CST@0) + (mul_lo @op1 INTEGER_CST@0))) +/* High-high product: high(op0) * high(op1). */ +(match (mul_hihi @op0 @op1 @0) + (mult:c + (mul_hi @op0 INTEGER_CST@0) + (mul_hi @op1 INTEGER_CST@0))) +/* Cross sum: xh*yl + xl*yh. + Note: matches any PLUS; operands are validated as actual cross + products by the forwprop consumer (long_mul_check_consistency). */ +(match (mul_cross_sum @mul_hilo0 @mul_hilo1) + (plus:c @mul_hilo0 @mul_hilo1)) +/* Low sum: cross_sum + (xl*yl >> N). */ +(match (mul_low_sum @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) + (plus:c + (mul_cross_sum @mul_hilo0 @mul_hilo1) + (mul_hi + (mul_lolo @op0 @op1 INTEGER_CST@1) + INTEGER_CST@0))) +/* Carry from low-sum overflow: (cast?) (hilo > low_sum) << N. + No explicit type/width guard needed: mul_low_sum delegates to + mul_cross_sum + mul_hi + mul_lolo, which provide deep structural + constraints, and @0 ties the shift amount to the inner constants. */ +(match (mul_carry_low_sum @op0 @op1 @mul_hilo0 @mul_hilo1 @mul_hilo2 @0 @1) + (lshift + (convert? (gt + @mul_hilo0 + (mul_low_sum @op0 @op1 @mul_hilo1 @mul_hilo2 INTEGER_CST@0 + INTEGER_CST@1))) + INTEGER_CST@0)) +/* Carry from cross-sum overflow: (cast?) (hilo > cross_sum) << N. + Explicit guard required because mul_cross_sum is just (plus:c @0 @1) + with no inherent type or halfwidth constraint. */ +(match (mul_carry_cross_sum @mul_hilo0 @mul_hilo1 @mul_hilo2 @0) + (lshift + (convert? (gt + @mul_hilo0 + (mul_cross_sum @mul_hilo1 @mul_hilo2))) + INTEGER_CST@0) + (with { + tree op_type = TREE_TYPE (@mul_hilo0); } + (if (INTEGRAL_TYPE_P (op_type) + && TYPE_UNSIGNED (op_type) + && TYPE_PRECISION (op_type) % 2 == 0 + && tree_fits_uhwi_p (@0) + && tree_to_uhwi (@0) == TYPE_PRECISION (op_type) / 2)))) +/* Carry from addition overflow: (cast?) (a > a + b). + :c on gt also matches the LT form: (cast?) (a + b < a). */ +(match (mul_carry_low @0 @1) + (convert? + (gt:c @0 (plus:c @1 @0))) + (with { tree op_type = TREE_TYPE (@0); } + (if (INTEGRAL_TYPE_P (op_type) && TYPE_UNSIGNED (op_type))))) +/* Low accumulate: (xl*yl >> N) + (cross_sum & mask). */ +(match (mul_low_accum @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) + (plus:c + (mul_hi + (mul_lolo @op0 @op1 INTEGER_CST@0) + INTEGER_CST@1) + (mul_lo (mul_cross_sum @mul_hilo0 @mul_hilo1) INTEGER_CST@0))) +/* Ladder sum form 1: (hilo0 & mask) + hilo1 + (xl*yl >> N). + First variant: @mul_hilo1 is inside the inner plus:c alongside + (mul_lo ...). */ +(match (mul_ladder_sum1 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) + (plus:c + (plus:c + (mul_lo + @mul_hilo0 + INTEGER_CST@0) + @mul_hilo1) + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1))) +/* Second variant: @mul_hilo1 is the outermost addend and could match + anything, so guard that its definition is a MULT_EXPR. */ +(match (mul_ladder_sum1 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) + (plus:c + (plus:c + (mul_lo @mul_hilo0 INTEGER_CST@0) + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1)) + @mul_hilo1) + (with { + tree_code mul_hilo_code = TREE_CODE (@mul_hilo1); + tree_code rhs_code = ERROR_MARK; + if (mul_hilo_code == SSA_NAME) + { + gimple *def = SSA_NAME_DEF_STMT (@mul_hilo1); + if (def && gimple_code (def) == GIMPLE_ASSIGN) + rhs_code = gimple_assign_rhs_code (def); + } } + (if (rhs_code == MULT_EXPR)))) +/* Partial ladder sum: (xl*yl >> N) + hilo. */ +(match (mul_ladder_part_sum @op0 @op1 @mul_hilo0 @0 @1) + (plus:c + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1) + @mul_hilo0)) +/* Ladder sum form 2: (ladder_part_sum & mask) + hilo. */ +(match (mul_ladder_sum2 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) + (plus:c + (mul_lo + (mul_ladder_part_sum @op0 @op1 @mul_hilo0 INTEGER_CST@0 INTEGER_CST@1) + INTEGER_CST@0) + @mul_hilo1)) +/* Ladder sum form 3: (hilo0 & mask) + (hilo1 & mask) + (xl*yl >> N). */ +(match (mul_ladder_sum3 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) + (plus:c + (plus:c + (mul_lo @mul_hilo0 INTEGER_CST@0) + (mul_lo @mul_hilo1 INTEGER_CST@0)) + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1))) +(match (mul_ladder_sum3 @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1) + (plus:c + (plus:c + (mul_lo @mul_hilo0 INTEGER_CST@0) + (mul_hi (mul_lolo @op0 @op1 INTEGER_CST@0) INTEGER_CST@1)) + (mul_lo @mul_hilo1 INTEGER_CST@0))) +/* Long-multiply high-part emit chain produced by forwprop's recognizer: + + (N) ((2N) op1 * (2N) op2) >> N + + `(convert? @X)` accepts a bare operand (PRE may hoist the (T_2N) cast + out into a PHI on a shared slot). The lowering splits an operand + wider than T_N into T_N halves rather than truncating it. Wide type + must be unsigned mode-precision integer of even width; BITINT_TYPE is + refused. */ +(match (long_mul_high_chain @0 @1) + (convert (rshift (mult:c@3 (convert? @0) (convert? @1)) INTEGER_CST@2)) + (with { + tree wide_type = TREE_TYPE (@3); } + (if (INTEGRAL_TYPE_P (wide_type) + && TYPE_UNSIGNED (wide_type) + && type_has_mode_precision_p (wide_type) + && TREE_CODE (wide_type) != BITINT_TYPE + && TYPE_PRECISION (wide_type) >= 8 + && (TYPE_PRECISION (wide_type) & 3) == 0 + && tree_fits_uhwi_p (@2) + && tree_to_uhwi (@2) * 2 == TYPE_PRECISION (wide_type))))) +#endif + /* Floatint point/integer comparison and integer->integer or floating point -> float point conversion. */ (match (cond_expr_convert_p @0 @2 @3 @6) diff --git a/gcc/testsuite/gcc.dg/long-mul-128-Og.c b/gcc/testsuite/gcc.dg/long-mul-128-Og.c new file mode 100644 index 000000000000..3a9bd703c116 --- /dev/null +++ b/gcc/testsuite/gcc.dg/long-mul-128-Og.c @@ -0,0 +1,26 @@ +/* { dg-do compile { target int128 } } */ +/* { dg-options "-Og -fexpensive-optimizations" } */ + +/* The -Og pipeline does not run pass_optimize_widening_mul, so the + long-multiply fold must not emit a 2N wide-multiply chain here: + nothing would lower it before expansion. */ + +typedef __uint128_t u128; + +u128 +mulh (u128 x, u128 y) +{ + u128 x_hi = x >> 64; + u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF; + u128 y_hi = y >> 64; + u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF; + u128 mulhilo = x_hi * y_lo; + u128 mullohi = x_lo * y_hi; + u128 cross_sum = mulhilo + mullohi; + u128 mullolo = x_lo * y_lo; + u128 shrlolo = mullolo >> 64; + u128 add_cross_sum = cross_sum + shrlolo; + int carry = add_cross_sum < mulhilo; + u128 cond = ((u128) carry << 64) + x_hi * y_hi; + return cond + (add_cross_sum >> 64); +} diff --git a/gcc/testsuite/gcc.dg/torture/long-mul-128.c b/gcc/testsuite/gcc.dg/torture/long-mul-128.c new file mode 100644 index 000000000000..1be4dec1141c --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/long-mul-128.c @@ -0,0 +1,121 @@ +/* { dg-do run { target int128 } } */ + +/* Runtime correctness for the full 128-bit pipeline: forwprop folds the + longhand to (u256) x * (u256) y >> 128 and widening_mul lowers it back + to a 128-bit longhand. mulh_reference stays unfolded via volatiles. */ + +typedef __uint128_t u128; + +/* The recognized longhand high-part multiply, shared by the callers below. + static inline so each caller inlines a copy, exposing its own chain to + forwprop. */ +static inline u128 +mulh_inline (u128 x, u128 y) +{ + u128 x_hi = x >> 64; + u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF; + u128 y_hi = y >> 64; + u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF; + u128 mulhilo = x_hi * y_lo; + u128 mullohi = x_lo * y_hi; + u128 cross_sum = mulhilo + mullohi; + u128 mullolo = x_lo * y_lo; + u128 shrlolo = mullolo >> 64; + u128 add_cross_sum = cross_sum + shrlolo; + int carry = add_cross_sum < mulhilo; + u128 cond = ((u128) carry << 64) + x_hi * y_hi; + return cond + (add_cross_sum >> 64); +} + +/* Standalone folded instance (noipa keeps it distinct from the inline + copies), validated against the unfolded reference. */ +__attribute__((noipa)) u128 +mulh_folded (u128 x, u128 y) +{ + return mulh_inline (x, y); +} + +__attribute__((noipa)) u128 +mulh_reference (u128 x, u128 y) +{ + volatile u128 x_hi = x >> 64; + volatile u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF; + volatile u128 y_hi = y >> 64; + volatile u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF; + u128 mulhilo = x_hi * y_lo; + u128 mullohi = x_lo * y_hi; + u128 cross_sum = mulhilo + mullohi; + u128 mullolo = x_lo * y_lo; + u128 shrlolo = mullolo >> 64; + u128 add_cross_sum = cross_sum + shrlolo; + int carry = add_cross_sum < mulhilo; + u128 cond = ((u128) carry << 64) + x_hi * y_hi; + return cond + (add_cross_sum >> 64); +} + +/* Two mulh calls sharing an operand: inlining exposes both chains and + VN CSEs the shared (u256) cast. Guard that lowering the first chain + does not free a cast the second still references. */ +__attribute__((noipa)) u128 +mulh_shared_xor (u128 x, u128 y, u128 z) +{ + return mulh_inline (x, y) ^ mulh_inline (x, z); +} + +/* One chain's high half feeding the next, first high part also live. After + recognition the second chain multiplies by the first product shifted down; + truncating that shift would leave the product live past its own lowering. */ +__attribute__((noipa)) u128 +mulh_chain_high (u128 x, u128 y, u128 z, u128 *first) +{ + u128 h1 = mulh_inline (x, y); + *first = h1; + return mulh_inline (h1, z); +} + +/* Squaring: VN CSEs the two (u256) casts of x, so lowering sees the + same stmt on both operand-cast slots. */ +__attribute__((noipa)) u128 +mulh_square (u128 x) +{ + return mulh_inline (x, x); +} + +int +main (void) +{ + static const u128 vals[] = { + 0, + 1, + (u128)0xFFFFFFFFFFFFFFFF, /* low half all-ones */ + ((u128)1 << 64), /* 2^64 */ + ((u128)1 << 127), /* high bit */ + ~(u128)0, /* all-ones */ + ((u128)0xDEADBEEFCAFEBABE << 64) | 0x0123456789ABCDEF, + ((u128)0x8000000000000001 << 64) | 0xFFFFFFFFFFFFFFFE, + }; + const unsigned n = sizeof (vals) / sizeof (vals[0]); + + for (unsigned i = 0; i < n; i++) + for (unsigned j = 0; j < n; j++) + { + u128 x = vals[i], y = vals[j]; + if (mulh_folded (x, y) != mulh_reference (x, y)) + __builtin_abort (); + for (unsigned k = 0; k < n; k++) + { + u128 z = vals[k]; + u128 want = mulh_reference (x, y) ^ mulh_reference (x, z); + if (mulh_shared_xor (x, y, z) != want) + __builtin_abort (); + u128 first = 0; + u128 h1 = mulh_reference (x, y); + if (mulh_chain_high (x, y, z, &first) != mulh_reference (h1, z) + || first != h1) + __builtin_abort (); + } + if (mulh_square (x) != mulh_reference (x, x)) + __builtin_abort (); + } + return 0; +} diff --git a/gcc/testsuite/gcc.dg/torture/long-mul-64-run.c b/gcc/testsuite/gcc.dg/torture/long-mul-64-run.c new file mode 100644 index 000000000000..0824f453630a --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/long-mul-64-run.c @@ -0,0 +1,180 @@ +/* { dg-do run { target int128 } } */ + +/* Runtime behavior of the recognizer on the longhand 64x64 high-part + idiom. Two groups: shapes that must fold, checked against a 128-bit + reference multiply, and near misses that must not fold (each violates + one recognizer guard: low mask value, carry shift tie, cross-half + orientation, operand consistency), checked against their literal + meaning computed behind volatiles. Either way a misfold aborts. */ + +typedef __UINT64_TYPE__ uint64_t; +typedef unsigned __int128 uint128_t; + +/* The genuine idiom. */ +__attribute__((noipa)) uint64_t +mulh_good (uint64_t x, uint64_t y) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + uint64_t carry = (uint64_t) (hilo > low_sum) << 32; + return xh * yh + (low_sum >> 32) + carry; +} + +/* The idiom with an extra addend appended after the full chain: the + folded form must keep the addend on top of the wide multiply. */ +__attribute__((noipa)) uint64_t +mulh_acc (uint64_t x, uint64_t y, uint64_t acc) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + int carry_out = hilo > low_sum; + uint64_t carry = (uint64_t) carry_out << 32; + return xh * yh + (low_sum >> 32) + carry + acc; +} + +/* Same, with the extra addend interleaved into the middle of the + chain. */ +__attribute__((noipa)) uint64_t +mulh_acc_interleaved (uint64_t x, uint64_t y, uint64_t acc) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + int carry_out = hilo > low_sum; + uint64_t carry = (uint64_t) carry_out << 32; + return ((xh * yh + acc) + (low_sum >> 32)) + carry; +} + +/* Wrong low mask (0xFFFF, not the half mask). */ +__attribute__((noipa)) uint64_t +mulh_wrong_mask (uint64_t x, uint64_t y) +{ + uint64_t xl = x & 0xFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + uint64_t carry = (uint64_t) (hilo > low_sum) << 32; + return xh * yh + (low_sum >> 32) + carry; +} + +/* Wrong carry position (<< 16, not the half width). */ +__attribute__((noipa)) uint64_t +mulh_wrong_carry_shift (uint64_t x, uint64_t y) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + uint64_t carry = (uint64_t) (hilo > low_sum) << 16; + return xh * yh + (low_sum >> 32) + carry; +} + +/* Doubled cross term (hilo + hilo, same orientation). */ +__attribute__((noipa)) uint64_t +mulh_doubled_cross (uint64_t x, uint64_t y) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t cross = hilo + hilo; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + uint64_t carry = (uint64_t) (hilo > low_sum) << 32; + return xh * yh + (low_sum >> 32) + carry; +} + +/* Third operand sneaks into one cross term. */ +__attribute__((noipa)) uint64_t +mulh_mixed_ops (uint64_t x, uint64_t y, uint64_t z) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t zh = z >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * zh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + uint64_t carry = (uint64_t) (hilo > low_sum) << 32; + return xh * yh + (low_sum >> 32) + carry; +} + +/* What each (mis)shaped source literally means, computed behind + volatiles so no folding applies. */ +__attribute__((noipa)) uint64_t +ref_eval (uint64_t x, uint64_t y, uint64_t z, int variant) +{ + volatile uint64_t vx = x, vy = y, vz = z; + uint64_t xh = vx >> 32, yl0 = vy & 0xFFFFFFFF, yh = vy >> 32, zh = vz >> 32; + uint64_t xl, yl; + switch (variant) + { + case 1: xl = vx & 0xFFFF; yl = vy & 0xFFFF; break; + default: xl = vx & 0xFFFFFFFF; yl = yl0; break; + } + uint64_t hilo = xh * yl; + uint64_t lohi; + switch (variant) + { + case 3: lohi = hilo; break; + case 4: lohi = xl * zh; break; + default: lohi = xl * yh; break; + } + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + uint64_t shift = (variant == 2) ? 16 : 32; + uint64_t carry = (uint64_t) (hilo > low_sum) << shift; + return xh * yh + (low_sum >> 32) + carry; +} + +int +main (void) +{ + static const uint64_t vals[] = { + 0, 1, 0xFFFFFFFFULL, 0x100000000ULL, 0xFFFFFFFFFFFFFFFFULL, + 0xDEADBEEFCAFEBABEULL, 0x8000000080000000ULL, 0x00000001FFFFFFFFULL + }; + const int n = sizeof (vals) / sizeof (vals[0]); + for (int i = 0; i < n; i++) + for (int j = 0; j < n; j++) + { + uint64_t x = vals[i], y = vals[j], z = vals[(i + j) % n]; + uint64_t hi = (uint64_t) (((uint128_t) x * y) >> 64); + if (mulh_good (x, y) != hi) + __builtin_abort (); + if (mulh_acc (x, y, z) != hi + z) + __builtin_abort (); + if (mulh_acc_interleaved (x, y, z) != hi + z) + __builtin_abort (); + if (mulh_wrong_mask (x, y) != ref_eval (x, y, z, 1)) + __builtin_abort (); + if (mulh_wrong_carry_shift (x, y) != ref_eval (x, y, z, 2)) + __builtin_abort (); + if (mulh_doubled_cross (x, y) != ref_eval (x, y, z, 3)) + __builtin_abort (); + if (mulh_mixed_ops (x, y, z) != ref_eval (x, y, z, 4)) + __builtin_abort (); + } + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c new file mode 100644 index 000000000000..d191f2217afb --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c @@ -0,0 +1,417 @@ +/* { dg-do run } */ +/* { dg-require-effective-target int128 } */ +/* { dg-options "-O3" } */ + +typedef __UINT64_TYPE__ uint64_t; +typedef unsigned __int128 uint128_t; + +/* Reference: high part of 64x64 -> 128 multiply. */ +__attribute__((noipa)) +uint64_t mulh_ref (uint64_t x, uint64_t y) +{ + return (uint64_t)(((uint128_t)x * y) >> 64); +} + +/* Carry pattern for high part. */ +__attribute__((noipa)) +uint64_t mulh_carry (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + uint64_t mulhilo = x_hi * y_lo; + uint64_t mullohi = x_lo * y_hi; + uint64_t cross_sum = mulhilo + mullohi; + uint64_t mullolo = x_lo * y_lo; + uint64_t shrlolo = mullolo >> 32; + uint64_t add_cross_sum = cross_sum + shrlolo; + int carry = add_cross_sum < mulhilo; + uint64_t cond = ((uint64_t) carry << 32) + x_hi * y_hi; + uint64_t add = cond + (add_cross_sum >> 32); + + return add; +} + +/* Ladder pattern for high part. */ +__attribute__((noipa)) +uint64_t mulh_ladder (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_lo = y & 0xFFFFFFFFUL; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t t0 = y_lo * x_lo; + uint64_t t1 = y_lo * x_hi; + uint64_t t2 = y_hi * x_lo; + uint64_t t3 = y_hi * x_hi; + uint64_t t0_hi = t0 >> 32; + uint64_t u0 = t0_hi + t1; + uint64_t u0_lo = u0 & 0xFFFFFFFFUL; + uint64_t u0_hi = u0 >> 32; + uint64_t u1 = u0_lo + t2; + uint64_t u1_hi = u1 >> 32; + uint64_t u2 = u0_hi + t3; + uint64_t hw = u2 + u1_hi; + + return hw; +} + +/* Ladder-long full multiply (both high and low parts). */ +__attribute__((noipa)) +void full_mul (uint64_t x, uint64_t y, uint64_t *p) +{ + uint64_t xl = x & 0xFFFFFFFFUL; + uint64_t xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFFUL; + uint64_t yh = y >> 32; + uint64_t mulll = xl * yl; + uint64_t mullh = xl * yh; + uint64_t mulhl = xh * yl; + uint64_t mulhh = xh * yh; + uint64_t shr8 = mulll >> 32; + uint64_t conv10 = mullh & 0xFFFFFFFFUL; + uint64_t add = shr8 + conv10; + uint64_t conv12 = mulhl & 0xFFFFFFFFUL; + uint64_t add13 = add + conv12; + uint64_t shr14 = add13 >> 32; + uint64_t shr15 = mullh >> 32; + uint64_t add16 = mulhh + shr15; + uint64_t shr17 = mulhl >> 32; + uint64_t add18 = add16 + shr17; + uint64_t add19 = add18 + shr14; + p[1] = add19; + uint64_t add_13_shl = add13 << 32; + uint64_t and17 = mulll & 0xFFFFFFFFUL; + uint64_t or_val = add_13_shl | and17; + p[0] = or_val; +} + +/* Two-carry pattern for high part. */ +__attribute__((noipa)) +uint64_t mulh_two_carry (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + + uint64_t lolo = x_lo * y_lo; + uint64_t hilo = x_hi * y_lo; + uint64_t lohi = x_lo * y_hi; + uint64_t hihi = x_hi * y_hi; + + uint64_t cross_sum = hilo + lohi; + uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32; + + uint64_t cross_shifted = cross_sum << 32; + uint64_t low_result = lolo + cross_shifted; + uint64_t low_carry = (uint64_t)(low_result < cross_shifted); + + uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry; + + return high; +} + +/* Two-carry full multiply (both high and low parts). */ +__attribute__((noipa)) +void full_mul_two_carry (uint64_t x, uint64_t y, uint64_t *p) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + + uint64_t lolo = x_lo * y_lo; + uint64_t hilo = x_hi * y_lo; + uint64_t lohi = x_lo * y_hi; + uint64_t hihi = x_hi * y_hi; + + uint64_t cross_sum = hilo + lohi; + uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32; + + uint64_t cross_shifted = cross_sum << 32; + uint64_t low_result = lolo + cross_shifted; + uint64_t low_carry = (uint64_t)(low_result < cross_shifted); + + uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry; + + p[0] = low_result; + p[1] = high; +} + +/* Carry-long pattern for high part. */ +__attribute__((noipa)) +uint64_t mulh_carry_long (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t x_hi = x >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFFUL; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint64_t interm = cross_sum_hi + y_hi_x_hi; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t interm_plus_carry = interm + carry; + return interm_plus_carry + low_accum_hi; +} + +/* Carry-long full multiply (both high and low parts). */ +__attribute__((noipa)) +void full_mul_carry_long (uint64_t x, uint64_t y, uint64_t *p) +{ + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t x_hi = x >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFFUL; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint64_t upper_mid = y_hi_x_hi + carry; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t upper_mid_with_cross = upper_mid + cross_sum_hi; + p[1] = upper_mid_with_cross + low_accum_hi; + uint64_t low_accum_shifted = low_accum << 32; + uint64_t y_lo_x_lo_lo = y_lo_x_lo & 0xFFFFFFFFUL; + p[0] = low_accum_shifted | y_lo_x_lo_lo; +} + +/* Ladder-long pattern for high part. */ +__attribute__((noipa)) +uint64_t mulh_ladder_long (uint64_t x, uint64_t y) +{ + uint64_t xl = x & 0xFFFFFFFFUL; + uint64_t xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFFUL; + uint64_t yh = y >> 32; + uint64_t mulll = xl * yl; + uint64_t mullh = xl * yh; + uint64_t mulhl = xh * yl; + uint64_t mulhh = xh * yh; + uint64_t shr8 = mulll >> 32; + uint64_t conv10 = mullh & 0xFFFFFFFFUL; + uint64_t add = shr8 + conv10; + uint64_t conv12 = mulhl & 0xFFFFFFFFUL; + uint64_t add13 = add + conv12; + uint64_t shr14 = add13 >> 32; + uint64_t shr15 = mullh >> 32; + uint64_t add16 = mulhh + shr15; + uint64_t shr17 = mulhl >> 32; + uint64_t add18 = add16 + shr17; + return add18 + shr14; +} + +/* PHI-form, cond_carry_add (strict carry-on-true). */ +__attribute__((noipa)) +uint64_t mulh_carry_phi (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + uint64_t mulhilo = x_hi * y_lo; + uint64_t mullohi = x_lo * y_hi; + uint64_t cross_sum = mulhilo + mullohi; + uint64_t mullolo = x_lo * y_lo; + uint64_t add_cross_sum = cross_sum + (mullolo >> 32); + uint64_t add = x_hi * y_hi + (add_cross_sum >> 32); + if (add_cross_sum < mulhilo) + add += (uint64_t)1 << 32; + return add; +} + +/* PHI-form, cond_carry_add_neg (negated branch, carry-on-false). */ +__attribute__((noipa)) +uint64_t mulh_carry_phi_neg (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + uint64_t mulhilo = x_hi * y_lo; + uint64_t mullohi = x_lo * y_hi; + uint64_t cross_sum = mulhilo + mullohi; + uint64_t mullolo = x_lo * y_lo; + uint64_t add_cross_sum = cross_sum + (mullolo >> 32); + uint64_t add = x_hi * y_hi + (add_cross_sum >> 32); + if (add_cross_sum >= mulhilo) + ; + else + add += (uint64_t)1 << 32; + return add; +} + +/* PHI-form, cond_carry_add written as gt (operand-swapped from lt). */ +__attribute__((noipa)) +uint64_t mulh_carry_phi_gt (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + uint64_t mulhilo = x_hi * y_lo; + uint64_t mullohi = x_lo * y_hi; + uint64_t cross_sum = mulhilo + mullohi; + uint64_t mullolo = x_lo * y_lo; + uint64_t add_cross_sum = cross_sum + (mullolo >> 32); + uint64_t add = x_hi * y_hi + (add_cross_sum >> 32); + if (mulhilo > add_cross_sum) + add += (uint64_t)1 << 32; + return add; +} + +/* PHI-form, cond_carry_add_neg written as le (operand-swapped from ge). */ +__attribute__((noipa)) +uint64_t mulh_carry_phi_le (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + uint64_t mulhilo = x_hi * y_lo; + uint64_t mullohi = x_lo * y_hi; + uint64_t cross_sum = mulhilo + mullohi; + uint64_t mullolo = x_lo * y_lo; + uint64_t add_cross_sum = cross_sum + (mullolo >> 32); + uint64_t add = x_hi * y_hi + (add_cross_sum >> 32); + if (mulhilo <= add_cross_sum) + ; + else + add += (uint64_t)1 << 32; + return add; +} + +/* Low part via PLUS: lolo + (cross_sum << 32) with no comparison. */ +__attribute__((noipa)) +uint64_t mul_low_plus (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + uint64_t lolo = x_lo * y_lo; + uint64_t hilo = x_hi * y_lo; + uint64_t lohi = x_lo * y_hi; + uint64_t cross_sum = hilo + lohi; + uint64_t cross_shifted = cross_sum << 32; + return lolo + cross_shifted; +} + +/* PHI-form, two-carry shape with the low carry as the PHI + (LMK_CARRY_LOW path in match_long_mul_phi). */ +__attribute__((noipa)) +uint64_t mulh_two_carry_low_phi (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + + uint64_t lolo = x_lo * y_lo; + uint64_t hilo = x_hi * y_lo; + uint64_t lohi = x_lo * y_hi; + uint64_t hihi = x_hi * y_hi; + + uint64_t cross_sum = hilo + lohi; + uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32; + uint64_t cross_shifted = cross_sum << 32; + uint64_t low_result = lolo + cross_shifted; + + uint64_t high = hihi + (cross_sum >> 32) + cross_carry; + if (low_result < cross_shifted) + high += 1; + + return high; +} + +int main () +{ + /* Boundary inputs: zero, one, half-word mask, half-word+1, signed max, + unsigned max. */ + uint64_t vals[] = { + 0, 1, 0xFFFFFFFFUL, 0x100000000ULL, + 0x7FFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL + }; + int n = sizeof (vals) / sizeof (vals[0]); + + for (int i = 0; i < n; i++) + for (int j = 0; j < n; j++) + { + uint64_t x = vals[i], y = vals[j]; + uint64_t expected_hi = mulh_ref (x, y); + uint64_t expected_lo = x * y; + + if (mulh_carry (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_ladder (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_two_carry (x, y) != expected_hi) + __builtin_abort (); + + uint64_t p[2]; + full_mul (x, y, p); + if (p[1] != expected_hi) + __builtin_abort (); + if (p[0] != expected_lo) + __builtin_abort (); + + uint64_t q[2]; + full_mul_two_carry (x, y, q); + if (q[1] != expected_hi) + __builtin_abort (); + if (q[0] != expected_lo) + __builtin_abort (); + + if (mulh_carry_long (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_ladder_long (x, y) != expected_hi) + __builtin_abort (); + + uint64_t r[2]; + full_mul_carry_long (x, y, r); + if (r[1] != expected_hi) + __builtin_abort (); + if (r[0] != expected_lo) + __builtin_abort (); + + if (mulh_carry_phi (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_neg (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_gt (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_le (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_two_carry_low_phi (x, y) != expected_hi) + __builtin_abort (); + + if (mul_low_plus (x, y) != expected_lo) + __builtin_abort (); + } + + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c new file mode 100644 index 000000000000..498481a01932 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c @@ -0,0 +1,394 @@ +/* { dg-do run } */ +/* { dg-options "-O3" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; + +/* Reference: high part of 32x32 -> 64 multiply. */ +__attribute__((noipa)) +uint32_t mulh_ref (uint32_t x, uint32_t y) +{ + return (uint32_t)(((uint64_t)x * y) >> 32); +} + +/* Carry pattern for high part. */ +__attribute__((noipa)) +uint32_t mulh_carry (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t shrlolo = mullolo >> 16; + uint32_t add_cross_sum = cross_sum + shrlolo; + int carry = add_cross_sum < mulhilo; + uint32_t cond = ((uint32_t) carry << 16) + x_hi * y_hi; + uint32_t add = cond + (add_cross_sum >> 16); + + return add; +} + +/* Ladder pattern for high part. */ +__attribute__((noipa)) +uint32_t mulh_ladder (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t y_lo = y & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_hi = y >> 16; + uint32_t t0 = y_lo * x_lo; + uint32_t t1 = y_lo * x_hi; + uint32_t t2 = y_hi * x_lo; + uint32_t t3 = y_hi * x_hi; + uint32_t t0_hi = t0 >> 16; + uint32_t u0 = t0_hi + t1; + uint32_t u0_lo = u0 & 0xFFFF; + uint32_t u0_hi = u0 >> 16; + uint32_t u1 = u0_lo + t2; + uint32_t u1_hi = u1 >> 16; + uint32_t u2 = u0_hi + t3; + uint32_t hw = u2 + u1_hi; + + return hw; +} + +/* Ladder-long pattern for full multiplication (both high and low parts). */ +__attribute__((noipa)) +void full_mul (uint32_t x, uint32_t y, uint32_t *p) +{ + uint32_t xl = x & 0xFFFF; + uint32_t xh = x >> 16; + uint32_t yl = y & 0xFFFF; + uint32_t yh = y >> 16; + uint32_t mulll = xl * yl; + uint32_t mullh = xl * yh; + uint32_t mulhl = xh * yl; + uint32_t mulhh = xh * yh; + uint32_t shr8 = mulll >> 16; + uint32_t conv10 = mullh & 0xFFFF; + uint32_t add = shr8 + conv10; + uint32_t conv12 = mulhl & 0xFFFF; + uint32_t add13 = add + conv12; + uint32_t shr14 = add13 >> 16; + uint32_t shr15 = mullh >> 16; + uint32_t add16 = mulhh + shr15; + uint32_t shr17 = mulhl >> 16; + uint32_t add18 = add16 + shr17; + uint32_t add19 = add18 + shr14; + p[1] = add19; + uint32_t add_13_shl = add13 << 16; + uint32_t and17 = mulll & 0xFFFF; + uint32_t or_val = add_13_shl | and17; + p[0] = or_val; +} + +/* Two-carry pattern for high part (32-bit). */ +__attribute__((noipa)) +uint32_t mulh_two_carry (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + + uint32_t lolo = x_lo * y_lo; + uint32_t hilo = x_hi * y_lo; + uint32_t lohi = x_lo * y_hi; + uint32_t hihi = x_hi * y_hi; + + uint32_t cross_sum = hilo + lohi; + uint32_t cross_carry = (uint32_t)(cross_sum < hilo) << 16; + + uint32_t cross_shifted = cross_sum << 16; + uint32_t low_result = lolo + cross_shifted; + uint32_t low_carry = (uint32_t)(low_result < cross_shifted); + + uint32_t high = hihi + (cross_sum >> 16) + cross_carry + low_carry; + + return high; +} + +/* Two-carry full multiply (32-bit, both high and low parts). */ +__attribute__((noipa)) +void full_mul_two_carry (uint32_t x, uint32_t y, uint32_t *p) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + + uint32_t lolo = x_lo * y_lo; + uint32_t hilo = x_hi * y_lo; + uint32_t lohi = x_lo * y_hi; + uint32_t hihi = x_hi * y_hi; + + uint32_t cross_sum = hilo + lohi; + uint32_t cross_carry = (uint32_t)(cross_sum < hilo) << 16; + + uint32_t cross_shifted = cross_sum << 16; + uint32_t low_result = lolo + cross_shifted; + uint32_t low_carry = (uint32_t)(low_result < cross_shifted); + + uint32_t high = hihi + (cross_sum >> 16) + cross_carry + low_carry; + + p[0] = low_result; + p[1] = high; +} + +/* Carry-long pattern for high part. */ +__attribute__((noipa)) +uint32_t mulh_carry_long (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo_x_hi = y_lo * x_hi; + uint32_t y_hi_x_hi = y_hi * x_hi; + uint32_t y_hi_x_lo = y_hi * x_lo; + uint32_t y_lo_x_lo = y_lo * x_lo; + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint32_t carry = (uint32_t) carry_out << 16; + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16; + uint32_t cross_sum_lo = cross_sum & 0xFFFF; + uint32_t cross_sum_hi = cross_sum >> 16; + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint32_t interm = cross_sum_hi + y_hi_x_hi; + uint32_t low_accum_hi = low_accum >> 16; + uint32_t interm_plus_carry = interm + carry; + return interm_plus_carry + low_accum_hi; +} + +/* Carry-long full multiply (both high and low parts). */ +__attribute__((noipa)) +void full_mul_carry_long (uint32_t x, uint32_t y, uint32_t *p) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo_x_hi = y_lo * x_hi; + uint32_t y_hi_x_hi = y_hi * x_hi; + uint32_t y_hi_x_lo = y_hi * x_lo; + uint32_t y_lo_x_lo = y_lo * x_lo; + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint32_t carry = (uint32_t) carry_out << 16; + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16; + uint32_t cross_sum_lo = cross_sum & 0xFFFF; + uint32_t cross_sum_hi = cross_sum >> 16; + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint32_t upper_mid = y_hi_x_hi + carry; + uint32_t low_accum_hi = low_accum >> 16; + uint32_t upper_mid_with_cross = upper_mid + cross_sum_hi; + p[1] = upper_mid_with_cross + low_accum_hi; + uint32_t low_accum_shifted = low_accum << 16; + uint32_t y_lo_x_lo_lo = y_lo_x_lo & 0xFFFF; + p[0] = low_accum_shifted | y_lo_x_lo_lo; +} + +/* Ladder-long pattern for high part. */ +__attribute__((noipa)) +uint32_t mulh_ladder_long (uint32_t x, uint32_t y) +{ + uint32_t xl = x & 0xFFFF; + uint32_t xh = x >> 16; + uint32_t yl = y & 0xFFFF; + uint32_t yh = y >> 16; + uint32_t mulll = xl * yl; + uint32_t mullh = xl * yh; + uint32_t mulhl = xh * yl; + uint32_t mulhh = xh * yh; + uint32_t shr8 = mulll >> 16; + uint32_t conv10 = mullh & 0xFFFF; + uint32_t add = shr8 + conv10; + uint32_t conv12 = mulhl & 0xFFFF; + uint32_t add13 = add + conv12; + uint32_t shr14 = add13 >> 16; + uint32_t shr15 = mullh >> 16; + uint32_t add16 = mulhh + shr15; + uint32_t shr17 = mulhl >> 16; + uint32_t add18 = add16 + shr17; + return add18 + shr14; +} + +/* PHI-form, cond_carry_add (strict carry-on-true). */ +__attribute__((noipa)) +uint32_t mulh_carry_phi (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum < mulhilo) + add += (uint32_t)1 << 16; + return add; +} + +/* PHI-form, cond_carry_add_neg (negated branch, carry-on-false). */ +__attribute__((noipa)) +uint32_t mulh_carry_phi_neg (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum >= mulhilo) + ; + else + add += (uint32_t)1 << 16; + return add; +} + +/* PHI-form, cond_carry_add written as gt (operand-swapped from lt). */ +__attribute__((noipa)) +uint32_t mulh_carry_phi_gt (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (mulhilo > add_cross_sum) + add += (uint32_t)1 << 16; + return add; +} + +/* PHI-form, cond_carry_add_neg written as le (operand-swapped from ge). */ +__attribute__((noipa)) +uint32_t mulh_carry_phi_le (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (mulhilo <= add_cross_sum) + ; + else + add += (uint32_t)1 << 16; + return add; +} + +/* PHI-form, two-carry shape with the low carry as the PHI + (LMK_CARRY_LOW path in match_long_mul_phi). */ +__attribute__((noipa)) +uint32_t mulh_two_carry_low_phi (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + + uint32_t lolo = x_lo * y_lo; + uint32_t hilo = x_hi * y_lo; + uint32_t lohi = x_lo * y_hi; + uint32_t hihi = x_hi * y_hi; + + uint32_t cross_sum = hilo + lohi; + uint32_t cross_carry = (uint32_t)(cross_sum < hilo) << 16; + uint32_t cross_shifted = cross_sum << 16; + uint32_t low_result = lolo + cross_shifted; + + uint32_t high = hihi + (cross_sum >> 16) + cross_carry; + if (low_result < cross_shifted) + high += 1; + + return high; +} + +int main () +{ + /* Boundary inputs: zero, one, half-word mask, half-word+1, signed max, + unsigned max. */ + uint32_t vals[] = { 0, 1, 0xFFFF, 0x10000, 0x7FFFFFFFU, 0xFFFFFFFFU }; + int n = sizeof (vals) / sizeof (vals[0]); + + for (int i = 0; i < n; i++) + for (int j = 0; j < n; j++) + { + uint32_t x = vals[i], y = vals[j]; + uint32_t expected_hi = mulh_ref (x, y); + uint32_t expected_lo = x * y; + + if (mulh_carry (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_ladder (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_two_carry (x, y) != expected_hi) + __builtin_abort (); + + uint32_t p[2]; + full_mul (x, y, p); + if (p[1] != expected_hi) + __builtin_abort (); + if (p[0] != expected_lo) + __builtin_abort (); + + uint32_t q[2]; + full_mul_two_carry (x, y, q); + if (q[1] != expected_hi) + __builtin_abort (); + if (q[0] != expected_lo) + __builtin_abort (); + + if (mulh_carry_long (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_ladder_long (x, y) != expected_hi) + __builtin_abort (); + + uint32_t r[2]; + full_mul_carry_long (x, y, r); + if (r[1] != expected_hi) + __builtin_abort (); + if (r[0] != expected_lo) + __builtin_abort (); + + if (mulh_carry_phi (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_neg (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_gt (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_carry_phi_le (x, y) != expected_hi) + __builtin_abort (); + + if (mulh_two_carry_low_phi (x, y) != expected_hi) + __builtin_abort (); + } + + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c new file mode 100644 index 000000000000..99165656918f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c @@ -0,0 +1,385 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-forwprop-details -fdump-tree-widening_mul-details" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; +typedef struct { uint32_t v[2]; } v2i32; + +/* High part follows the long form + xh*yh + carry + (cross_sum >> N) + (low_accum >> N). */ + +uint64_t mulh_carry (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = cross_sum < y_lo_x_hi; + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint64_t interm = cross_sum_hi + y_hi_x_hi; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t interm_plus_carry = interm + carry; + uint64_t hw64 = interm_plus_carry + low_accum_hi; + + return hw64; +} + +uint64_t mulh_carry_comm (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = x_hi * y_lo; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = x_lo * y_hi; + uint64_t y_lo_x_lo = x_lo * y_lo; + uint64_t cross_sum = y_lo_x_hi + y_hi_x_lo; + int carry_out = (cross_sum < y_lo_x_hi); + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = y_lo_x_lo_hi + cross_sum_lo; + uint64_t inter = y_hi_x_hi + cross_sum_hi; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t interm_plus_carry = carry + inter; + uint64_t hw64 = low_accum_hi + interm_plus_carry; + + return hw64; +} + +uint32_t mulh_carry_32 (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo_x_hi = y_lo * x_hi; + uint32_t y_hi_x_hi = y_hi * x_hi; + uint32_t y_hi_x_lo = y_hi * x_lo; + uint32_t y_lo_x_lo = y_lo * x_lo; + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint32_t carry = (uint32_t) carry_out << 16; + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16; + uint32_t cross_sum_lo = cross_sum & 0xFFFF; + uint32_t cross_sum_hi = cross_sum >> 16; + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint32_t interm = cross_sum_hi + y_hi_x_hi; + uint32_t low_accum_hi = low_accum >> 16; + uint32_t interm_plus_carry = interm + carry; + uint32_t hw64 = interm_plus_carry + low_accum_hi; + + return hw64; +} + +/* The 128-bit variant lowers to longhand in pass_optimize_widening_mul; + no target provides a 256-bit multiply. */ +#ifdef __SIZEOF_INT128__ +__uint128_t mulh_carry_128 (__uint128_t x, __uint128_t y) +{ + __uint128_t x_lo = x & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t x_hi = x >> 64; + __uint128_t y_lo = y & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t y_hi = y >> 64; + __uint128_t y_lo_x_hi = y_lo * x_hi; + __uint128_t y_hi_x_hi = y_hi * x_hi; + __uint128_t y_hi_x_lo = y_hi * x_lo; + __uint128_t y_lo_x_lo = y_lo * x_lo; + __uint128_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = cross_sum < y_lo_x_hi; + __uint128_t carry = (__uint128_t) carry_out << 64; + __uint128_t y_lo_x_lo_hi = y_lo_x_lo >> 64; + __uint128_t cross_sum_lo = cross_sum & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t cross_sum_hi = cross_sum >> 64; + __uint128_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + __uint128_t interm = cross_sum_hi + y_hi_x_hi; + __uint128_t low_accum_hi = low_accum >> 64; + __uint128_t interm_plus_carry = interm + carry; + __uint128_t hw64 = interm_plus_carry + low_accum_hi; + + return hw64; +} +#endif + +void full_mul_carry (uint64_t x, uint64_t y, uint64_t* p) { + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint64_t upper_mid = y_hi_x_hi + carry; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t upper_mid_with_cross = upper_mid + cross_sum_hi; + uint64_t hw64 = upper_mid_with_cross + low_accum_hi; + p[1] = hw64; + uint64_t low_accum_shifted = low_accum << 32; + uint64_t y_lo_x_lo_lo = y_lo_x_lo & 0xFFFFFFFF; + uint64_t lw64 = low_accum_shifted | y_lo_x_lo_lo; + p[0] = lw64; +} + +/* This will be optimized during the second forwprop run. + Disable SLP so the expected fold count is target-independent. */ +__attribute__((optimize("no-tree-slp-vectorize"))) +v2i32 mulh_carry_v2i32 (v2i32 x, v2i32 y) +{ + v2i32 result; + for (int i = 0; i < 2; i++) + { + uint32_t x_lo = x.v[i] & 0xFFFF; + uint32_t y_lo = y.v[i] & 0xFFFF; + uint32_t x_hi = x.v[i] >> 16; + uint32_t y_hi = y.v[i] >> 16; + + uint32_t y_lo_x_hi = y_lo * x_hi; + uint32_t y_hi_x_hi = y_hi * x_hi; + uint32_t y_hi_x_lo = y_hi * x_lo; + uint32_t y_lo_x_lo = y_lo * x_lo; + + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = cross_sum < y_lo_x_hi; + uint32_t carry = (uint32_t) carry_out << 16; + + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16; + uint32_t cross_sum_lo = cross_sum & 0xFFFF; + uint32_t cross_sum_hi = cross_sum >> 16; + + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint32_t interm = cross_sum_hi + y_hi_x_hi; + uint32_t low_accum_hi = low_accum >> 16; + uint32_t interm_plus_carry = interm + carry; + + result.v[i] = interm_plus_carry + low_accum_hi; + } + + return result; +} + +/* High part collapses the cross sum and (xl*yl >> N) into a single + low_sum carrying the overflow compare: + xh*yh + (low_sum >> N) + ((hilo > low_sum) << N). */ + +uint32_t mulh_carry_low_sum (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t shrlolo = mullolo >> 16; + uint32_t low_sum = cross_sum + shrlolo; + int carry = low_sum < mulhilo; + uint32_t cond = ((uint32_t) carry << 16) + x_hi * y_hi; + uint32_t add = cond + (low_sum >> 16); + + return add; +} + +void full_mul_carry_low_sum (uint32_t x, uint32_t y, uint32_t* p) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t shrlolo = mullolo >> 16; + uint32_t low_sum = cross_sum + shrlolo; + int carry = low_sum < mulhilo; + uint32_t cond = ((uint32_t) carry << 16) + x_hi * y_hi; + uint32_t add = cond + (low_sum >> 16); + p[1] = add; + uint32_t low_sum_shr = low_sum << 16; + uint32_t mullololo = mullolo & 0xFFFF; + uint32_t low = low_sum_shr | mullololo; + p[0] = low; +} + +uint32_t mulh_carry_low_sum_comm (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = y_lo * x_hi; + uint32_t mullohi = y_hi * x_lo; + uint32_t cross_sum = mullohi + mulhilo; + uint32_t mullolo = x_lo * y_lo; + uint32_t shrlolo = mullolo >> 16; + uint32_t low_sum = shrlolo + cross_sum; + int carry = low_sum < mulhilo; + uint32_t cond = ((uint32_t) carry << 16) + x_hi * y_hi; + uint32_t add = cond + (low_sum >> 16); + + return add; +} + +uint32_t mulh_carry_low_sum_lohi (uint32_t x, uint32_t y) { + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t low_sum = cross_sum + (mullolo >> 16); + int carry_occurred = (low_sum < mullohi); + uint32_t cond = (uint32_t) carry_occurred << 16; + uint32_t add = x_hi * y_hi + cond + (low_sum >> 16); + + return add; +} + +/* The 128-bit variant will fail during the high sequence generation + (no target provides a 256-bit multiply) and is excluded from the + expected fold counts below. */ +#ifdef __SIZEOF_INT128__ +__uint128_t mulh_carry_low_sum_128 (__uint128_t x, __uint128_t y) +{ + __uint128_t x_hi = x >> 64; + __uint128_t x_lo = x & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t y_hi = y >> 64; + __uint128_t y_lo = y & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t mulhilo = x_hi * y_lo; + __uint128_t mullohi = x_lo * y_hi; + __uint128_t cross_sum = mulhilo + mullohi; + __uint128_t mullolo = x_lo * y_lo; + __uint128_t shrlolo = mullolo >> 64; + __uint128_t low_sum = cross_sum + shrlolo; + int carry = low_sum < mulhilo; + __uint128_t cond = ((__uint128_t) carry << 64) + x_hi * y_hi; + __uint128_t add = cond + (low_sum >> 64); + + return add; +} +#endif + +/* This will be optimized during the second forwprop run. + Disable SLP so the expected fold count is target-independent. */ +__attribute__((optimize("no-tree-slp-vectorize"))) +v2i32 mulh_carry_low_sum_v2i32 (v2i32 x, v2i32 y) +{ + v2i32 result; + for (int i = 0; i < 2; i++) + { + uint32_t x_hi = x.v[i] >> 16; + uint32_t x_lo = x.v[i] & 0xFFFF; + uint32_t y_hi = y.v[i] >> 16; + uint32_t y_lo = y.v[i] & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t shrlolo = mullolo >> 16; + uint32_t low_sum = cross_sum + shrlolo; + int carry = low_sum < mulhilo; + uint32_t cond = ((uint32_t) carry << 16) + x_hi * y_hi; + uint32_t add = cond + (low_sum >> 16); + result.v[i] = add; + } + + return result; +} + +/* PHI-form coverage: the carry summand is the join of a 2-arg PHI + guarded by an unsigned compare, recognized by cond_carry_add / + cond_carry_add_neg and folded by match_long_mul_phi. */ + +uint32_t mulh_carry_phi (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum < mulhilo) + add += (uint32_t)1 << 16; + return add; +} + +uint64_t mulh_carry_long_phi (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + (y_lo_x_lo >> 32); + uint64_t hw64 = y_hi_x_hi + cross_sum_hi + (low_accum >> 32); + if (cross_sum < y_lo_x_hi) + hw64 += (uint64_t)1 << 32; + return hw64; +} + +/* PHI-form, cond_carry_add_neg (negated branch, carry-on-false). */ +uint32_t mulh_carry_phi_neg (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum >= mulhilo) + ; + else + add += (uint32_t)1 << 16; + return add; +} + +/* On targets with __int128 support the two 128-bit highparts also + fold; without it they are elided by #ifdef and the count drops + by 2. */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 10 "forwprop1" { target { oi_mode && int128 } } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 8 "forwprop1" { target { ! { oi_mode && int128 } } } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 2 "forwprop2" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded\\." 2 "forwprop1" } } */ +/* Three PHI-form highparts, one per polarity pair (gt via mulh_carry_phi + and mulh_carry_long_phi, le via mulh_carry_phi_neg). */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded \\(carry PHI\\)" 3 "forwprop1" } } */ +/* Only the two 128-bit (OImode) chains are lowered. sparc64 and hppa64 + have OImode and __int128 but no native DImode high part, so their u64 + chains lower too and the count would exceed 2; exclude them. */ +/* { dg-final { scan-tree-dump-times "Lowered long-mul high-part chain" 2 "widening_mul" { target { { oi_mode && int128 } && { ! { sparc*-*-* hppa*-*-* } } } } } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-cse-128.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-cse-128.c new file mode 100644 index 000000000000..53b5eba9e2db --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-cse-128.c @@ -0,0 +1,52 @@ +/* { dg-do compile { target { oi_mode && int128 } } } */ +/* { dg-options "-O3 -fdump-tree-forwprop1-details -fdump-tree-optimized" } */ + +/* Two differently-spelled high-part longhands of the same 128x128 + product both fold to the canonical (u256) x * (u256) y >> 128, so + value numbering proves them equal and the function folds to 0. */ + +typedef __uint128_t u128; + +u128 both_spellings (u128 x, u128 y) +{ + /* Spelling 1: overflow-compare carry form. */ + u128 x_hi = x >> 64; + u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF; + u128 y_hi = y >> 64; + u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF; + u128 mulhilo = x_hi * y_lo; + u128 mullohi = x_lo * y_hi; + u128 cross_sum = mulhilo + mullohi; + u128 mullolo = x_lo * y_lo; + u128 shrlolo = mullolo >> 64; + u128 add_cross_sum = cross_sum + shrlolo; + int carry = add_cross_sum < mulhilo; + u128 cond = ((u128) carry << 64) + x_hi * y_hi; + u128 h1 = cond + (add_cross_sum >> 64); + + /* Spelling 2: ladder form. */ + u128 a_lo = x & (u128)0xFFFFFFFFFFFFFFFF; + u128 b_lo = y & (u128)0xFFFFFFFFFFFFFFFF; + u128 a_hi = x >> 64; + u128 b_hi = y >> 64; + u128 t0 = b_lo * a_lo; + u128 t1 = b_lo * a_hi; + u128 t2 = b_hi * a_lo; + u128 t3 = b_hi * a_hi; + u128 t0_hi = t0 >> 64; + u128 u0 = t0_hi + t1; + u128 u0_lo = u0 & (u128)0xFFFFFFFFFFFFFFFF; + u128 u0_hi = u0 >> 64; + u128 u1 = u0_lo + t2; + u128 u1_hi = u1 >> 64; + u128 u2 = u0_hi + t3; + u128 h2 = u2 + u1_hi; + + return h1 ^ h2; +} + +/* Both spellings are recognized. */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 2 "forwprop1" } } */ +/* Once canonical, VN proves them equal and the function folds to 0. */ +/* { dg-final { scan-tree-dump "return 0;" "optimized" } } */ +/* { dg-final { scan-tree-dump-not " \\* " "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-trunc-128.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-trunc-128.c new file mode 100644 index 000000000000..00f0338df5e2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-chain-trunc-128.c @@ -0,0 +1,80 @@ +/* { dg-do run { target int128 } } */ +/* { dg-options "-O3" } */ + +/* A user cast of the recognized 128-bit high part merges with the + chain's final truncation, so widening_mul lowering sees an outermost + convert to a type narrower than 128 bits. Checks it builds the + longhand at narrow precision and converts to the lhs type. */ + +typedef __uint128_t u128; +typedef unsigned long long u64; +typedef unsigned int u32; + +static inline u128 +mulh128 (u128 x, u128 y) +{ + u128 x_hi = x >> 64; + u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF; + u128 y_hi = y >> 64; + u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF; + u128 mulhilo = x_hi * y_lo; + u128 mullohi = x_lo * y_hi; + u128 cross_sum = mulhilo + mullohi; + u128 mullolo = x_lo * y_lo; + u128 shrlolo = mullolo >> 64; + u128 add_cross_sum = cross_sum + shrlolo; + int carry = add_cross_sum < mulhilo; + u128 cond = ((u128) carry << 64) + x_hi * y_hi; + return cond + (add_cross_sum >> 64); +} + +__attribute__((noipa)) u64 +trunc64 (u128 x, u128 y) { return (u64) mulh128 (x, y); } + +__attribute__((noipa)) u32 +trunc32 (u128 x, u128 y) { return (u32) mulh128 (x, y); } + +__attribute__((noipa)) u128 +mulh_reference (u128 x, u128 y) +{ + volatile u128 x_hi = x >> 64; + volatile u128 x_lo = x & (u128)0xFFFFFFFFFFFFFFFF; + volatile u128 y_hi = y >> 64; + volatile u128 y_lo = y & (u128)0xFFFFFFFFFFFFFFFF; + u128 mulhilo = x_hi * y_lo; + u128 mullohi = x_lo * y_hi; + u128 cross_sum = mulhilo + mullohi; + u128 mullolo = x_lo * y_lo; + u128 shrlolo = mullolo >> 64; + u128 add_cross_sum = cross_sum + shrlolo; + int carry = add_cross_sum < mulhilo; + u128 cond = ((u128) carry << 64) + x_hi * y_hi; + return cond + (add_cross_sum >> 64); +} + +int +main (void) +{ + static const u128 vals[] = { + 0, + 1, + (u128)0xFFFFFFFFFFFFFFFF, + ((u128)1 << 64), + ((u128)1 << 127), + ~(u128)0, + ((u128)0xDEADBEEFCAFEBABE << 64) | 0x0123456789ABCDEF, + ((u128)0x8000000000000001 << 64) | 0xFFFFFFFFFFFFFFFE, + }; + const unsigned n = sizeof (vals) / sizeof (vals[0]); + + for (unsigned i = 0; i < n; i++) + for (unsigned j = 0; j < n; j++) + { + u128 ref = mulh_reference (vals[i], vals[j]); + if (trunc64 (vals[i], vals[j]) != (u64) ref) + __builtin_abort (); + if (trunc32 (vals[i], vals[j]) != (u32) ref) + __builtin_abort (); + } + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-extra-addend.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-extra-addend.c new file mode 100644 index 000000000000..5e36a1592ec2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-extra-addend.c @@ -0,0 +1,63 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-forwprop-details" } */ + +/* Chains carrying addends that are not part of the long-multiply idiom + (an accumulator merged in by reassociation, a foreign shifted term) + must still fold, with the extra addends preserved on top of the wide + multiply. A leaf that classifies as a long-mul summand but breaks + operand consistency kills the match instead (no subset retry). */ + +typedef __UINT64_TYPE__ uint64_t; + +/* Extra addend appended after the full high-part chain. Folds. */ +uint64_t +mulh_acc (uint64_t x, uint64_t y, uint64_t acc) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + int carry_out = hilo > low_sum; + uint64_t carry = (uint64_t) carry_out << 32; + return xh * yh + (low_sum >> 32) + carry + acc; +} + +/* Extra addend interleaved into the middle of the chain. Folds. */ +uint64_t +mulh_acc_interleaved (uint64_t x, uint64_t y, uint64_t acc) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + int carry_out = hilo > low_sum; + uint64_t carry = (uint64_t) carry_out << 32; + return ((xh * yh + acc) + (low_sum >> 32)) + carry; +} + +/* Foreign leaf that classifies as a summand (a second high-high + product of different operands): consumed by the multiset, operand + consistency fails, no fold. */ +uint64_t +mulh_foreign_hihi (uint64_t x, uint64_t y, uint64_t a, uint64_t b) +{ + uint64_t xl = x & 0xFFFFFFFF, xh = x >> 32; + uint64_t yl = y & 0xFFFFFFFF, yh = y >> 32; + uint64_t ah = a >> 32, bh = b >> 32; + uint64_t hilo = xh * yl; + uint64_t lohi = xl * yh; + uint64_t cross = hilo + lohi; + uint64_t lolo = xl * yl; + uint64_t low_sum = cross + (lolo >> 32); + int carry_out = hilo > low_sum; + uint64_t carry = (uint64_t) carry_out << 32; + return xh * yh + (low_sum >> 32) + carry + ah * bh; +} + +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded" 2 "forwprop1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c new file mode 100644 index 000000000000..7b7384d86455 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c @@ -0,0 +1,333 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-forwprop-details -fdump-tree-widening_mul-details" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; +typedef struct { uint32_t v[2]; } v2i32; +typedef struct { uint64_t v[2]; } v2i64; + +uint64_t mulh_ladder (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t t0 = y_lo * x_lo; + uint64_t t1 = y_lo * x_hi; + uint64_t t2 = y_hi * x_lo; + uint64_t t3 = y_hi * x_hi; + uint64_t t0_hi = t0 >> 32; + uint64_t u0 = t0_hi + t1; + uint64_t u0_lo = u0 & 0xFFFFFFFF; + uint64_t u0_hi = u0 >> 32; + uint64_t u1 = u0_lo + t2; + uint64_t u1_hi = u1 >> 32; + uint64_t u2 = u0_hi + t3; + uint64_t hw64 = u2 + u1_hi; + + return hw64; +} + +uint64_t mulh_ladder_comm (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t t0 = x_lo * y_lo; + uint64_t t1 = x_lo * y_hi; + uint64_t t2 = x_hi * y_lo; + uint64_t t3 = x_hi * y_hi; + uint64_t t0_hi = t0 >> 32; + uint64_t u0 = t1 + t0_hi; + uint64_t u0_lo = u0 & 0xFFFFFFFF; + uint64_t u0_hi = u0 >> 32; + uint64_t u1 = t2 + u0_lo; + uint64_t u1_hi = u1 >> 32; + uint64_t u2 = u1_hi + u0_hi; + uint64_t hw64 = t3 + u2; + + return hw64; +} + +uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t y_lo = y & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_hi = y >> 16; + uint32_t t0 = y_lo * x_lo; + uint32_t t1 = y_lo * x_hi; + uint32_t t2 = y_hi * x_lo; + uint32_t t3 = y_hi * x_hi; + uint32_t t0_hi = t0 >> 16; + uint32_t u0 = t0_hi + t1; + uint32_t u0_lo = u0 & 0xFFFF; + uint32_t u0_hi = u0 >> 16; + uint32_t u1 = u0_lo + t2; + uint32_t u1_hi = u1 >> 16; + uint32_t u2 = u0_hi + t3; + uint32_t hw64 = u2 + u1_hi; + + return hw64; +} + +/* The 128-bit variant lowers to longhand in pass_optimize_widening_mul; + no target provides a 256-bit multiply. */ +#ifdef __SIZEOF_INT128__ +__uint128_t umulh_variant_i128 (__uint128_t x, __uint128_t y) +{ + __uint128_t x_lo = x & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t y_lo = y & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t x_hi = x >> 64; + __uint128_t y_hi = y >> 64; + __uint128_t t0 = y_lo * x_lo; + __uint128_t t1 = y_lo * x_hi; + __uint128_t t2 = y_hi * x_lo; + __uint128_t t3 = y_hi * x_hi; + __uint128_t t0_hi = t0 >> 64; + __uint128_t u0 = t0_hi + t1; + __uint128_t u0_lo = u0 & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t u0_hi = u0 >> 64; + __uint128_t u1 = u0_lo + t2; + __uint128_t u1_hi = u1 >> 64; + __uint128_t u2 = u0_hi + t3; + __uint128_t hw64 = u2 + u1_hi; + + return hw64; +} +#endif + +v2i64 full_mul_ladder (uint64_t x, uint64_t y) +{ + uint64_t and_x = x & 0xFFFFFFFF; + uint64_t and_y = y & 0xFFFFFFFF; + uint64_t mul_i = and_y * and_x; + uint64_t shr_x = x >> 32; + uint64_t mul_i27 = and_y * shr_x; + uint64_t shr_y = y >> 32; + uint64_t mul_i28 = shr_y * and_x; + uint64_t mul_i29 = shr_y * shr_x; + uint64_t shr10 = mul_i >> 32; + uint64_t and11 = mul_i27 & 0xFFFFFFFF; + uint64_t add = and11 + mul_i28; + uint64_t add12 = add + shr10; + uint64_t shr13 = mul_i27 >> 32; + uint64_t shr14 = add12 >> 32; + uint64_t add15 = shr13 + mul_i29; + uint64_t add16 = add15 + shr14; + uint64_t shl = add12 << 32; + uint64_t and17 = mul_i & 0xFFFFFFFF; + uint64_t or_val = shl | and17; + v2i64 result; + result.v[0] = or_val; + result.v[1] = add16; + return result; +} + +/* This will be optimized during the second forwprop run. + Disable SLP so the expected fold count is target-independent. */ +__attribute__((optimize("no-tree-slp-vectorize"))) +v2i32 mulh_ladder_v2i32 (v2i32 x, v2i32 y) +{ + v2i32 result; + for(int i=0; i<2; ++i) + { + uint32_t x_lo = x.v[i] & 0xFFFF; + uint32_t y_lo = y.v[i] & 0xFFFF; + uint32_t x_hi = x.v[i] >> 16; + uint32_t y_hi = y.v[i] >> 16; + uint32_t t0 = y_lo * x_lo; + uint32_t t1 = y_lo * x_hi; + uint32_t t2 = y_hi * x_lo; + uint32_t t3 = y_hi * x_hi; + uint32_t t0_hi = t0 >> 16; + uint32_t u0 = t0_hi + t1; + uint32_t u0_lo = u0 & 0xFFFF; + uint32_t u0_hi = u0 >> 16; + uint32_t u1 = u0_lo + t2; + uint32_t u1_hi = u1 >> 16; + uint32_t u2 = u0_hi + t3; + result.v[i] = u2 + u1_hi; + } + + return result; +} + +/* Ladder-long variants: hi-part sum uses the long form + (xh*yh + cross_hi_a + cross_hi_b + mid_hi). */ + +uint32_t mulh_ladder_long (uint32_t x, uint32_t y) +{ + uint32_t xl = x & 0xFFFF; + uint32_t xh = x >> 16; + uint32_t yl = y & 0xFFFF; + uint32_t yh = y >> 16; + uint32_t mulll = xl * yl; + uint32_t mullh = xl * yh; + uint32_t mulhl = xh * yl; + uint32_t mulhh = xh * yh; + uint32_t shr8 = mulll >> 16; + uint32_t conv10 = mullh & 0xFFFF; + uint32_t add = shr8 + conv10; + uint32_t conv12 = mulhl & 0xFFFF; + uint32_t add13 = add + conv12; + uint32_t shr14 = add13 >> 16; + uint32_t shr15 = mullh >> 16; + uint32_t add16 = mulhh + shr15; + uint32_t shr17 = mulhl >> 16; + uint32_t add18 = add16 + shr17; + uint32_t add19 = add18 + shr14; + + return add19; +} + +void full_mul_ladder_long (uint32_t x, uint32_t y, uint32_t *p) +{ + uint32_t xl = x & 0xFFFF; + uint32_t xh = x >> 16; + uint32_t yl = y & 0xFFFF; + uint32_t yh = y >> 16; + uint32_t mulll = xl * yl; + uint32_t mullh = xl * yh; + uint32_t mulhl = xh * yl; + uint32_t mulhh = xh * yh; + uint32_t shr8 = mulll >> 16; + uint32_t conv10 = mullh & 0xFFFF; + uint32_t add = shr8 + conv10; + uint32_t conv12 = mulhl & 0xFFFF; + uint32_t add13 = add + conv12; + uint32_t shr14 = add13 >> 16; + uint32_t shr15 = mullh >> 16; + uint32_t add16 = mulhh + shr15; + uint32_t shr17 = mulhl >> 16; + uint32_t add18 = add16 + shr17; + uint32_t add19 = add18 + shr14; + p[1] = add19; + uint32_t add_13_shl = add13 << 16; + uint32_t and17 = mulll & 0xFFFF; + uint32_t or_val = add_13_shl | and17; + p[0] = or_val; +} + +uint32_t mulh_ladder_long_comm (uint32_t x, uint32_t y) +{ + uint32_t xl = x & 0xFFFF; + uint32_t xh = x >> 16; + uint32_t yl = y & 0xFFFF; + uint32_t yh = y >> 16; + uint32_t mulll = yl * xl; + uint32_t mullh = yh * xl; + uint32_t mulhl = yl * xh; + uint32_t mulhh = yh * xh; + uint32_t shr8 = mulll >> 16; + uint32_t conv10 = mullh & 0xFFFF; + uint32_t add = conv10 + shr8; + uint32_t conv12 = mulhl & 0xFFFF; + uint32_t add13 = conv12 + add; + uint32_t shr14 = add13 >> 16; + uint32_t shr15 = mullh >> 16; + uint32_t shr17 = mulhl >> 16; + uint32_t add16 = shr14 + shr17; + uint32_t add18 = add16 + shr15; + uint32_t add19 = mulhh + add18; + + return add19; +} + +/* The 128-bit variant lowers to longhand in pass_optimize_widening_mul; + no target provides a 256-bit multiply. */ +#ifdef __SIZEOF_INT128__ +__uint128_t mulh_ladder_long_128 (__uint128_t x, __uint128_t y) +{ + __uint128_t xl = x & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t xh = x >> 64; + __uint128_t yl = y & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t yh = y >> 64; + __uint128_t mulll = xl * yl; + __uint128_t mullh = xl * yh; + __uint128_t mulhl = xh * yl; + __uint128_t mulhh = xh * yh; + __uint128_t shr8 = mulll >> 64; + __uint128_t conv10 = mullh & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t add = shr8 + conv10; + __uint128_t conv12 = mulhl & (__uint128_t)0xFFFFFFFFFFFFFFFF; + __uint128_t add13 = add + conv12; + __uint128_t shr14 = add13 >> 64; + __uint128_t shr15 = mullh >> 64; + __uint128_t add16 = mulhh + shr15; + __uint128_t shr17 = mulhl >> 64; + __uint128_t add18 = add16 + shr17; + __uint128_t add19 = add18 + shr14; + + return add19; +} +#endif + +uint32_t mulh_ladder_long_hllh (uint32_t x, uint32_t y) +{ + uint32_t xl = x & 0xFFFF; + uint32_t xh = x >> 16; + uint32_t yl = y & 0xFFFF; + uint32_t yh = y >> 16; + uint32_t mulll = xl * yl; + uint32_t mullh = xl * yh; + uint32_t mulhl = xh * yl; + uint32_t mulhh = xh * yh; + uint32_t shr8 = mulll >> 16; + uint32_t conv10 = mulhl & 0xFFFF; + uint32_t add = shr8 + conv10; + uint32_t conv12 = mullh & 0xFFFF; + uint32_t add13 = add + conv12; + uint32_t shr14 = add13 >> 16; + uint32_t shr15 = mulhl >> 16; + uint32_t add16 = mulhh + shr15; + uint32_t shr17 = mullh >> 16; + uint32_t add18 = add16 + shr17; + uint32_t add19 = add18 + shr14; + + return add19; +} + +/* This will be optimized during the second forwprop run. + Disable SLP so the expected fold count is target-independent. */ +__attribute__((optimize("no-tree-slp-vectorize"))) +v2i32 mul_ladder_long_v2i32 (v2i32 x, v2i32 y) +{ + v2i32 result; + for (int i = 0; i < 2; i++) + { + uint32_t xl = x.v[i] & 0xFFFF; + uint32_t xh = x.v[i] >> 16; + uint32_t yl = y.v[i] & 0xFFFF; + uint32_t yh = y.v[i] >> 16; + uint32_t mulll = xl * yl; + uint32_t mullh = xl * yh; + uint32_t mulhl = xh * yl; + uint32_t mulhh = xh * yh; + uint32_t shr8 = mulll >> 16; + uint32_t conv10 = mullh & 0xFFFF; + uint32_t add = shr8 + conv10; + uint32_t conv12 = mulhl & 0xFFFF; + uint32_t add13 = add + conv12; + uint32_t shr14 = add13 >> 16; + uint32_t shr15 = mullh >> 16; + uint32_t add16 = mulhh + shr15; + uint32_t shr17 = mulhl >> 16; + uint32_t add18 = add16 + shr17; + result.v[i] = add18 + shr14; + } + + return result; +} + +/* On targets with __int128 support the 128-bit highpart also folds; + without it it is elided by #ifdef and the count drops by 2. */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 10 "forwprop1" { target { oi_mode && int128 } } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 8 "forwprop1" { target { ! { oi_mode && int128 } } } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 2 "forwprop2" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded\\." 2 "forwprop1" } } */ +/* Only the two 128-bit (OImode) chains are lowered. sparc64 and hppa64 + have OImode and __int128 but no native DImode high part, so their u64 + chains lower too and the count would exceed 2; exclude them. */ +/* { dg-final { scan-tree-dump-times "Lowered long-mul high-part chain" 2 "widening_mul" { target { { oi_mode && int128 } && { ! { sparc*-*-* hppa*-*-* } } } } } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c new file mode 100644 index 000000000000..37c0193ece09 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c @@ -0,0 +1,54 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-forwprop-details" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; + +/* Low part via PLUS form: lolo + (cross_sum << halfwidth). + No GT/LT comparison on the result, so long_mul_check_low_plus_defer + should fold without deferring. */ +uint32_t mul_low_plus_32 (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t lolo = x_lo * y_lo; + uint32_t hilo = x_hi * y_lo; + uint32_t lohi = x_lo * y_hi; + uint32_t cross_sum = hilo + lohi; + uint32_t cross_shifted = cross_sum << 16; + return lolo + cross_shifted; +} + +/* 64-bit variant. */ +uint64_t mul_low_plus_64 (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + uint64_t lolo = x_lo * y_lo; + uint64_t hilo = x_hi * y_lo; + uint64_t lohi = x_lo * y_hi; + uint64_t cross_sum = hilo + lohi; + uint64_t cross_shifted = cross_sum << 32; + return lolo + cross_shifted; +} + +/* Commuted operand order. */ +uint32_t mul_low_plus_comm (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t lolo = y_lo * x_lo; + uint32_t hilo = y_lo * x_hi; + uint32_t lohi = y_hi * x_lo; + uint32_t cross_sum = lohi + hilo; + uint32_t cross_shifted = cross_sum << 16; + return cross_shifted + lolo; +} + +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 3 "forwprop1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c new file mode 100644 index 000000000000..7b239e2439e1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c @@ -0,0 +1,193 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-optimized" } */ + +typedef __UINT32_TYPE__ uint32_t; + +/* Only one cross-product (xh*yl), missing xl*yh. + Should NOT be folded. */ +uint32_t partial_one_cross (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t y_lo = y & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_hi = y >> 16; + uint32_t t0 = y_lo * x_lo; + uint32_t t1 = y_lo * x_hi; + uint32_t t3 = y_hi * x_hi; + uint32_t t0_hi = t0 >> 16; + uint32_t u0 = t0_hi + t1; + uint32_t u0_hi = u0 >> 16; + return t3 + u0_hi; +} + +/* Only xl*yl and xh*yh, no cross-products at all. + Should NOT be folded. */ +uint32_t partial_no_cross (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t y_lo = y & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_hi = y >> 16; + uint32_t t0 = y_lo * x_lo; + uint32_t t3 = y_hi * x_hi; + return t3 + (t0 >> 16); +} + +/* Only cross-products, missing xl*yl and xh*yh. + Should NOT be folded. */ +uint32_t partial_only_cross (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t y_lo = y & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_hi = y >> 16; + uint32_t t1 = y_lo * x_hi; + uint32_t t2 = y_hi * x_lo; + return (t1 + t2) >> 16; +} + +/* Full ladder structure but one cross-product uses z instead of y. + long_mul_check_consistency should reject the mismatched operand. + Should NOT be folded. */ +uint32_t partial_mismatched_op (uint32_t x, uint32_t y, uint32_t z) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t y_lo = y & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_hi = y >> 16; + uint32_t z_lo = z & 0xFFFF; + uint32_t t0 = y_lo * x_lo; + uint32_t t1 = y_lo * x_hi; + uint32_t t2 = z_lo * x_lo; + uint32_t t3 = y_hi * x_hi; + uint32_t t0_hi = t0 >> 16; + uint32_t u0 = t0_hi + t1; + uint32_t u0_lo = u0 & 0xFFFF; + uint32_t u0_hi = u0 >> 16; + uint32_t u1 = u0_lo + t2; + uint32_t u1_hi = u1 >> 16; + uint32_t u2 = u0_hi + t3; + return u2 + u1_hi; +} + +/* Uses conditionals in the computation. + Should NOT be folded. */ +unsigned mulhu_conditional (unsigned u, unsigned v) { + unsigned a, b, c, d, p, q, rlow, rhigh; + + a = u >> 16; + b = u & 0xFFFF; + c = v >> 16; + d = v & 0xFFFF; + + p = a*c; + q = b*d; + rlow = (-a + b)*(c - d); + rhigh = (int)((-a + b)^(c - d)) >> 31; + if (rlow == 0) rhigh = 0; + + q = q + (q >> 16); + rlow = rlow + p; + if (rlow < p) rhigh = rhigh + 1; + rlow = rlow + q; + if (rlow < q) rhigh = rhigh + 1; + + return p + (rlow >> 16) + (rhigh << 16); +} + +/* Signed operands. + Should NOT be folded. */ +int mulhs_signed (int u, int v) { + unsigned u0, v0, w0; + int u1, v1, w1, w2, t; + + u0 = u & 0xFFFF; + u1 = u >> 16; + v0 = v & 0xFFFF; + v1 = v >> 16; + w0 = u0*v0; + t = u1*v0 + (w0 >> 16); + w1 = t & 0xFFFF; + w2 = t >> 16; + w1 = u0*v1 + w1; + return u1*v1 + w2 + (w1 >> 16); +} + +/* PHI-form near-miss: non-power-of-two carry increment. + match.pd rejects via integer_pow2p@3. + Should NOT be folded. */ +uint32_t partial_phi_nonpow2 (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16, x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16, y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum < mulhilo) + add += (uint32_t)3 << 16; + return add; +} + +/* PHI-form near-miss: carry increment shifted by less than halfwidth. + match_long_mul_phi rejects via shift_amt == halfwidth. + Should NOT be folded. */ +uint32_t partial_phi_wrong_shift (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16, x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16, y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum < mulhilo) + add += (uint32_t)1 << 15; + return add; +} + +/* PHI-form near-miss: equality compare in place of the strict carry + predicate. cond_carry_add and cond_carry_add_neg only encode + gt / lt / le / ge. + Should NOT be folded. */ +uint32_t partial_phi_wrong_compare (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16, x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16, y_lo = y & 0xFFFF; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * y_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum == mulhilo) + add += (uint32_t)1 << 16; + return add; +} + +/* PHI-form near-miss: one cross-product uses z instead of y. + long_mul_check_consistency rejects the inconsistent (op0, op1). + Should NOT be folded. */ +uint32_t partial_phi_wrong_cross (uint32_t x, uint32_t y, uint32_t z) +{ + uint32_t x_hi = x >> 16, x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16, y_lo = y & 0xFFFF; + uint32_t z_hi = z >> 16; + uint32_t mulhilo = x_hi * y_lo; + uint32_t mullohi = x_lo * z_hi; + uint32_t cross_sum = mulhilo + mullohi; + uint32_t mullolo = x_lo * y_lo; + uint32_t add_cross_sum = cross_sum + (mullolo >> 16); + uint32_t add = x_hi * y_hi + (add_cross_sum >> 16); + if (add_cross_sum < mulhilo) + add += (uint32_t)1 << 16; + return add; +} + +/* Verify no fold in any forwprop pass by checking the optimized IR + for MULT_HIGHPART_EXPR (h*) and WIDEN_MULT_EXPR (w*). */ +/* { dg-final { scan-tree-dump-not " h\\* " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " w\\* " "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c new file mode 100644 index 000000000000..effed8262469 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c @@ -0,0 +1,140 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-forwprop-details" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; + +/* High part using two separate carries (cross carry + low carry). */ +uint64_t mulh_two_carry (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + + uint64_t lolo = x_lo * y_lo; + uint64_t hilo = x_hi * y_lo; + uint64_t lohi = x_lo * y_hi; + uint64_t hihi = x_hi * y_hi; + + uint64_t cross_sum = hilo + lohi; + uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32; + + uint64_t cross_shifted = cross_sum << 32; + uint64_t low_result = lolo + cross_shifted; + uint64_t low_carry = (uint64_t)(low_result < cross_shifted); + + uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry; + + return high; +} + +/* Commuted operand order. */ +uint64_t mulh_two_carry_comm (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + + uint64_t lolo = x_lo * y_lo; + uint64_t lohi = x_lo * y_hi; + uint64_t hilo = x_hi * y_lo; + uint64_t hihi = x_hi * y_hi; + + uint64_t cross_sum = lohi + hilo; + uint64_t cross_carry = (uint64_t)(cross_sum < lohi) << 32; + + uint64_t cross_shifted = cross_sum << 32; + uint64_t low_result = cross_shifted + lolo; + uint64_t low_carry = (uint64_t)(low_result < lolo); + + uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry; + + return high; +} + +/* 32-bit variant. */ +uint32_t mulh_two_carry_32 (uint32_t x, uint32_t y) +{ + uint32_t x_hi = x >> 16; + uint32_t x_lo = x & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo = y & 0xFFFF; + + uint32_t lolo = x_lo * y_lo; + uint32_t hilo = x_hi * y_lo; + uint32_t lohi = x_lo * y_hi; + uint32_t hihi = x_hi * y_hi; + + uint32_t cross_sum = hilo + lohi; + uint32_t cross_carry = (uint32_t)(cross_sum < hilo) << 16; + + uint32_t cross_shifted = cross_sum << 16; + uint32_t low_result = lolo + cross_shifted; + uint32_t low_carry = (uint32_t)(low_result < cross_shifted); + + uint32_t high = hihi + (cross_sum >> 16) + cross_carry + low_carry; + + return high; +} + +/* Full multiply: both high and low parts. */ +uint64_t full_mul_two_carry (uint64_t x, uint64_t y, uint64_t *lo) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + + uint64_t lolo = x_lo * y_lo; + uint64_t hilo = x_hi * y_lo; + uint64_t lohi = x_lo * y_hi; + uint64_t hihi = x_hi * y_hi; + + uint64_t cross_sum = hilo + lohi; + uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32; + + uint64_t cross_shifted = cross_sum << 32; + uint64_t low_result = lolo + cross_shifted; + uint64_t low_carry = (uint64_t)(low_result < cross_shifted); + + uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry; + + *lo = low_result; + return high; +} + +/* Low carry written as an if-branch + 2-arg PHI. Exercises + match_long_mul_phi's LMK_CARRY_LOW path (shift = 0). */ +uint64_t mulh_two_carry_low_phi (uint64_t x, uint64_t y) +{ + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFFUL; + uint64_t y_hi = y >> 32; + uint64_t y_lo = y & 0xFFFFFFFFUL; + + uint64_t lolo = x_lo * y_lo; + uint64_t hilo = x_hi * y_lo; + uint64_t lohi = x_lo * y_hi; + uint64_t hihi = x_hi * y_hi; + + uint64_t cross_sum = hilo + lohi; + uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32; + uint64_t cross_shifted = cross_sum << 32; + uint64_t low_result = lolo + cross_shifted; + + uint64_t high = hihi + (cross_sum >> 32) + cross_carry; + if (low_result < cross_shifted) + high += 1; + + return high; +} + +/* The LOW fold for full_mul_two_carry lands in forwprop4 because + `lolo + cross_shifted' also feeds the HIGH fold's low-carry + compare; long_mul_check_low_plus_defer holds it until the HIGH + fold has consumed the compare. */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 4 "forwprop3" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded \\(carry PHI\\)" 1 "forwprop3" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded\\." 1 "forwprop4" } } */ diff --git a/gcc/testsuite/gcc.target/aarch64/long_mul.c b/gcc/testsuite/gcc.target/aarch64/long_mul.c new file mode 100644 index 000000000000..f9c765380d8c --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/long_mul.c @@ -0,0 +1,100 @@ +/* { dg-do compile } */ +/* { dg-options "-O3" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; + +/* 64-bit ladder pattern for high part. */ +uint64_t mulh_ladder (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t t0 = y_lo * x_lo; + uint64_t t1 = y_lo * x_hi; + uint64_t t2 = y_hi * x_lo; + uint64_t t3 = y_hi * x_hi; + uint64_t t0_hi = t0 >> 32; + uint64_t u0 = t0_hi + t1; + uint64_t u0_lo = u0 & 0xFFFFFFFF; + uint64_t u0_hi = u0 >> 32; + uint64_t u1 = u0_lo + t2; + uint64_t u1_hi = u1 >> 32; + uint64_t u2 = u0_hi + t3; + return u2 + u1_hi; +} + +/* 64-bit carry pattern for high part. */ +uint64_t mulh_carry (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = cross_sum < y_lo_x_hi; + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint64_t interm = cross_sum_hi + y_hi_x_hi; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t interm_plus_carry = interm + carry; + return interm_plus_carry + low_accum_hi; +} + +/* 32-bit ladder pattern for high part. */ +uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t y_lo = y & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_hi = y >> 16; + uint32_t t0 = y_lo * x_lo; + uint32_t t1 = y_lo * x_hi; + uint32_t t2 = y_hi * x_lo; + uint32_t t3 = y_hi * x_hi; + uint32_t t0_hi = t0 >> 16; + uint32_t u0 = t0_hi + t1; + uint32_t u0_lo = u0 & 0xFFFF; + uint32_t u0_hi = u0 >> 16; + uint32_t u1 = u0_lo + t2; + uint32_t u1_hi = u1 >> 16; + uint32_t u2 = u0_hi + t3; + return u2 + u1_hi; +} + +/* 32-bit carry pattern for high part. */ +uint32_t mulh_carry_32 (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo_x_hi = y_lo * x_hi; + uint32_t y_hi_x_hi = y_hi * x_hi; + uint32_t y_hi_x_lo = y_hi * x_lo; + uint32_t y_lo_x_lo = y_lo * x_lo; + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint32_t carry = (uint32_t) carry_out << 16; + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16; + uint32_t cross_sum_lo = cross_sum & 0xFFFF; + uint32_t cross_sum_hi = cross_sum >> 16; + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint32_t interm = cross_sum_hi + y_hi_x_hi; + uint32_t low_accum_hi = low_accum >> 16; + uint32_t interm_plus_carry = interm + carry; + return interm_plus_carry + low_accum_hi; +} + +/* 64-bit patterns should emit umulh. */ +/* { dg-final { scan-assembler-times "umulh\t" 2 } } */ +/* 32-bit patterns should emit umull (32x32->64 widening multiply). */ +/* { dg-final { scan-assembler-times "umull\t" 2 } } */ diff --git a/gcc/testsuite/gcc.target/arm/long-mul-thumb1-inline.c b/gcc/testsuite/gcc.target/arm/long-mul-thumb1-inline.c new file mode 100644 index 000000000000..f36b4739d3a6 --- /dev/null +++ b/gcc/testsuite/gcc.target/arm/long-mul-thumb1-inline.c @@ -0,0 +1,47 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target arm_thumb1_ok } */ +/* { dg-options "-O2 -mthumb -mcpu=cortex-m0 -fdump-tree-forwprop1-details -fdump-tree-widening_mul-details" } */ + +/* Thumb-1 (cortex-m0) has no umull and no DImode multiply, so a DImode + multiply would expand to the __aeabi_lmul libcall. widening_mul + re-synthesizes the recognized u32 high part from the HImode widening + multiply Thumb-1 does have, so no libcall is emitted. */ + +typedef __INT32_TYPE__ i32; +typedef __UINT32_TYPE__ u32; +typedef __UINT64_TYPE__ u64; + +u32 mulh32 (u32 x, u32 y) +{ + u32 x_hi = x >> 16, x_lo = x & 0xFFFF; + u32 y_hi = y >> 16, y_lo = y & 0xFFFF; + u32 mulhilo = x_hi * y_lo; + u32 mullohi = x_lo * y_hi; + u32 cross_sum = mulhilo + mullohi; + u32 mullolo = x_lo * y_lo; + u32 shrlolo = mullolo >> 16; + u32 acs = cross_sum + shrlolo; + int carry = acs < mulhilo; + u32 cond = ((u32) carry << 16) + x_hi * y_hi; + return cond + (acs >> 16); +} + +/* Signed operands sign-extended into the unsigned wide type. The atom + accepts them via `(convert? @X)'; long_mul_split_operand must sign- + extend the narrow operand into the high half (arithmetic shift by + N-1 on the signed narrow) -- a broken sign-extend branch would + zero the high and miscompile any negative input. */ +u32 mulhs_split (i32 a, i32 b) +{ + return (u32) (((u64) a * (u64) b) >> 32); +} + +/* Recognizer canonicalizes; widening_mul re-synthesizes the longhand. */ +/* { dg-final { scan-tree-dump "Long multiplication high part folded" "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "Lowered long-mul high-part chain" 2 "widening_mul" } } */ +/* No multiplication libcall: the longhand stays inline. */ +/* { dg-final { scan-assembler-not "__aeabi_lmul" } } */ +/* Split's signed branch emits an arithmetic shift by narrow_prec-1 on + each signed narrow source of mulhs_split -- once per operand, + absent when broken. */ +/* { dg-final { scan-tree-dump-times "\\(D\\) >> 31" 2 "widening_mul" } } */ diff --git a/gcc/testsuite/gcc.target/arm/long-mul-umull.c b/gcc/testsuite/gcc.target/arm/long-mul-umull.c new file mode 100644 index 000000000000..721b640f7b70 --- /dev/null +++ b/gcc/testsuite/gcc.target/arm/long-mul-umull.c @@ -0,0 +1,73 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target arm_arm_ok } */ +/* { dg-options "-O2 -marm -fdump-tree-widening_mul-details" } */ + +/* With umull available, the recognizer folds the u32 high-part longhand + to a DImode multiply that becomes a single umull, while the u64 + longhand becomes a TImode chain that widening_mul re-synthesizes as + four umull. No libcalls. */ + +typedef __UINT64_TYPE__ u64; +typedef __UINT32_TYPE__ u32; + +u32 mulh32 (u32 x, u32 y) +{ + u32 x_hi = x >> 16, x_lo = x & 0xFFFF; + u32 y_hi = y >> 16, y_lo = y & 0xFFFF; + u32 mulhilo = x_hi * y_lo; + u32 mullohi = x_lo * y_hi; + u32 cross_sum = mulhilo + mullohi; + u32 mullolo = x_lo * y_lo; + u32 shrlolo = mullolo >> 16; + u32 acs = cross_sum + shrlolo; + int carry = acs < mulhilo; + u32 cond = ((u32) carry << 16) + x_hi * y_hi; + return cond + (acs >> 16); +} + +u64 mulh64 (u64 x, u64 y) +{ + u64 x_hi = x >> 32, x_lo = x & 0xFFFFFFFF; + u64 y_hi = y >> 32, y_lo = y & 0xFFFFFFFF; + u64 mulhilo = x_hi * y_lo; + u64 mullohi = x_lo * y_hi; + u64 cross_sum = mulhilo + mullohi; + u64 mullolo = x_lo * y_lo; + u64 shrlolo = mullolo >> 32; + u64 acs = cross_sum + shrlolo; + int carry = acs < mulhilo; + u64 cond = ((u64) carry << 32) + x_hi * y_hi; + return cond + (acs >> 32); +} + +/* Two longhands chained through the low half, with the first high part also + live. After recognition the second chain reads its operand off the first + product as a masked low half, so lowering both leaves a live TImode + multiply the target cannot expand. */ + +u64 chain_low (u64 a, u64 b, u64 c, u64 *hi1) +{ + *hi1 = mulh64 (a, b); + return mulh64 (a * b, c); +} + +/* The same through the high half: after recognition the second chain + multiplies by the first product shifted down, and truncating that shift + would leave the product live instead. */ + +u64 chain_high (u64 a, u64 b, u64 c, u64 *hi1) +{ + u64 h1 = mulh64 (a, b); + *hi1 = h1; + return mulh64 (h1, c); +} + +/* mulh32 collapses to one umull and mulh64 lowers to four; chain_low and + chain_high inline two longhands each, for nine and eight. */ +/* { dg-final { scan-assembler-times "\tumull\t" 22 } } */ +/* One lowering in mulh64 and two in each chain. mulh32 contributes none: + its DImode multiply is converted to a widening multiply instead. */ +/* { dg-final { scan-tree-dump-times "Lowered long-mul high-part chain" 5 "widening_mul" } } */ +/* { dg-final { scan-tree-dump "Narrowed low-half-only long multiply" "widening_mul" } } */ +/* { dg-final { scan-assembler-not "__aeabi_lmul" } } */ +/* { dg-final { scan-assembler-not "__multi3" } } */ diff --git a/gcc/testsuite/gcc.target/i386/long_mul.c b/gcc/testsuite/gcc.target/i386/long_mul.c new file mode 100644 index 000000000000..d4b03ed1beda --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/long_mul.c @@ -0,0 +1,100 @@ +/* { dg-do compile { target { ! ia32 } } } */ +/* { dg-options "-O3" } */ + +typedef __UINT32_TYPE__ uint32_t; +typedef __UINT64_TYPE__ uint64_t; + +/* 64-bit ladder pattern for high part. */ +uint64_t mulh_ladder (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_hi = y >> 32; + uint64_t t0 = y_lo * x_lo; + uint64_t t1 = y_lo * x_hi; + uint64_t t2 = y_hi * x_lo; + uint64_t t3 = y_hi * x_hi; + uint64_t t0_hi = t0 >> 32; + uint64_t u0 = t0_hi + t1; + uint64_t u0_lo = u0 & 0xFFFFFFFF; + uint64_t u0_hi = u0 >> 32; + uint64_t u1 = u0_lo + t2; + uint64_t u1_hi = u1 >> 32; + uint64_t u2 = u0_hi + t3; + return u2 + u1_hi; +} + +/* 64-bit carry pattern for high part. */ +uint64_t mulh_carry (uint64_t x, uint64_t y) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t y_lo = y & 0xFFFFFFFF; + uint64_t y_hi = y >> 32; + uint64_t y_lo_x_hi = y_lo * x_hi; + uint64_t y_hi_x_hi = y_hi * x_hi; + uint64_t y_hi_x_lo = y_hi * x_lo; + uint64_t y_lo_x_lo = y_lo * x_lo; + uint64_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = cross_sum < y_lo_x_hi; + uint64_t carry = (uint64_t) carry_out << 32; + uint64_t y_lo_x_lo_hi = y_lo_x_lo >> 32; + uint64_t cross_sum_lo = cross_sum & 0xFFFFFFFF; + uint64_t cross_sum_hi = cross_sum >> 32; + uint64_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint64_t interm = cross_sum_hi + y_hi_x_hi; + uint64_t low_accum_hi = low_accum >> 32; + uint64_t interm_plus_carry = interm + carry; + return interm_plus_carry + low_accum_hi; +} + +/* 32-bit ladder pattern for high part. */ +uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t y_lo = y & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_hi = y >> 16; + uint32_t t0 = y_lo * x_lo; + uint32_t t1 = y_lo * x_hi; + uint32_t t2 = y_hi * x_lo; + uint32_t t3 = y_hi * x_hi; + uint32_t t0_hi = t0 >> 16; + uint32_t u0 = t0_hi + t1; + uint32_t u0_lo = u0 & 0xFFFF; + uint32_t u0_hi = u0 >> 16; + uint32_t u1 = u0_lo + t2; + uint32_t u1_hi = u1 >> 16; + uint32_t u2 = u0_hi + t3; + return u2 + u1_hi; +} + +/* 32-bit carry pattern for high part. */ +uint32_t mulh_carry_32 (uint32_t x, uint32_t y) +{ + uint32_t x_lo = x & 0xFFFF; + uint32_t x_hi = x >> 16; + uint32_t y_lo = y & 0xFFFF; + uint32_t y_hi = y >> 16; + uint32_t y_lo_x_hi = y_lo * x_hi; + uint32_t y_hi_x_hi = y_hi * x_hi; + uint32_t y_hi_x_lo = y_hi * x_lo; + uint32_t y_lo_x_lo = y_lo * x_lo; + uint32_t cross_sum = y_hi_x_lo + y_lo_x_hi; + int carry_out = (cross_sum < y_lo_x_hi); + uint32_t carry = (uint32_t) carry_out << 16; + uint32_t y_lo_x_lo_hi = y_lo_x_lo >> 16; + uint32_t cross_sum_lo = cross_sum & 0xFFFF; + uint32_t cross_sum_hi = cross_sum >> 16; + uint32_t low_accum = cross_sum_lo + y_lo_x_lo_hi; + uint32_t interm = cross_sum_hi + y_hi_x_hi; + uint32_t low_accum_hi = low_accum >> 16; + uint32_t interm_plus_carry = interm + carry; + return interm_plus_carry + low_accum_hi; +} + +/* 64-bit patterns should emit mulq (unsigned 64x64->128 multiply). */ +/* { dg-final { scan-assembler-times "\tmulq" 2 } } */ +/* 32-bit patterns should emit imulq (64-bit multiply of zero-extended operands). */ +/* { dg-final { scan-assembler-times "\timulq" 2 } } */ diff --git a/gcc/testsuite/gcc.target/i386/widen_mult_high_chain.c b/gcc/testsuite/gcc.target/i386/widen_mult_high_chain.c new file mode 100644 index 000000000000..7cfa42c9b3a5 --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/widen_mult_high_chain.c @@ -0,0 +1,32 @@ +/* { dg-do compile { target { lp64 } } } */ +/* { dg-options "-O3" } */ + +/* The high 128 bits of a 128 x 128 -> 256 product has no widening + multiply (no TI x TI -> OI) and no 256-bit expansion path. forwprop + folds the longhand to the canonical (uint256_t) a * (uint256_t) b + >> 128 shape, and widening_mul re-synthesizes it from four + 64 x 64 -> 128 multiplies (mulq). No __mulOI3 libcall. */ + +__uint128_t +mulh_carry_128 (__uint128_t x, __uint128_t y) +{ + __uint128_t x_hi = x >> 64; + __uint128_t x_lo = x & (__uint128_t) 0xFFFFFFFFFFFFFFFF; + __uint128_t y_hi = y >> 64; + __uint128_t y_lo = y & (__uint128_t) 0xFFFFFFFFFFFFFFFF; + __uint128_t mulhilo = x_hi * y_lo; + __uint128_t mullohi = x_lo * y_hi; + __uint128_t cross_sum = mulhilo + mullohi; + __uint128_t mullolo = x_lo * y_lo; + __uint128_t shrlolo = mullolo >> 64; + __uint128_t add_cross_sum = cross_sum + shrlolo; + int carry = add_cross_sum < mulhilo; + __uint128_t cond = ((__uint128_t) carry << 64) + x_hi * y_hi; + __uint128_t add = cond + (add_cross_sum >> 64); + + return add; +} + +/* { dg-final { scan-assembler-not "__multi3" } } */ +/* { dg-final { scan-assembler-not "__mulOI3" } } */ +/* { dg-final { scan-assembler-times "\tmulq" 4 } } */ diff --git a/gcc/testsuite/lib/target-supports.exp b/gcc/testsuite/lib/target-supports.exp index 42cbb5ce3df0..e6edd6233a23 100644 --- a/gcc/testsuite/lib/target-supports.exp +++ b/gcc/testsuite/lib/target-supports.exp @@ -4983,6 +4983,26 @@ proc check_effective_target_int128 { } { }] } +# Return 1 if the target's mode table includes OImode (a 256-bit +# scalar_int_mode). Enumerated from `INT_MODE (OI, 32)' declarations +# in gcc/config/*/*-modes.def. + +proc check_effective_target_oi_mode { } { + return [check_cached_effective_target oi_mode { + expr { [istarget aarch64*-*-*] + || [istarget i?86-*-*] + || [istarget x86_64-*-*] + || [istarget riscv*-*-*] + || [istarget sparc*-*-*] + || [istarget s390*-*-*] + || [istarget loongarch*-*-*] + || [istarget arm*-*-*] + || [istarget alpha*-*-*] + || [istarget ia64-*-*] + || [istarget hppa*-*-*] } + }] +} + # Return 1 if the target supports unsigned int->float conversion # diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc index 75f06c6ba410..645ccfb301a2 100644 --- a/gcc/tree-ssa-forwprop.cc +++ b/gcc/tree-ssa-forwprop.cc @@ -58,6 +58,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa.h" #include "gimple-range.h" #include "tree-ssa-dce.h" +#include "tree-ssa-math-opts.h" /* This pass propagates the RHS of assignment statements into use sites of the LHS of the assignment. It's basically a specialized @@ -3623,6 +3624,1177 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) return true; } +/* Long-multiply fold framework. + + Walks the outer addition or bit_ior chain on a candidate statement, + classifies each summand against the atom match patterns from + match.pd, and looks the resulting multiset of (kind, extract) tuples + up in a table. On a hit, three cross-summand consistency checks + decide whether the wide multiply is emitted. */ + +/* Match.pd recognizers for the conditional carry-add pattern. The + two names split the gcond polarity: cond_carry_add matches when + the true edge selects (base + pow2), cond_carry_add_neg when the + true edge selects base. */ + +extern bool gimple_cond_carry_add (tree, tree *, tree (*)(tree)); +extern bool gimple_cond_carry_add_neg (tree, tree *, tree (*)(tree)); + +/* Match.pd functions to match long multiplication. */ + +extern bool gimple_mul_hi (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_lo (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_hilo (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_lolo (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_hihi (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_cross_sum (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_low_sum (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_low_accum (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_carry_cross_sum (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_carry_low_sum (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_carry_low (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_ladder_sum1 (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_ladder_sum2 (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_ladder_sum3 (tree, tree *, tree (*)(tree)); +extern bool gimple_mul_ladder_part_sum (tree, tree *, tree (*)(tree)); + +/* Append to SEQ statements assigning DEST the high-part multiply of + OP1 and OP2, emitted as + (N)(((2N) op1 * (2N) op2) >> N). + pass_optimize_widening_mul's convert_mult_to_widen and + convert_mult_to_highpart later rewrite this to a single + WIDEN_MULT_EXPR or MULT_HIGHPART_EXPR when the target supports it, + otherwise the 2N multiply expands directly. Emitting the canonical + widening shape keeps target-capability decisions in the layer that + already owns them. */ + +static void +build_mul_high_seq (tree op1, tree op2, tree dest, location_t loc, + gimple_seq *seq) +{ + tree op_type = TREE_TYPE (op1); + unsigned int width = TYPE_PRECISION (op_type); + tree wide_type = build_nonstandard_integer_type (width * 2, 1); + + tree wide_a = gimple_convert (seq, loc, wide_type, op1); + tree wide_b = gimple_convert (seq, loc, wide_type, op2); + tree wide_prod = gimple_build (seq, loc, MULT_EXPR, wide_type, + wide_a, wide_b); + tree hi = gimple_build (seq, loc, RSHIFT_EXPR, wide_type, wide_prod, + build_int_cst (integer_type_node, width)); + + gimple *prod = gimple_build_assign (dest, NOP_EXPR, hi); + gimple_set_location (prod, loc); + gimple_seq_add_stmt (seq, prod); +} + +/* Append to SEQ statements combining ACC with each of EXTRAS under + OUTER, the last one assigning to STMT's lhs. EXTRAS are leaves of + STMT's own chain, so any combining order is valid. */ + +static void +long_mul_apply_extras (tree acc, const vec<tree> &extras, tree_code outer, + gassign *stmt, gimple_seq *seq) +{ + location_t loc = gimple_location (stmt); + tree lhs = gimple_assign_lhs (stmt); + for (unsigned i = 0; i + 1 < extras.length (); i++) + acc = gimple_build (seq, loc, outer, TREE_TYPE (lhs), acc, extras[i]); + gimple *last = gimple_build_assign (lhs, outer, acc, extras.last ()); + gimple_set_location (last, loc); + gimple_seq_add_stmt (seq, last); +} + +/* Replace STMT with a high-part multiply of OP1 and OP2, combining any + EXTRAS back on top under OUTER. */ + +static void +create_mul_high_seq (tree op1, tree op2, gassign *stmt, + const vec<tree> &extras, tree_code outer) +{ + gimple_seq seq = NULL; + tree lhs = gimple_assign_lhs (stmt); + tree dest = extras.is_empty () ? lhs : make_ssa_name (TREE_TYPE (lhs)); + build_mul_high_seq (op1, op2, dest, gimple_location (stmt), &seq); + if (!extras.is_empty ()) + long_mul_apply_extras (dest, extras, outer, stmt, &seq); + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gsi_replace_with_seq (&gsi, seq, true); +} + +/* Replace STMT with a low-part multiply of OP1 and OP2, combining any + EXTRAS back on top under OUTER. */ + +static void +create_mul_low_seq (tree op1, tree op2, gassign *stmt, + const vec<tree> &extras, tree_code outer) +{ + gimple_seq seq = NULL; + tree lhs = gimple_assign_lhs (stmt); + tree dest = extras.is_empty () ? lhs : make_ssa_name (TREE_TYPE (lhs)); + gimple *prod = gimple_build_assign (dest, MULT_EXPR, op1, op2); + gimple_set_location (prod, gimple_location (stmt)); + gimple_seq_add_stmt (&seq, prod); + if (!extras.is_empty ()) + long_mul_apply_extras (dest, extras, outer, stmt, &seq); + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gsi_replace_with_seq (&gsi, seq, true); +} + +/* Widest match.pd atom (mul_carry_low_sum) takes 7 captures; round up + to 8 for the scratch buffers below. */ +static constexpr unsigned LONG_MUL_MAX_CAPTURES = 8; + +/* Longest variant in long_mul_table has 4 summands. */ +static constexpr unsigned LONG_MUL_MAX_SUMMANDS = 4; + +/* Cap on the leaves set aside as not part of the idiom, so an + arbitrarily long unrelated chain still bails early. */ +static constexpr unsigned LONG_MUL_MAX_EXTRAS = 4; + +enum long_mul_kind { + LMK_MUL_HIHI, + LMK_MUL_LOLO, + LMK_MUL_HILO, + LMK_CROSS_SUM, + LMK_LOW_ACCUM, + LMK_LOW_SUM, + LMK_LADDER_SUM1, + LMK_LADDER_SUM2, + LMK_LADDER_SUM3, + LMK_LADDER_PART_SUM, + LMK_CARRY_LOW, + LMK_CARRY_CROSS_SUM, + LMK_CARRY_LOW_SUM, +}; + +/* How the leaf wraps its inner kind. Carry kinds use LMX_NONE: their + match.pd pattern bakes the lshift in, so the leaf is already the + complete carry expression. */ + +enum long_mul_extract { + LMX_NONE, + LMX_HI, + LMX_LO, + LMX_SHL_N, +}; + +struct long_mul_summand { + long_mul_kind kind; + long_mul_extract extract; + tree op0, op1; + tree hilo0, hilo1, hilo2; + tree carry_a, carry_b; + unsigned HOST_WIDE_INT shift; + unsigned HOST_WIDE_INT mask; +}; + +/* Walk the OUTER addition or BIT_IOR chain rooted at STMT and collect + the leaf operands into LEAVES. Descends through single-use + intermediate stmts of the same code. Returns false once the leaf + count exceeds LONG_MUL_MAX_SUMMANDS + LONG_MUL_MAX_EXTRAS, so an + overlong chain bails mid-walk instead of after a full traversal. + + If SHARED_DEF_OUT is non-NULL, record there the first inner stmt that + shares the outer code but has more than one use -- descending into it + would change semantics, so it stays as a leaf. Such a leaf often + classifies as something no row matches, silently disabling the fold; + the caller surfaces this as a dump-file hint. */ + +static bool +long_mul_linearize_chain (gimple *stmt, tree_code outer, vec<tree> &leaves, + gimple **shared_def_out = NULL) +{ + auto_vec<tree, 8> stack; + stack.safe_push (gimple_assign_rhs2 (stmt)); + stack.safe_push (gimple_assign_rhs1 (stmt)); + + while (!stack.is_empty ()) + { + tree t = stack.pop (); + if (TREE_CODE (t) == SSA_NAME) + { + gimple *def = SSA_NAME_DEF_STMT (t); + if (def + && is_gimple_assign (def) + && gimple_assign_rhs_code (def) == outer) + { + if (has_single_use (t)) + { + stack.safe_push (gimple_assign_rhs2 (def)); + stack.safe_push (gimple_assign_rhs1 (def)); + continue; + } + if (shared_def_out && !*shared_def_out) + *shared_def_out = def; + } + } + leaves.safe_push (t); + if (leaves.length () > LONG_MUL_MAX_SUMMANDS + LONG_MUL_MAX_EXTRAS) + return false; + } + return !leaves.is_empty (); +} + +/* If EXPR is defined by LSHIFT_EXPR with a uhwi-valued amount, return + the shifted input via *INNER_OUT and the amount via *SHIFT_OUT. */ + +static bool +long_mul_is_lshift_def (tree expr, tree *inner_out, + unsigned HOST_WIDE_INT *shift_out) +{ + if (TREE_CODE (expr) != SSA_NAME) + return false; + gimple *def = SSA_NAME_DEF_STMT (expr); + if (!def || !is_gimple_assign (def) + || gimple_assign_rhs_code (def) != LSHIFT_EXPR) + return false; + tree amount = gimple_assign_rhs2 (def); + if (!tree_fits_uhwi_p (amount)) + return false; + *inner_out = gimple_assign_rhs1 (def); + *shift_out = tree_to_uhwi (amount); + return true; +} + +/* Fill INFO's kind plus the captures from RES_OPS that the kind requires. + The kind itself determines how many (op0, op1) and hilo captures to + pick up from RES_OPS, and whether a baked-in shift is present. */ + +static void +long_mul_set_summand (long_mul_summand *info, long_mul_kind kind, + const tree *res_ops) +{ + info->kind = kind; + unsigned n_ops = 0; + unsigned n_hilos = 0; + int shift_idx = -1; + switch (kind) + { + case LMK_MUL_HIHI: + case LMK_MUL_LOLO: + case LMK_MUL_HILO: + n_ops = 2; + break; + case LMK_CROSS_SUM: + n_hilos = 2; + break; + case LMK_LOW_ACCUM: + case LMK_LOW_SUM: + case LMK_LADDER_SUM1: + case LMK_LADDER_SUM2: + case LMK_LADDER_SUM3: + n_ops = 2; + n_hilos = 2; + break; + case LMK_LADDER_PART_SUM: + n_ops = 2; + n_hilos = 1; + break; + case LMK_CARRY_CROSS_SUM: + n_hilos = 3; + shift_idx = 3; + break; + case LMK_CARRY_LOW_SUM: + n_ops = 2; + n_hilos = 3; + shift_idx = 5; + break; + case LMK_CARRY_LOW: + info->carry_a = res_ops[0]; + info->carry_b = res_ops[1]; + return; + } + if (n_ops >= 1) + info->op0 = res_ops[0]; + if (n_ops >= 2) + info->op1 = res_ops[1]; + if (n_hilos >= 1) + info->hilo0 = res_ops[n_ops]; + if (n_hilos >= 2) + info->hilo1 = res_ops[n_ops + 1]; + if (n_hilos >= 3) + info->hilo2 = res_ops[n_ops + 2]; + if (shift_idx >= 0) + /* The carry atoms (mul_carry_cross_sum, mul_carry_low_sum) capture the + shift as an INTEGER_CST already checked with tree_fits_uhwi_p, so this + cannot overflow. */ + info->shift = tree_to_uhwi (res_ops[shift_idx]); +} + +/* Classify LEAF as a carry-kind summand. The lshift amount is baked + into mul_carry_cross_sum / mul_carry_low_sum, so they're tried before + any branch that looks for a generic (X >> N) or (X << N) wrapper. */ + +static bool +long_mul_classify_carry (tree leaf, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + /* mul_carry_low_sum's inner is constrained to mul_low_sum (cross_sum + + mul_hi(mul_lolo)); mul_carry_cross_sum's inner is just + mul_cross_sum (any plus); mul_carry_low matches gt:c (@0, plus(@0, + @1)) without a baked-in shift. Most specific first, so the + less-constrained pattern doesn't shadow the more-constrained one. */ + if (gimple_mul_carry_low_sum (leaf, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_CARRY_LOW_SUM, res_ops); + return true; + } + if (gimple_mul_carry_cross_sum (leaf, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_CARRY_CROSS_SUM, res_ops); + return true; + } + if (gimple_mul_carry_low (leaf, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_CARRY_LOW, res_ops); + return true; + } + return false; +} + +/* Plus-based summand kinds shared by the (X >> SHIFT) and (X << SHIFT) + classifiers. Order is by specificity: mul_low_sum's first arm is any + plus, so mul_ladder_sum1/3 (which constrain that arm to a plus + containing a mul_lo) and mul_low_accum (which constrains both arms) + shadow it and must come first. */ + +static bool +long_mul_classify_plus_kinds (tree inner, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + if (gimple_mul_low_accum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LOW_ACCUM, res_ops); + return true; + } + if (gimple_mul_ladder_sum3 (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LADDER_SUM3, res_ops); + return true; + } + if (gimple_mul_ladder_sum1 (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LADDER_SUM1, res_ops); + return true; + } + if (gimple_mul_low_sum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LOW_SUM, res_ops); + return true; + } + if (gimple_mul_ladder_sum2 (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LADDER_SUM2, res_ops); + return true; + } + return false; +} + +/* Classify INNER -- already unwrapped from an outer (X >> SHIFT) -- as + a high-half-extracted summand. mul_hilo (mult-shape) is orthogonal + to the plus-based kinds and is tried first; ladder_part_sum (one arm + unconstrained) and mul_cross_sum (any plus) are the fallbacks after + the shared plus-based ladder. */ + +static bool +long_mul_classify_hi_extract (tree inner, unsigned HOST_WIDE_INT shift, + long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + info->extract = LMX_HI; + info->shift = shift; + if (gimple_mul_hilo (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_HILO, res_ops); + return true; + } + if (long_mul_classify_plus_kinds (inner, info)) + return true; + if (gimple_mul_ladder_part_sum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_LADDER_PART_SUM, res_ops); + return true; + } + if (gimple_mul_cross_sum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_CROSS_SUM, res_ops); + return true; + } + return false; +} + +/* Classify INNER -- already unwrapped from an outer (X & MASK) -- as + a low-half-masked summand. */ + +static bool +long_mul_classify_lo_extract (tree inner, unsigned HOST_WIDE_INT mask, + long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + info->extract = LMX_LO; + info->mask = mask; + if (gimple_mul_lolo (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_LOLO, res_ops); + return true; + } + return false; +} + +/* Classify INNER -- already unwrapped from an outer (X << SHIFT) -- as + a left-shifted summand. No mul_hilo / ladder_part_sum here -- those + shapes appear only under (X >> SHIFT). */ + +static bool +long_mul_classify_shl_extract (tree inner, unsigned HOST_WIDE_INT shift, + long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + info->extract = LMX_SHL_N; + info->shift = shift; + if (long_mul_classify_plus_kinds (inner, info)) + return true; + if (gimple_mul_cross_sum (inner, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_CROSS_SUM, res_ops); + return true; + } + return false; +} + +/* Classify LEAF as one of the bare-kind summands (no extraction + wrapper): mul_hihi or mul_lolo standing on their own. */ + +static bool +long_mul_classify_bare (tree leaf, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + if (gimple_mul_hihi (leaf, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_HIHI, res_ops); + return true; + } + if (gimple_mul_lolo (leaf, res_ops, NULL)) + { + long_mul_set_summand (info, LMK_MUL_LOLO, res_ops); + return true; + } + return false; +} + +/* Classify LEAF as one of the long-multiply summand shapes. On success, + fill *INFO with the kind, extract, captured operands and shift/mask. + Dispatches to per-extract helpers; the order matters because the + carry kinds bake an lshift into the pattern and would otherwise be + misread by the (X << N) branch. */ + +static bool +long_mul_classify_summand (tree leaf, long_mul_summand *info) +{ + tree res_ops[LONG_MUL_MAX_CAPTURES]; + *info = {}; + + if (long_mul_classify_carry (leaf, info)) + return true; + + if (gimple_mul_hi (leaf, res_ops, NULL)) + return long_mul_classify_hi_extract (res_ops[0], + tree_to_uhwi (res_ops[1]), info); + + if (gimple_mul_lo (leaf, res_ops, NULL)) + return long_mul_classify_lo_extract (res_ops[0], + tree_to_uhwi (res_ops[1]), info); + + tree inner; + unsigned HOST_WIDE_INT shift; + if (long_mul_is_lshift_def (leaf, &inner, &shift)) + return long_mul_classify_shl_extract (inner, shift, info); + + return long_mul_classify_bare (leaf, info); +} + +/* qsort comparator: sort summands by (kind, extract) to put a multiset + into canonical order for table lookup. Unstable sort within a tie is + harmless: no row in long_mul_table pairs distinct subterms under the + same (kind, extract), and long_mul_check_consistency cross-validates + that matching summands share one canonical (op0, op1). */ + +static int +long_mul_summand_compare (const void *a, const void *b) +{ + const long_mul_summand *sa = (const long_mul_summand *) a; + const long_mul_summand *sb = (const long_mul_summand *) b; + if (sa->kind != sb->kind) + return (int) sa->kind - (int) sb->kind; + return (int) sa->extract - (int) sb->extract; +} + +/* One row of the long-multiply variant table. COUNT is how many entries + of SIG carry the row's signature (2 to LONG_MUL_MAX_SUMMANDS); a row + with fewer summands leaves the remaining SIG entries zero-initialized. + Those zeros are not a terminator -- {LMK_MUL_HIHI, LMX_NONE} is itself a + valid signature -- so long_mul_signature_matches is bounded by COUNT, + never by a sentinel entry. */ + +struct long_mul_row { + enum long_mul_row_part { HIGH_PART, LOW_PART } part; + tree_code outer; + unsigned char count; + struct { + long_mul_kind kind; + long_mul_extract extract; + } sig[LONG_MUL_MAX_SUMMANDS]; + bool (*extra_check) (const vec<long_mul_summand> &, gimple *); +}; + +/* True if (A, B) is the same pair as (OP0, OP1) in either order. */ + +static inline bool +long_mul_same_ops (tree a, tree b, tree op0, tree op1) +{ + return (a == op0 && b == op1) || (a == op1 && b == op0); +} + +/* True if H is a cross-half product of (OP0, OP1) -- gimple_mul_hilo + recognizes it and its captured operands match the pair. */ + +static bool +long_mul_is_cross_half (tree h, tree op0, tree op1) +{ + tree scratch[LONG_MUL_MAX_CAPTURES]; + return gimple_mul_hilo (h, scratch, NULL) + && long_mul_same_ops (scratch[0], scratch[1], op0, op1); +} + +/* Orientation of the mul_hilo capture H relative to (OP0, OP1): + returns 0 for high(OP0)*low(OP1), 1 for high(OP1)*low(OP0), or -1 + if H does not decompose that way. A cross-sum of two mul_hilos must + see one of each orientation -- otherwise a doubled factor would fold + to the wrong value. (In a self-multiply the two orientations + coincide; see the OP0 == OP1 bypass in long_mul_check_consistency.) */ + +static int +long_mul_hilo_orientation (tree h, tree op0, tree op1) +{ + tree scratch[LONG_MUL_MAX_CAPTURES]; + if (!gimple_mul_hilo (h, scratch, NULL)) + return -1; + if (scratch[0] == op0 && scratch[1] == op1) + return 0; + if (scratch[0] == op1 && scratch[1] == op0) + return 1; + return -1; +} + +/* Find the first summand that carries operand captures, and return its + (op0, op1) pair in *OP0_OUT / *OP1_OUT. Returns false if no summand + provides them. */ + +static bool +long_mul_canonical_ops (const vec<long_mul_summand> &summands, + tree *op0_out, tree *op1_out) +{ + for (const long_mul_summand &s : summands) + if (s.op0) + { + *op0_out = s.op0; + *op1_out = s.op1; + return true; + } + return false; +} + +/* Return the first summand in SUMMANDS whose kind matches KIND, or NULL. */ + +static const long_mul_summand * +long_mul_find_summand (const vec<long_mul_summand> &summands, + long_mul_kind kind) +{ + for (const long_mul_summand &s : summands) + if (s.kind == kind) + return &s; + return NULL; +} + +/* Run the cross-summand validation invariants and return the canonical + (op0, op1). Returns false unless all summands that carry operands use + the same (op0, op1) pair (in either order), every LMX_HI/LMX_SHL_N shift + equals halfwidth, every captured hilo is a true cross-half product of + (op0, op1), and every cross-half pair (both those inside a single + mul_cross_sum-bearing summand and those spread across separate + LMK_MUL_HILO summands) contains one of each orientation. */ + +static bool +long_mul_check_consistency (const vec<long_mul_summand> &summands, + tree *op0_out, tree *op1_out) +{ + tree op0, op1; + if (!long_mul_canonical_ops (summands, &op0, &op1)) + return false; + + tree op_type = TREE_TYPE (op0); + if (!INTEGRAL_TYPE_P (op_type) + || TYPE_PRECISION (op_type) % 2 != 0) + return false; + unsigned int halfwidth = TYPE_PRECISION (op_type) / 2; + + /* Self-multiply (x*x) collapses the two cross-halves onto one value, + so the complementarity constraint is a trivial no-op there. */ + bool need_orient = op0 != op1; + int mul_hilo_orient[2] = { 0, 0 }; + + for (const long_mul_summand &s : summands) + { + if (s.op0 && !long_mul_same_ops (s.op0, s.op1, op0, op1)) + return false; + if ((s.extract == LMX_HI || s.extract == LMX_SHL_N) + && s.shift != halfwidth) + return false; + tree hilos[3] = { s.hilo0, s.hilo1, s.hilo2 }; + for (tree h : hilos) + if (h && !long_mul_is_cross_half (h, op0, op1)) + return false; + + if (!need_orient) + continue; + + /* The two cross-sum operands are the last two non-null hilos: + (hilo1, hilo2) for the CARRY_*_SUM kinds, (hilo0, hilo1) for + the CROSS_SUM / SUM / ACCUM / LADDER_SUM kinds, none for the + rest. */ + tree a = NULL_TREE; + tree b = NULL_TREE; + if (s.hilo2) + { + a = s.hilo1; + b = s.hilo2; + } + else if (s.hilo1) + { + a = s.hilo0; + b = s.hilo1; + } + if (a && b + && (long_mul_hilo_orientation (a, op0, op1) + == long_mul_hilo_orientation (b, op0, op1))) + return false; + + /* Two LMK_MUL_HILO summands (the two-hilos ladder form) stand for + the two cross-halves separately; count orientations and require + the pair to be complementary. s.op0/op1 is already validated to + match (op0, op1) in some order above. */ + if (s.kind == LMK_MUL_HILO && s.op0) + mul_hilo_orient[s.op0 == op1]++; + } + + if (mul_hilo_orient[0] + mul_hilo_orient[1] >= 2 + && (mul_hilo_orient[0] == 0 || mul_hilo_orient[1] == 0)) + return false; + + *op0_out = op0; + *op1_out = op1; + return true; +} + +/* Compare the (already-sorted) SUMMANDS multiset against ROW.sig. */ + +static bool +long_mul_signature_matches (const vec<long_mul_summand> &summands, + const long_mul_row &row) +{ + if (row.count != summands.length ()) + return false; + for (unsigned i = 0; i < row.count; i++) + if (summands[i].kind != row.sig[i].kind + || summands[i].extract != row.sig[i].extract) + return false; + return true; +} + +/* Extra check for the two-carries high-part row: the LMK_CARRY_LOW summand's + two operands (carry_a, carry_b) must be a (cross_shifted, mul_lolo) pair + consistent with the multiset's canonical (op0, op1). */ + +static bool +long_mul_check_two_carries (const vec<long_mul_summand> &summands, + gimple *) +{ + tree op0, op1; + if (!long_mul_canonical_ops (summands, &op0, &op1)) + return false; + unsigned int halfwidth = TYPE_PRECISION (TREE_TYPE (op0)) / 2; + + const long_mul_summand *cl = long_mul_find_summand (summands, LMK_CARRY_LOW); + if (!cl) + return false; + + /* The two carry_low operands must be (cross_shifted, mul_lolo) in either + order. cross_shifted = LSHIFT_EXPR (mul_cross_sum, halfwidth). */ + tree cs = cl->carry_a, lolo = cl->carry_b; + tree inner; + unsigned HOST_WIDE_INT shift; + if (!long_mul_is_lshift_def (cs, &inner, &shift)) + { + std::swap (cs, lolo); + if (!long_mul_is_lshift_def (cs, &inner, &shift)) + return false; + } + if (shift != halfwidth) + return false; + + tree scratch[LONG_MUL_MAX_CAPTURES]; + if (!gimple_mul_cross_sum (inner, scratch, NULL)) + return false; + for (int i = 0; i < 2; i++) + if (!long_mul_is_cross_half (scratch[i], op0, op1)) + return false; + if (!gimple_mul_lolo (lolo, scratch, NULL) + || !long_mul_same_ops (scratch[0], scratch[1], op0, op1)) + return false; + + return true; +} + +/* The lolo + cross_shifted shape is also the low half of a two-carry + long-multiply, where an unsigned overflow compare against one of + the PLUS operands is the low-carry term consumed by the matching + high-part fold. Folding to mul_lo here destroys cross_shifted, + which both the compare and the high-part match still need; defer + so the high-part fold runs first. After it does, the compare is + dead and the surviving lolo + cross_shifted is picked up by this + row in the next forwprop instance. Returns false to defer. */ + +static bool +long_mul_check_low_plus_defer (const vec<long_mul_summand> &, gimple *stmt) +{ + /* The PHI entry passes its gphi as the candidate but commits only to + HIGH_PART rows, so a LOW_PART row never folds from there. Guard the + gimple_assign accessors regardless, so this stays correct if a future + PLUS-shaped row reachable from the PHI path uses it. */ + if (!is_gimple_assign (stmt)) + return false; + + tree lhs = gimple_assign_lhs (stmt); + tree rhs1 = gimple_assign_rhs1 (stmt); + tree rhs2 = gimple_assign_rhs2 (stmt); + + imm_use_iterator iter; + gimple *use_stmt; + FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) + { + tree cmp_op1 = NULL_TREE, cmp_op2 = NULL_TREE; + enum tree_code use_code = ERROR_MARK; + if (is_gimple_assign (use_stmt)) + { + use_code = gimple_assign_rhs_code (use_stmt); + cmp_op1 = gimple_assign_rhs1 (use_stmt); + cmp_op2 = gimple_assign_rhs2 (use_stmt); + } + else if (gcond *cond = dyn_cast<gcond *> (use_stmt)) + { + use_code = gimple_cond_code (cond); + cmp_op1 = gimple_cond_lhs (cond); + cmp_op2 = gimple_cond_rhs (cond); + } + if (use_code == GT_EXPR || use_code == LT_EXPR + || use_code == GE_EXPR || use_code == LE_EXPR) + { + tree other = (cmp_op1 == lhs) ? cmp_op2 + : (cmp_op2 == lhs) ? cmp_op1 : NULL_TREE; + if (other && (other == rhs1 || other == rhs2)) + return false; + } + } + return true; +} + +/* Long-multiply variant table. Each row enumerates the multiset of + (kind, extract) summands that compose one long-multiply form. Rows + are sorted by long_mul_summand_compare, matching the input summands' + sort order, so a plain element-wise compare suffices. Rows describe + unsigned schoolbook expansions on an even-width 2N-bit type split at + half-width N; EXTRA_CHECK carries invariants the (kind, extract) + signature cannot express. + + The formula on each row uses xh, xl, yh, yl for the half-width pieces + of x and y, cross_sum for xh*yl + xl*yh, and hilo for either cross-half + product (consumers validate the operand shape). */ + +static const long_mul_row long_mul_table[] = { + /* HIGH-PART folds. */ + /* xh*yh + (low_sum >> N) + ((hilo > low_sum) << N), + low_sum = cross_sum + (xl*yl >> N). */ + { long_mul_row::HIGH_PART, PLUS_EXPR, 3, + { { LMK_MUL_HIHI, LMX_NONE }, + { LMK_LOW_SUM, LMX_HI }, + { LMK_CARRY_LOW_SUM, LMX_NONE } }, + NULL }, + /* xh*yh + (low_accum >> N) + (cross_sum >> N) + ((hilo > cross_sum) << N), + low_accum = (xl*yl >> N) + (cross_sum & mask). */ + { long_mul_row::HIGH_PART, PLUS_EXPR, 4, + { { LMK_MUL_HIHI, LMX_NONE }, + { LMK_CROSS_SUM, LMX_HI }, + { LMK_LOW_ACCUM, LMX_HI }, + { LMK_CARRY_CROSS_SUM, LMX_NONE } }, + NULL }, + /* xh*yh + (cross_sum >> N) + carry_low + ((hilo > cross_sum) << N), + carry_low = (xl*yl + (cross_sum << N)) < (cross_sum << N). */ + { long_mul_row::HIGH_PART, PLUS_EXPR, 4, + { { LMK_MUL_HIHI, LMX_NONE }, + { LMK_CROSS_SUM, LMX_HI }, + { LMK_CARRY_LOW, LMX_NONE }, + { LMK_CARRY_CROSS_SUM, LMX_NONE } }, + long_mul_check_two_carries }, + /* xh*yh + (hilo >> N) + (ladder_sum1 >> N), + ladder_sum1 = (hilo & mask) + hilo' + (xl*yl >> N), + hilo, hilo' the two cross-half products. */ + { long_mul_row::HIGH_PART, PLUS_EXPR, 3, + { { LMK_MUL_HIHI, LMX_NONE }, + { LMK_MUL_HILO, LMX_HI }, + { LMK_LADDER_SUM1, LMX_HI } }, + NULL }, + /* xh*yh + (ladder_sum2 >> N) + (ladder_part_sum >> N), + ladder_part_sum = (xl*yl >> N) + hilo, + ladder_sum2 = (ladder_part_sum & mask) + hilo'. */ + { long_mul_row::HIGH_PART, PLUS_EXPR, 3, + { { LMK_MUL_HIHI, LMX_NONE }, + { LMK_LADDER_SUM2, LMX_HI }, + { LMK_LADDER_PART_SUM, LMX_HI } }, + NULL }, + /* xh*yh + (hilo >> N) + (hilo' >> N) + (ladder_sum3 >> N), + ladder_sum3 = (hilo & mask) + (hilo' & mask) + (xl*yl >> N). */ + { long_mul_row::HIGH_PART, PLUS_EXPR, 4, + { { LMK_MUL_HIHI, LMX_NONE }, + { LMK_MUL_HILO, LMX_HI }, + { LMK_MUL_HILO, LMX_HI }, + { LMK_LADDER_SUM3, LMX_HI } }, + NULL }, + /* LOW-PART folds. Recover the lower 2N bits from xl*yl plus a + shifted cross-half term. */ + /* xl*yl + (cross_sum << N). */ + { long_mul_row::LOW_PART, PLUS_EXPR, 2, + { { LMK_MUL_LOLO, LMX_NONE }, + { LMK_CROSS_SUM, LMX_SHL_N } }, + long_mul_check_low_plus_defer }, + /* (xl*yl & mask) | (low_accum << N), + low_accum = (xl*yl >> N) + (cross_sum & mask). */ + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, + { { LMK_MUL_LOLO, LMX_LO }, + { LMK_LOW_ACCUM, LMX_SHL_N } }, + NULL }, + /* (xl*yl & mask) | (low_sum << N), + low_sum = cross_sum + (xl*yl >> N). */ + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, + { { LMK_MUL_LOLO, LMX_LO }, + { LMK_LOW_SUM, LMX_SHL_N } }, + NULL }, + /* (xl*yl & mask) | (ladder_sum1 << N), + ladder_sum1 as in the high ladder row above. */ + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, + { { LMK_MUL_LOLO, LMX_LO }, + { LMK_LADDER_SUM1, LMX_SHL_N } }, + NULL }, + /* (xl*yl & mask) | (ladder_sum2 << N), + ladder_sum2 as in the high ladder row above. */ + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, + { { LMK_MUL_LOLO, LMX_LO }, + { LMK_LADDER_SUM2, LMX_SHL_N } }, + NULL }, + /* (xl*yl & mask) | (ladder_sum3 << N), + ladder_sum3 as in the high ladder-long row above. */ + { long_mul_row::LOW_PART, BIT_IOR_EXPR, 2, + { { LMK_MUL_LOLO, LMX_LO }, + { LMK_LADDER_SUM3, LMX_SHL_N } }, + NULL }, +}; + +/* If a multi-used inner addition (sharing the chain's outer code) blocked + linearization of a long-mul candidate, emit a dump-file hint pointing + at it. */ + +static void +long_mul_hint_shared_intermediate (gimple *shared_def) +{ + if (!shared_def || !dump_file || !(dump_flags & TDF_DETAILS)) + return; + fprintf (dump_file, "long-mul fold rejected: shared intermediate at "); + print_gimple_stmt (dump_file, shared_def, 0, TDF_SLIM); +} + +/* Search long_mul_table for a row whose multiset matches SUMMANDS for + outer kind OUTER on a result of type LHS_TYPE. CANDIDATE_STMT is + passed to per-row extra_check predicates. On a hit, returns the + matching row and writes the half-width operands via OUT_OP0/OUT_OP1. + No IR mutation. */ + +static const long_mul_row * +long_mul_classify_match (const vec<long_mul_summand> &summands, + tree lhs_type, tree_code outer, + gimple *candidate_stmt, + tree *out_op0, tree *out_op1) +{ + /* HIGH_PART rows emit a 2N-bit multiply that pass_optimize + _widening_mul consumes -- either via WIDEN_MULT_EXPR / + MULT_HIGHPART conversion when the target has a native 2N + multiply, or via lower_long_mul_high_chain when it does not. + LOW_PART rows emit a plain MULT_EXPR. Emission needs a 2N + mode to exist in the mode table AND the widening_mul pass to + be active: without the pass, the emit could reach RTL expand + as an unexpandable 2N multiply (e.g. OImode). BITINT_TYPE is + refused -- the long_mul_high_chain atom excludes it. */ + scalar_int_mode mode, wide_mode; + bool can_emit_high + = optimize_widening_mul_active_p () + && TREE_CODE (lhs_type) != BITINT_TYPE + && is_a <scalar_int_mode> (TYPE_MODE (lhs_type), &mode) + && GET_MODE_2XWIDER_MODE (mode).exists (&wide_mode); + + for (const long_mul_row &row : long_mul_table) + { + if (row.outer != outer + || (row.part == long_mul_row::HIGH_PART && !can_emit_high) + || !long_mul_signature_matches (summands, row)) + continue; + + tree op0, op1; + if (!long_mul_check_consistency (summands, &op0, &op1)) + continue; + + /* Do not emit the wide chain when an operand is subject to + abnormal coalescing: the widening_mul-side consumers refuse + such operands (see convert_mult_to_widen), which would leave + the chain without a consumer. */ + if (row.part == long_mul_row::HIGH_PART + && ((TREE_CODE (op0) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)) + || (TREE_CODE (op1) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)))) + continue; + + if (row.extra_check && !row.extra_check (summands, candidate_stmt)) + continue; + + *out_op0 = op0; + *out_op1 = op1; + return &row; + } + return NULL; +} + +/* Walk STMT's outer chain (kind OUTER), classify each leaf as a + long-multiply summand, optionally add the already-classified EXTRA, + and look the multiset up in long_mul_table for a result of type + LHS_TYPE. CANDIDATE is passed to per-row extra_check predicates. + + If EXTRAS_OUT is non-NULL, leaves matching no summand are set aside + there instead of failing the match, and the caller must re-apply + them on top of the folded multiply. A leaf that does match is + always consumed: if that makes the signature miss every row the + match fails, rather than retrying with the leaf demoted to an extra + (subset search would be exponential). + + Returns the matched row and the half-width operands via + OUT_OP0/OUT_OP1, or NULL on a miss. No IR mutation. */ + +static const long_mul_row * +long_mul_classify_chain (gimple *stmt, tree_code outer, tree lhs_type, + gimple *candidate, const long_mul_summand *extra, + vec<tree> *extras_out, + tree *out_op0, tree *out_op1) +{ + auto_vec<tree, LONG_MUL_MAX_SUMMANDS + LONG_MUL_MAX_EXTRAS> leaves; + gimple *shared_def = NULL; + if (!long_mul_linearize_chain (stmt, outer, leaves, &shared_def)) + return NULL; + + auto_vec<long_mul_summand, + LONG_MUL_MAX_SUMMANDS + LONG_MUL_MAX_EXTRAS + 1> summands; + for (tree leaf : leaves) + { + long_mul_summand s; + if (long_mul_classify_summand (leaf, &s)) + summands.quick_push (s); + else if (extras_out && extras_out->length () < LONG_MUL_MAX_EXTRAS) + extras_out->safe_push (leaf); + else + { + long_mul_hint_shared_intermediate (shared_def); + return NULL; + } + } + if (extra) + summands.quick_push (*extra); + if (summands.length () < 2 + || summands.length () > LONG_MUL_MAX_SUMMANDS) + return NULL; + summands.qsort (long_mul_summand_compare); + + const long_mul_row *row + = long_mul_classify_match (summands, lhs_type, outer, candidate, + out_op0, out_op1); + if (!row) + long_mul_hint_shared_intermediate (shared_def); + return row; +} + +/* Top-level entry for long-multiply folding. Walks STMT's outer + addition or BIT_IOR chain, classifies the summands, and dispatches + to create_mul_high_seq / create_mul_low_seq if the multiset matches + a known long-multiply form. Returns true on success. */ + +static bool +match_long_mul (gassign *stmt) +{ + tree_code outer = gimple_assign_rhs_code (stmt); + if (outer != PLUS_EXPR && outer != BIT_IOR_EXPR) + return false; + + /* Skip non-candidate adds (signed, pointer, odd-width) before walking the + chain. No legitimate long-mul leaf has a type the atoms would reject. + This just avoids the linearize/classify work on every other PLUS/IOR. */ + tree lhs_type = TREE_TYPE (gimple_assign_lhs (stmt)); + if (!INTEGRAL_TYPE_P (lhs_type) + || !TYPE_UNSIGNED (lhs_type) + || TYPE_PRECISION (lhs_type) % 2 != 0) + return false; + + /* Only start at the end of a chain: a consumer with the same code + linearizes through this statement anyway, so starting here is + redundant. A consumer in another block does not count -- folding + at the later use could sink a loop-invariant multiply into a + loop. */ + use_operand_p use_p; + gimple *use_stmt; + if (single_imm_use (gimple_assign_lhs (stmt), &use_p, &use_stmt) + && is_gimple_assign (use_stmt) + && gimple_assign_rhs_code (use_stmt) == outer + && gimple_bb (use_stmt) == gimple_bb (stmt)) + return false; + + auto_vec<tree, LONG_MUL_MAX_EXTRAS> extras; + tree op0, op1; + const long_mul_row *row + = long_mul_classify_chain (stmt, outer, lhs_type, stmt, NULL, &extras, + &op0, &op1); + if (!row) + return false; + + if (row->part == long_mul_row::HIGH_PART) + { + create_mul_high_seq (op0, op1, stmt, extras, outer); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Long multiplication high part folded.\n"); + return true; + } + create_mul_low_seq (op0, op1, stmt, extras, outer); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Long multiplication low part folded.\n"); + return true; +} + +/* PHI-driven entry for long-multiply folding. When PHI's value + flattens to base + (carry << N), probe sum to classify the carry + kind, linearize base for the remaining high-part summands, and run + the long-multiply table. On a hit, emit a 2N-bit multiply at the + top of the join block with PHI_RES as its LHS and remove the PHI. + Otherwise leave the IR untouched. Only HIGH_PART rows are + reachable. LOW_PART rows are BIT_IOR-shaped and never produce a + carry PHI. */ + +static bool +match_long_mul_phi (gphi *phi) +{ + tree phi_res = gimple_phi_result (phi); + tree lhs_type = TREE_TYPE (phi_res); + if (!INTEGRAL_TYPE_P (lhs_type) || !TYPE_UNSIGNED (lhs_type) + || TYPE_PRECISION (lhs_type) % 2 != 0) + return false; + + tree cca_ops[4]; + if (!gimple_cond_carry_add (phi_res, cca_ops, NULL) + && !gimple_cond_carry_add_neg (phi_res, cca_ops, NULL)) + return false; + tree cmp_lhs = cca_ops[0]; + tree sum = cca_ops[1]; + tree base = cca_ops[2]; + + /* Classify sum and populate the carry summand directly. Most + specific first, mirroring long_mul_classify_carry's order. */ + long_mul_summand carry = {}; + tree sum_ops[LONG_MUL_MAX_CAPTURES]; + unsigned HOST_WIDE_INT shift_amt + = wi::exact_log2 (wi::to_wide (cca_ops[3])); + unsigned HOST_WIDE_INT halfwidth = TYPE_PRECISION (lhs_type) / 2; + carry.shift = shift_amt; + + if (gimple_mul_low_sum (sum, sum_ops, NULL) + && shift_amt == halfwidth) + { + /* mul_carry_low_sum's flat form ties the outer lshift amount to + the inner mul_hi's INTEGER_CST@0 via match.pd capture re-use; + the PHI form has no such tie, so gate on shift_amt explicitly. */ + carry.kind = LMK_CARRY_LOW_SUM; + carry.op0 = sum_ops[0]; + carry.op1 = sum_ops[1]; + carry.hilo0 = cmp_lhs; + carry.hilo1 = sum_ops[2]; + carry.hilo2 = sum_ops[3]; + } + else if (gimple_mul_cross_sum (sum, sum_ops, NULL) + && shift_amt == halfwidth) + { + /* mul_cross_sum is just (plus:c @0 @1) with no half-width + constraint. Gate here to mirror mul_carry_cross_sum; + a mismatch falls through to the LMK_CARRY_LOW branch. */ + carry.kind = LMK_CARRY_CROSS_SUM; + carry.hilo0 = cmp_lhs; + carry.hilo1 = sum_ops[0]; + carry.hilo2 = sum_ops[1]; + } + else if (shift_amt == 0 && TREE_CODE (sum) == SSA_NAME) + { + gimple *def = SSA_NAME_DEF_STMT (sum); + if (!is_gimple_assign (def) + || gimple_assign_rhs_code (def) != PLUS_EXPR) + return false; + tree p1 = gimple_assign_rhs1 (def); + tree p2 = gimple_assign_rhs2 (def); + if (p1 != cmp_lhs && p2 != cmp_lhs) + return false; + carry.kind = LMK_CARRY_LOW; + carry.carry_a = cmp_lhs; + carry.carry_b = p1 == cmp_lhs ? p2 : p1; + } + else + return false; + + /* Linearize base, the rest of the high-part chain. */ + if (TREE_CODE (base) != SSA_NAME) + return false; + gimple *base_def = SSA_NAME_DEF_STMT (base); + if (!is_gimple_assign (base_def) + || gimple_assign_rhs_code (base_def) != PLUS_EXPR) + return false; + + tree op0, op1; + const long_mul_row *row + = long_mul_classify_chain (base_def, PLUS_EXPR, lhs_type, phi, &carry, + NULL, &op0, &op1); + if (!row || row->part != long_mul_row::HIGH_PART) + return false; + + gimple_seq seq = NULL; + build_mul_high_seq (op0, op1, phi_res, gimple_location (phi), &seq); + gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi)); + gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT); + gimple_stmt_iterator psi = gsi_for_stmt (phi); + remove_phi_node (&psi, false); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Long multiplication high part folded (carry PHI).\n"); + return true; +} /* Determine whether applying the 2 permutations (mask1 then mask2) gives back one of the input. */ @@ -5409,14 +6581,19 @@ pass_forwprop::execute (function *fun) } } - /* Record degenerate PHIs in the lattice. */ - for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si); - gsi_next (&si)) + /* Fold PHI-form long-multiply carries and record degenerate + PHIs in the lattice. Iterator advanced up front so a folded + PHI can be removed in-flight; a long-mul carry PHI is never + degenerate, so the two cases are disjoint. */ + for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);) { gphi *phi = si.phi (); + gsi_next (&si); tree res = gimple_phi_result (phi); if (virtual_operand_p (res)) continue; + if (match_long_mul_phi (phi)) + continue; tree first = NULL_TREE; bool all_same = true; @@ -5882,11 +7059,15 @@ pass_forwprop::execute (function *fun) } else if (TREE_CODE_CLASS (code) == tcc_comparison) changed |= forward_propagate_into_comparison (&gsi); - else if ((code == PLUS_EXPR - || code == BIT_IOR_EXPR - || code == BIT_XOR_EXPR) - && simplify_rotate (&gsi)) - changed = true; + else if ((code == PLUS_EXPR || code == BIT_IOR_EXPR)) + { + bool folded = match_long_mul (as_a <gassign *> (stmt)); + if (!folded) + folded = simplify_rotate (&gsi); + changed |= folded; + } + else if (code == BIT_XOR_EXPR) + changed |= simplify_rotate (&gsi); else if (code == VEC_PERM_EXPR) changed |= simplify_permutation (&gsi); else if (code == CONSTRUCTOR diff --git a/gcc/tree-ssa-math-opts.cc b/gcc/tree-ssa-math-opts.cc index 0df1909ebc43..ead37104840a 100644 --- a/gcc/tree-ssa-math-opts.cc +++ b/gcc/tree-ssa-math-opts.cc @@ -6541,6 +6541,484 @@ optimize_spaceship (gcond *stmt) } +/* Long-multiply inverse-lowering helper. + + The forwprop long-multiply recognizer canonicalizes a hand-written + longhand high-part multiply into a cast+mult+shift+cast chain + `(N) ((2N) a * (2N) b) >> N'. When the target lacks an expansion + path for the wide form, `lower_long_mul_high_chain' resynthesizes + the longhand at narrow precision via `build_long_mul_partials'. */ + +/* Test whether the target supports an (HALF)-by-(HALF)->NARROW unsigned + widening multiply. Returns true on success, with the half-width + scalar int mode placed in *HALF_MODE. */ + +static bool +can_widen_to_narrow_p (scalar_int_mode narrow_mode, unsigned int half_width, + scalar_int_mode *half_mode) +{ + if (!int_mode_for_size (half_width, 0).exists (half_mode)) + return false; + return convert_optab_handler (umul_widen_optab, narrow_mode, *half_mode) + != CODE_FOR_nothing; +} + +/* Append to *SEQ the operand split and partial products for an unsigned + long multiply of OP1 by OP2 at the precision of TREE_TYPE (OP1). + HALF_TYPE is the (N/2)-bit unsigned type; HALF_AMT is the integer-typed + shift constant equal to N/2. + + Outputs the four partial products via *LOLO, *HILO, *LOHI, *HIHI. + + USE_WIDEN selects the partial-product form: + true - cast halves to HALF_TYPE and use WIDEN_MULT_EXPR (needs + an (N/2)-by-(N/2)->N widening multiply optab). + false - mask/shift halves within the N-bit accumulator and use + plain MULT_EXPR; the halves fit in N/2 bits so the N-bit + low product is exact. */ + +static void +build_long_mul_partials (gimple_seq *seq, location_t loc, tree op1, tree op2, + tree half_type, tree half_amt, + tree *lolo, tree *hilo, tree *lohi, tree *hihi, + bool use_widen) +{ + tree acc_type = TREE_TYPE (op1); + tree op1_hi = gimple_build (seq, loc, RSHIFT_EXPR, acc_type, op1, half_amt); + tree op2_hi = gimple_build (seq, loc, RSHIFT_EXPR, acc_type, op2, half_amt); + tree op1_lo, op2_lo; + tree_code mul_code; + + if (use_widen) + { + op1_lo = gimple_build (seq, loc, NOP_EXPR, half_type, op1); + op2_lo = gimple_build (seq, loc, NOP_EXPR, half_type, op2); + op1_hi = gimple_build (seq, loc, NOP_EXPR, half_type, op1_hi); + op2_hi = gimple_build (seq, loc, NOP_EXPR, half_type, op2_hi); + mul_code = WIDEN_MULT_EXPR; + } + else + { + tree mask = wide_int_to_tree (acc_type, + wi::mask (TYPE_PRECISION (half_type), false, + TYPE_PRECISION (acc_type))); + op1_lo = gimple_build (seq, loc, BIT_AND_EXPR, acc_type, op1, mask); + op2_lo = gimple_build (seq, loc, BIT_AND_EXPR, acc_type, op2, mask); + mul_code = MULT_EXPR; + } + + *lolo = gimple_build (seq, loc, mul_code, acc_type, op1_lo, op2_lo); + *hilo = gimple_build (seq, loc, mul_code, acc_type, op1_hi, op2_lo); + *lohi = gimple_build (seq, loc, mul_code, acc_type, op1_lo, op2_hi); + *hihi = gimple_build (seq, loc, mul_code, acc_type, op1_hi, op2_hi); +} + +/* Emit into *SEQ the high N bits of the unsigned product A * B, where A and B + are NARROW_TYPE (N-bit) values, as a longhand over (N/2)-bit partials. + Returns the high-part SSA. */ + +static tree +emit_long_mul_highpart (gimple_seq *seq, location_t loc, tree a, tree b, + tree narrow_type) +{ + scalar_int_mode narrow_mode + = as_a <scalar_int_mode> (TYPE_MODE (narrow_type)); + unsigned int half_width = GET_MODE_PRECISION (narrow_mode) / 2; + /* Prefer (N/2)-by-(N/2)->N widening partials; fall back to plain MULT_EXPR + when the target lacks the widen optab. See build_long_mul_partials. */ + scalar_int_mode half_mode; + bool use_widen = can_widen_to_narrow_p (narrow_mode, half_width, &half_mode); + tree half_type = build_nonstandard_integer_type (half_width, 1); + tree half_amt = build_int_cst (integer_type_node, half_width); + tree half_mask = wide_int_to_tree (narrow_type, + wi::mask (half_width, false, + TYPE_PRECISION (narrow_type))); + + tree lolo, hilo, lohi, hihi; + build_long_mul_partials (seq, loc, a, b, half_type, half_amt, + &lolo, &hilo, &lohi, &hihi, use_widen); + tree cross_sum = gimple_build (seq, loc, PLUS_EXPR, narrow_type, hilo, lohi); + tree cross_lt = gimple_build (seq, loc, LT_EXPR, boolean_type_node, + cross_sum, hilo); + tree cross_lt_n = gimple_build (seq, loc, NOP_EXPR, narrow_type, cross_lt); + tree cross_carry = gimple_build (seq, loc, LSHIFT_EXPR, narrow_type, + cross_lt_n, half_amt); + tree lolo_hi = gimple_build (seq, loc, RSHIFT_EXPR, narrow_type, + lolo, half_amt); + tree cross_lo = gimple_build (seq, loc, BIT_AND_EXPR, narrow_type, + cross_sum, half_mask); + tree low_accum = gimple_build (seq, loc, PLUS_EXPR, narrow_type, + lolo_hi, cross_lo); + tree low_accum_hi = gimple_build (seq, loc, RSHIFT_EXPR, narrow_type, + low_accum, half_amt); + tree cross_hi = gimple_build (seq, loc, RSHIFT_EXPR, narrow_type, + cross_sum, half_amt); + tree t1 = gimple_build (seq, loc, PLUS_EXPR, narrow_type, hihi, cross_hi); + tree t2 = gimple_build (seq, loc, PLUS_EXPR, narrow_type, t1, low_accum_hi); + return gimple_build (seq, loc, PLUS_EXPR, narrow_type, t2, cross_carry); +} + +/* Emit into *SEQ the high N bits (NARROW_TYPE) of the unsigned product of two + 2N-bit values given as N-bit halves, x = L1 + H1*2^N and y = L2 + H2*2^N: + the high half of x*y is the high N bits of L1*L2, plus H1*L2 and L1*H2, all + mod 2^N. */ + +static tree +combine_long_mul_halves (gimple_seq *seq, location_t loc, tree l1, tree h1, + tree l2, tree h2, tree narrow_type) +{ + tree hh = emit_long_mul_highpart (seq, loc, l1, l2, narrow_type); + tree c1 = gimple_build (seq, loc, MULT_EXPR, narrow_type, h1, l2); + tree c2 = gimple_build (seq, loc, MULT_EXPR, narrow_type, l1, h2); + tree s = gimple_build (seq, loc, PLUS_EXPR, narrow_type, hh, c1); + return gimple_build (seq, loc, PLUS_EXPR, narrow_type, s, c2); +} + +/* True when OP fits NARROW_PREC bits as an unsigned value. Looks + through widening casts and PHIs, falling back to `tree_nonzero_bits' + otherwise. PHI_SEEN guards against cycles. */ + +static bool +long_mul_op_fits_p (tree op, unsigned narrow_prec, bitmap phi_seen) +{ + if (!TYPE_UNSIGNED (TREE_TYPE (op))) + return false; + if (TYPE_PRECISION (TREE_TYPE (op)) <= narrow_prec) + return true; + if (TREE_CODE (op) == SSA_NAME) + { + gimple *def = SSA_NAME_DEF_STMT (op); + if (is_gimple_assign (def) + && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))) + return long_mul_op_fits_p (gimple_assign_rhs1 (def), narrow_prec, + phi_seen); + if (gphi *phi = dyn_cast <gphi *> (def)) + if (bitmap_set_bit (phi_seen, SSA_NAME_VERSION (op))) + { + for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) + if (!long_mul_op_fits_p (gimple_phi_arg_def (phi, i), + narrow_prec, phi_seen)) + return false; + return true; + } + } + return wi::min_precision (tree_nonzero_bits (op), UNSIGNED) <= narrow_prec; +} + +/* Split the 2N-bit unsigned value OP into its low and high N bits (*LO and + *HI, both NARROW_TYPE) using only N-bit operations, as the target has no 2N + multiply or shift. A 2N product recurses on its operands, its high half + coming from combine_long_mul_halves. A value shifted down by N recurses on + the shifted value and takes its high half, rather than reading the 2N shift. + A widening cast's low half is the truncated source and its high half is what + the cast extended with, zero or the source's replicated sign bit. A value + that provably fits N bits has a zero high half. Returns false otherwise. */ + +static bool +long_mul_split_operand (gimple_seq *seq, location_t loc, tree op, + tree narrow_type, tree *lo, tree *hi) +{ + unsigned int narrow_prec = TYPE_PRECISION (narrow_type); + if (TREE_CODE (op) == SSA_NAME) + { + gimple *def = SSA_NAME_DEF_STMT (op); + if (is_gimple_assign (def) && gimple_assign_rhs_code (def) == MULT_EXPR) + { + tree a_lo, a_hi, b_lo, b_hi; + if (!long_mul_split_operand (seq, loc, gimple_assign_rhs1 (def), + narrow_type, &a_lo, &a_hi) + || !long_mul_split_operand (seq, loc, gimple_assign_rhs2 (def), + narrow_type, &b_lo, &b_hi)) + return false; + *lo = gimple_build (seq, loc, MULT_EXPR, narrow_type, a_lo, b_lo); + *hi = combine_long_mul_halves (seq, loc, a_lo, a_hi, b_lo, b_hi, + narrow_type); + return true; + } + /* A 2N value shifted down by N is its own high half: split the source + and use that half. Reading the shift instead leaves the 2N source + live, and the target cannot expand it. This has to come before the + widening-cast case below, which would take such a value as it + stands. */ + if (is_gimple_assign (def) + && gimple_assign_rhs_code (def) == RSHIFT_EXPR + && tree_fits_uhwi_p (gimple_assign_rhs2 (def)) + && tree_to_uhwi (gimple_assign_rhs2 (def)) == narrow_prec) + { + tree src_lo, src_hi; + if (!long_mul_split_operand (seq, loc, gimple_assign_rhs1 (def), + narrow_type, &src_lo, &src_hi)) + return false; + *lo = src_hi; + *hi = build_zero_cst (narrow_type); + return true; + } + if (is_gimple_assign (def) + && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))) + { + tree src = gimple_assign_rhs1 (def); + tree src_type = TREE_TYPE (src); + if (INTEGRAL_TYPE_P (src_type) + && TYPE_PRECISION (src_type) <= narrow_prec) + { + *lo = gimple_convert (seq, loc, narrow_type, src); + if (TYPE_UNSIGNED (src_type)) + *hi = build_zero_cst (narrow_type); + else + { + /* Sign extension: the high N bits replicate the sign bit. */ + tree snarrow = signed_type_for (narrow_type); + tree s = gimple_convert (seq, loc, snarrow, *lo); + tree amt = build_int_cst (integer_type_node, narrow_prec - 1); + tree sh = gimple_build (seq, loc, RSHIFT_EXPR, snarrow, s, + amt); + *hi = gimple_convert (seq, loc, narrow_type, sh); + } + return true; + } + } + } + + /* A value provably within N bits: its low half is the truncation to N bits + (a subreg, not a 2N shift), its high half is zero. */ + auto_bitmap phi_seen; + if (long_mul_op_fits_p (op, narrow_prec, phi_seen)) + { + *lo = gimple_convert (seq, loc, narrow_type, op); + *hi = build_zero_cst (narrow_type); + return true; + } + return false; +} + +/* True when every use of PROD reads only its low NARROW_PREC bits -- a + truncation to at most NARROW_PREC bits, or an AND with a low-bit mask. */ + +static bool +long_mul_only_low_half_used_p (tree prod, unsigned int narrow_prec) +{ + imm_use_iterator iui; + gimple *use_stmt; + FOR_EACH_IMM_USE_STMT (use_stmt, iui, prod) + { + if (is_gimple_debug (use_stmt)) + continue; + if (!is_gimple_assign (use_stmt)) + return false; + tree_code code = gimple_assign_rhs_code (use_stmt); + if (CONVERT_EXPR_CODE_P (code)) + { + tree t = TREE_TYPE (gimple_assign_lhs (use_stmt)); + if (!INTEGRAL_TYPE_P (t) || TYPE_PRECISION (t) > narrow_prec) + return false; + } + else if (code == BIT_AND_EXPR + && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST) + { + if (wi::min_precision (wi::to_wide (gimple_assign_rhs2 (use_stmt)), + UNSIGNED) > narrow_prec) + return false; + } + else + return false; + } + return true; +} + +static bool narrow_long_mul_low_half (gimple_stmt_iterator *); + +/* OP1 and OP2 are the operands of a 2N multiply just narrowed or lowered; + that rewrite now reads each through an N-bit low-half cast. An operand + defined by another 2N multiply can thereby become low-half-only -- narrow + it too, recursing through chained wide products such as (a*b)*c. */ + +static void +narrow_long_mul_operands (tree op1, tree op2) +{ + for (tree op : { op1, op2 }) + if (TREE_CODE (op) == SSA_NAME) + { + gimple *def = SSA_NAME_DEF_STMT (op); + if (is_gimple_assign (def) && gimple_assign_rhs_code (def) == MULT_EXPR) + { + gimple_stmt_iterator dgsi = gsi_for_stmt (def); + narrow_long_mul_low_half (&dgsi); + } + } +} + +/* If the statement at *GSI is res = a * b with a 2N-bit unsigned result + whose mode the target cannot multiply (no insn and no libcall, so it would + abort expand_mult), and every use reads only the low N bits, narrow it to + res = (2N) ((N) a * (N) b) and return true. The low N bits of a product + depend only on the low N bits of the operands, so this preserves every + use; the unused high half becomes zero. The gate keeps it target-aware: + where a wide or high-part multiply exists the mult is left for + convert_mult_to_widen / convert_mult_to_highpart, so this (which match.pd's + shorten rule omits for MULT_EXPR) does not pessimize it. */ + +static bool +narrow_long_mul_low_half (gimple_stmt_iterator *gsi) +{ + gimple *stmt = gsi_stmt (*gsi); + if (!is_gimple_assign (stmt) || gimple_assign_rhs_code (stmt) != MULT_EXPR) + return false; + + tree lhs = gimple_assign_lhs (stmt); + tree wide_type = TREE_TYPE (lhs); + scalar_int_mode wide_mode; + if (!INTEGRAL_TYPE_P (wide_type) + || !TYPE_UNSIGNED (wide_type) + || !is_a <scalar_int_mode> (TYPE_MODE (wide_type), &wide_mode) + || targetm.scalar_mode_supported_p (wide_mode)) + return false; + + unsigned int narrow_prec = TYPE_PRECISION (wide_type) / 2; + if (!long_mul_only_low_half_used_p (lhs, narrow_prec)) + return false; + + tree op1 = gimple_assign_rhs1 (stmt); + tree op2 = gimple_assign_rhs2 (stmt); + location_t loc = gimple_location (stmt); + tree narrow_type = build_nonstandard_integer_type (narrow_prec, 1); + gimple_seq seq = NULL; + tree a = gimple_convert (&seq, loc, narrow_type, op1); + tree b = gimple_convert (&seq, loc, narrow_type, op2); + tree np = gimple_build (&seq, loc, MULT_EXPR, narrow_type, a, b); + gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT); + gimple *conv = gimple_build_assign (lhs, NOP_EXPR, np); + gimple_set_location (conv, loc); + gsi_replace (gsi, conv, true); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Narrowed low-half-only long multiply.\n"); + + narrow_long_mul_operands (op1, op2); + return true; +} + +/* Match.pd recognizer for the long-multiply recognizer's high-part + emit chain. */ + +extern bool gimple_long_mul_high_chain (tree, tree *, tree (*)(tree)); + +/* Rewrite the `long_mul_high_chain' whose tail is the statement at GSI + + wide_a = (T_2N) op1 + wide_b = (T_2N) op2 + wide_prod = wide_a * wide_b + hi = wide_prod >> N + lhs = (convert) hi + + to a longhand high-part synthesis at T_N precision. Never materializes + T_2N in gimple, so it covers cases where the 2N mode has no expansion path + (e.g. the high 128 bits of a 128x128 product where 2N=OImode). An operand + wider than T_N -- a shared wide product or a sign-extended cast -- is split + into T_N halves rather than truncated, so no high input bits are dropped. + Returns true on a rewrite. */ + +static bool +lower_long_mul_high_chain (gimple_stmt_iterator *gsi) +{ + gimple *trunc_stmt = gsi_stmt (*gsi); + if (!is_gimple_assign (trunc_stmt)) + return false; + + tree narrow_lhs = gimple_assign_lhs (trunc_stmt); + tree ops[2]; + if (!gimple_long_mul_high_chain (narrow_lhs, ops, NULL)) + return false; + + /* Walk the matched chain back to the 2N multiply and take narrow_type at + half its precision. */ + gimple *shift_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (trunc_stmt)); + gimple *mult_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (shift_stmt)); + unsigned int narrow_prec + = TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (mult_stmt))) / 2; + tree narrow_type = build_nonstandard_integer_type (narrow_prec, /*uns=*/1); + scalar_int_mode narrow_mode; + if (!is_a <scalar_int_mode> (TYPE_MODE (narrow_type), &narrow_mode)) + return false; + + /* Lower only when the target cannot form the N-bit high part itself. */ + if (can_mult_highpart_p (narrow_mode, true)) + return false; + + location_t loc = gimple_location (trunc_stmt); + gimple_seq seq = NULL; + + /* Split each operand into N-bit halves and combine. An operand that fits + N bits yields h == 0, so its cross term folds away; with both fitting + the combine is just a plain N-bit high part. */ + tree l1, h1, l2, h2; + if (!long_mul_split_operand (&seq, loc, gimple_assign_rhs1 (mult_stmt), + narrow_type, &l1, &h1) + || !long_mul_split_operand (&seq, loc, gimple_assign_rhs2 (mult_stmt), + narrow_type, &l2, &h2)) + return false; + tree hi = combine_long_mul_halves (&seq, loc, l1, h1, l2, h2, narrow_type); + + /* Merging the chain's truncation with a later user cast can retarget the + outer convert to any integral type, so convert the narrow result once + here (the high part is < 2^N, so the conversion preserves it). */ + gimple *result_stmt; + tree lhs_type = TREE_TYPE (narrow_lhs); + if (useless_type_conversion_p (lhs_type, narrow_type)) + result_stmt = gimple_build_assign (narrow_lhs, hi); + else + result_stmt = gimple_build_assign (narrow_lhs, NOP_EXPR, hi); + gimple_set_location (result_stmt, loc); + gimple_seq_add_stmt (&seq, result_stmt); + + gsi_replace_with_seq (gsi, seq, true); + + /* Clean up the shift and the 2N mult now -- LTRANS runs no DCE between + widening_mul and expand, and a dead 2N mult would abort expand_mult. + Dead upstream (T_2N) casts, if any, are harmless NOP_EXPRs and land + with normal DCE. */ + if (has_zero_uses (gimple_assign_lhs (shift_stmt))) + { + gimple_stmt_iterator dgsi = gsi_for_stmt (shift_stmt); + gsi_remove (&dgsi, true); + release_defs (shift_stmt); + } + + /* The mult is either dead (low half recomputed elsewhere) or now read only + for its low half -- narrow_long_mul_low_half rewrites it, recursing into + its operands. Removing a dead mult can leave a chained 2N mult that fed + it low-half-only, so narrow those operands on that path. */ + gimple_stmt_iterator mgsi = gsi_for_stmt (mult_stmt); + if (has_zero_uses (gimple_assign_lhs (mult_stmt))) + { + tree op1 = gimple_assign_rhs1 (mult_stmt); + tree op2 = gimple_assign_rhs2 (mult_stmt); + gsi_remove (&mgsi, true); + release_defs (mult_stmt); + narrow_long_mul_operands (op1, op2); + } + else + narrow_long_mul_low_half (&mgsi); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Lowered long-mul high-part chain.\n"); + return true; +} + +/* True when pass_optimize_widening_mul will run. Shared with the + forwprop long-multiply recognizer so its wide-chain emit stays + paired with the lowering that rescues an unsupported 2N shape. + The -Og pipeline (pass_all_optimizations_g) does not contain + pass_optimize_widening_mul at all, so -Og -fexpensive-optimizations + must not enable the emit: the unlowered 2N multiply would reach + expand as an unexpandable mode (e.g. OImode) and ICE. + -fdisable-tree-widening_mul is not observed. */ + +bool +optimize_widening_mul_active_p (void) +{ + return flag_expensive_optimizations && optimize && !optimize_debug; +} + /* Find integer multiplications where the operands are extended from smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR or MULT_HIGHPART_EXPR where appropriate. */ @@ -6570,7 +7048,7 @@ public: /* opt_pass methods: */ bool gate (function *) final override { - return flag_expensive_optimizations && optimize; + return optimize_widening_mul_active_p (); } unsigned int execute (function *) final override; @@ -6638,6 +7116,8 @@ math_opts_dom_walker::after_dom_children (basic_block bb) switch (code) { case MULT_EXPR: + if (narrow_long_mul_low_half (&gsi)) + break; if (!convert_mult_to_widen (stmt, &gsi) && !convert_expand_mult_copysign (stmt, &gsi) && convert_mult_to_fma (stmt, @@ -6704,6 +7184,16 @@ math_opts_dom_walker::after_dom_children (basic_block bb) match_unsigned_saturation_mul (&gsi, as_a<gassign *> (stmt)); match_unsigned_saturation_trunc (&gsi, as_a<gassign *> (stmt)); match_saturation_add_with_assign (&gsi, as_a<gassign *> (stmt)); + /* fall-through */ + case CONVERT_EXPR: + /* The long-multiply recognizer's high-part emit ends in an + outer convert. If the trailing cast+mult+shift+cast + chain has no expansion strategy at the 2N width, lower + the whole chain to a longhand high-part at narrow + precision. */ + if (gsi_stmt (gsi) == stmt + && lower_long_mul_high_chain (&gsi)) + continue; break; default:; diff --git a/gcc/tree-ssa-math-opts.h b/gcc/tree-ssa-math-opts.h index f750b52b5936..5de1697ff678 100644 --- a/gcc/tree-ssa-math-opts.h +++ b/gcc/tree-ssa-math-opts.h @@ -23,4 +23,6 @@ along with GCC; see the file COPYING3. If not see extern tree powi_as_mults (gimple_stmt_iterator *, location_t, tree, HOST_WIDE_INT); +extern bool optimize_widening_mul_active_p (void); + #endif /* GCC_TREE_SSA_MATH_OPTS_H */