[COMMITTED PATCH v9 3/7] forwprop: Add long-multiply two-carry variant

Extend the long-multiply fold to the variant where the cross sum and
the low-half accumulation each carry through a separate unsigned
overflow compare:

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

An extra check validates the carry_low operands against the multiset's
canonical (op0, op1).

	PR tree-optimization/107090

gcc/ChangeLog:

	* match.pd: Add mul_carry_low atom recognizer.
	* tree-ssa-forwprop.cc (gimple_mul_carry_low): Declare.
	(enum long_mul_kind): Add LMK_CARRY_LOW.
	(struct long_mul_summand): Add carry_a / carry_b for the
	LMK_CARRY_LOW summand's two operands.
	(long_mul_set_summand): Handle LMK_CARRY_LOW.
	(long_mul_classify_carry): Try mul_carry_low after the
	more-constrained mul_carry_low_sum / mul_carry_cross_sum.
	(long_mul_find_summand): New helper, find the first summand
	with a given kind.
	(long_mul_check_two_carries): New extra check, validates the
	LMK_CARRY_LOW summand's operands against the canonical
	(op0, op1); gates the two-carry HIGH_PART row added to
	long_mul_table.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/long-mul-two-carry.c: New test.

Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---

(no changes since v1)

 gcc/match.pd                                  |   7 ++
 .../gcc.dg/tree-ssa/long-mul-two-carry.c      | 112 ++++++++++++++++++
 gcc/tree-ssa-forwprop.cc                      |  81 ++++++++++++-
 3 files changed, 198 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 3e92fbab7a5c..bdb18df8140c 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -12838,6 +12838,13 @@ and,
        && TYPE_PRECISION (op_type) % 2 == 0
        && tree_fits_uhwi_p (@0)
        && tree_to_uhwi (@0) == TYPE_PRECISION (op_type) / 2))))
