From: Jakub Jelinek <jakub@redhat.com>
To: Richard Biener <rguenther@suse.de>
Cc: gcc-patches@gcc.gnu.org
Subject: [PATCH] tree-ssa-math-opts: popcount (X) == 1 to (X ^ (X - 1)) > (X - 1) optimization [PR90693]
Date: Fri, 17 Nov 2023 15:01:04 +0100 [thread overview]
Message-ID: <ZVdyIFfKpN9rkOWh@tucnak> (raw)
Hi!
Per the earlier discussions on this PR, the following patch folds
popcount (x) == 1 (and != 1) into (x ^ (x - 1)) > x - 1 (or <=)
if the corresponding popcount optab isn't implemented (I think any
double-word popcount or call will be necessarily slower than the
above cheap 3 op check and even for -Os larger or same size).
I've noticed e.g. C++ aligned new starts with std::has_single_bit
which does popcount (x) == 1.
As a follow-up, I'm considering changing in this routine the popcount
call to IFN_POPCOUNT with 2 arguments and during expansion test costs.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
2023-11-17 Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/90693
* tree-ssa-math-opts.cc (match_single_bit_test): New function.
(math_opts_dom_walker::after_dom_children): Call it for EQ_EXPR
and NE_EXPR assignments and GIMPLE_CONDs.
* gcc.target/i386/pr90693.c: New test.
--- gcc/tree-ssa-math-opts.cc.jj 2023-11-13 15:51:02.920562303 +0100
+++ gcc/tree-ssa-math-opts.cc 2023-11-17 11:37:02.255905475 +0100
@@ -5154,6 +5154,72 @@ match_uaddc_usubc (gimple_stmt_iterator
return true;
}
+/* 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. */
+
+static void
+match_single_bit_test (gimple_stmt_iterator *gsi, gimple *stmt)
+{
+ tree clhs, crhs;
+ enum tree_code code;
+ if (gimple_code (stmt) == GIMPLE_COND)
+ {
+ clhs = gimple_cond_lhs (stmt);
+ crhs = gimple_cond_rhs (stmt);
+ code = gimple_cond_code (stmt);
+ }
+ else
+ {
+ clhs = gimple_assign_rhs1 (stmt);
+ crhs = gimple_assign_rhs2 (stmt);
+ code = gimple_assign_rhs_code (stmt);
+ }
+ if (code != EQ_EXPR && code != NE_EXPR)
+ return;
+ if (TREE_CODE (clhs) != SSA_NAME || !integer_onep (crhs))
+ return;
+ gimple *call = SSA_NAME_DEF_STMT (clhs);
+ combined_fn cfn = gimple_call_combined_fn (call);
+ switch (cfn)
+ {
+ CASE_CFN_POPCOUNT:
+ break;
+ default:
+ return;
+ }
+ if (!has_single_use (clhs))
+ return;
+ tree arg = gimple_call_arg (call, 0);
+ tree type = TREE_TYPE (arg);
+ if (!INTEGRAL_TYPE_P (type))
+ return;
+ if (direct_internal_fn_supported_p (IFN_POPCOUNT, type, OPTIMIZE_FOR_BOTH))
+ return;
+ tree argm1 = make_ssa_name (type);
+ gimple *g = gimple_build_assign (argm1, PLUS_EXPR, arg,
+ build_int_cst (type, -1));
+ gsi_insert_before (gsi, g, GSI_SAME_STMT);
+ g = gimple_build_assign (make_ssa_name (type), BIT_XOR_EXPR, arg, argm1);
+ gsi_insert_before (gsi, g, GSI_SAME_STMT);
+ if (gcond *cond = dyn_cast <gcond *> (stmt))
+ {
+ gimple_cond_set_lhs (cond, gimple_assign_lhs (g));
+ gimple_cond_set_rhs (cond, argm1);
+ gimple_cond_set_code (cond, code == EQ_EXPR ? GT_EXPR : LE_EXPR);
+ }
+ else
+ {
+ gimple_assign_set_rhs1 (stmt, gimple_assign_lhs (g));
+ gimple_assign_set_rhs2 (stmt, argm1);
+ gimple_assign_set_rhs_code (stmt, code == EQ_EXPR ? GT_EXPR : LE_EXPR);
+ }
+ update_stmt (stmt);
+ gimple_stmt_iterator gsi2 = gsi_for_stmt (call);
+ gsi_remove (&gsi2, true);
+ release_defs (call);
+}
+
/* Return true if target has support for divmod. */
static bool
@@ -5807,6 +5873,11 @@ math_opts_dom_walker::after_dom_children
match_uaddc_usubc (&gsi, stmt, code);
break;
+ case EQ_EXPR:
+ case NE_EXPR:
+ match_single_bit_test (&gsi, stmt);
+ break;
+
default:;
}
}
@@ -5872,7 +5943,10 @@ math_opts_dom_walker::after_dom_children
}
}
else if (gimple_code (stmt) == GIMPLE_COND)
- optimize_spaceship (as_a <gcond *> (stmt));
+ {
+ match_single_bit_test (&gsi, stmt);
+ optimize_spaceship (as_a <gcond *> (stmt));
+ }
gsi_next (&gsi);
}
if (fma_state.m_deferring_p
--- gcc/testsuite/gcc.target/i386/pr90693.c.jj 2023-11-16 19:31:43.383587048 +0100
+++ gcc/testsuite/gcc.target/i386/pr90693.c 2023-11-16 19:33:23.676177086 +0100
@@ -0,0 +1,29 @@
+/* PR tree-optimization/90693 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -mno-abm -mno-popcnt -fdump-tree-optimized" } */
+/* { dg-final { scan-tree-dump-not "POPCOUNT \\\(" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "__builtin_popcount(ll)? \\\(" "optimized" } } */
+
+int
+foo (unsigned int x)
+{
+ return __builtin_popcount (x) == 1;
+}
+
+int
+bar (unsigned int x)
+{
+ return (x ^ (x - 1)) > x - 1;
+}
+
+int
+baz (unsigned long long x)
+{
+ return __builtin_popcountll (x) == 1;
+}
+
+int
+qux (unsigned long long x)
+{
+ return (x ^ (x - 1)) > x - 1;
+}
Jakub
next reply other threads:[~2023-11-17 14:01 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-11-17 14:01 Jakub Jelinek [this message]
2023-11-18 10:27 ` [PATCH] tree-ssa-math-opts: popcount (X) == 1 to (X ^ (X - 1)) > (X - 1) optimization for direct optab [PR90693] Jakub Jelinek
2023-11-19 4:03 ` Jeff Law
2023-11-20 8:01 ` Richard Biener
2023-11-20 9:05 ` Jakub Jelinek
2023-11-19 3:59 ` [PATCH] tree-ssa-math-opts: popcount (X) == 1 to (X ^ (X - 1)) > (X - 1) optimization [PR90693] Jeff Law
2023-11-20 7:54 ` Richard Biener
2023-11-20 8:37 ` Jakub Jelinek
2023-11-20 8:39 ` Richard Biener
2023-11-20 8:41 ` Jakub Jelinek
2023-11-20 13:03 ` Jeff Law
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=ZVdyIFfKpN9rkOWh@tucnak \
--to=jakub@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=rguenther@suse.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).