https://gcc.gnu.org/g:b5e422deba1e461c1f6fc3ad50d3c5bdf178f2c0
commit r17-5726-gb5e422deba1e461c1f6fc3ad50d3c5bdf178f2c0 Author: Philipp Tomsich <[email protected]> Date: Sat Oct 24 16:03:47 2026 +0200 forwprop: Reject mismatched long-multiply ladders [PR128117] Two of the ladder forms of a long multiplication's high part mask one cross product and add the other unmasked. With hilo and hilo' the cross products xh*yl and xl*yh in either order, N the half width and mask the low-half mask, they are xh*yh + (hilo >> N) + (ladder_sum1 >> N) ladder_sum1 = (hilo & mask) + hilo' + (xl*yl >> N) xh*yh + (ladder_sum2 >> N) + (ladder_part_sum >> N) ladder_part_sum = (xl*yl >> N) + hilo ladder_sum2 = (ladder_part_sum & mask) + hilo' The high half of hilo only reaches the result through (hilo >> N) or ladder_part_sum. Neither table row checked that the cross product in that term is hilo and not hilo', so chains with hilo' there were folded as well. That counts the high half of hilo' twice and drops the high half of hilo. Add a check to both rows that the cross product in (hilo >> N) or ladder_part_sum has the same operands as the one the ladder sum masks. The other rows are not affected. Where both high halves are added on their own, long_mul_check_consistency already requires them to be different products. The remaining rows do not add either one on its own, and the carry compares detect the overflow with either cross product. Bootstrapped and regtested on aarch64-linux-gnu and x86_64-linux-gnu. PR tree-optimization/128117 gcc/ChangeLog: * tree-ssa-forwprop.cc (long_mul_check_ladder_sum1): New. (long_mul_check_ladder_sum2): New. (long_mul_table): Use them for the ladder_sum1 and ladder_sum2 high-part rows. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/long-mul-ladder.c: Add full_mul_ladder_comm, mulh_ladder_square and full_mul_ladder_square, and update the fold counts. * gcc.dg/tree-ssa/pr128117.c: New test. Co-authored-by: Konstantinos Eleftheriou <[email protected]> Diff: --- gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c | 81 +++++++++++- gcc/testsuite/gcc.dg/tree-ssa/pr128117.c | 158 ++++++++++++++++++++++++ gcc/tree-ssa-forwprop.cc | 36 +++++- 3 files changed, 270 insertions(+), 5 deletions(-) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c index 7b7384d86455..894c69f14d70 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-ladder.c @@ -50,6 +50,27 @@ uint64_t mulh_ladder_comm (uint64_t x, uint64_t y) return hw64; } +/* mulh_ladder with y = x. */ +uint64_t mulh_ladder_square (uint64_t x) +{ + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t x_hi = x >> 32; + uint64_t t0 = x_lo * x_lo; + uint64_t t1 = x_lo * x_hi; + uint64_t t2 = x_hi * x_lo; + uint64_t t3 = x_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; +} + uint32_t mulh_ladder_32 (uint32_t x, uint32_t y) { uint32_t x_lo = x & 0xFFFF; @@ -125,6 +146,60 @@ v2i64 full_mul_ladder (uint64_t x, uint64_t y) return result; } +/* full_mul_ladder with x and y swapped, masking the other cross product. */ +v2i64 full_mul_ladder_comm (uint64_t x, uint64_t y) +{ + uint64_t and_x = x & 0xFFFFFFFF; + uint64_t and_y = y & 0xFFFFFFFF; + uint64_t mul_i = and_x * and_y; + uint64_t shr_y = y >> 32; + uint64_t mul_i27 = and_x * shr_y; + uint64_t shr_x = x >> 32; + uint64_t mul_i28 = shr_x * and_y; + uint64_t mul_i29 = shr_x * shr_y; + 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; +} + +/* full_mul_ladder with y = x. */ +v2i64 full_mul_ladder_square (uint64_t x) +{ + uint64_t and_x = x & 0xFFFFFFFF; + uint64_t mul_i = and_x * and_x; + uint64_t shr_x = x >> 32; + uint64_t mul_i27 = and_x * shr_x; + uint64_t mul_i28 = shr_x * and_x; + uint64_t mul_i29 = shr_x * 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"))) @@ -323,10 +398,10 @@ v2i32 mul_ladder_long_v2i32 (v2i32 x, v2i32 y) /* On targets with __int128 support the 128-bit highpart also folds; without it it is elided by #ifdef and the count drops by 2. */ -/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 10 "forwprop1" { target { oi_mode && int128 } } } } */ -/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 8 "forwprop1" { target { ! { oi_mode && int128 } } } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 13 "forwprop1" { target { oi_mode && int128 } } } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 11 "forwprop1" { target { ! { oi_mode && int128 } } } } } */ /* { dg-final { scan-tree-dump-times "Long multiplication high part folded\\." 2 "forwprop2" } } */ -/* { dg-final { scan-tree-dump-times "Long multiplication low part folded\\." 2 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "Long multiplication low part folded\\." 4 "forwprop1" } } */ /* Only the two 128-bit (OImode) chains are lowered. sparc64 and hppa64 have OImode and __int128 but no native DImode high part, so their u64 chains lower too and the count would exceed 2; exclude them. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr128117.c b/gcc/testsuite/gcc.dg/tree-ssa/pr128117.c new file mode 100644 index 000000000000..abf0a96fd3d4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr128117.c @@ -0,0 +1,158 @@ +/* PR tree-optimization/128117 */ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-forwprop1-details" } */ + +typedef __UINT64_TYPE__ uint64_t; + +/* Adds the high half of t2 where that of t1 is needed. + Should NOT be folded. */ +__attribute__((noipa)) +uint64_t mulh_ladder_wrong_hilo (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 t1_lo = t1 & 0xFFFFFFFF; + uint64_t u0 = t1_lo + t2; + uint64_t u1 = u0 + t0_hi; + uint64_t u1_hi = u1 >> 32; + uint64_t t2_hi = t2 >> 32; + uint64_t u2 = t2_hi + t3; + uint64_t hw64 = u2 + u1_hi; + + return hw64; +} + +/* As above, but adding t0_hi before t2. + Should NOT be folded. */ +__attribute__((noipa)) +uint64_t mulh_ladder_wrong_hilo_assoc (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 t1_lo = t1 & 0xFFFFFFFF; + uint64_t u0 = t1_lo + t0_hi; + uint64_t u1 = u0 + t2; + uint64_t u1_hi = u1 >> 32; + uint64_t t2_hi = t2 >> 32; + uint64_t u2 = t2_hi + t3; + uint64_t hw64 = u2 + u1_hi; + + return hw64; +} + +/* As mulh_ladder_wrong_hilo, with x and y swapped. + Should NOT be folded. */ +__attribute__((noipa)) +uint64_t mulh_ladder_wrong_hilo_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 t1_lo = t1 & 0xFFFFFFFF; + uint64_t u0 = t1_lo + t2; + uint64_t u1 = u0 + t0_hi; + uint64_t u1_hi = u1 >> 32; + uint64_t t2_hi = t2 >> 32; + uint64_t u2 = t2_hi + t3; + uint64_t hw64 = u2 + u1_hi; + + return hw64; +} + +/* Adds the high half of v0 where that of u0 is needed. + Should NOT be folded. */ +__attribute__((noipa)) +uint64_t mulh_ladder_wrong_part_sum (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 u1 = u0_lo + t2; + uint64_t u1_hi = u1 >> 32; + uint64_t v0 = t0_hi + t2; + uint64_t v0_hi = v0 >> 32; + uint64_t u2 = v0_hi + t3; + uint64_t hw64 = u2 + u1_hi; + + return hw64; +} + +/* As mulh_ladder_wrong_part_sum, with x and y swapped. + Should NOT be folded. */ +__attribute__((noipa)) +uint64_t mulh_ladder_wrong_part_sum_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 = t0_hi + t1; + uint64_t u0_lo = u0 & 0xFFFFFFFF; + uint64_t u1 = u0_lo + t2; + uint64_t u1_hi = u1 >> 32; + uint64_t v0 = t0_hi + t2; + uint64_t v0_hi = v0 >> 32; + uint64_t u2 = v0_hi + t3; + uint64_t hw64 = u2 + u1_hi; + + return hw64; +} + +int main () +{ + /* Each call returns 0. The high part of x * y is 0xFFFFFFFE. */ + uint64_t x = 0xFFFFFFFF00000000ULL; + uint64_t y = 0xFFFFFFFFULL; + + if (mulh_ladder_wrong_hilo (x, y) != 0) + __builtin_abort (); + + if (mulh_ladder_wrong_hilo_assoc (x, y) != 0) + __builtin_abort (); + + if (mulh_ladder_wrong_hilo_comm (y, x) != 0) + __builtin_abort (); + + if (mulh_ladder_wrong_part_sum (x, y) != 0) + __builtin_abort (); + + if (mulh_ladder_wrong_part_sum_comm (y, x) != 0) + __builtin_abort (); + + return 0; +} + +/* { dg-final { scan-tree-dump-not "Long multiplication high part folded\\." "forwprop1" } } */ diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc index b526c85ef34d..ac858e66100c 100644 --- a/gcc/tree-ssa-forwprop.cc +++ b/gcc/tree-ssa-forwprop.cc @@ -4381,6 +4381,38 @@ long_mul_check_two_carries (const vec<long_mul_summand> &summands, return true; } +/* Extra check for xh*yh + (hilo >> N) + (ladder_sum1 >> N). hilo must be + the product that ladder_sum1 masks, since the high half of the unmasked + one is already in the sum. */ + +static bool +long_mul_check_ladder_sum1 (const vec<long_mul_summand> &summands, + gimple *) +{ + const long_mul_summand *hilo + = long_mul_find_summand (summands, LMK_MUL_HILO); + const long_mul_summand *sum + = long_mul_find_summand (summands, LMK_LADDER_SUM1); + return long_mul_hilo_orientation (sum->hilo[0], hilo->op0, hilo->op1) == 0; +} + +/* Likewise for xh*yh + (ladder_sum2 >> N) + (ladder_part_sum >> N): + ladder_part_sum must hold the product that ladder_sum2 masks. */ + +static bool +long_mul_check_ladder_sum2 (const vec<long_mul_summand> &summands, + gimple *) +{ + const long_mul_summand *part + = long_mul_find_summand (summands, LMK_LADDER_PART_SUM); + const long_mul_summand *sum + = long_mul_find_summand (summands, LMK_LADDER_SUM2); + tree masked[LONG_MUL_MAX_CAPTURES]; + return (gimple_mul_hilo (sum->hilo[0], masked, NULL) + && (long_mul_hilo_orientation (part->hilo[0], masked[0], masked[1]) + == 0)); +} + /* The lolo + cross_shifted shape is also the low half of a two-carry long-multiply, where an unsigned overflow compare against one of the PLUS operands is the low-carry term consumed by the matching @@ -4478,7 +4510,7 @@ static const long_mul_row long_mul_table[] = { { { LMK_MUL_HIHI, LMX_NONE }, { LMK_MUL_HILO, LMX_HI }, { LMK_LADDER_SUM1, LMX_HI } }, - NULL }, + long_mul_check_ladder_sum1 }, /* xh*yh + (ladder_sum2 >> N) + (ladder_part_sum >> N), ladder_part_sum = (xl*yl >> N) + hilo, ladder_sum2 = (ladder_part_sum & mask) + hilo'. */ @@ -4486,7 +4518,7 @@ static const long_mul_row long_mul_table[] = { { { LMK_MUL_HIHI, LMX_NONE }, { LMK_LADDER_SUM2, LMX_HI }, { LMK_LADDER_PART_SUM, LMX_HI } }, - NULL }, + long_mul_check_ladder_sum2 }, /* 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,