+/* Carry from addition overflow: (cast?) (a > a + b).
+   :c on gt also matches the LT form: (cast?) (a + b < a).  */
+(match (mul_carry_low @0 @1)
+  (convert?
+    (gt:c @0 (plus:c @1 @0)))
+  (with { tree op_type = TREE_TYPE (@0); }
+  (if (INTEGRAL_TYPE_P (op_type) && TYPE_UNSIGNED (op_type)))))
 /* Low accumulate: (xl*yl >> N) + (cross_sum & mask).  */
 (match (mul_low_accum @op0 @op1 @mul_hilo0 @mul_hilo1 @0 @1)
   (plus:c
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
new file mode 100644
index 000000000000..288363429dd9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/long-mul-two-carry.c
@@ -0,0 +1,112 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-forwprop-details" } */
+
+typedef __UINT32_TYPE__ uint32_t;
+typedef __UINT64_TYPE__ uint64_t;
+
+/* High part using two separate carries (cross carry + low carry).  */
+uint64_t mulh_two_carry (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 hihi = x_hi * y_hi;
+
+  uint64_t cross_sum = hilo + lohi;
+  uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32;
+
+  uint64_t cross_shifted = cross_sum << 32;
+  uint64_t low_result = lolo + cross_shifted;
+  uint64_t low_carry = (uint64_t)(low_result < cross_shifted);
+
+  uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry;
+
+  return high;
+}
+
+/* Commuted operand order.  */
+uint64_t mulh_two_carry_comm (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 lohi = x_lo * y_hi;
+  uint64_t hilo = x_hi * y_lo;
+  uint64_t hihi = x_hi * y_hi;
+
+  uint64_t cross_sum = lohi + hilo;
+  uint64_t cross_carry = (uint64_t)(cross_sum < lohi) << 32;
+
+  uint64_t cross_shifted = cross_sum << 32;
+  uint64_t low_result = cross_shifted + lolo;
+  uint64_t low_carry = (uint64_t)(low_result < lolo);
+
+  uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry;
+
+  return high;
+}
+
+/* 32-bit variant.  */
+uint32_t mulh_two_carry_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 hihi = x_hi * y_hi;
+
+  uint32_t cross_sum = hilo + lohi;
+  uint32_t cross_carry = (uint32_t)(cross_sum < hilo) << 16;
+
+  uint32_t cross_shifted = cross_sum << 16;
+  uint32_t low_result = lolo + cross_shifted;
+  uint32_t low_carry = (uint32_t)(low_result < cross_shifted);
+
+  uint32_t high = hihi + (cross_sum >> 16) + cross_carry + low_carry;
+
+  return high;
+}
+
+/* Full multiply: both high and low parts.  */
+uint64_t full_mul_two_carry (uint64_t x, uint64_t y, uint64_t *lo)
+{
+  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 hihi = x_hi * y_hi;
+
+  uint64_t cross_sum = hilo + lohi;
+  uint64_t cross_carry = (uint64_t)(cross_sum < hilo) << 32;
+
+  uint64_t cross_shifted = cross_sum << 32;
+  uint64_t low_result = lolo + cross_shifted;
+  uint64_t low_carry = (uint64_t)(low_result < cross_shifted);
+
+  uint64_t high = hihi + (cross_sum >> 32) + cross_carry + low_carry;
+
+  *lo = low_result;
+  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
diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
index dd59459615bf..aafbc2275b81 100644
--- a/gcc/tree-ssa-forwprop.cc
+++ b/gcc/tree-ssa-forwprop.cc
@@ -3625,6 +3625,7 @@ extern bool gimple_mul_low_sum (tree, tree *, tree (*)(tree));
 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));
 
 /* Append to SEQ statements assigning DEST the high-part multiply of
    OP1 and OP2, emitted as
@@ -3727,6 +3728,7 @@ enum long_mul_kind {
   LMK_CROSS_SUM,
   LMK_LOW_ACCUM,
   LMK_LOW_SUM,
+  LMK_CARRY_LOW,
   LMK_CARRY_CROSS_SUM,
   LMK_CARRY_LOW_SUM,
 };
@@ -3747,6 +3749,7 @@ struct long_mul_summand {
   long_mul_extract extract;
   tree op0, op1;
   tree hilo0, hilo1, hilo2;
+  tree carry_a, carry_b;
   unsigned HOST_WIDE_INT shift;
 };
 
@@ -3854,6 +3857,10 @@ long_mul_set_summand (long_mul_summand *info, long_mul_kind kind,
       n_hilos = 3;
       shift_idx = 5;
       break;
+    case LMK_CARRY_LOW:
+      info->carry_a = res_ops[0];
+      info->carry_b = res_ops[1];
+      return;
     }
   if (n_ops >= 1)
     info->op0 = res_ops[0];
@@ -3882,8 +3889,9 @@ long_mul_classify_carry (tree leaf, long_mul_summand *info)
   tree res_ops[LONG_MUL_MAX_CAPTURES];
   /* mul_carry_low_sum's inner is constrained to mul_low_sum (cross_sum
      + mul_hi(mul_lolo)); mul_carry_cross_sum's inner is just
-     mul_cross_sum (any plus).  Most specific first, so the less-
-     constrained pattern doesn't shadow the more-constrained one.  */
+     mul_cross_sum (any plus); mul_carry_low matches gt:c (@0, plus(@0,
+     @1)) without a baked-in shift.  Most specific first, so the
+     less-constrained pattern doesn't shadow the more-constrained one.  */
   if (gimple_mul_carry_low_sum (leaf, res_ops, NULL))
     {
       long_mul_set_summand (info, LMK_CARRY_LOW_SUM, res_ops);
@@ -3894,6 +3902,11 @@ long_mul_classify_carry (tree leaf, long_mul_summand *info)
       long_mul_set_summand (info, LMK_CARRY_CROSS_SUM, res_ops);
       return true;
     }
