From: Kyrylo Tkachov <[email protected]>
Reassociation rebalances a chain of four or more comparisons into a tree,
because the reassociation width of the boolean mode is the width of an
integer bitwise operation. A conditional compare sequence cannot use that
parallelism: every conditional comparison tests the flags that the previous
comparison set. Splitting the chain therefore costs a sequence. For
int
f (int a, int b, int c, int d, int e, int f, int g, int h)
{
return (a < b) & (c < d) & (e < f) & (g < h);
}
reassociation produced
_3 = _1 & _2;
_16 = _4 & _5;
_17 = _3 & _16;
and AArch64 emitted two sequences and a bitwise operation:
cmp w0, w1
ccmp w2, w3, 0, lt
cset w1, lt
cmp w4, w5
ccmp w6, w7, 0, lt
cset w0, lt
and w0, w1, w0
Keep the chain linear when it expands to one conditional compare sequence.
That needs every operand to be a scalar comparison in the same block, at
least one of them foldable into the flags, and at most one that can trap,
since only the first comparison of a sequence is unconditional. One operand
may be an AND/IOR of its own, which the expander emits first. AArch64 then
emits one sequence:
cmp w4, w5
ccmp w6, w7, 0, lt
ccmp w2, w3, 0, lt
ccmp w0, w1, 0, lt
cset w0, lt
The chain that a balanced tree of the same comparisons produces is now the
same, so the source shape no longer decides the result.
Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill
gcc/
* tree-ssa-reassoc.cc (ccmp_comparison_p): New function.
(ccmp_sequence_p): Likewise.
(ccmp_chain_p): Likewise.
(reassociate_bb): Do not rewrite a conditional compare chain to
parallel form.
gcc/testsuite/
* gcc.c-torture/execute/ccmp-tree-1.c: New test.
* gcc.target/aarch64/ccmp_6.c: New test.
* gcc.target/aarch64/ccmp_10.c: Likewise.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
.../gcc.c-torture/execute/ccmp-tree-1.c | 90 +++++++++++++++++++
gcc/testsuite/gcc.target/aarch64/ccmp_10.c | 24 +++++
gcc/testsuite/gcc.target/aarch64/ccmp_6.c | 63 +++++++++++++
gcc/tree-ssa-reassoc.cc | 86 ++++++++++++++++++
4 files changed, 263 insertions(+)
create mode 100644 gcc/testsuite/gcc.c-torture/execute/ccmp-tree-1.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/ccmp_10.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/ccmp_6.c
diff --git a/gcc/testsuite/gcc.c-torture/execute/ccmp-tree-1.c
b/gcc/testsuite/gcc.c-torture/execute/ccmp-tree-1.c
new file mode 100644
index 00000000000..9d7f5241f19
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/ccmp-tree-1.c
@@ -0,0 +1,90 @@
+/* Execution test for conditional-compare chains built from AND/IOR trees of
+ comparisons. Each function is compared against a reference computed with
+ volatile operands so that it cannot be folded into the same code. */
+
+extern void abort (void);
+
+#define OPS int a, int b, int c, int d, int e, int f, int g, int h
+#define ARGS a, b, c, d, e, f, g, h
+
+/* Balanced AND tree. */
+static int __attribute__((noipa)) t1 (OPS)
+{ return ((a < b) & (c < d)) & ((e < f) & (g < h)); }
+
+/* Balanced OR tree. */
+static int __attribute__((noipa)) t2 (OPS)
+{ return ((a < b) | (c < d)) | ((e < f) | (g < h)); }
+
+/* AND of an OR chain and an AND chain. */
+static int __attribute__((noipa)) t3 (OPS)
+{ return ((a < b) | (c < d)) & ((e < f) & (g < h)); }
+
+/* OR of an AND chain and an OR chain. */
+static int __attribute__((noipa)) t4 (OPS)
+{ return ((a < b) & (c < d)) | ((e < f) | (g < h)); }
+
+/* Deeper: eight leaves. */
+static int __attribute__((noipa)) t5 (OPS)
+{
+ return (((a < b) & (c < d)) & ((e < f) & (g < h)))
+ & (((a < c) & (b < d)) & ((e < g) & (f < h)));
+}
+
+/* Mixed signed and unsigned leaves. */
+static int __attribute__((noipa)) t6 (OPS)
+{
+ return (((unsigned) a < (unsigned) b) & (c < d))
+ & ((e < f) & ((unsigned) g < (unsigned) h));
+}
+
+/* Immediates, some inside and some outside the CCMP 5-bit range. */
+static int __attribute__((noipa)) t7 (OPS)
+{ return ((a == 3) & (b == 31)) & ((c == 32) & (d == -4)); }
+
+/* Reference versions. V forces separate evaluation of every leaf. */
+#define V(x) ({ volatile int v_ = (x); v_; })
+
+static int r1 (OPS)
+{ return (V(a < b) & V(c < d)) & (V(e < f) & V(g < h)); }
+static int r2 (OPS)
+{ return (V(a < b) | V(c < d)) | (V(e < f) | V(g < h)); }
+static int r3 (OPS)
+{ return (V(a < b) | V(c < d)) & (V(e < f) & V(g < h)); }
+static int r4 (OPS)
+{ return (V(a < b) & V(c < d)) | (V(e < f) | V(g < h)); }
+static int r5 (OPS)
+{
+ return ((V(a < b) & V(c < d)) & (V(e < f) & V(g < h)))
+ & ((V(a < c) & V(b < d)) & (V(e < g) & V(f < h)));
+}
+static int r6 (OPS)
+{
+ return (V((unsigned) a < (unsigned) b) & V(c < d))
+ & (V(e < f) & V((unsigned) g < (unsigned) h));
+}
+static int r7 (OPS)
+{ return (V(a == 3) & V(b == 31)) & (V(c == 32) & V(d == -4)); }
+static const int vals[] = { -4, 0, 3, 31, 32, 33 };
+#define NV ((int) (sizeof (vals) / sizeof (vals[0])))
+
+int
+main (void)
+{
+ for (int i0 = 0; i0 < NV; i0++)
+ for (int i1 = 0; i1 < NV; i1++)
+ for (int i2 = 0; i2 < NV; i2++)
+ for (int i3 = 0; i3 < NV; i3++)
+ {
+ int a = vals[i0], b = vals[i1], c = vals[i2], d = vals[i3];
+ int e = vals[i3], f = vals[i0], g = vals[i2], h = vals[i1];
+
+ if (t1 (ARGS) != r1 (ARGS)) abort ();
+ if (t2 (ARGS) != r2 (ARGS)) abort ();
+ if (t3 (ARGS) != r3 (ARGS)) abort ();
+ if (t4 (ARGS) != r4 (ARGS)) abort ();
+ if (t5 (ARGS) != r5 (ARGS)) abort ();
+ if (t6 (ARGS) != r6 (ARGS)) abort ();
+ if (t7 (ARGS) != r7 (ARGS)) abort ();
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_10.c
b/gcc/testsuite/gcc.target/aarch64/ccmp_10.c
new file mode 100644
index 00000000000..a7fd4f2400e
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ccmp_10.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 --param tree-reassoc-width=2
-fdump-tree-reassoc2-details" } */
+
+/* A vector comparison does not set the condition flags, so a chain of them
+ is not a conditional compare sequence and keeps the parallel form. */
+
+typedef int v4si __attribute__ ((vector_size (16)));
+
+v4si
+vector_chain (v4si a, v4si b, v4si c, v4si d, v4si e, v4si f, v4si g, v4si h)
+{
+ return (a < b) & (c < d) & (e < f) & (g < h);
+}
+
+/* A chain of scalar comparisons becomes one sequence instead. */
+
+int
+scalar_chain (int a, int b, int c, int d, int e, int f, int g, int h)
+{
+ return (a < b) & (c < d) & (e < f) & (g < h);
+}
+
+/* { dg-final { scan-tree-dump-times "was chosen for reassociation" 1
"reassoc2" } } */
+/* { dg-final { scan-assembler-times {\tccmp\t} 3 } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_6.c
b/gcc/testsuite/gcc.target/aarch64/ccmp_6.c
new file mode 100644
index 00000000000..9feec51d8de
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ccmp_6.c
@@ -0,0 +1,63 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { check-function-bodies "**" "" } } */
+
+/* A chain of four comparisons is wide enough for reassociation to build a
+ balanced tree. Both source shapes have to reach expansion as one chain,
+ which a conditional compare sequence can hold in the flags. */
+
+/*
+** and_chain:
+** cmp w4, w5
+** ccmp w6, w7, 0, lt
+** ccmp w2, w3, 0, lt
+** ccmp w0, w1, 0, lt
+** cset w0, lt
+** ret
+*/
+int
+and_chain (int a, int b, int c, int d, int e, int f, int g, int h)
+{
+ return (a < b) & (c < d) & (e < f) & (g < h);
+}
+
+/*
+** and_tree:
+** cmp w4, w5
+** ccmp w6, w7, 0, lt
+** ccmp w2, w3, 0, lt
+** ccmp w0, w1, 0, lt
+** cset w0, lt
+** ret
+*/
+int
+and_tree (int a, int b, int c, int d, int e, int f, int g, int h)
+{
+ return ((a < b) & (c < d)) & ((e < f) & (g < h));
+}
+
+/*
+** ior_tree:
+** cmp w4, w5
+** ccmp w6, w7, 1, ge
+** ccmp w2, w3, 1, ge
+** ccmp w0, w1, 1, ge
+** cset w0, lt
+** ret
+*/
+int
+ior_tree (int a, int b, int c, int d, int e, int f, int g, int h)
+{
+ return ((a < b) | (c < d)) | ((e < f) | (g < h));
+}
+
+/* Both operands hold a value in the flags at the same time, so this one
+ needs two sequences and a bitwise operation. */
+
+int
+and_of_ior (int a, int b, int c, int d, int e, int f, int g, int h)
+{
+ return ((a < b) | (c < d)) & ((e < f) | (g < h));
+}
+
+/* { dg-final { scan-assembler-times {\tand\tw[0-9]+, w[0-9]+, w[0-9]+} 1 } }
*/
diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc
index dec64883891..d424dff7406 100644
--- a/gcc/tree-ssa-reassoc.cc
+++ b/gcc/tree-ssa-reassoc.cc
@@ -5165,6 +5165,84 @@ swap_ops_for_binary_stmt (const vec<operand_entry *>
&ops,
std::swap (*oe1, *oe2);
}
+/* Return true if OP is set by a comparison in BB, which a conditional
+ compare can compute into the condition flags. */
+
+static bool
+ccmp_comparison_p (tree op, basic_block bb)
+{
+ if (TREE_CODE (op) != SSA_NAME)
+ return false;
+
+ gimple *def = SSA_NAME_DEF_STMT (op);
+ if (!is_gimple_assign (def)
+ || gimple_bb (def) != bb
+ || TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
+ return false;
+
+ /* A conditional compare sets the flags from one comparison of two
+ registers. */
+ machine_mode mode = TYPE_MODE (TREE_TYPE (gimple_assign_rhs1 (def)));
+ return ((SCALAR_INT_MODE_P (mode) || SCALAR_FLOAT_MODE_P (mode))
+ && known_le (GET_MODE_SIZE (mode), UNITS_PER_WORD));
+}
+
+/* Return true if OP is an AND/IOR in BB, which the expander can emit as a
+ conditional compare sequence of its own. */
+
+static bool
+ccmp_sequence_p (tree op, basic_block bb)
+{
+ if (TREE_CODE (op) != SSA_NAME || !has_single_use (op))
+ return false;
+
+ gimple *def = SSA_NAME_DEF_STMT (op);
+ if (!is_gimple_assign (def) || gimple_bb (def) != bb)
+ return false;
+
+ tree_code code = gimple_assign_rhs_code (def);
+ return code == BIT_AND_EXPR || code == BIT_IOR_EXPR;
+}
+
+/* Return true if the CODE chain in BB with operands OPS expands to one
+ conditional compare sequence. Such a sequence holds a single value in
+ the condition flags, so every operand has to be a comparison that the
+ next conditional compare tests, and at least one of them has to be a
+ comparison that the expander can fold into the flags. Only the first
+ comparison of the sequence is unconditional, so at most one operand may
+ trap. One operand may be a sequence of its own, which the expander then
+ has to emit first. */
+
+static bool
+ccmp_chain_p (const vec<operand_entry *> &ops, tree_code code, basic_block bb)
+{
+ if (!targetm.have_ccmp ()
+ || (code != BIT_AND_EXPR && code != BIT_IOR_EXPR))
+ return false;
+
+ bool seen_sequence = false;
+ bool seen_foldable = false;
+ unsigned trapping = 0;
+
+ for (const operand_entry *oe : ops)
+ {
+ if (!ccmp_comparison_p (oe->op, bb))
+ {
+ if (seen_sequence || !ccmp_sequence_p (oe->op, bb))
+ return false;
+ seen_sequence = true;
+ continue;
+ }
+
+ if (gimple_could_trap_p (SSA_NAME_DEF_STMT (oe->op)) && ++trapping > 1)
+ return false;
+
+ seen_foldable |= has_single_use (oe->op);
+ }
+
+ return seen_foldable;
+}
+
/* If definition of RHS1 or RHS2 dominates STMT, return the later of those
two definitions, otherwise return STMT. Sets INSERT_BEFORE to indicate
whether RHS1 op RHS2 can be inserted before or needs to be inserted
@@ -7153,11 +7231,19 @@ reassociate_bb (basic_block bb)
mult_num = rank_ops_for_fma (&ops);
}
+ /* A chain that expands to a conditional compare sequence
+ has to stay linear. Every conditional compare tests the
+ flags that the previous comparison set, so the sequence
+ cannot be split into independent parts. */
+ bool ccmp_chain = (ops_num > 2
+ && ccmp_chain_p (ops, rhs_code, bb));
+
/* Only rewrite the expression tree to parallel in the
last reassoc pass to avoid useless work back-and-forth
with initial linearization. */
bool has_fma = mult_num >= 2 && mult_num != ops_num;
if (!reassoc_insert_powi_p
+ && !ccmp_chain
&& ops.length () > 3
&& (width = get_reassociation_width (&ops, mult_num, lhs,
rhs_code, mode))
--
2.50.1 (Apple Git-155)
