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