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);
+}
+
/* 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
