This expands on optimizing `popcount(a) == 1` to also handle
`popcount(a) <= 1`. `<= 1` can be expanded as `(a & -a) == 0`
like what is done for `== 1` if we know that a was nonzero.
We have to do the optimization in 2 places due to if we have
an optab entry for popcount or not.
Built and tested for aarch64-linux-gnu.
PR middle-end/90693
gcc/ChangeLog:
* internal-fn.cc (expand_POPCOUNT): Handle the second argument
being `-1` for `<= 1`.
* tree-ssa-math-opts.cc (match_single_bit_test): Handle LE/GT
cases.
(math_opts_dom_walker::after_dom_children): Call match_single_bit_test
for LE_EXPR/GT_EXPR also.
gcc/testsuite/ChangeLog:
* gcc.target/aarch64/popcnt-le-1.c: New test.
* gcc.target/aarch64/popcnt-le-2.c: New test.
* gcc.target/aarch64/popcnt-le-3.c: New test.
Signed-off-by: Andrew Pinski <quic_apin...@quicinc.com>
---
gcc/internal-fn.cc | 20 +++++++++++-
.../gcc.target/aarch64/popcnt-le-1.c | 29 +++++++++++++++++
.../gcc.target/aarch64/popcnt-le-2.c | 31 +++++++++++++++++++
.../gcc.target/aarch64/popcnt-le-3.c | 31 +++++++++++++++++++
gcc/tree-ssa-math-opts.cc | 25 +++++++++++----
5 files changed, 129 insertions(+), 7 deletions(-)
create mode 100644 gcc/testsuite/gcc.target/aarch64/popcnt-le-1.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/popcnt-le-2.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/popcnt-le-3.c
diff --git a/gcc/internal-fn.cc b/gcc/internal-fn.cc
index 4e33db365ac..b55f089cf56 100644
--- a/gcc/internal-fn.cc
+++ b/gcc/internal-fn.cc
@@ -5304,11 +5304,16 @@ expand_POPCOUNT (internal_fn fn, gcall *stmt)
Use rtx costs in that case to determine if .POPCOUNT (arg) == 1
or (arg ^ (arg - 1)) > arg - 1 is cheaper.
If .POPCOUNT second argument is 0, we additionally know that arg
- is non-zero, so use arg & (arg - 1) == 0 instead. */
+ is non-zero, so use arg & (arg - 1) == 0 instead.
+ If .POPCOUNT second argument is -1, the comparison was either `<= 1`
+ or `> 1`. */
bool speed_p = optimize_insn_for_speed_p ();
tree lhs = gimple_call_lhs (stmt);
tree arg = gimple_call_arg (stmt, 0);
bool nonzero_arg = integer_zerop (gimple_call_arg (stmt, 1));
+ bool was_le = integer_minus_onep (gimple_call_arg (stmt, 1));
+ if (was_le)
+ nonzero_arg = true;
tree type = TREE_TYPE (arg);
machine_mode mode = TYPE_MODE (type);
machine_mode lhsmode = TYPE_MODE (TREE_TYPE (lhs));
@@ -5360,10 +5365,23 @@ expand_POPCOUNT (internal_fn fn, gcall *stmt)
emit_insn (popcount_insns);
else
{
+ start_sequence ();
emit_insn (cmp_insns);
plhs = expand_normal (lhs);
if (GET_MODE (cmp) != GET_MODE (plhs))
cmp = convert_to_mode (GET_MODE (plhs), cmp, 1);
+ /* For `<= 1`, we need to produce `2 - cmp` or `cmp ? 1 : 2` as that
+ then gets compared against 1 and we need the false case to be 2. */
+ if (was_le)
+ {
+ cmp = expand_simple_binop (GET_MODE (cmp), MINUS, const2_rtx,
+ cmp, NULL_RTX, 1, OPTAB_WIDEN);
+ if (!cmp)
+ goto fail;
+ }
emit_move_insn (plhs, cmp);
+ rtx_insn *all_insns = get_insns ();
+ end_sequence ();
+ emit_insn (all_insns);
}
}
diff --git a/gcc/testsuite/gcc.target/aarch64/popcnt-le-1.c
b/gcc/testsuite/gcc.target/aarch64/popcnt-le-1.c
new file mode 100644
index 00000000000..b4141da982c
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/popcnt-le-1.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-rtl-expand-details" } */
+/* { dg-final { check-function-bodies "**" "" } } */
+/* PR middle-end/90693 */
+
+#pragma GCC target "+nocssc"
+
+/*
+** le32:
+** sub w([0-9]+), w0, #1
+** tst w0, w\1
+** cset w0, eq
+** ret
+*/
+
+unsigned le32 (const unsigned int a) {
+ return __builtin_popcountg (a) <= 1;
+}
+
+/*
+** gt32:
+** sub w([0-9]+), w0, #1
+** tst w0, w\1
+** cset w0, ne
+** ret
+*/
+unsigned gt32 (const unsigned int a) {
+ return __builtin_popcountg (a) > 1;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/popcnt-le-2.c
b/gcc/testsuite/gcc.target/aarch64/popcnt-le-2.c
new file mode 100644
index 00000000000..975552ca63e
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/popcnt-le-2.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -mgeneral-regs-only -fdump-tree-optimized" } */
+/* { dg-final { scan-tree-dump-not "POPCOUNT \\\(" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "__builtin_popcount \\\(" "optimized" } } */
+/* { dg-final { check-function-bodies "**" "" } } */
+/* PR middle-end/90693 */
+
+#pragma GCC target "+nocssc"
+
+/*
+** le32:
+** sub w([0-9]+), w0, #1
+** tst w\1, w0
+** cset w0, eq
+** ret
+*/
+
+unsigned le32 (const unsigned int a) {
+ return __builtin_popcountg (a) <= 1;
+}
+
+/*
+** gt32:
+** sub w([0-9]+), w0, #1
+** tst w\1, w0
+** cset w0, ne
+** ret
+*/
+unsigned gt32 (const unsigned int a) {
+ return __builtin_popcountg (a) > 1;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/popcnt-le-3.c
b/gcc/testsuite/gcc.target/aarch64/popcnt-le-3.c
new file mode 100644
index 00000000000..b811e6f6e8f
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/popcnt-le-3.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-rtl-expand-details" } */
+/* { dg-final { check-function-bodies "**" "" } } */
+/* PR middle-end/90693 */
+
+#pragma GCC target "+nocssc"
+
+/*
+** le16:
+** sub w([0-9]+), w0, #1
+** and w([0-9]+), w0, w\1
+** tst w\2, 65535
+** cset w0, eq
+** ret
+*/
+
+unsigned le16 (const unsigned short a) {
+ return __builtin_popcountg (a) <= 1;
+}
+
+/*
+** gt16:
+** sub w([0-9]+), w0, #1
+** and w([0-9]+), w0, w\1
+** tst w\2, 65535
+** cset w0, ne
+** ret
+*/
+unsigned gt16 (const unsigned short a) {
+ return __builtin_popcountg (a) > 1;
+}
diff --git a/gcc/tree-ssa-math-opts.cc b/gcc/tree-ssa-math-opts.cc
index 3c93fca5b53..d61668aacfc 100644
--- a/gcc/tree-ssa-math-opts.cc
+++ b/gcc/tree-ssa-math-opts.cc
@@ -5433,13 +5433,15 @@ match_uaddc_usubc (gimple_stmt_iterator *gsi, gimple
*stmt, tree_code code)
/* Replace .POPCOUNT (x) == 1 or .POPCOUNT (x) != 1 with
(x & (x - 1)) > x - 1 or (x & (x - 1)) <= x - 1 if .POPCOUNT
- isn't a direct optab. */
+ isn't a direct optab. Also handle `<=`/`>` to be
+ `x & (x - 1) !=/== x`. */
static void
match_single_bit_test (gimple_stmt_iterator *gsi, gimple *stmt)
{
tree clhs, crhs;
enum tree_code code;
+ bool was_le = false;
if (gimple_code (stmt) == GIMPLE_COND)
{
clhs = gimple_cond_lhs (stmt);
@@ -5452,8 +5454,11 @@ match_single_bit_test (gimple_stmt_iterator *gsi, gimple
*stmt)
crhs = gimple_assign_rhs2 (stmt);
code = gimple_assign_rhs_code (stmt);
}
- if (code != EQ_EXPR && code != NE_EXPR)
+ if (code != LE_EXPR && code != GT_EXPR
+ && code != EQ_EXPR && code != NE_EXPR)
return;
+ if (code == LE_EXPR || code == GT_EXPR)
+ was_le = true;
if (TREE_CODE (clhs) != SSA_NAME || !integer_onep (crhs))
return;
gimple *call = SSA_NAME_DEF_STMT (clhs);
@@ -5477,8 +5482,9 @@ match_single_bit_test (gimple_stmt_iterator *gsi, gimple
*stmt)
/* Tell expand_POPCOUNT the popcount result is only used in equality
comparison with one, so that it can decide based on rtx costs. */
gimple *g = gimple_build_call_internal (IFN_POPCOUNT, 2, arg,
- nonzero_arg ? integer_zero_node
- : integer_one_node);
+ was_le ? integer_minus_one_node
+ : (nonzero_arg ? integer_zero_node
+ : integer_one_node));
gimple_call_set_lhs (g, gimple_call_lhs (call));
gimple_stmt_iterator gsi2 = gsi_for_stmt (call);
gsi_replace (&gsi2, g, true);
@@ -5489,11 +5495,16 @@ match_single_bit_test (gimple_stmt_iterator *gsi,
gimple *stmt)
build_int_cst (type, -1));
gsi_insert_before (gsi, g, GSI_SAME_STMT);
g = gimple_build_assign (make_ssa_name (type),
- nonzero_arg ? BIT_AND_EXPR : BIT_XOR_EXPR,
+ (nonzero_arg || was_le) ? BIT_AND_EXPR :
BIT_XOR_EXPR,
arg, argm1);
gsi_insert_before (gsi, g, GSI_SAME_STMT);
tree_code cmpcode;
- if (nonzero_arg)
+ if (was_le)
+ {
+ argm1 = build_zero_cst (type);
+ cmpcode = code == LE_EXPR ? EQ_EXPR : NE_EXPR;
+ }
+ else if (nonzero_arg)
{
argm1 = build_zero_cst (type);
cmpcode = code;
@@ -6188,6 +6199,8 @@ math_opts_dom_walker::after_dom_children (basic_block bb)
case EQ_EXPR:
case NE_EXPR:
+ case LE_EXPR:
+ case GT_EXPR:
match_single_bit_test (&gsi, stmt);
break;
--
2.43.0
