Extend the long-multiply fold to a LOW_PART shape that recovers the
lower 2N bits as a plain unsigned sum of the xl*yl product and the
shifted cross-product sum:
xl*yl + (cross_sum << N)
cross_sum = xh*yl + xl*yh
This shape also appears as 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 high-part fold. Folding
to mul_lo here would destroy (cross_sum << N), which both the compare
and the high-part match still need; an extra check defers the LOW
fold when any GT/LT/GE/LE use shares an operand with the PLUS, so the
high-part fold runs first. After it does, the compare is dead and
the surviving lolo + (cross_sum << N) is picked up by this row in the
next forwprop instance.
gcc/ChangeLog:
* tree-ssa-forwprop.cc (long_mul_check_low_plus_defer): New
helper, defers the fold when any GT/LT/GE/LE use shares an
operand with the PLUS.
(long_mul_table): Add the LOW_PART PLUS_EXPR row gated on
long_mul_check_low_plus_defer.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/long-mul-low-plus.c: New test.
* gcc.dg/tree-ssa/long-mul-two-carry.c: Add a forwprop4 LOW
fold expectation for full_mul_two_carry, deferred from
forwprop3 by long_mul_check_low_plus_defer.
Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---
(no changes since v1)
.../gcc.dg/tree-ssa/long-mul-low-plus.c | 54 +++++++++++++++++++
.../gcc.dg/tree-ssa/long-mul-two-carry.c | 11 ++--
gcc/tree-ssa-forwprop.cc | 54 +++++++++++++++++++
3 files changed, 114 insertions(+), 5 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c
b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c
new file mode 100644
index 000000000000..37c0193ece09
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-low-plus.c
@@ -0,0 +1,54 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-forwprop-details" } */
+
+typedef __UINT32_TYPE__ uint32_t;
+typedef __UINT64_TYPE__ uint64_t;
+
+/* Low part via PLUS form: lolo + (cross_sum << halfwidth).
+ No GT/LT comparison on the result, so long_mul_check_low_plus_defer
+ should fold without deferring. */
+uint32_t mul_low_plus_32 (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 cross_sum = hilo + lohi;
+ uint32_t cross_shifted = cross_sum << 16;
+ return lolo + cross_shifted;
+}
+
+/* 64-bit variant. */
+uint64_t mul_low_plus_64 (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 cross_sum = hilo + lohi;
+ uint64_t cross_shifted = cross_sum << 32;
+ return lolo + cross_shifted;
+}
+
+/* Commuted operand order. */
+uint32_t mul_low_plus_comm (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 = y_lo * x_lo;
+ uint32_t hilo = y_lo * x_hi;
+ uint32_t lohi = y_hi * x_lo;
+ uint32_t cross_sum = lohi + hilo;
+ uint32_t cross_shifted = cross_sum << 16;
+ return cross_shifted + lolo;
+}
+
+/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 3
"forwprop1" } } */
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 288363429dd9..662ad77748e5 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,8 +105,9 @@ uint64_t full_mul_two_carry (uint64_t x, uint64_t y,
uint64_t *lo)
return high;
}
-/* Folds land in forwprop3 because the LT_EXPR low-carry compare is
- only canonicalized into the gt:c-plus-overflow shape that
- mul_carry_low matches by an earlier pass between forwprop1 and
- forwprop3. */
-/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 4
"forwprop3" } } */
\ No newline at end of file
+/* The LOW fold for full_mul_two_carry lands in forwprop4 because
+ `lolo + cross_shifted' also feeds the HIGH fold's low-carry
+ compare; long_mul_check_low_plus_defer holds it until the HIGH
+ fold has consumed the compare. */
+/* { dg-final { scan-tree-dump-times "Long multiplication high part folded." 4
"forwprop3" } } */
+/* { dg-final { scan-tree-dump-times "Long multiplication low part folded." 1
"forwprop4" } } */
diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
index f9c0f1a9854d..30f3a0310d0f 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -4272,6 +4272,55 @@ long_mul_check_two_carries (const vec<long_mul_summand>
&summands,
return true;
}
+/* 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
+ high-part fold. Folding to mul_lo here destroys cross_shifted,
+ which both the compare and the high-part match still need; defer
+ so the high-part fold runs first. After it does, the compare is
+ dead and the surviving lolo + cross_shifted is picked up by this
+ row in the next forwprop instance. Returns false to defer. */
+
+static bool
+long_mul_check_low_plus_defer (const vec<long_mul_summand> &, gimple *stmt)
+{
+ if (!is_gimple_assign (stmt))
+ return false;
+
+ tree lhs = gimple_assign_lhs (stmt);
+ tree rhs1 = gimple_assign_rhs1 (stmt);
+ tree rhs2 = gimple_assign_rhs2 (stmt);
+
+ imm_use_iterator iter;
+ gimple *use_stmt;
+ FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
+ {
+ tree cmp_op1 = NULL_TREE, cmp_op2 = NULL_TREE;
+ enum tree_code use_code = ERROR_MARK;
+ if (is_gimple_assign (use_stmt))
+ {
+ use_code = gimple_assign_rhs_code (use_stmt);
+ cmp_op1 = gimple_assign_rhs1 (use_stmt);
+ cmp_op2 = gimple_assign_rhs2 (use_stmt);
+ }
+ else if (gcond *cond = dyn_cast<gcond *> (use_stmt))
+ {
+ use_code = gimple_cond_code (cond);
+ cmp_op1 = gimple_cond_lhs (cond);
+ cmp_op2 = gimple_cond_rhs (cond);
+ }
+ if (use_code == GT_EXPR || use_code == LT_EXPR
+ || use_code == GE_EXPR || use_code == LE_EXPR)
+ {
+ tree other = (cmp_op1 == lhs) ? cmp_op2
+ : (cmp_op2 == lhs) ? cmp_op1 : NULL_TREE;
+ if (other && (other == rhs1 || other == rhs2))
+ return false;
+ }
+ }
+ return true;
+}
+
/* Long-multiply variant table. Each row enumerates the multiset of
(kind, extract) summands that compose one long-multiply form. Rows
are sorted by long_mul_summand_compare, matching the input summands'
@@ -4335,6 +4384,11 @@ static const long_mul_row long_mul_table[] = {
NULL },
/* LOW-PART folds. Recover the lower 2N bits from xl*yl plus a
shifted cross-half term. */
+ /* xl*yl + (cross_sum << N). */
+ { long_mul_row::LOW_PART, PLUS_EXPR, 2,
+ { { LMK_MUL_LOLO, LMX_NONE },
+ { LMK_CROSS_SUM, LMX_SHL_N } },
+ long_mul_check_low_plus_defer },
/* (xl*yl & mask) | (low_accum << N),
low_accum = (xl*yl >> N) + (cross_sum & mask). */
{ long_mul_row::LOW_PART, BIT_IOR_EXPR, 2,
--
2.55.0
