From: Kyrylo Tkachov <[email protected]>
The conditional-compare expander accepts a plain boolean as a comparison
against zero. This is useful when a chain also contains an explicit
comparison. It is harmful when every leaf is a boolean. For example:
_Bool
f (_Bool x, _Bool y)
{
return x || y;
}
AArch64 emitted:
and w1, w1, 255
tst w0, 255
ccmp w1, 0, 0, eq
cset w0, ne
Make candidate recognition report whether it found an explicit comparison.
It already validates every statement before it follows the next definition.
Reject a candidate without an explicit comparison.
TER fallback starts a new conditional-compare recognition call for each
forwarded suffix. Cache accepted all-boolean subchains in the existing
per-function ssaexpand state so that these calls inspect a linear chain in
linear time. The state is shared by cfgexpand and expression expansion and
is released when RTL expansion finishes.
The example then emits:
orr w0, w0, w1
Tests cover all-boolean and mixed chains, a non-binary boolean definition,
and a long rejected chain.
Changes since v1:
- Report explicit comparisons during candidate recognition.
- Cache all-boolean subchains so TER fallback stays linear.
- Add non-binary definition and long-chain tests.
gcc/
PR middle-end/109832
* ccmp.cc (ccmp_tree_comparison_p): Report whether an accepted leaf
is a comparison.
(ccmp_candidate_p): Propagate the result and cache all-boolean
candidates.
(expand_ccmp_expr): Reject an all-boolean candidate.
* tree-outof-ssa.h (ssaexpand::ccmp_no_comparison): New member.
* tree-outof-ssa.cc (finish_out_of_ssa): Free it.
gcc/testsuite/
PR middle-end/109832
* gcc.target/aarch64/ccmp_7.c: New test.
* gcc.target/aarch64/ccmp_9.c: Likewise.
* gcc.target/aarch64/ccmp_11.c: Likewise.
* gcc.target/aarch64/ccmp_13.c: Likewise.
Signed-off-by: Kyrylo Tkachov <[email protected]>
---
diff --git a/gcc/ccmp.cc b/gcc/ccmp.cc
index 0564ccf34bf..c30345f99d5 100644
--- a/gcc/ccmp.cc
+++ b/gcc/ccmp.cc
@@ -38,14 +38,18 @@ along with GCC; see the file COPYING3. If not see
#include "ccmp.h"
#include "predict.h"
-/* Check whether T is a simple boolean variable or a SSA name
- set by a comparison operator in the same basic block. */
+/* Check whether T is a simple boolean variable or an SSA name set by a
+ comparison operator in BB. Set *HAS_COMPARISON if T is the latter. */
static bool
-ccmp_tree_comparison_p (tree t, basic_block bb)
+ccmp_tree_comparison_p (tree t, basic_block bb,
+ bool *has_comparison = nullptr)
{
gimple *g = get_gimple_for_ssa_name (t);
tree_code tcode;
+ if (has_comparison)
+ *has_comparison = false;
+
/* If we have a boolean variable allow it and generate a compare
to zero reg when expanding. */
if (!g)
@@ -58,7 +62,12 @@ ccmp_tree_comparison_p (tree t, basic_block bb)
if (bb != gimple_bb (g))
return false;
tcode = gimple_assign_rhs_code (g);
- return TREE_CODE_CLASS (tcode) == tcc_comparison;
+ if (TREE_CODE_CLASS (tcode) != tcc_comparison)
+ return false;
+
+ if (has_comparison)
+ *has_comparison = true;
+ return true;
}
/* The following functions expand conditional compare (CCMP) instructions.
@@ -90,16 +99,19 @@ 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. */
-/* Check whether G is a potential conditional compare candidate; OUTER is true
if
- G is the outer most AND/IOR. */
+/* Return true if G is a potential conditional compare candidate. Set
+ *HAS_COMPARISON if it contains a comparison that will be folded into the
+ flags. OUTER is true if G is the outermost AND/IOR. */
static bool
-ccmp_candidate_p (gimple *g, bool outer = false)
+ccmp_candidate_p (gimple *g, bool *has_comparison, bool outer = false)
{
tree lhs, op0, op1;
gimple *gs0, *gs1;
tree_code tcode;
basic_block bb;
+ *has_comparison = false;
+
if (!g || !is_gimple_assign (g))
return false;
@@ -115,20 +127,46 @@ ccmp_candidate_p (gimple *g, bool outer = false)
if (!outer && !has_single_use (lhs))
return false;
+ if (SA.ccmp_no_comparison
+ && bitmap_bit_p (SA.ccmp_no_comparison, SSA_NAME_VERSION (lhs)))
+ {
+ *has_comparison = false;
+ return true;
+ }
+
bb = gimple_bb (g);
gs0 = get_gimple_for_ssa_name (op0); /* gs0 may be NULL */
gs1 = get_gimple_for_ssa_name (op1); /* gs1 may be NULL */
- 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))
- return true;
- if (ccmp_tree_comparison_p (op1, bb) && ccmp_candidate_p (gs0))
- return true;
+ bool comparison0, comparison1;
+ bool leaf0 = ccmp_tree_comparison_p (op0, bb, &comparison0);
+ bool leaf1 = ccmp_tree_comparison_p (op1, bb, &comparison1);
+
+ if (leaf0 && leaf1)
+ *has_comparison = comparison0 || comparison1;
+ else if (leaf0 || leaf1)
+ {
+ bool inner_has_comparison;
+ if (!ccmp_candidate_p (leaf0 ? gs1 : gs0, &inner_has_comparison))
+ return false;
+ *has_comparison = inner_has_comparison
+ || (leaf0 ? comparison0 : comparison1);
+ }
+ else
+ return false;
+
/* 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. */
- return false;
+
+ if (!*has_comparison)
+ {
+ if (!SA.ccmp_no_comparison)
+ SA.ccmp_no_comparison = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (SA.ccmp_no_comparison, SSA_NAME_VERSION (lhs));
+ }
+
+ return true;
}
/* Extract the comparison we want to do from the tree. */
@@ -291,7 +329,8 @@ expand_ccmp_expr (gimple *g, machine_mode mode)
rtx_insn *last;
rtx tmp;
- if (!ccmp_candidate_p (g, true))
+ bool has_comparison;
+ if (!ccmp_candidate_p (g, &has_comparison, true) || !has_comparison)
return NULL_RTX;
last = get_last_insn ();
diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_11.c
b/gcc/testsuite/gcc.target/aarch64/ccmp_11.c
new file mode 100644
index 00000000000..8605e177989
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ccmp_11.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-reassoc" } */
+/* PR middle-end/109832 */
+
+/* Rejected all-boolean subchains are cached during expansion. */
+
+extern _Bool t (void);
+
+#define B t ()
+
+_Bool
+bool_call_chain (void)
+{
+ return B | B | B | B | B | B | B | B
+ | B | B | B | B | B | B | B | B
+ | B | B | B | B | B | B | B | B
+ | B | B | B | B | B | B | B | B;
+}
+
+/* { dg-final { scan-assembler-not {\tccmp\t} } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_13.c
b/gcc/testsuite/gcc.target/aarch64/ccmp_13.c
new file mode 100644
index 00000000000..81ef431e137
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ccmp_13.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgimple" } */
+/* PR middle-end/109832 */
+
+/* A non-binary boolean definition is not a conditional-compare chain. */
+
+_Bool __GIMPLE (ssa, startwith ("expand"))
+bool_not_ior (_Bool a, _Bool b)
+{
+ _Bool _1;
+ _Bool _2;
+
+ __BB(2):
+ _1 = ~a_3(D);
+ _2 = _1 | b_4(D);
+ return _2;
+}
+
+/* { dg-final { scan-assembler-not {\tccmp\t} } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_7.c
b/gcc/testsuite/gcc.target/aarch64/ccmp_7.c
new file mode 100644
index 00000000000..d9c75eb6b0b
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ccmp_7.c
@@ -0,0 +1,38 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* PR middle-end/109832 */
+
+/* A conditional compare folds a comparison into the flags. When the operands
+ are plain booleans there is no comparison to fold and the bitwise operation
+ is cheaper, so no conditional compare should be formed. */
+
+_Bool
+bool_ior (_Bool x, _Bool y)
+{
+ return x || y;
+}
+
+_Bool
+bool_and (_Bool x, _Bool y)
+{
+ return x && y;
+}
+
+extern _Bool t (void);
+
+_Bool
+bool_call_ior (void)
+{
+ _Bool x = t ();
+ _Bool y = t ();
+ return x | y;
+}
+
+_Bool
+bool_ior_tree (_Bool a, _Bool b, _Bool c, _Bool d)
+{
+ return (a | b) | (c | d);
+}
+
+/* { dg-final { scan-assembler-not {\tccmp\t} } } */
+/* { dg-final { scan-assembler-times {\torr\tw[0-9]+, w[0-9]+, w[0-9]+} 5 } }
*/
diff --git a/gcc/testsuite/gcc.target/aarch64/ccmp_9.c
b/gcc/testsuite/gcc.target/aarch64/ccmp_9.c
new file mode 100644
index 00000000000..029dffa1b93
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/ccmp_9.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-reassoc" } */
+/* PR middle-end/109832 */
+
+/* One explicit comparison is enough for a chain to be worth a conditional
+ compare, so the boolean operands become comparisons against zero. */
+
+int
+bool_and_cmp_last (_Bool a, _Bool b, _Bool c, int x, int y)
+{
+ return ((a & b) & c) & (x < y);
+}
+
+int
+bool_and_cmp_first (_Bool a, _Bool b, _Bool c, int x, int y)
+{
+ return (((x < y) & a) & b) & c;
+}
+
+/* { dg-final { scan-assembler-times {\tccmp\t} 6 } } */
diff --git a/gcc/tree-outof-ssa.cc b/gcc/tree-outof-ssa.cc
index 409e951b212..ece86e2ab6f 100644
--- a/gcc/tree-outof-ssa.cc
+++ b/gcc/tree-outof-ssa.cc
@@ -1489,6 +1489,8 @@ finish_out_of_ssa (struct ssaexpand *sa)
free (sa->partition_to_pseudo);
if (sa->values)
BITMAP_FREE (sa->values);
+ if (sa->ccmp_no_comparison)
+ BITMAP_FREE (sa->ccmp_no_comparison);
delete_var_map (sa->map);
BITMAP_FREE (sa->partitions_for_parm_default_defs);
BITMAP_FREE (sa->partitions_for_undefined_values);
diff --git a/gcc/tree-outof-ssa.h b/gcc/tree-outof-ssa.h
index bfe9a1290b8..3d05c623708 100644
--- a/gcc/tree-outof-ssa.h
+++ b/gcc/tree-outof-ssa.h
@@ -34,6 +34,10 @@ struct ssaexpand
its definition should be forwarded. */
bitmap values;
+ /* For an SSA name version V bit V is set iff conditional-compare
+ recognition found no explicit comparison that can be folded. */
+ bitmap ccmp_no_comparison;
+
/* For a partition number I partition_to_pseudo[I] contains the
RTL expression of the allocated space of it (either a MEM or
a pseudos REG). */
--
2.50.1 (Apple Git-155)