+  if (gimple_mul_carry_low (leaf, res_ops, NULL))
+    {
+      long_mul_set_summand (info, LMK_CARRY_LOW, res_ops);
+      return true;
+    }
   return false;
 }
 
@@ -4124,6 +4137,18 @@ long_mul_canonical_ops (const vec<long_mul_summand> &summands,
   return false;
 }
 
+/* Return the first summand in SUMMANDS whose kind matches KIND, or NULL.  */
+
+static const long_mul_summand *
+long_mul_find_summand (const vec<long_mul_summand> &summands,
+		       long_mul_kind kind)
+{
+  for (const long_mul_summand &s : summands)
+    if (s.kind == kind)
+      return &s;
+  return NULL;
+}
+
 /* Run the cross-summand validation invariants and return the canonical
    (op0, op1).  Returns false unless all summands that carry operands use
    the same (op0, op1) pair (in either order), every LMX_HI/LMX_SHL_N shift
@@ -4219,6 +4244,50 @@ long_mul_signature_matches (const vec<long_mul_summand> &summands,
   return true;
 }
 
+/* Extra check for the two-carries high-part row: the LMK_CARRY_LOW summand's
+   two operands (carry_a, carry_b) must be a (cross_shifted, mul_lolo) pair
+   consistent with the multiset's canonical (op0, op1).  */
+
+static bool
+long_mul_check_two_carries (const vec<long_mul_summand> &summands,
+			    gimple *)
+{
+  tree op0, op1;
+  if (!long_mul_canonical_ops (summands, &op0, &op1))
+    return false;
+  unsigned int halfwidth = TYPE_PRECISION (TREE_TYPE (op0)) / 2;
+
+  const long_mul_summand *cl = long_mul_find_summand (summands, LMK_CARRY_LOW);
+  if (!cl)
+    return false;
+
+  /* The two carry_low operands must be (cross_shifted, mul_lolo) in either
+     order.  cross_shifted = LSHIFT_EXPR (mul_cross_sum, halfwidth).  */
+  tree cs = cl->carry_a, lolo = cl->carry_b;
+  tree inner;
+  unsigned HOST_WIDE_INT shift;
+  if (!long_mul_is_lshift_def (cs, &inner, &shift))
+    {
+      std::swap (cs, lolo);
+      if (!long_mul_is_lshift_def (cs, &inner, &shift))
+	return false;
+    }
+  if (shift != halfwidth)
+    return false;
+
+  tree scratch[LONG_MUL_MAX_CAPTURES];
+  if (!gimple_mul_cross_sum (inner, scratch, NULL))
+    return false;
+  for (int i = 0; i < 2; i++)
+    if (!long_mul_is_cross_half (scratch[i], op0, op1))
+      return false;
+  if (!gimple_mul_lolo (lolo, scratch, NULL)
+      || !long_mul_same_ops (scratch[0], scratch[1], op0, op1))
+    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'
@@ -4248,6 +4317,14 @@ static const long_mul_row long_mul_table[] = {
       { LMK_LOW_ACCUM, LMX_HI },
       { LMK_CARRY_CROSS_SUM, LMX_NONE } },
     NULL },
+  /* xh*yh + (cross_sum >> N) + carry_low + ((hilo > cross_sum) << N),
+     carry_low = (xl*yl + (cross_sum << N)) < (cross_sum << N).  */
+  { long_mul_row::HIGH_PART, PLUS_EXPR, 4,
+    { { LMK_MUL_HIHI, LMX_NONE },
+      { LMK_CROSS_SUM, LMX_HI },
+      { LMK_CARRY_LOW, LMX_NONE },
+      { LMK_CARRY_CROSS_SUM, LMX_NONE } },
+    long_mul_check_two_carries },
   /* LOW-PART folds.  Recover the lower 2N bits from xl*yl plus a
      shifted cross-half term.  */
   /* (xl*yl & mask) | (low_accum << N),
-- 
2.55.0