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.
(long_mul_set_summand): Handle the new 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_table): Add HIGH_PART and LOW_PART rows for each
ladder form.
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 85a60848b2e6..ca6d57814776 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -12256,6 +12256,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..36eadd05aae1
--- /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 LP64 the __int128-guarded highpart also folds; on non-LP64 it
+ is elided by #ifdef and the count drops by 2. */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 8
"forwprop1" { target lp64 } } } */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 5
"forwprop1" { target { ! lp64 } } } } */
+/* { 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 ea989c809181..f9c0f1a9854d 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -3605,6 +3605,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));
/* Replace STMT with a high-part multiply of OP1 and OP2, emitted as
(N)(((2N) op1 * (2N) op2) >> N).
@@ -3674,6 +3678,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,
@@ -3792,9 +3800,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;
@@ -3855,9 +3870,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)
@@ -3868,18 +3884,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,
@@ -3895,6 +3927,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);
@@ -3922,8 +3959,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,
@@ -4272,6 +4309,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),
@@ -4286,6 +4347,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
