On Mon, 23 Mar 2026 at 06:58, Andrew Pinski
<[email protected]> wrote:
>
> On Thu, Mar 19, 2026 at 3:15 AM Konstantinos Eleftheriou
> <[email protected]> wrote:
> >
> > Recognize and flatten carry-diamond patterns found in longhand
> > 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)).
>
> Seems like the right place for this kind of optimization is phiopt, it
> already has code to find
> `if (a) b;` and `if (a) b; else c;` shape basic blocks.
> and is designed to remove phis and basic blocks this way.
>
> Also I am not sure why you can't have some simple match patterns for this.
> Something like:
> ```
> // sum = a + b;
> // if (b > sum) result = base + 1;
> // into
> // carry = (type)(b > sum); result = base + carry; */
> (simplify
> (cond (gt@3 @0 (plus @0 @1)) (plus @2 integer_onep) @2)
> (plus @2 (convert:type @3))
> ```
> This seems exactly what you are trying to do, right?
You're right, the (cond ...) form is the natural way to express this.
Your proposed patterns cover the core case directly and phiopt runs
before forwprop (so pass ordering isn't. a problem either). We just
hadn't thought of it, as we had already implemented the other part of
the optimisation in forwprop.
We'll rewrite and submit a v2.
>
> For the power of 2 case you can replace integer_onep with
> integer_pow2p and then do:
> (plus @2 (lshift (convert:type @3) { p2; } ))
>
> where p2 is the log2 of the power2 constant.
> You can add the other checks which you do for widening multiple or
> multiply high, etc. You could even do that check in a helper function
> and just call that here after match.
>
> Thanks,
> Andrew Pinski
>
> >
> > Bootstrapped/regtested on AArch64 and x86-64.
> >
> > gcc/ChangeLog:
> >
> > * tree-ssa-forwprop.cc: Include tm_p.h.
> > (is_defined_by_mult): New helper for is_long_mul_carry.
> > (is_long_mul_carry): New function.
> > (recognize_overflow_cond): New function.
> > (emit_carry_compare): New function.
> > (commit_carry_replacement): New function.
> > (flatten_carry_diamond): New function.
> > (pass_forwprop::execute): Call flatten_carry_diamond on PHIs.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.dg/tree-ssa/forwprop-44.c: New test.
> > * gcc.dg/tree-ssa/forwprop-45.c: New test.
> >
> > Signed-off-by: Konstantinos Eleftheriou <[email protected]>
> > ---
> >
> > gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c | 21 +
> > gcc/testsuite/gcc.dg/tree-ssa/forwprop-45.c | 44 ++
> > gcc/tree-ssa-forwprop.cc | 460 ++++++++++++++++++++
> > 3 files changed, 525 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/testsuite/gcc.dg/tree-ssa/forwprop-44.c
> > b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c
> > new file mode 100644
> > index 000000000000..8c359ca8cdc7
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-44.c
> > @@ -0,0 +1,21 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O2 -fdump-tree-forwprop1-details" } */
> > +
> > +/* Test that forwprop 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 "Flattening carry diamond" "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..1144b3af832a
> > --- /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-details" } */
> > +/* { dg-require-effective-target lp64 } */
> > +
> > +/* Test that forwprop 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-times "Flattening carry diamond" 3
> > "forwprop1" } } */
> > diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
> > index b5544414ca6e..9296ee1f5346 100644
> > --- a/gcc/tree-ssa-forwprop.cc
> > +++ b/gcc/tree-ssa-forwprop.cc
> > @@ -24,6 +24,7 @@ along with GCC; see the file COPYING3. If not see
> > #include "rtl.h"
> > #include "tree.h"
> > #include "gimple.h"
> > +#include "tm_p.h"
> > #include "cfghooks.h"
> > #include "tree-pass.h"
> > #include "ssa.h"
> > @@ -3558,6 +3559,448 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi)
> > return true;
> > }
> >
> > +/* Helper functions for flatten_carry_diamond. */
> > +
> > +/* Return true if OP is defined by a multiplication, or (when DEPTH > 0)
> > + any of its def-chain operands are, up to DEPTH levels deep. This
> > + catches cross-sum operands (PLUS_EXPR of two MULTs) and shifted lolo
> > + products (RSHIFT_EXPR of a MULT). */
> > +
> > +static bool
> > +is_defined_by_mult (tree op, int depth)
> > +{
> > + if (TREE_CODE (op) != SSA_NAME)
> > + return false;
> > + gimple *def = SSA_NAME_DEF_STMT (op);
> > + if (!def || !is_gimple_assign (def))
> > + return false;
> > + enum tree_code code = gimple_assign_rhs_code (def);
> > + if (code == MULT_EXPR || code == WIDEN_MULT_EXPR)
> > + return true;
> > + if (depth > 0)
> > + {
> > + if (is_defined_by_mult (gimple_assign_rhs1 (def), depth - 1))
> > + return true;
> > + if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS
> > + && is_defined_by_mult (gimple_assign_rhs2 (def), depth - 1))
> > + return true;
> > + }
> > + return false;
> > +}
> > +
> > +/* Return true if ADDEND or the other operand of the sum
> > + (sum = addend + other) is defined by a multiplication (possibly one
> > + level deep), suggesting this carry diamond is part of a long-multiply
> > + pattern. */
> > +
> > +static bool
> > +is_long_mul_carry (tree addend, tree sum_op1, tree sum_op2)
> > +{
> > + tree other_op = (sum_op1 == addend) ? sum_op2 : sum_op1;
> > + return is_defined_by_mult (addend, 1)
> > + || is_defined_by_mult (other_op, 1);
> > +}
> > +
> > +/* Given a conditional COND that tests unsigned overflow from an addition,
> > + normalize to: addend > sum, and verify sum = addend + other.
> > + OVERFLOW_ON_TRUE indicates whether the overflow (carry) path is taken
> > + on the true edge of the conditional. Returns true on success. */
> > +
> > +static bool
> > +recognize_overflow_cond (gcond *cond, bool overflow_on_true,
> > + tree *addend, tree *sum,
> > + tree *sum_op1, tree *sum_op2)
> > +{
> > + enum tree_code cond_code = gimple_cond_code (cond);
> > + tree cond_lhs = gimple_cond_lhs (cond);
> > + tree cond_rhs = gimple_cond_rhs (cond);
> > +
> > + if (overflow_on_true)
> > + {
> > + if (cond_code == GT_EXPR)
> > + { *addend = cond_lhs; *sum = cond_rhs; }
> > + else if (cond_code == LT_EXPR)
> > + { *addend = cond_rhs; *sum = cond_lhs; }
> > + else
> > + return false;
> > + }
> > + else
> > + {
> > + if (cond_code == LE_EXPR)
> > + { *addend = cond_lhs; *sum = cond_rhs; }
> > + else if (cond_code == GE_EXPR)
> > + { *addend = cond_rhs; *sum = cond_lhs; }
> > + else
> > + return false;
> > + }
> > +
> > + if (TREE_CODE (*sum) != SSA_NAME)
> > + return false;
> > + gimple *sum_def = SSA_NAME_DEF_STMT (*sum);
> > + if (!sum_def || !is_gimple_assign (sum_def)
> > + || gimple_assign_rhs_code (sum_def) != PLUS_EXPR)
> > + return false;
> > + *sum_op1 = gimple_assign_rhs1 (sum_def);
> > + *sum_op2 = gimple_assign_rhs2 (sum_def);
> > + if (*sum_op1 != *addend && *sum_op2 != *addend)
> > + return false;
> > +
> > + return true;
> > +}
> > +
> > +/* Emit: carry = (bool)(addend > sum); carry_ext = (TYPE)carry.
> > + Appends two statements to NEW_STMTS. Returns carry_ext SSA name. */
> > +
> > +static tree
> > +emit_carry_compare (tree addend, tree sum, tree type,
> > + location_t loc, gimple_seq *new_stmts)
> > +{
> > + tree carry = make_ssa_name (boolean_type_node);
> > + gimple *carry_stmt = gimple_build_assign (carry, GT_EXPR, addend, sum);
> > + gimple_set_location (carry_stmt, loc);
> > + gimple_seq_add_stmt (new_stmts, carry_stmt);
> > +
> > + tree carry_ext = make_ssa_name (type);
> > + gimple *ext_stmt = gimple_build_assign (carry_ext, NOP_EXPR, carry);
> > + gimple_set_location (ext_stmt, loc);
> > + gimple_seq_add_stmt (new_stmts, ext_stmt);
> > +
> > + return carry_ext;
> > +}
> > +
> > +/* Commit the replacement sequence NEW_STMTS at the top of BB_JOIN,
> > + replace all uses of RESULT with RESULT_NEW, and fold the branch in
> > + COND so that the edge identified by KILL_TRUE_EDGE becomes dead. */
> > +
> > +static void
> > +commit_carry_replacement (basic_block bb_join, tree result, tree
> > result_new,
> > + gimple_seq new_stmts, gcond *cond,
> > + bool kill_true_edge)
> > +{
> > + gimple_stmt_iterator gsi = gsi_after_labels (bb_join);
> > + gsi_insert_seq_before (&gsi, new_stmts, GSI_SAME_STMT);
> > +
> > + replace_uses_by (result, result_new);
> > +
> > + if (kill_true_edge)
> > + gimple_cond_make_false (cond);
> > + else
> > + gimple_cond_make_true (cond);
> > + update_stmt (cond);
> > +}
> > +
> > +
> > +/* Recognize and flatten a carry-diamond pattern rooted at PHI.
> > +
> > + A carry diamond implements unsigned overflow detection with
> > + conditional carry propagation:
> > +
> > + BB_cond:
> > + sum = a + b;
> > + if (addend > sum) goto BB_then; else goto BB_join;
> > +
> > + BB_then: (single stmt, single pred/succ)
> > + x = base + C;
> > +
> > + BB_join:
> > + result = PHI <base(BB_cond), x(BB_then)>
> > +
> > + This is semantically: result = base + (overflow ? C : 0).
> > +
> > + We replace it with straight-line code:
> > +
> > + carry = (type)(addend > sum); // 0 or 1
> > + carry_val = carry << log2(C); // for power-of-2 C
> > + result = base + carry_val;
> > +
> > + 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)).
> > +
> > + Returns true if the PHI was flattened (caller must remove it). */
> > +
> > +static bool
> > +flatten_carry_diamond (gphi *phi)
> > +{
> > + if (gimple_phi_num_args (phi) != 2)
> > + return false;
> > +
> > + tree result = gimple_phi_result (phi);
> > + if (virtual_operand_p (result))
> > + return false;
> > +
> > + tree type = TREE_TYPE (result);
> > + if (!INTEGRAL_TYPE_P (type) || !TYPE_UNSIGNED (type))
> > + return false;
> > +
> > + /* Flattening replaces a conditional branch with straight-line code
> > + (comparison + shift + add). When the carry diamond is part of a
> > + long-multiply pattern and the target can fold it into a widening
> > + multiply, the carry expression is consumed entirely and never
> > + reaches RTL -- always flatten in that case. Otherwise, only
> > + flatten when branches are expensive (BRANCH_COST >= 2). */
> > + bool speed = optimize_function_for_speed_p (cfun);
> > + bool cheap_branches = BRANCH_COST (speed, false) < 2;
> > +
> > + /* Check whether the target can fold a long-multiply pattern for
> > + this type width. This must mirror the checks in create_mul_high_seq:
> > + either umul_highpart at full width, or widening/regular multiply
> > + at double width. */
> > + bool can_fold_long_mul = false;
> > + const unsigned int width = TYPE_PRECISION (type);
> > + if (width % 2 == 0 && width <= MAX_FIXED_MODE_SIZE)
> > + {
> > + scalar_int_mode fw_mode;
> > + if (int_mode_for_size (width, 0).exists (&fw_mode))
> > + {
> > + if (optab_handler (umul_highpart_optab, fw_mode)
> > + != CODE_FOR_nothing)
> > + can_fold_long_mul = true;
> > + else
> > + {
> > + scalar_int_mode dw_mode;
> > + if (int_mode_for_size (width * 2, 0).exists (&dw_mode)
> > + && (find_widening_optab_handler (umul_widen_optab,
> > + dw_mode, fw_mode)
> > + != CODE_FOR_nothing
> > + || optab_handler (smul_optab, dw_mode)
> > + != CODE_FOR_nothing))
> > + can_fold_long_mul = true;
> > + }
> > + }
> > + }
> > +
> > + /* Early-out: if branches are cheap and the target can't fold
> > + long multiplies, there's no benefit to flattening. */
> > + if (cheap_branches && !can_fold_long_mul)
> > + return false;
> > +
> > + basic_block bb_join = gimple_bb (phi);
> > + if (EDGE_COUNT (bb_join->preds) != 2)
> > + return false;
> > +
> > + /* Try both orientations of the PHI arguments: arg 0 may be the
> > + then-edge value or the fallthrough value, and vice versa. */
> > + for (int swap = 0; swap < 2; swap++)
> > + {
> > + int then_idx = swap;
> > + int cond_idx = 1 - swap;
> > +
> > + tree x_val = gimple_phi_arg_def (phi, then_idx);
> > + tree base = gimple_phi_arg_def (phi, cond_idx);
> > + edge then_edge = gimple_phi_arg_edge (phi, then_idx);
> > + edge cond_edge = gimple_phi_arg_edge (phi, cond_idx);
> > +
> > + basic_block bb_then = then_edge->src;
> > + basic_block bb_cond = cond_edge->src;
> > +
> > + /* BB_then: single predecessor (BB_cond), single successor
> > + (BB_join). */
> > + if (!single_pred_p (bb_then) || !single_succ_p (bb_then))
> > + continue;
> > + if (single_pred (bb_then) != bb_cond)
> > + continue;
> > +
> > + /* BB_then must have exactly one non-debug statement of the form
> > + x = base + C, where C is an integer constant. */
> > + gimple *then_stmt = last_and_only_stmt (bb_then);
> > + if (!then_stmt
> > + || !is_gimple_assign (then_stmt)
> > + || gimple_assign_rhs_code (then_stmt) != PLUS_EXPR)
> > + continue;
> > +
> > + tree then_rhs1 = gimple_assign_rhs1 (then_stmt);
> > + tree then_rhs2 = gimple_assign_rhs2 (then_stmt);
> > + tree carry_const;
> > + if (then_rhs1 == base && TREE_CODE (then_rhs2) == INTEGER_CST)
> > + carry_const = then_rhs2;
> > + else if (then_rhs2 == base && TREE_CODE (then_rhs1) == INTEGER_CST)
> > + carry_const = then_rhs1;
> > + else
> > + continue;
> > +
> > + if (x_val != gimple_assign_lhs (then_stmt))
> > + continue;
> > +
> > + /* BB_cond must end with a conditional testing unsigned overflow
> > + of an addition. */
> > + gcond *cond = safe_dyn_cast<gcond *> (last_nondebug_stmt (bb_cond));
> > + if (!cond)
> > + continue;
> > +
> > + /* Determine whether bb_cond branches to bb_then on the TRUE edge
> > + or the FALSE edge. Note: then_edge is bb_then->bb_join (always
> > + FALLTHRU), so we must look at the edge from bb_cond to bb_then. */
> > + edge cond_to_then = find_edge (bb_cond, bb_then);
> > + if (!cond_to_then)
> > + continue;
> > + bool then_is_true = (cond_to_then->flags & EDGE_TRUE_VALUE) != 0;
> > +
> > + /* Normalize to: addend > sum (the overflow check).
> > + The then-edge must correspond to the "overflow" case. */
> > + tree addend, sum, sum_op1, sum_op2;
> > + if (!recognize_overflow_cond (cond, then_is_true,
> > + &addend, &sum, &sum_op1, &sum_op2))
> > + continue;
> > +
> > + /* On targets with cheap branches, only flatten if this carry
> > + diamond is part of a long-multiply pattern. can_fold_long_mul
> > + is guaranteed true here by the early-out above. */
> > + if (cheap_branches
> > + && !is_long_mul_carry (addend, sum_op1, sum_op2))
> > + continue;
> > +
> > + /* Only handle C = power-of-2 (including 1); other constants have
> > + no downstream match.pd pattern to fold into. */
> > + int shift_amt_val = wi::exact_log2 (wi::to_wide (carry_const));
> > + if (shift_amt_val < 0)
> > + continue;
> > +
> > + /* All checks passed -- build the replacement. */
> > + if (dump_file && (dump_flags & TDF_DETAILS))
> > + fprintf (dump_file,
> > + "Flattening carry diamond: PHI in BB %d "
> > + "(cond BB %d, then BB %d)\n",
> > + bb_join->index, bb_cond->index, bb_then->index);
> > +
> > + location_t loc = gimple_location (cond);
> > + gimple_seq new_stmts = NULL;
> > +
> > + tree carry_ext = emit_carry_compare (addend, sum, type, loc,
> > + &new_stmts);
> > +
> > + tree carry_val;
> > + if (shift_amt_val == 0)
> > + {
> > + /* C = 1: no shift needed. */
> > + carry_val = carry_ext;
> > + }
> > + else
> > + {
> > + /* C is a power of 2 > 1: use LSHIFT_EXPR for match.pd compat. */
> > + tree shift_amt = build_int_cst (integer_type_node, shift_amt_val);
> > + tree carry_shifted = make_ssa_name (type);
> > + gimple *shift_stmt
> > + = gimple_build_assign (carry_shifted, LSHIFT_EXPR,
> > + carry_ext, shift_amt);
> > + gimple_set_location (shift_stmt, loc);
> > + gimple_seq_add_stmt (&new_stmts, shift_stmt);
> > + carry_val = carry_shifted;
> > + }
> > +
> > + /* result_new = base + carry_val */
> > + tree result_new = make_ssa_name (type);
> > + gimple *add_stmt
> > + = gimple_build_assign (result_new, PLUS_EXPR, base, carry_val);
> > + gimple_set_location (add_stmt, loc);
> > + gimple_seq_add_stmt (&new_stmts, add_stmt);
> > +
> > + commit_carry_replacement (bb_join, result, result_new, new_stmts,
> > + cond, then_is_true);
> > + return true;
> > + }
> > +
> > + /* Degenerate carry diamond: PHI<C, 0> or PHI<0, C> where C is a power
> > + of 2. This occurs when (type)(a < b) << N gets lowered into a
> > + conditional branch and CCP folds the constant assignments, leaving
> > + the PHI with two integer-constant arguments. Flatten to:
> > + carry = (type)(addend > sum); result = carry << log2(C). */
> > + for (int swap = 0; swap < 2; swap++)
> > + {
> > + int carry_idx = swap;
> > + int zero_idx = 1 - swap;
> > +
> > + tree carry_val = gimple_phi_arg_def (phi, carry_idx);
> > + tree zero_val = gimple_phi_arg_def (phi, zero_idx);
> > +
> > + if (!integer_zerop (zero_val) || TREE_CODE (carry_val) != INTEGER_CST
> > + || integer_zerop (carry_val))
> > + continue;
> > +
> > + int shift_amt_val = wi::exact_log2 (wi::to_wide (carry_val));
> > + if (shift_amt_val < 0)
> > + continue;
> > +
> > + edge carry_edge = gimple_phi_arg_edge (phi, carry_idx);
> > + edge zero_edge = gimple_phi_arg_edge (phi, zero_idx);
> > +
> > + basic_block bb_empty = zero_edge->src;
> > + basic_block bb_cond = carry_edge->src;
> > +
> > + /* The zero-value block must be empty, with single predecessor
> > + (bb_cond) and single successor (bb_join). */
> > + if (!single_pred_p (bb_empty) || !single_succ_p (bb_empty))
> > + continue;
> > + if (single_pred (bb_empty) != bb_cond)
> > + continue;
> > +
> > + if (last_nondebug_stmt (bb_empty))
> > + continue;
> > +
> > + gcond *cond = safe_dyn_cast<gcond *> (last_nondebug_stmt (bb_cond));
> > + if (!cond)
> > + continue;
> > +
> > + /* The overflow (carry) path goes directly from bb_cond to bb_join.
> > + The non-overflow path goes through bb_empty. Determine which
> > + edge of the conditional leads to bb_empty. */
> > + edge cond_to_empty = find_edge (bb_cond, bb_empty);
> > + if (!cond_to_empty)
> > + continue;
> > + bool overflow_on_true
> > + = (cond_to_empty->flags & EDGE_TRUE_VALUE) == 0;
> > +
> > + tree addend, sum, sum_op1, sum_op2;
> > + if (!recognize_overflow_cond (cond, overflow_on_true,
> > + &addend, &sum, &sum_op1, &sum_op2))
> > + continue;
> > +
> > + /* On targets with cheap branches, only flatten if this carry
> > + diamond is part of a long-multiply pattern. */
> > + if (cheap_branches
> > + && !is_long_mul_carry (addend, sum_op1, sum_op2))
> > + continue;
> > +
> > + /* All checks passed -- build the replacement. */
> > + if (dump_file && (dump_flags & TDF_DETAILS))
> > + fprintf (dump_file,
> > + "Flattening carry diamond: PHI in BB %d "
> > + "(cond BB %d, empty BB %d, degenerate)\n",
> > + bb_join->index, bb_cond->index, bb_empty->index);
> > +
> > + location_t loc = gimple_location (cond);
> > + gimple_seq new_stmts = NULL;
> > +
> > + tree carry_ext = emit_carry_compare (addend, sum, type, loc,
> > + &new_stmts);
> > +
> > + tree result_new;
> > + if (shift_amt_val == 0)
> > + {
> > + /* C = 1: no shift needed. */
> > + result_new = carry_ext;
> > + }
> > + else
> > + {
> > + /* C is a power of 2 > 1: result = carry_ext << log2(C). */
> > + tree shift_amt = build_int_cst (integer_type_node, shift_amt_val);
> > + result_new = make_ssa_name (type);
> > + gimple *shift_stmt
> > + = gimple_build_assign (result_new, LSHIFT_EXPR,
> > + carry_ext, shift_amt);
> > + gimple_set_location (shift_stmt, loc);
> > + gimple_seq_add_stmt (&new_stmts, shift_stmt);
> > + }
> > +
> > + commit_carry_replacement (bb_join, result, result_new, new_stmts,
> > + cond, !overflow_on_true);
> > + return true;
> > + }
> > +
> > + return false;
> > +}
> > +
> >
> > /* Determine whether applying the 2 permutations (mask1 then mask2)
> > gives back one of the input. */
> > @@ -5386,6 +5829,23 @@ pass_forwprop::execute (function *fun)
> > }
> > }
> >
> > + /* Flatten carry diamonds: convert conditional carry propagation
> > + (if (addend > sum) base += C) to straight-line code
> > + (base += (type)(addend > sum) << log2(C)). This exposes the
> > + carry as a comparison expression for downstream long-multiply
> > + pattern matching. */
> > + for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si); )
> > + {
> > + gphi *phi = si.phi ();
> > + if (flatten_carry_diamond (phi))
> > + {
> > + remove_phi_node (&si, true);
> > + cfg_changed = true;
> > + continue;
> > + }
> > + gsi_next (&si);
> > + }
> > +
> > /* Apply forward propagation to all stmts in the basic-block.
> > Note we update GSI within the loop as necessary. */
> > unsigned int uid = 1;
> > --
> > 2.52.0
> >
