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)).
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
