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.
Also why can't you use a similar infrastructure as the `saturated add`
to find this part? rather than depending on phiopt here?
Thanks,
Andrea
> +}
> +
> /* 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
>
