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 >
