From: Kyrylo Tkachov <[email protected]>
Reassociation rebalances a chain of four or more comparisons into a tree.
The reassociation width of the boolean mode is the width of an integer
bitwise operation. A conditional-compare sequence cannot use that
parallelism because every conditional comparison tests the flags that the
previous comparison set. 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;
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 only when every operand is a scalar comparison in the
same block and at least one comparison can be folded into the flags. Put a
forwarded trapping comparison in the innermost pair. The expander tries
both orders of that pair and can make this comparison unconditional.
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
Tests cover linear and balanced source forms, unsupported operands,
trapping comparisons in every source position, and comparison results with
other uses.
Changes since v1:
- Require the complete operand list to form one CCMP sequence.
- Put a trapping comparison first and reject conflicting heads.
- Add tests for trapping positions and comparison results with other uses.
gcc/
* tree-ssa-reassoc.cc (ccmp_comparison_p): New function.
(prepare_ccmp_chain): Likewise.
(reassociate_bb): Keep a complete conditional-compare chain linear
and put its required first operand in the innermost pair.
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.
* gcc.target/aarch64/ccmp_12.c: Likewise.
* gcc.target/aarch64/ccmp_14.c: Likewise.
* gcc.target/aarch64/fccmp_6.c: Likewise.
* gcc.target/aarch64/fccmp_8.c: Likewise.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
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..b67b2410484
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ccmp_10.c
@@ -0,0 +1,33 @@
+/* { 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);
+}
+
+/* A nested integer IOR is not a conditional compare sequence. */
+
+int
+integer_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-tree-dump-times "was chosen for reassociation" 1
"reassoc2" } } */
+/* { dg-final { scan-assembler-times {\tccmp\t} 5 } } */
+/* { dg-final { scan-assembler-times {\tand\tw[0-9]+, w[0-9]+, w[0-9]+} 1 } }
*/
diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_12.c
b/gcc/testsuite/gcc.target/aarch64/ccmp_12.c
new file mode 100644
index 00000000000..0d9fcb00c89
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ccmp_12.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 --param tree-reassoc-width=2
-fdump-tree-reassoc2-details" } */
+
+/* Comparison leaves can have uses outside the chain. A chain stays linear
+ when another comparison can be folded into the flags. */
+
+volatile int result;
+
+int
+one_multi_use (int a, int b, int c, int d, int e, int f, int g, int h)
+{
+ int x = a < b;
+ result = x;
+ return x & (c < d) & (e < f) & (g < h);
+}
+/* { dg-final { scan-assembler-times {\tccmp\t} 3 } } */
+/* { dg-final { scan-tree-dump-not "was chosen for reassociation" "reassoc2" }
} */
diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_14.c
b/gcc/testsuite/gcc.target/aarch64/ccmp_14.c
new file mode 100644
index 00000000000..0ff0cd5ae7d
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ccmp_14.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 --param tree-reassoc-width=2
-fdump-tree-reassoc2-details" } */
+
+/* If no comparison can be folded, the chain keeps the parallel form. */
+
+volatile int results[4];
+
+int
+all_multi_use (int a, int b, int c, int d, int e, int f, int g, int h)
+{
+ int x0 = a < b;
+ int x1 = c < d;
+ int x2 = e < f;
+ int x3 = g < h;
+ results[0] = x0;
+ results[1] = x1;
+ results[2] = x2;
+ results[3] = x3;
+ return x0 & x1 & x2 & x3;
+}
+
+/* { dg-final { scan-tree-dump-times "was chosen for reassociation" 1
"reassoc2" } } */
+/* { dg-final { scan-assembler-not {\tccmp\t} } } */
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/testsuite/gcc.target/aarch64/fccmp_6.c
b/gcc/testsuite/gcc.target/aarch64/fccmp_6.c
new file mode 100644
index 00000000000..5ded1304f03
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/fccmp_6.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+/* A trapping comparison must start the sequence. Test every source
+ position in a chain that is long enough for parallel reassociation. */
+
+#define DEF(N, EXPR) \
+ int f##N (double a, double b, int c, int d, int e, int f, int g, int h) \
+ { return (EXPR); }
+
+DEF (0, (a < b) & (c < d) & (e < f) & (g < h))
+DEF (1, (c < d) & (a < b) & (e < f) & (g < h))
+DEF (2, (c < d) & (e < f) & (a < b) & (g < h))
+DEF (3, (c < d) & (e < f) & (g < h) & (a < b))
+
+/* { dg-final { scan-assembler-times {\tfcmpe\t} 4 } } */
+/* { dg-final { scan-assembler-times {\tccmp\t} 12 } } */
+/* { dg-final { scan-assembler-times {\tcset\t} 4 } } */
+/* { dg-final { scan-assembler-not {\tand\t} } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/fccmp_8.c
b/gcc/testsuite/gcc.target/aarch64/fccmp_8.c
new file mode 100644
index 00000000000..1f49069b710
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/fccmp_8.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 --param tree-reassoc-width=2
-fdump-tree-reassoc2-details" } */
+
+/* Two trapping comparisons cannot both start one sequence. */
+
+int
+two_traps (double a, double b, double c, double 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" } } */
diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc
index dec64883891..737d30ba0a4 100644
--- a/gcc/tree-ssa-reassoc.cc
+++ b/gcc/tree-ssa-reassoc.cc
@@ -5165,6 +5165,66 @@ 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 scalar comparison. */
+ 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 all operands in OPS form one conditional compare sequence
+ for CODE in BB. Put the operand that must start the sequence last in OPS,
+ where rewrite_expr_tree builds the innermost pair. Every operand must be a
+ comparison, and at least one must be foldable into the flags. */
+
+static bool
+prepare_ccmp_chain (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_foldable = false;
+ int head = -1;
+
+ for (unsigned int i = 0; i < ops.length (); ++i)
+ {
+ const operand_entry *oe = ops[i];
+ if (!ccmp_comparison_p (oe->op, bb))
+ return false;
+
+ bool foldable = has_single_use (oe->op);
+ if (foldable
+ && gimple_could_trap_p (SSA_NAME_DEF_STMT (oe->op)))
+ {
+ if (head >= 0)
+ return false;
+ head = i;
+ }
+
+ /* Comparison leaves can have uses outside this chain. */
+ seen_foldable |= foldable;
+ }
+
+ if (head >= 0)
+ std::swap (*ops[head], *ops.last ());
+ 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 +7213,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
+ && prepare_ccmp_chain (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))
@@ -7178,7 +7246,7 @@ reassociate_bb (basic_block bb)
to make sure the ones that get the double
binary op are chosen wisely. */
int len = ops.length ();
- if (!reassoc_insert_powi_p
+ if (!reassoc_insert_powi_p && !ccmp_chain
&& len >= 3
&& (!has_fma
/* width > 1 means ranking ops results in better
--
2.50.1 (Apple Git-155)
