On Fri, May 29, 2026 at 3:48 AM Andrew Pinski < [email protected]> wrote:
> On Thu, May 28, 2026 at 12:09 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)); > > > > with cmp:c matching four logical relations: the unsigned-overflow carry > > idiom ((a + b) < a, a > (a + b)) and its negation (a + b > a, > > a < a + b). The rewrite is sound for any boolean comparison, so all > > four variants are kept -- both senses are equally useful for branch > > elimination on cheap-branch targets. > > > > 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 the > > surrounding idiom. 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). > > > > The simplification is gated on fold_cond_carry_add_profitable_p in > > gimple-match-head.cc, which combines BRANCH_COST with an optab probe: > > on cheap-branch targets the fold fires only when the surrounding long > > multiply can also be folded, either via umul_highpart at TYPE's width > > or via a widening/regular multiply at double width. The check is > > target-and-width capability only -- the match.pd predicate does not > > walk SSA uses to confirm that the carry actually feeds a long multiply. > > On a cheap-branch target that does support the long-multiply fold the > > pattern can therefore fire on a carry-add that is not in fact part of > > a long multiply; this is a small amount of IR churn (one branch elided > > and replaced by a compare-and-shift), not a correctness or performance > > regression. > > > > Bootstrapped/regtested on AArch64 and x86-64. > > > > gcc/ChangeLog: > > > > * gimple-match-head.cc (fold_cond_carry_add_profitable_p): > > New helper. > > * match.pd: Add simplification for conditional power-of-two > > add to a shifted comparison. > > > > 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]> > > > > Ref: #423 > > Signed-off-by: Konstantinos Eleftheriou < > [email protected]> > > --- > > > > (no changes since v1) > > > > gcc/gimple-match-head.cc | 23 +++++++++++ > > gcc/match.pd | 22 ++++++++++ > > gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c | 20 +++++++++ > > gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c | 45 +++++++++++++++++++++ > > 4 files changed, 110 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/gimple-match-head.cc b/gcc/gimple-match-head.cc > > index 757e324cb21a..8970dd7c72b6 100644 > > --- a/gcc/gimple-match-head.cc > > +++ b/gcc/gimple-match-head.cc > > @@ -47,6 +47,8 @@ along with GCC; see the file COPYING3. If not see > > #include "tree-eh.h" > > #include "dbgcnt.h" > > #include "tm.h" > > +#include "tm_p.h" > > +#include "predict.h" > > #include "gimple-range.h" > > #include "langhooks.h" > > #include "attribs.h" > > @@ -249,6 +251,27 @@ optimize_successive_divisions_p (tree divisor, tree > inner_div) > > return true; > > } > > > > +/* True if flattening the conditional carry-add > > + (cond C (base + pow2) base) of TYPE pays off on the current target: > > + branches are expensive, or the surrounding long-multiply can be > > + folded (which means the target can compute a highpart multiply > > + directly or via a wider multiply). */ > > + > > +static bool > > +fold_cond_carry_add_profitable_p (tree type) > > +{ > > + /* BRANCH_COST >= 2 is the conventional "branches are expensive" > > + threshold used by tree-ssa-reassoc.cc and expmed.cc. */ > > + if (BRANCH_COST (optimize_function_for_speed_p (cfun), false) >= 2) > > + return true; > > + > > + const unsigned int width = TYPE_PRECISION (type); > > + if (width % 2 != 0 || width > MAX_FIXED_MODE_SIZE) > > + return false; > > + > > + return can_mult_highpart_p (TYPE_MODE (type), true); > > Since I mentioned we should remove the can_mult_highpart_p check in > the other case. This is the wrong check here too. > I think MAX_FIXED_MODE_SIZE is enough. > `(width % 2) != 0` also seems wrong. Why do you want to allow a 12bit > type here? It seems like what you want the precision is the same as > the mode (ignoring PSI; a power of 2). > So the call to `fold_cond_carry_add_profitable_p (type)` should > become `type_has_mode_precision_p (type)`. > I am not seeing the need for BRANCH_COST here either. > Fixed in the new version. > > Also why can't you use a similar infrastructure as the `saturated add` > to find this part? rather than depending on phiopt here? > You're right, we fixed that too. > > Thanks, > Andrea > > Thanks, Konstantinos > > +} > > + > > /* Return true if EXPR1 and EXPR2 have the same value, but not > necessarily > > same type. The types can differ through nop conversions. */ > > #define bitwise_equal_p(expr1, expr2) \ > > diff --git a/gcc/match.pd b/gcc/match.pd > > index ff13a07ea94b..cb7cbf9971c7 100644 > > --- a/gcc/match.pd > > +++ b/gcc/match.pd > > @@ -6179,6 +6179,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)) > > + > > + (for cmp (gt lt)) with cmp:c matches four relations: the > > + unsigned-overflow carry idiom and its negation, both senses. > > + The rewrite is sound for any boolean comparison. */ > > +(for cmp (gt lt) > > + (simplify > > + (cond (cmp:c@4 @0 (plus:c @0 @1)) (plus @2 integer_pow2p@3) @2) > > + (if (INTEGRAL_TYPE_P (type) > > + && TYPE_UNSIGNED (type) > > + && INTEGRAL_TYPE_P (TREE_TYPE (@0)) > > + && TYPE_UNSIGNED (TREE_TYPE (@0)) > > + && fold_cond_carry_add_profitable_p (TREE_TYPE (@0))) > > + (plus @2 > > + (lshift > > + (convert (convert:boolean_type_node @4)) > > + { build_int_cst (integer_type_node, > > + wi::exact_log2 (wi::to_wide (@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..0d9e91697cdd > > --- /dev/null > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c > > @@ -0,0 +1,20 @@ > > +/* { dg-do compile } */ > > +/* { dg-options "-O2 -fdump-tree-phiopt2" } */ > > + > > +/* Test that phiopt 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 "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..a9e579bc216d > > --- /dev/null > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c > > @@ -0,0 +1,45 @@ > > +/* { dg-do compile } */ > > +/* { dg-options "-O2 -fdump-tree-phiopt2" } */ > > +/* { dg-require-effective-target lp64 } */ > > + > > +/* Test that phiopt flattens a conditional carry-add with a > > + non-trivial shift: > > + sum = a + b; if (b > sum) result = base + (1UL << 32); > > + to > > + result = base + ((type)(b > sum) << 32); > > + This is the shape that match.pd's mul_carry_cross_sum pattern > > + expects. */ > > + > > +unsigned long > > +test_cond_carry_add_shifted (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 conditional carry-adds in sequence, as in long-multiply carry > > + chains: one with a shifted constant and one with a plain +1. */ > > + > > +unsigned long > > +test_cond_carry_add_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 > > >
