On Thu, Mar 26, 2026 at 4:11 AM Konstantinos Eleftheriou <[email protected]> wrote: > > Recognize and flatten carry-diamond patterns found in longhand
This is NOT a diamond form even. This is a triangle form of a basic block. I missed this in my previous review. > 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. */ This is also NOT a diamond but rather than a triangle bb form but I would not even use those terms here. > +(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)) A bunch of things are wrong here. This seems lower quality than your previous changes even. First you don't need the `:c` on the second plus since the canonical form is always `var + CST`. Second you can just use integer_pow2p directly instead of using INTEGER_CST and then checking. Third you are checking the type of @2/@3 (because the type here is the type of the outer expression which is the same as the true/false operands of the cond_expr) which is not correct here. You need to checking the type of @0. Fourth you can capture the cmp and then reuse it below. Also you had much more constraints on doing this when it was done in forwprop. Why did you remove them here? > + (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; })))))) Without the with you can just do: build_int_cst (integer_type_node, wi::exact_log2 (wi::to_wide (@3))); Which is exactly what is done in other patterns that convert integer_pow2p to a shift. Thanks, Andrea > + > /* (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 >
