On Thu, Mar 26, 2026 at 12:14 PM Konstantinos Eleftheriou
<[email protected]> wrote:
>
> 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)
The :c on the 2nd plus isn't necessary, INTEGER_CST always appears second.
> + (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))))
Do not replicate (cmp ...), instead capture it and re-use that captured
value here.
Otherwise looks reasonable. It may raise eybrows from AVR folks,
a wide shift might be expensive (but at least not as expensive as
a multiplication).
You are tackling 'type' wider than word_mode, right?
> + { 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
>
