[COMMITTED PATCH v9 4/7] forwprop: Add long-multiply ladder variants
Konstantinos Eleftheriou <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
Extend the long-multiply fold to the ladder forms, which propagate the cross-product carries via mask / shift / add steps on intermediate sums rather than via an explicit overflow compare: 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 high-part chain is xh*yh + (hilo >> N) + (ladder_sumN >> N) [+ ...]; the corresponding LOW_PART recovers (xl*yl & mask) | (ladder_sumN << N). PR tree-optimization/107090 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 bdb18df8140c..86042b02beea 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -12852,6 +12852,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 aafbc2275b81..81a3bacd909f 100644 --- a/gcc/tree-ssa-forwprop.cc +++ b/gcc/tree-ssa-forwprop.cc @@ -3626,6 +3626,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 @@ -3728,6 +3732,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, @@ -3845,9 +3853,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; @@ -3911,9 +3926,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) @@ -3924,18 +3940,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, @@ -3951,6 +3983,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); @@ -3976,8 +4013,8 @@ long_mul_classify_lo_extract (tree inner, long_mul_summand *info) } /* 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, @@ -4325,6 +4362,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), @@ -4339,6 +4400,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