The 1/2 long-multiply fold walks a top-level + statement to find
its summands. Hand-written long-multiply code commonly writes the
carry as a 2-arg PHI
if (mul_hilo0 > low_sum)
result = result_partial + (1ULL << N);
else
result = result_partial;
with no top-level + at the join, leaving the existing matcher
nothing to walk.
Add a PHI-driven entry. Two match.pd recognisers cond_carry_add
and cond_carry_add_neg match the PHI<base + pow2, base> shape
guarded by an unsigned compare on (a, sum) in either polarity.
match_long_mul_phi in tree-ssa-forwprop.cc classifies the captured
sum into a CARRY_LOW / CARRY_CROSS_SUM / CARRY_LOW_SUM summand,
linearises base for the remaining high-part summands, and runs
long_mul_table. On a match it emits a 2N-bit multiply with
PHI_RES as its LHS and removes the PHI; only HIGH_PART rows are
reachable (LOW_PART rows are BIT_IOR-shaped and never produce a
carry PHI).
Factor long_mul_classify_match and build_mul_high_seq out of
match_long_mul and create_mul_high_seq, and add
long_mul_classify_chain wrapping the linearise + classify + sort
+ match block, so the new PHI entry reuses 1/2's table search
and wide-multiply emit.
PR tree-optimization/107090
gcc/ChangeLog:
* match.pd: Add cond_carry_add and cond_carry_add_neg match
recognisers for the 2-arg PHI form PHI<base + pow2, base>,
one per gcond polarity.
* tree-ssa-forwprop.cc (gimple_cond_carry_add): Declare.
(gimple_cond_carry_add_neg): Declare.
(create_mul_high_seq): Use build_mul_high_seq.
(build_mul_high_seq): New seq-producing wide-multiply build.
(long_mul_classify_match): New classify-only entry to the
long_mul_table.
(long_mul_classify_chain): New shared helper wrapping
linearise + classify + sort + table lookup.
(match_long_mul_phi): New PHI-driven entry; recognises 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_phi on each
PHI in the degenerate-PHI walk.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/long-mul-boundary-64.c: Add PHI-form runtime
variants at 64-bit operand width covering cond_carry_add
(lt, gt), cond_carry_add_neg (ge, le), and the CARRY_LOW PHI
path.
* gcc.dg/tree-ssa/long-mul-boundary.c: Same at 32-bit halfword.
* gcc.dg/tree-ssa/long-mul-carry.c: Add PHI-form CARRY_LOW_SUM,
CARRY_CROSS_SUM, and negated-branch compile variants; bump
expected forwprop1 high-part fold counts by 3 (int128 target)
and 2 (!int128).
* gcc.dg/tree-ssa/long-mul-partial.c: Add PHI-form near-miss
cases probing the non-pow2 increment, wrong-shift, equality-
compare, and mismatched-cross-product gates of
match_long_mul_phi.
* gcc.dg/tree-ssa/long-mul-two-carry.c: Add PHI-form CARRY_LOW
variant; bump expected forwprop3 high-part fold count by 1 on
int128 targets.
Co-authored-by: Philipp Tomsich <[email protected]>
Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---
Changes in v6:
- Reorder so the long-multiply fold (was 2/2) is now 1/2 and a new
PHI-form recognition pass is 2/2. Reverting 2/2 leaves a working
long-multiply fold for the flat-shifted-compare carry form.
- Drop v5's standalone flatten_cond_carry_add driver. The same
cond_carry_add / cond_carry_add_neg match.pd recognizers now feed
a match_long_mul_phi entry inside the long-multiply fold, so a
PHI-shaped carry folds straight to the wide-multiply output.
- Factor long_mul_classify_chain, long_mul_classify_match and
build_mul_high_seq for sharing between match_long_mul and the new
match_long_mul_phi.
- cond_carry_add_neg uses le / ge instead of gt / lt to encode the
carry condition strictly. v5 inverted the compare via
invert_tree_comparison in the flatten driver; v6 synthesises the
carry summand directly inside match_long_mul_phi and so requires
the recogniser to encode the strict form.
- Delete forwprop-44/45/46.c; add PHI-form coverage in
long-mul-carry.c, long-mul-two-carry.c, long-mul-boundary.c
and long-mul-boundary-64.c.
- Add PHI-form near-miss tests in long-mul-partial.c and
operand-swap polarity coverage in long-mul-boundary{,-64}.c.
- Refresh stale long-mul comment references (check_hilo_and_ops,
fold_mul_low_plus) and reword mul_carry_low's :c-on-gt note to
the correct LT form (a + b < a).
Changes in v5:
- 1/2:
- Replace the match.pd simplify on COND_EXPR with cond_carry_add
/ cond_carry_add_neg match recognizers (cond^), split by gcond
polarity, plus a flatten_cond_carry_add driver in
tree-ssa-forwprop.cc. The driver inverts the gcond's
comparison for the _neg form. Modelled on match_saturation_add.
- Remove fold_cond_carry_add_profitable_p and the tm_p.h /
predict.h includes from gimple-match-head.cc. The width >
MAX_FIXED_MODE_SIZE and width % 2 != 0 guards were
prerequisites for the can_mult_highpart_p fallback path, not
soundness checks. type_has_mode_precision_p subsumes them.
- Retarget the test scans from phiopt2 to forwprop1. Add
forwprop-46.c covering all four arm/comparison polarities.
- forwprop-45.c uses __UINT64_TYPE__ instead of unsigned long
and drops the lp64 restriction, covering the type > word_mode
regime on 32-bit targets.
- 2/2:
- Lower the high-part as (N)(((2N) op1 * (2N) op2) >> N).
pass_optimize_widening_mul rewrites this to WIDEN_MULT_EXPR /
MULT_HIGHPART_EXPR on supporting targets. Removes
can_mult_highpart_p queries from forwprop.
- Replace the can_mult_highpart_p prefilter in match_long_mul
with a targetm.scalar_mode_supported_p check on the 2N mode.
Test scans select on int128, mirroring the gate, instead of
lp64.
- Drop the m_long_mul_fold_p pass parameter and its passes.def
arguments. The long-mul fold runs in every forwprop instance.
Test scans retargeted from forwprop2 to forwprop1.
- Stop restricting forwprop-44.c to lp64. With the
can_mult_highpart_p gating gone, the fold is target-independent
and the test passes on ilp32 targets too.
Changes in v4:
- 1/2:
- Rebuild the guard with per-conjunct reasoning: require both
operands to be SSA names (drops degenerate one-side-constant
cases that fold trivially elsewhere), require the type to
have_mode_precision_p (excludes BITINT_TYPE precision != mode
and similar oddities), drop the explicit MAX_FIXED_MODE_SIZE
width cap (subsumed by have_mode_precision_p), and gate on the
flat optab via can_mult_highpart_p of the 2N mode.
- Retain BRANCH_COST >= 2: keep the flatten conditional on a
target where the branchless form is generally cheaper.
- Rewrite the cover letter to describe the gate as the
composition of these conjuncts and to clarify that the
transformation now only ever introduces a (mul_hi-like)
can_mult_highpart_p shape, not a libgcc multi-precision call.
- 2/2:
- Convert per-variant fold_mul_* functions into a
table-driven long_mul fold framework.
- Migrate each variant into a row in long_mul_table (six
HIGH_PART, six LOW_PART rows) keyed by (kind, extract).
- Add cross-summand consistency checks
(long_mul_check_consistency, long_mul_check_two_carries,
long_mul_check_low_plus_defer) shared across rows.
- Drop emission to a libgcc multi-precision call from RTL
expansion; defer to pass_optimize_widening_mul / RTL
expansion to pick native umul_highpart, a widening multiply, or
a synthesised sequence. Emission is gated on
can_mult_highpart_p.
- Structural redesign: per-variant fold_mul_* functions
consolidated into a single linearise + classify + table-lookup
framework (long_mul_table, match_long_mul,
long_mul_classify_summand, long_mul_check_consistency). Each
variant is now a row in long_mul_table; consistency checks are
shared across rows.
- Fast-fail prefilters in match_long_mul: LHS-type prefilter at
entry (no legitimate long-mul leaf has a signed / pointer /
float / odd-width type) and a can_mult_highpart_p probe before
the row loop to skip HIGH_PART rows on unsupported targets.
- Bound long_mul_linearize_chain mid-walk by LONG_MUL_MAX_SUMMANDS
so an overlong addition / BIT_IOR chain bails immediately rather
than after a full traversal.
- Emit a dump-file hint pointing at the shared inner addition when
long-mul folding rejects a chain because of a multi-used
intermediate (caching the partial sum into a single-use SSA
name normally enables the fold).
Changes in v3:
- Moved carry-diamond flattening from forwprop to match.pd,
replacing ~460 lines of C++ with a 17-line match.pd pattern.
- Two-carry test scans forwprop3 (the first forwprop after phiopt2,
since early phiopt restricts which tree codes are allowed).
- Set location for new sequences.
- Updated mul_carry_low pattern.
- Added the `mul_low_plus` pattern.
- Fixed formatting issues.
Changes in v2:
- Fixed the testcases by separating the high part's fold count for
32-bit and 64-bit targets.
gcc/match.pd | 25 ++
.../gcc.dg/tree-ssa/long-mul-boundary-64.c | 122 ++++++++
.../gcc.dg/tree-ssa/long-mul-boundary.c | 122 ++++++++
.../gcc.dg/tree-ssa/long-mul-carry.c | 66 +++-
.../gcc.dg/tree-ssa/long-mul-partial.c | 74 +++++
.../gcc.dg/tree-ssa/long-mul-two-carry.c | 28 +-
gcc/tree-ssa-forwprop.cc | 293 ++++++++++++++----
7 files changed, 663 insertions(+), 67 deletions(-)
diff --git a/gcc/match.pd b/gcc/match.pd
index d58b3721a576..0b2fa07e79b3 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -6226,6 +6226,31 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(lshift (convert (bit_xor (convert:boolean_type_node @0)
{ boolean_true_node; })) { shift; })))))))
+/* Recognise 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
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
index b086d7f75788..e0ff1822c283 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary-64.c
@@ -218,6 +218,113 @@ uint64_t mulh_ladder_long (uint64_t x, uint64_t y)
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;
+}
+
+/* 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,
@@ -270,6 +377,21 @@ int main ()
__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-boundary.c
b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c
index 926acaddeade..498481a01932 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-boundary.c
@@ -217,6 +217,113 @@ uint32_t mulh_ladder_long (uint32_t x, uint32_t y)
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,
@@ -266,6 +373,21 @@ int main ()
__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
index ecffabb3eda0..95037a35ff8a 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-carry.c
@@ -305,7 +305,69 @@ v2i32 mulh_carry_long_v2i32 (v2i32 x, v2i32 y)
return result;
}
-/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 8
"forwprop1" { target int128 } } } */
+/* PHI-form variants: the carry-add is written as a 2-arg PHI from an
+ if-branch instead of a flat shifted-compare. Exercises
+ 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;
+}
+
+/* _neg-polarity PHI variant: negated carry-detect branch, exercising
+ match.pd's cond_carry_add_neg recognisers (le/ge form). */
+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;
+}
+
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded."
11 "forwprop1" { target int128 } } } */
/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 2
"forwprop2" { target int128 } } } */
-/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 5
"forwprop1" { target { ! int128 } } } } */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 7
"forwprop1" { target { ! int128 } } } } */
/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 2
"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
index 0c022094a379..7b239e2439e1 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-partial.c
@@ -113,6 +113,80 @@ int mulhs_signed (int u, int v) {
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" } } */
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
index 4307793d4c46..95439c338027 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c
@@ -105,12 +105,38 @@ uint64_t full_mul_two_carry (uint64_t x, uint64_t y,
uint64_t *lo)
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 high/low split across forwprop3/forwprop4 is intentional: see
long_mul_check_low_plus_defer in tree-ssa-forwprop.cc. On targets
without a native 2N scalar mode the HIGH fold is skipped, so the
paired LOW fold for full_mul_two_carry stays deferred and never
fires either. */
-/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 4
"forwprop3" { target int128 } } } */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 5
"forwprop3" { target int128 } } } */
/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 1
"forwprop3" { target { ! int128 } } } } */
/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 1
"forwprop4" { target int128 } } } */
/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 0
"forwprop4" { target { ! int128 } } } } */
diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
index cfe2709e63ab..6c682a2e3948 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -3568,6 +3568,13 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)
return true;
}
+/* 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. */
@@ -3597,26 +3604,31 @@ extern bool gimple_mul_carry_low (tree, tree *, tree
(*)(tree));
already owns them. */
static void
-create_mul_high_seq (tree op1, tree op2, gimple *stmt)
+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);
- location_t loc = gimple_location (stmt);
- gimple_seq seq = NULL;
-
- 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,
+ 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,
+ tree hi = gimple_build (seq, loc, RSHIFT_EXPR, wide_type, wide_prod,
build_int_cst (integer_type_node, width));
- gimple *prod = gimple_build_assign (gimple_get_lhs (stmt), NOP_EXPR, hi);
+ gimple *prod = gimple_build_assign (dest, NOP_EXPR, hi);
gimple_set_location (prod, loc);
- gimple_seq_add_stmt (&seq, prod);
+ gimple_seq_add_stmt (seq, prod);
+}
+static void
+create_mul_high_seq (tree op1, tree op2, gimple *stmt)
+{
+ gimple_seq seq = NULL;
+ build_mul_high_seq (op1, op2, gimple_get_lhs (stmt),
+ gimple_location (stmt), &seq);
gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
gsi_replace_with_seq (&gsi, seq, true);
}
@@ -4363,6 +4375,94 @@ long_mul_hint_shared_intermediate (gimple *shared_def)
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 (later lowered by
+ pass_optimize_widening_mul); LOW_PART rows emit a plain MULT_EXPR.
+ Skip HIGH_PART rows when the target lacks the 2N scalar mode, so
+ the multiply does not survive to RTL expansion as a libcall. */
+ scalar_int_mode mode, wide_mode;
+ bool can_emit_high
+ = is_a <scalar_int_mode> (TYPE_MODE (lhs_type), &mode)
+ && GET_MODE_2XWIDER_MODE (mode).exists (&wide_mode)
+ && targetm.scalar_mode_supported_p (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;
+
+ 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 append EXTRA as an additional
+ pre-classified summand, sort the multiset, and look it up in
+ long_mul_table on a result of type LHS_TYPE. CANDIDATE is passed
+ to per-row extra_check predicates. On a hit, returns the matched
+ row and writes the half-width operands via OUT_OP0/OUT_OP1; on a
+ miss returns NULL and emits a shared-intermediate hint to the
+ dump file when one blocked linearization. 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,
+ tree *out_op0, tree *out_op1)
+{
+ auto_vec<tree, LONG_MUL_MAX_SUMMANDS + 1> leaves;
+ gimple *shared_def = NULL;
+ if (!long_mul_linearize_chain (stmt, outer, leaves, &shared_def))
+ return NULL;
+ unsigned total = leaves.length () + (extra ? 1 : 0);
+ if (total < 2 || total > LONG_MUL_MAX_SUMMANDS)
+ return NULL;
+
+ auto_vec<long_mul_summand, LONG_MUL_MAX_SUMMANDS> summands;
+ for (tree leaf : leaves)
+ {
+ long_mul_summand s;
+ if (!long_mul_classify_summand (leaf, &s))
+ {
+ long_mul_hint_shared_intermediate (shared_def);
+ return NULL;
+ }
+ summands.quick_push (s);
+ }
+ if (extra)
+ summands.quick_push (*extra);
+ 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
@@ -4387,67 +4487,127 @@ match_long_mul (gimple *stmt)
|| TYPE_PRECISION (lhs_type) % 2 != 0)
return false;
- auto_vec<tree, LONG_MUL_MAX_SUMMANDS + 1> leaves;
- gimple *shared_def = NULL;
- if (!long_mul_linearize_chain (stmt, outer, leaves, &shared_def))
- return false;
- if (leaves.length () < 2)
+ tree op0, op1;
+ const long_mul_row *row
+ = long_mul_classify_chain (stmt, outer, lhs_type, stmt, NULL,
+ &op0, &op1);
+ if (!row)
return false;
- auto_vec<long_mul_summand, LONG_MUL_MAX_SUMMANDS> summands;
- for (tree leaf : leaves)
+ if (row->part == long_mul_row::HIGH_PART)
{
- long_mul_summand s;
- if (!long_mul_classify_summand (leaf, &s))
- {
- long_mul_hint_shared_intermediate (shared_def);
- return false;
- }
- summands.quick_push (s);
+ create_mul_high_seq (op0, op1, stmt);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Long multiplication high part folded.\n");
+ return true;
}
- summands.qsort (long_mul_summand_compare);
+ create_mul_low_seq (op0, op1, stmt);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Long multiplication low part folded.\n");
+ return true;
+}
- /* HIGH_PART rows emit a 2N-bit multiply (later lowered by
- pass_optimize_widening_mul); LOW_PART rows emit a plain MULT_EXPR.
- Skip HIGH_PART rows when the target lacks the 2N scalar mode, so
- the multiply does not survive to RTL expansion as a libcall.
- scalar_mode_supported_p is a static target property, invariant
- across forwprop instances. */
- scalar_int_mode mode, wide_mode;
- bool can_emit_high
- = is_a <scalar_int_mode> (TYPE_MODE (lhs_type), &mode)
- && GET_MODE_2XWIDER_MODE (mode).exists (&wide_mode)
- && targetm.scalar_mode_supported_p (wide_mode);
+/* PHI-driven entry for long-multiply folding. When PHI's value
+ flattens to base + (carry << N), probe sum to classify the carry
+ kind, linearise 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. */
- 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;
+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 op0, op1;
- if (!long_mul_check_consistency (summands, &op0, &op1))
- continue;
+ 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;
- if (row.extra_check && !row.extra_check (summands, stmt))
- continue;
+ /* 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;
- if (row.part == long_mul_row::HIGH_PART)
- {
- create_mul_high_seq (op0, op1, stmt);
- 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);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Long multiplication low part folded.\n");
- return true;
- }
+ tree op0, op1;
+ const long_mul_row *row
+ = long_mul_classify_chain (base_def, PLUS_EXPR, lhs_type, phi, &carry,
+ &op0, &op1);
+ if (!row || row->part != long_mul_row::HIGH_PART)
+ return false;
- long_mul_hint_shared_intermediate (shared_def);
- 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)
@@ -6235,14 +6395,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;
--
2.52.0
