[PATCH v8 4/7] forwprop: Add long-multiply ladder variants

Extend the long-multiply fold to the ladder forms, which propagate
the cross-product carries via a sequence of mask / shift / add steps
on intermediate sums rather than via an explicit overflow compare.
Three structural shapes are recognized:

  ladder_sum1   = (hilo & mask) + hilo' + (xl*yl >> N)
  ladder_part_sum = (xl*yl >> N) + hilo
  ladder_sum2   = (ladder_part_sum & mask) + hilo'
  ladder_sum3   = (hilo & mask) + (hilo' & mask) + (xl*yl >> N)

The full HIGH_PART chain looks like:

  xh*yh + (hilo >> N) + (ladder_sumN >> N) [+ ...]

The corresponding LOW_PART recovers (xl*yl & mask) | (ladder_sumN << N).
match_long_mul picks up each shape via its table row; classifier
ordering keeps more-constrained ladder forms ahead of mul_low_sum
and mul_cross_sum to avoid shadowing.

gcc/ChangeLog:

	* match.pd: Add mul_ladder_sum1, mul_ladder_sum2,
	mul_ladder_sum3 and mul_ladder_part_sum atom recognizers.
	* tree-ssa-forwprop.cc (gimple_mul_ladder_sum1): Declare.
	(gimple_mul_ladder_sum2): Likewise.
	(gimple_mul_ladder_sum3): Likewise.
	(gimple_mul_ladder_part_sum): Likewise.
	(enum long_mul_kind): Add LMK_LADDER_SUM1 / LMK_LADDER_SUM2
	/ LMK_LADDER_SUM3 / LMK_LADDER_PART_SUM, with the
	long_mul_table HIGH_PART and LOW_PART rows for each ladder
	form.
	(long_mul_set_summand): Handle the new kinds.
	(long_mul_classify_carry): Update the specificity note above
	long_mul_classify_plus_kinds.
	(long_mul_classify_plus_kinds): Try mul_ladder_sum3 and
	mul_ladder_sum1 before mul_low_sum (more-constrained
	first); add mul_ladder_sum2.
	(long_mul_classify_hi_extract): Add mul_ladder_part_sum
	branch.
	(long_mul_classify_lo_extract): Adjust.

gcc/testsuite/ChangeLog:

	* gcc.target/aarch64/long_mul.c: Add mulh_ladder and
	mulh_ladder_32 functions; bump expected umulh / umull
	scan counts from 1 to 2.
	* gcc.target/i386/long_mul.c: Same for mulq / imulq.
	* gcc.dg/tree-ssa/long-mul-ladder.c: New test.

Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---

(no changes since v1)

 gcc/match.pd                                  |  54 +++
 .../gcc.dg/tree-ssa/long-mul-ladder.c         | 329 ++++++++++++++++++
 gcc/testsuite/gcc.target/aarch64/long_mul.c   |  50 ++-
 gcc/testsuite/gcc.target/i386/long_mul.c      |  50 ++-
 gcc/tree-ssa-forwprop.cc                      |  93 ++++-
 5 files changed, 561 insertions(+), 15 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c

diff --git a/gcc/match.pd b/gcc/match.pd
index d2b704c6e555..0f07a66add81 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -12279,6 +12279,60 @@ and,
       (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)))
 #endif
 
 /* Floatint point/integer comparison and integer->integer
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..16bcd3fdab47
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c
@@ -0,0 +1,329 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-forwprop-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 int128 } } } */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 8 "forwprop1" { target { ! 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" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/long_mul.c b/gcc/testsuite/gcc.target/aarch64/long_mul.c
index 2a4709ecbfd0..f9c765380d8c 100644
--- a/gcc/testsuite/gcc.target/aarch64/long_mul.c
+++ b/gcc/testsuite/gcc.target/aarch64/long_mul.c
@@ -4,6 +4,27 @@
 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)
 {
@@ -28,6 +49,27 @@ uint64_t mulh_carry (uint64_t x, uint64_t y)
   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)
 {
@@ -52,7 +94,7 @@ uint32_t mulh_carry_32 (uint32_t x, uint32_t y)
   return interm_plus_carry + low_accum_hi;
 }
 
-/* 64-bit pattern should emit umulh.  */
-/* { dg-final { scan-assembler-times "umulh\t" 1 } } */
-/* 32-bit pattern should emit umull (32x32->64 widening multiply).  */
-/* { dg-final { scan-assembler-times "umull\t" 1 } } */
+/* 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/i386/long_mul.c b/gcc/testsuite/gcc.target/i386/long_mul.c
index 6ec87eb8dd21..d4b03ed1beda 100644
--- a/gcc/testsuite/gcc.target/i386/long_mul.c
+++ b/gcc/testsuite/gcc.target/i386/long_mul.c
@@ -4,6 +4,27 @@
 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)
 {
@@ -28,6 +49,27 @@ uint64_t mulh_carry (uint64_t x, uint64_t y)
   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)
 {
@@ -52,7 +94,7 @@ uint32_t mulh_carry_32 (uint32_t x, uint32_t y)
   return interm_plus_carry + low_accum_hi;
 }
 
-/* 64-bit pattern should emit mulq (unsigned 64x64->128 multiply).  */
-/* { dg-final { scan-assembler-times "\tmulq" 1 } } */
-/* 32-bit pattern should emit imulq (64-bit multiply of zero-extended operands).  */
-/* { dg-final { scan-assembler-times "\timulq" 1 } } */
+/* 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/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
index aefd1d978f4f..57b03c03bd77 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -3613,6 +3613,10 @@ 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
@@ -3715,6 +3719,10 @@ enum long_mul_kind {
   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,
@@ -3833,9 +3841,16 @@ long_mul_set_summand (long_mul_summand *info, long_mul_kind kind,
       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;
@@ -3899,9 +3914,10 @@ long_mul_classify_carry (tree leaf, long_mul_summand *info)
 }
 
 /* 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_low_accum (which constrains both arms) shadows it
-   and must come first.  */
+   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)
@@ -3912,18 +3928,34 @@ long_mul_classify_plus_kinds (tree inner, long_mul_summand *info)
       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; mul_cross_sum (any plus)
-   is the fallback after the shared plus-based kinds.  */
+   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,
@@ -3939,6 +3971,11 @@ long_mul_classify_hi_extract (tree inner, unsigned HOST_WIDE_INT shift,
     }
   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);
@@ -3966,8 +4003,8 @@ long_mul_classify_lo_extract (tree inner, unsigned HOST_WIDE_INT mask,
 }
 
 /* Classify INNER -- already unwrapped from an outer (X << SHIFT) -- as
-   a left-shifted summand.  No mul_hilo here -- that shape appears only
-   under (X >> SHIFT).  */
+   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,
@@ -4316,6 +4353,30 @@ static const long_mul_row long_mul_table[] = {
       { 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 & mask) | (low_accum << N),
@@ -4330,6 +4391,24 @@ static const long_mul_row long_mul_table[] = {
     { { 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
-- 
2.55.0