Hi Andrew, We submitted a new version: https://gcc.gnu.org/pipermail/gcc-patches/2026-June/721449.html.
The carry-add recognition is now integrated into the long-mul patterns. We kept the carry matching support as a separate patch in case that we want to revert it and add it as a standalone transformation in the future. Thanks, Konstantinos On Sat, Jun 13, 2026 at 1:21 AM Andrew Pinski <[email protected]> wrote: > On Fri, Jun 12, 2026 at 8:12 AM Konstantinos Eleftheriou > <[email protected]> wrote: > > > > A conditional add of a power-of-two value has the shape > > > > sum = a + b; > > if (cmp(a, sum)) result = base + pow2; > > else result = base; > > > > i.e. one of two values selected by a boolean. Rewrite to straight-line > > code: > > > > result = base + ((type)(cmp(a, sum)) << log2(pow2)); > > > > Implementation: two match.pd recognizers (cond_carry_add, > > cond_carry_add_neg) match the 2-arg PHI form via cond^. > > flatten_cond_carry_add in tree-ssa-forwprop.cc runs inside the > > existing degenerate-PHI walk; it lifts the branch by reusing the > > dominating gcond's comparison, inverting it via > > invert_tree_comparison for the _neg recognizer. Modelled on > > match_saturation_add in tree-ssa-math-opts.cc. > > > > Two recognizers cover the four enumerated relations. cond_carry_add > > matches when the gcond's true edge selects (base + pow2): the direct > > unsigned-overflow idiom ((a + b) < a, a > (a + b)). > > cond_carry_add_neg matches the inverse senses (a + b > a, a < a + b), > > where the gcond's true edge selects base; the driver inverts the > > comparison before reuse so the rewrite remains semantically > > equivalent. > > > > The transformation is independently useful as a branch-elimination > > peephole; the long-multiply fold in 2/2 is one consumer that needs > > the carry on a branch-free path. > > > > The fold accepts any unsigned integer type whose precision matches > > its mode (type_has_mode_precision_p (type)). Three regimes are > > intentionally covered, without any word_mode-relative restriction: > > > > - type == word_mode: the canonical 64x64 -> 128 case on 64-bit > > hosts (DImode = word_mode). > > - type > word_mode: hand-rolled 64-bit chains compiled for 32-bit > > hosts (DImode > SImode = word_mode). > > - type < word_mode: hand-rolled 32-bit chains on 64-bit hosts > > (SImode < DImode = word_mode); this is a target workload. > > > > (PHI<pow2, 0>) is already handled by the existing match.pd pattern: > > a ? powerof2cst : 0 -> a << log2(powerof2cst). > > I think you totally misunderstood my point. I am saying you should NOT > do the replacement at all for this in tree-ssa-forwprop.cc. > You should use the match patterns for the second part of the patch to > handle like the replacement would be when dealing with the matching > there. > > Thanks, > Andrea > > > > > > PR tree-optimization/107090 > > > > gcc/ChangeLog: > > > > * match.pd (cond_carry_add, cond_carry_add_neg): New match > > recognizers; split by gcond polarity. > > * tree-ssa-forwprop.cc (gimple_cond_carry_add): Declare. > > (gimple_cond_carry_add_neg): Declare. > > (flatten_cond_carry_add): New; inverts the gcond's comparison > > for the _neg recognizer before reuse. > > (pass_forwprop::execute): Flatten conditional carry-add > > patterns inside the existing degenerate-PHI walk. > > > > gcc/testsuite/ChangeLog: > > > > * gcc.dg/tree-ssa/forwprop-44.c: New test. > > * gcc.dg/tree-ssa/forwprop-45.c: New test. > > * gcc.dg/tree-ssa/forwprop-46.c: New test. > > > > Co-authored-by: Philipp Tomsich <[email protected]> > > Signed-off-by: Konstantinos Eleftheriou < > [email protected]> > > --- > > > > (no changes since v1) > > > > gcc/match.pd | 22 ++++++ > > gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c | 20 +++++ > > gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c | 44 +++++++++++ > > gcc/testsuite/gcc.dg/tree-ssa/forwprop-46.c | 49 ++++++++++++ > > gcc/tree-ssa-forwprop.cc | 83 ++++++++++++++++++++- > > 5 files changed, 215 insertions(+), 3 deletions(-) > > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c > > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/forwprop-46.c > > > > diff --git a/gcc/match.pd b/gcc/match.pd > > index e0d7ef80e14d..43d56e851172 100644 > > --- a/gcc/match.pd > > +++ b/gcc/match.pd > > @@ -6195,6 +6195,28 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > > (lshift (convert (bit_xor (convert:boolean_type_node @0) > > { boolean_true_node; })) { shift; > }))))))) > > > > +/* Flatten a conditional carry-add (a power-of-two carry added under > > + a guard) to a shifted compare: > > + (cmp a (plus a b)) ? (base + pow2) : base > > + -> base + ((type)(cmp a (plus a b)) << log2(pow2)) > > + > > + Two recognizers split the four relations by gcond polarity: > > + cond_carry_add: the gcond's true edge selects (base + pow2) > > + cond_carry_add_neg: the gcond's true edge selects base > > + The forwprop driver inverts the comparison for the _neg form > > + before reuse. Matches the 2-arg PHI form via cond^. */ > > +(if (INTEGRAL_TYPE_P (type) > > + && TYPE_UNSIGNED (type) > > + && type_has_mode_precision_p (type)) > > + (match (cond_carry_add @0 @1 @2 @3) > > + (cond^ (gt @0 (plus:c @0 @1)) (plus @2 integer_pow2p@3) @2)) > > + (match (cond_carry_add @0 @1 @2 @3) > > + (cond^ (lt (plus:c @0 @1) @0) (plus @2 integer_pow2p@3) @2)) > > + (match (cond_carry_add_neg @0 @1 @2 @3) > > + (cond^ (gt (plus:c @0 @1) @0) @2 (plus @2 integer_pow2p@3))) > > + (match (cond_carry_add_neg @0 @1 @2 @3) > > + (cond^ (lt @0 (plus:c @0 @1)) @2 (plus @2 integer_pow2p@3)))) > > + > > /* (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..f9d4e06b8107 > > --- /dev/null > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > > @@ -0,0 +1,20 @@ > > +/* { dg-do compile } */ > > +/* { dg-options "-O2 -fdump-tree-forwprop1" } */ > > + > > +/* Test that forwprop flattens a conditional carry-add > > + sum = a + b; if (b > sum) result = base + 1; > > + to straight-line code > > + result = base + (type)(b > sum); */ > > + > > +unsigned long > > +test_cond_carry_add (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 "PHI <" "forwprop1" } } */ > > 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..1b2e755febb6 > > --- /dev/null > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c > > @@ -0,0 +1,44 @@ > > +/* { dg-do compile } */ > > +/* { dg-options "-O2 -fdump-tree-forwprop1" } */ > > + > > +typedef __UINT64_TYPE__ uint64_t; > > + > > +/* Test that forwprop flattens a conditional carry-add with a > > + non-trivial shift: > > + sum = a + b; if (b > sum) result = base + ((uint64_t)1 << 32); > > + to > > + result = base + ((type)(b > sum) << 32); > > + This is the shape that match.pd's mul_carry_cross_sum pattern > > + expects. */ > > + > > +uint64_t > > +test_cond_carry_add_shifted (uint64_t a, uint64_t b, uint64_t base) > > +{ > > + uint64_t sum = a + b; > > + uint64_t result = base; > > + if (b > sum) > > + result = base + ((uint64_t)1 << 32); > > + return result; > > +} > > + > > +/* Two conditional carry-adds in sequence, as in long-multiply carry > > + chains: one with a shifted constant and one with a plain +1. */ > > + > > +uint64_t > > +test_cond_carry_add_chain (uint64_t a, uint64_t b, uint64_t c, > > + uint64_t d, uint64_t base) > > +{ > > + uint64_t sum1 = a + b; > > + uint64_t r1 = base; > > + if (b > sum1) > > + r1 = base + ((uint64_t)1 << 32); > > + > > + uint64_t sum2 = c + d; > > + uint64_t r2 = r1; > > + if (d > sum2) > > + r2 = r1 + 1; > > + > > + return r2; > > +} > > + > > +/* { dg-final { scan-tree-dump-not "PHI <" "forwprop1" } } */ > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-46.c > b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-46.c > > new file mode 100644 > > index 000000000000..4bc2e7a4cb37 > > --- /dev/null > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-46.c > > @@ -0,0 +1,49 @@ > > +/* { dg-do run } */ > > +/* { dg-options "-O2" } */ > > + > > +/* Runtime check for cond_carry_add flattening, all four polarities. */ > > + > > +extern void abort (void); > > + > > +__attribute__ ((noipa)) unsigned long > > +p1 (unsigned long a, unsigned long b, unsigned long base) > > +{ > > + unsigned long s = a + b, r = base; > > + if (s < a) r = base + 1; > > + return r; > > +} > > + > > +__attribute__ ((noipa)) unsigned long > > +p2 (unsigned long a, unsigned long b, unsigned long base) > > +{ > > + unsigned long s = a + b, r = base; > > + if (a > s) r = base + 1; > > + return r; > > +} > > + > > +__attribute__ ((noipa)) unsigned long > > +p3 (unsigned long a, unsigned long b, unsigned long base) > > +{ > > + unsigned long s = a + b, r = base + 1; > > + if (s > a) r = base; > > + return r; > > +} > > + > > +__attribute__ ((noipa)) unsigned long > > +p4 (unsigned long a, unsigned long b, unsigned long base) > > +{ > > + unsigned long s = a + b, r = base + 1; > > + if (a < s) r = base; > > + return r; > > +} > > + > > +int > > +main (void) > > +{ > > + unsigned long T = ~0UL; > > + if (p1 (5, 3, 100) != 100 || p1 (T, 1, 100) != 101) abort (); > > + if (p2 (5, 3, 100) != 100 || p2 (T, 1, 100) != 101) abort (); > > + if (p3 (5, 3, 100) != 100 || p3 (T, 1, 100) != 101) abort (); > > + if (p4 (5, 3, 100) != 100 || p4 (T, 1, 100) != 101) abort (); > > + return 0; > > +} > > diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc > > index 9bb001d2f63b..1e8f3aab48f4 100644 > > --- a/gcc/tree-ssa-forwprop.cc > > +++ b/gcc/tree-ssa-forwprop.cc > > @@ -3568,6 +3568,78 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) > > return true; > > } > > > > +/* Match.pd recognizers for the conditional carry-add pattern. The > > + two names split the gcond polarity: cond_carry_add matches when > > + the true edge selects (base + pow2), cond_carry_add_neg when the > > + true edge selects base. */ > > + > > +extern bool gimple_cond_carry_add (tree, tree *, tree (*)(tree)); > > +extern bool gimple_cond_carry_add_neg (tree, tree *, tree (*)(tree)); > > + > > +/* If PHI is a conditional power-of-two carry-add > > + res = cmp (a, a + b) ? base + pow2 : base; > > + replace it with branchless straight-line code: > > + cval = (type) cmp; > > + shifted = cval << log2 (pow2); > > + res = base + shifted; > > + The gcond's comparison is reused; for the _neg recognizer (true > > + edge selects base) it is inverted first. Returns true if the PHI > > + was rewritten. */ > > + > > +static bool > > +flatten_cond_carry_add (gphi *phi) > > +{ > > + tree phi_res = gimple_phi_result (phi); > > + tree type = TREE_TYPE (phi_res); > > + > > + tree ops[4]; > > + bool invert_cmp = false; > > + if (!gimple_cond_carry_add (phi_res, ops, NULL)) > > + { > > + if (!gimple_cond_carry_add_neg (phi_res, ops, NULL)) > > + return false; > > + invert_cmp = true; > > + } > > + > > + tree base = ops[2]; > > + tree pow2 = ops[3]; > > + > > + /* cond^ validated the CFG shape, so the PHI block's immediate > > + dominator is the gcond's block. */ > > + basic_block cond_bb > > + = get_immediate_dominator (CDI_DOMINATORS, gimple_bb (phi)); > > + gcond *cond_stmt > > + = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb)); > > + > > + if (!cond_stmt) > > + return false; > > + > > + enum tree_code cmp_code = gimple_cond_code (cond_stmt); > > + if (invert_cmp) > > + cmp_code = invert_tree_comparison (cmp_code, false); > > + > > + location_t loc = gimple_location (phi); > > + gimple_seq seq = NULL; > > + tree cmp > > + = gimple_build (&seq, loc, cmp_code, boolean_type_node, > > + gimple_cond_lhs (cond_stmt), > > + gimple_cond_rhs (cond_stmt)); > > + tree cval = gimple_build (&seq, loc, NOP_EXPR, type, cmp); > > + tree shifted > > + = gimple_build (&seq, loc, LSHIFT_EXPR, type, cval, > > + build_int_cst (integer_type_node, > > + wi::exact_log2 (wi::to_wide (pow2)))); > > + gassign *add = gimple_build_assign (phi_res, PLUS_EXPR, base, > shifted); > > + gimple_set_location (add, loc); > > + gimple_seq_add_stmt (&seq, add); > > + > > + gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi)); > > + gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT); > > + gimple_stmt_iterator psi = gsi_for_stmt (phi); > > + remove_phi_node (&psi, false); > > + > > + return true; > > +} > > > > /* Determine whether applying the 2 permutations (mask1 then mask2) > > gives back one of the input. */ > > @@ -5354,14 +5426,19 @@ pass_forwprop::execute (function *fun) > > } > > } > > > > - /* Record degenerate PHIs in the lattice. */ > > - for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si); > > - gsi_next (&si)) > > + /* Flatten conditional carry-add patterns and record degenerate > > + PHIs in the lattice. Iterator advanced up front so a flattened > > + PHI (a cond_carry_add can never be degenerate, so the two cases > > + are disjoint) can be removed in-flight. */ > > + for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);) > > { > > gphi *phi = si.phi (); > > + gsi_next (&si); > > tree res = gimple_phi_result (phi); > > if (virtual_operand_p (res)) > > continue; > > + if (flatten_cond_carry_add (phi)) > > + continue; > > > > tree first = NULL_TREE; > > bool all_same = true; > > -- > > 2.52.0 > > >
