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)
lmpx.com only provides a reader for public news (NNTP) servers. It is not
affiliated with the servers or forums shown here and is not responsible for
the content of articles, which is written by their respective authors.