Recognize and flatten carry-diamond patterns found in longhand
multiplication sequences. A carry diamond implements unsigned overflow
detection with conditional carry propagation:
sum = a + b;
if (addend > sum) result = base + C;
This is replaced with straight-line code:
carry = (type)(addend > sum);
result = base + (carry << log2(C));
This eliminates the conditional branch and exposes the carry as a
comparison expression, enabling downstream pattern matching (e.g.
long-multiplication folding in match.pd which expects the form
(lshift (convert? (gt ...)) INTEGER_CST)).
(PHI<pow2, 0>) is already handled by the existing match.pd
pattern: a ? powerof2cst : 0 -> a << log2(powerof2cst).
Bootstrapped/regtested on AArch64 and x86-64.
gcc/ChangeLog:
* match.pd: Add carry-diamond simplification for unsigned
overflow detection with conditional carry propagation.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/forwprop-44.c: New test.
* gcc.dg/tree-ssa/forwprop-45.c: New test.
Co-authored-by: Philipp Tomsich <[email protected]>
Signed-off-by: Konstantinos Eleftheriou <[email protected]>
---
(no changes since v1)
gcc/match.pd | 20 ++++++++++
gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c | 21 ++++++++++
gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c | 44 +++++++++++++++++++++
3 files changed, 85 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c
diff --git a/gcc/match.pd b/gcc/match.pd
index 1d6428bf7e53..59c3a9f2fe69 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -6555,6 +6555,26 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(lshift (convert (bit_xor (convert:boolean_type_node @0)
{ boolean_true_node; })) { shift; })))))))
+/* Carry diamond: (a > a+b) ? (base + pow2) : base
+ -> base + ((type)(a > a+b) << log2(pow2))
+ This flattens unsigned overflow detection with conditional carry
+ propagation to straight-line code, enabling downstream long-multiply
+ pattern matching. */
+(for cmp (gt lt)
+ (simplify
+ (cond (cmp:c @0 (plus:c @0 @1)) (plus:c @2 INTEGER_CST@3) @2)
+ (if (INTEGRAL_TYPE_P (type)
+ && TYPE_UNSIGNED (type)
+ && integer_pow2p (@3))
+ (with {
+ tree shift = build_int_cst (integer_type_node, tree_log2 (@3));
+ }
+ (plus @2
+ (lshift
+ (convert (convert:boolean_type_node
+ (cmp @0 (plus @0 @1))))
+ { shift; }))))))
+
/* (a > 1) ? 0 : (cast)a is the same as (cast)(a == 1)
for unsigned types. */
(simplify
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c
b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c
new file mode 100644
index 000000000000..432bdda60e5e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-phiopt2" } */
+
+/* Test that phiopt flattens a simple carry diamond:
+ sum = a + b;
+ if (b > sum) result = base + 1;
+ The conditional branch is replaced with straight-line code:
+ carry = (type)(b > sum); result = base + carry; */
+
+unsigned long
+test_carry_diamond (unsigned long a, unsigned long b,
+ unsigned long base)
+{
+ unsigned long sum = a + b;
+ unsigned long result = base;
+ if (b > sum)
+ result = base + 1;
+ return result;
+}
+
+/* { dg-final { scan-tree-dump-not "goto" "phiopt2" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c
b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c
new file mode 100644
index 000000000000..602c698e817a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c
@@ -0,0 +1,44 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-phiopt2" } */
+/* { dg-require-effective-target lp64 } */
+
+/* Test that phiopt flattens carry diamonds with a power-of-2 carry
+ constant. The conditional branch:
+ sum = a + b; if (b > sum) result = base + (1UL << 32);
+ is replaced with:
+ carry = (type)(b > sum); result = base + (carry << 32);
+ This form is what match.pd's mul_carry_cross_sum pattern expects. */
+
+unsigned long
+test_carry_diamond_shift (unsigned long a, unsigned long b,
+ unsigned long base)
+{
+ unsigned long sum = a + b;
+ unsigned long result = base;
+ if (b > sum)
+ result = base + (1UL << 32);
+ return result;
+}
+
+/* Two carry diamonds in sequence, as in long-multiply carry chains:
+ one with a shifted constant and one with a plain +1. */
+
+unsigned long
+test_carry_diamond_chain (unsigned long a, unsigned long b,
+ unsigned long c, unsigned long d,
+ unsigned long base)
+{
+ unsigned long sum1 = a + b;
+ unsigned long r1 = base;
+ if (b > sum1)
+ r1 = base + (1UL << 32);
+
+ unsigned long sum2 = c + d;
+ unsigned long r2 = r1;
+ if (d > sum2)
+ r2 = r1 + 1;
+
+ return r2;
+}
+
+/* { dg-final { scan-tree-dump-not "goto" "phiopt2" } } */
--
2.52.0
