From: Kyrylo Tkachov <[email protected]>
Reassociation can turn a chain of four comparisons into a balanced tree:
return ((a < b) & (c < d)) & ((e < f) & (g < h));
The conditional-compare expander rejects this when both operands are
subtrees. AArch64 then emits two separate chains:
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
A subtree can be appended when all its operators match the parent. Recognise
these uniform subtrees, expand the other operand first, then append each
comparison. AArch64 then emits one chain:
cmp w0, w1
ccmp w2, w3, 0, lt
ccmp w4, w5, 0, lt
ccmp w6, w7, 0, lt
cset w0, lt
Expand each recursive operand only once. Cache uniform-tree results so the
analysis remains linear for nested mixed trees. Mixed trees that cannot use
one condition-code value remain rejected.
Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill
gcc/
* ccmp.cc (ccmp_uniform_cache): New typedef.
(ccmp_uniform_chain_p): New function.
(ccmp_candidate_p): Accept a node with a uniform operand.
(expand_ccmp_chain): New function.
(expand_ccmp_expr_1): Append a uniform operand.
(expand_ccmp_expr): Create the uniform-tree cache.
gcc/testsuite/
* gcc.c-torture/execute/ccmp-tree-1.c: New test.
* gcc.target/aarch64/ccmp_6.c: New test.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
gcc/ccmp.cc | 94 ++++++++++++++++---
.../gcc.c-torture/execute/ccmp-tree-1.c | 90 ++++++++++++++++++
gcc/testsuite/gcc.target/aarch64/ccmp_6.c | 89 ++++++++++++++++++
3 files changed, 260 insertions(+), 13 deletions(-)
create mode 100644 gcc/testsuite/gcc.c-torture/execute/ccmp-tree-1.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/ccmp_6.c
diff --git a/gcc/ccmp.cc b/gcc/ccmp.cc
index f63e44dcc84..1c540f641b2 100644
--- a/gcc/ccmp.cc
+++ b/gcc/ccmp.cc
@@ -37,6 +37,7 @@ along with GCC; see the file COPYING3. If not see
#include "cfgexpand.h"
#include "ccmp.h"
#include "predict.h"
+#include "hash-map.h"
/* Check whether T is a simple boolean variable or a SSA name
set by a comparison operator in the same basic block. */
@@ -90,10 +91,40 @@ ccmp_tree_comparison_p (tree t, basic_block bb)
If all checks OK in expand_ccmp_expr, it emits insns in prep_seq, then
insns in gen_seq. */
+typedef hash_map<tree, bool> ccmp_uniform_cache;
+
+/* Return true if T is a CODE tree in BB whose leaves are comparisons.
+ CACHE records results for logical SSA definitions. */
+
+static bool
+ccmp_uniform_chain_p (tree t, tree_code code, basic_block bb,
+ ccmp_uniform_cache &cache)
+{
+ if (ccmp_tree_comparison_p (t, bb))
+ return true;
+
+ gimple *g = get_gimple_for_ssa_name (t);
+ if (!g || !is_gimple_assign (g) || gimple_assign_rhs_code (g) != code)
+ return false;
+
+ if (bool *value = cache.get (t))
+ return *value;
+
+ tree op0 = gimple_assign_rhs1 (g);
+ tree op1 = gimple_assign_rhs2 (g);
+ bool value = (TREE_CODE (op0) == SSA_NAME
+ && TREE_CODE (op1) == SSA_NAME
+ && ccmp_uniform_chain_p (op0, code, bb, cache)
+ && ccmp_uniform_chain_p (op1, code, bb, cache));
+ cache.put (t, value);
+ return value;
+}
+
/* Check whether G is a potential conditional compare candidate; OUTER is true
if
G is the outer most AND/IOR. */
static bool
-ccmp_candidate_p (gimple *g, bool outer = false)
+ccmp_candidate_p (gimple *g, ccmp_uniform_cache &cache,
+ bool outer = false)
{
tree lhs, op0, op1;
gimple *gs0, *gs1;
@@ -121,13 +152,16 @@ ccmp_candidate_p (gimple *g, bool outer = false)
if (ccmp_tree_comparison_p (op0, bb) && ccmp_tree_comparison_p (op1, bb))
return true;
- if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1))
+ if (ccmp_tree_comparison_p (op0, bb) && ccmp_candidate_p (gs1, cache))
return true;
- if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0))
+ if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0, cache))
return true;
- /* We skip ccmp_candidate_p (gs1) && ccmp_candidate_p (gs0) since
- there is no way to set and maintain the CC flag on both sides of
- the logical operator at the same time. */
+ /* A uniform chain can be appended to the other operand one comparison at
+ a time. */
+ if (ccmp_uniform_chain_p (op1, tcode, bb, cache))
+ return ccmp_candidate_p (gs0, cache);
+ if (ccmp_uniform_chain_p (op0, tcode, bb, cache))
+ return ccmp_candidate_p (gs1, cache);
return false;
}
@@ -179,6 +213,26 @@ expand_ccmp_next (tree op, tree_code code, rtx prev,
rhs1, rhs2, get_rtx_code (code, 0));
}
+/* Append the leaves of uniform CODE tree OP to conditional comparison PREV.
+ Return the extended comparison, or NULL_RTX if expansion fails. */
+
+static rtx
+expand_ccmp_chain (tree op, tree_code code, rtx prev,
+ rtx_insn **prep_seq, rtx_insn **gen_seq)
+{
+ gimple *g = get_gimple_for_ssa_name (op);
+ if (!g || gimple_assign_rhs_code (g) != code)
+ return expand_ccmp_next (op, code, prev, prep_seq, gen_seq);
+
+ prev = expand_ccmp_chain (gimple_assign_rhs1 (g), code, prev,
+ prep_seq, gen_seq);
+ if (!prev)
+ return NULL_RTX;
+
+ return expand_ccmp_chain (gimple_assign_rhs2 (g), code, prev,
+ prep_seq, gen_seq);
+}
+
/* Expand conditional compare gimple G. A typical CCMP sequence is like:
CC0 = CMP (a, b);
@@ -191,7 +245,8 @@ expand_ccmp_next (tree op, tree_code code, rtx prev,
PREP_SEQ returns all insns to prepare operand.
GEN_SEQ returns all compare insns. */
static rtx
-expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq)
+expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq, rtx_insn **gen_seq,
+ ccmp_uniform_cache &cache)
{
tree_code code = gimple_assign_rhs_code (g);
basic_block bb = gimple_bb (g);
@@ -270,22 +325,34 @@ expand_ccmp_expr_1 (gimple *g, rtx_insn **prep_seq,
rtx_insn **gen_seq)
}
else
{
- tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq);
+ tmp = expand_ccmp_expr_1 (gs1, prep_seq, gen_seq, cache);
if (!tmp)
return NULL_RTX;
return expand_ccmp_next (op0, code, tmp, prep_seq, gen_seq);
}
}
- else
+ else if (ccmp_tree_comparison_p (op1, bb))
{
gcc_assert (gimple_assign_rhs_code (gs0) == BIT_AND_EXPR
|| gimple_assign_rhs_code (gs0) == BIT_IOR_EXPR);
- gcc_assert (ccmp_tree_comparison_p (op1, bb));
- tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq);
+ tmp = expand_ccmp_expr_1 (gs0, prep_seq, gen_seq, cache);
if (!tmp)
return NULL_RTX;
return expand_ccmp_next (op1, code, tmp, prep_seq, gen_seq);
}
+ else
+ {
+ /* Start with one operand and append the uniform operand. */
+ tree first = op0, rest = op1;
+ if (!ccmp_uniform_chain_p (op1, code, bb, cache))
+ std::swap (first, rest);
+
+ tmp = expand_ccmp_expr_1 (get_gimple_for_ssa_name (first),
+ prep_seq, gen_seq, cache);
+ if (!tmp)
+ return NULL_RTX;
+ return expand_ccmp_chain (rest, code, tmp, prep_seq, gen_seq);
+ }
}
/* Main entry to expand conditional compare statement G.
@@ -296,14 +363,15 @@ expand_ccmp_expr (gimple *g, machine_mode mode)
{
rtx_insn *last;
rtx tmp;
+ ccmp_uniform_cache cache;
- if (!ccmp_candidate_p (g, true))
+ if (!ccmp_candidate_p (g, cache, true))
return NULL_RTX;
last = get_last_insn ();
rtx_insn *prep_seq = NULL, *gen_seq = NULL;
- tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq);
+ tmp = expand_ccmp_expr_1 (g, &prep_seq, &gen_seq, cache);
if (tmp)
{
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_6.c
b/gcc/testsuite/gcc.target/aarch64/ccmp_6.c
new file mode 100644
index 00000000000..aa2710775e5
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ccmp_6.c
@@ -0,0 +1,89 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { check-function-bodies "**" "" } } */
+
+/* Reassociation rebalances a chain of four comparisons into a tree, so the
+ conditional compare expander has to linearise it again. */
+
+/*
+** and_tree:
+** cmp w0, w1
+** ccmp w2, w3, 0, lt
+** ccmp w4, w5, 0, lt
+** ccmp w6, w7, 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 w0, w1
+** ccmp w2, w3, 1, ge
+** ccmp w4, w5, 1, ge
+** ccmp w6, w7, 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));
+}
+
+/* An AND chain that has to come first and a uniform OR chain. */
+
+/*
+** ior_of_and:
+** cmp w4, w5
+** ccmp w6, w7, 0, lt
+** ccmp w2, w3, 1, ge
+** ccmp w0, w1, 1, ge
+** cset w0, lt
+** ret
+*/
+int
+ior_of_and (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));
+}
+
+/* An OR chain that has to come first and a uniform AND chain. */
+
+/*
+** and_of_ior_chain:
+** cmp w4, w5
+** ccmp w6, w7, 1, ge
+** ccmp w2, w3, 0, lt
+** ccmp w0, w1, 0, lt
+** cset w0, lt
+** ret
+*/
+int
+and_of_ior_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));
+}
+
+/* The chain is linear, so neither of these can be expressed as one sequence
+ of conditional compares. Both operands would have to keep a value in the
+ flags at the same time. */
+
+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));
+}
+
+int
+ior_of_and_2 (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 } }
*/
+/* { dg-final { scan-assembler-times {\torr\tw[0-9]+, w[0-9]+, w[0-9]+} 1 } }
*/
--
2.50.1 (Apple Git-155)
