[COMMITTED PATCH v9 5/7] forwprop: Add long-multiply low-plus variant

Extend the long-multiply fold to a LOW_PART variant recovering the
lower 2N bits as

  xl*yl + (cross_sum << N)
  cross_sum = xh*yl + xl*yh

This form is also the low half of a two-carry long-multiply, where an
unsigned overflow compare against one of the PLUS operands feeds the
matching high-part fold.  Folding here would destroy (cross_sum << N)
while the compare still needs it, so the fold is deferred while any
GT/LT/GE/LE use shares an operand with the PLUS; once the high-part
fold has consumed the compare, the next forwprop instance folds the
rest.

	PR tree-optimization/107090

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; gates the LOW_PART PLUS_EXPR row added
	to long_mul_table.

gcc/testsuite/ChangeLog:

	* 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.
	* gcc.dg/tree-ssa/long-mul-low-plus.c: New test.

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 81a3bacd909f..b8e24882c8d8 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -4325,6 +4325,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'
@@ -4388,6 +4437,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