From: Noah Goldstein <goldstein.w.n@gmail.com>
To: gcc-patches@gcc.gnu.org
Cc: goldstein.w.n@gmail.com, hjl.tools@gmail.com, jakub@redhat.com
Subject: [PATCH v3] tree-optimization/95821 - Convert strlen + strchr to memchr
Date: Tue, 21 Jun 2022 11:12:15 -0700 [thread overview]
Message-ID: <20220621181215.2942551-1-goldstein.w.n@gmail.com> (raw)
In-Reply-To: <20220620163536.2653437-1-goldstein.w.n@gmail.com>
This patch allows for strchr(x, c) to the replace with memchr(x, c,
strlen(x) + 1) if strlen(x) has already been computed earlier in the
tree.
Handles PR95821: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95821
Since memchr doesn't need to re-find the null terminator it is faster
than strchr.
bootstrapped and tested on x86_64-linux.
PR tree-optimization/95821
gcc/
* tree-ssa-strlen.cc (strlen_pass::handle_builtin_strchr): Emit
memchr instead of strchr if strlen already computed.
gcc/testsuite/
* c-c++-common/pr95821-1.c: New test.
* c-c++-common/pr95821-2.c: New test.
* c-c++-common/pr95821-3.c: New test.
* c-c++-common/pr95821-4.c: New test.
* c-c++-common/pr95821-5.c: New test.
* c-c++-common/pr95821-6.c: New test.
* c-c++-common/pr95821-7.c: New test.
* c-c++-common/pr95821-8.c: New test.
---
gcc/testsuite/c-c++-common/pr95821-1.c | 15 ++++
gcc/testsuite/c-c++-common/pr95821-2.c | 17 ++++
gcc/testsuite/c-c++-common/pr95821-3.c | 17 ++++
gcc/testsuite/c-c++-common/pr95821-4.c | 16 ++++
gcc/testsuite/c-c++-common/pr95821-5.c | 19 +++++
gcc/testsuite/c-c++-common/pr95821-6.c | 18 ++++
gcc/testsuite/c-c++-common/pr95821-7.c | 18 ++++
gcc/testsuite/c-c++-common/pr95821-8.c | 19 +++++
gcc/tree-ssa-strlen.cc | 113 ++++++++++++++++++++-----
9 files changed, 233 insertions(+), 19 deletions(-)
create mode 100644 gcc/testsuite/c-c++-common/pr95821-1.c
create mode 100644 gcc/testsuite/c-c++-common/pr95821-2.c
create mode 100644 gcc/testsuite/c-c++-common/pr95821-3.c
create mode 100644 gcc/testsuite/c-c++-common/pr95821-4.c
create mode 100644 gcc/testsuite/c-c++-common/pr95821-5.c
create mode 100644 gcc/testsuite/c-c++-common/pr95821-6.c
create mode 100644 gcc/testsuite/c-c++-common/pr95821-7.c
create mode 100644 gcc/testsuite/c-c++-common/pr95821-8.c
diff --git a/gcc/testsuite/c-c++-common/pr95821-1.c b/gcc/testsuite/c-c++-common/pr95821-1.c
new file mode 100644
index 00000000000..e0beb609ea2
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/pr95821-1.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { scan-assembler "memchr" } } */
+
+#include <stddef.h>
+
+char *
+foo (char *s, char c)
+{
+ size_t slen = __builtin_strlen(s);
+ if(slen < 1000)
+ return NULL;
+
+ return __builtin_strchr(s, c);
+}
diff --git a/gcc/testsuite/c-c++-common/pr95821-2.c b/gcc/testsuite/c-c++-common/pr95821-2.c
new file mode 100644
index 00000000000..5429f0586be
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/pr95821-2.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { scan-assembler-not "memchr" } } */
+
+#include <stddef.h>
+
+char *
+foo (char *s, char c, char * other)
+{
+ size_t slen = __builtin_strlen(s);
+ if(slen < 1000)
+ return NULL;
+
+ *other = 0;
+
+ return __builtin_strchr(s, c);
+}
diff --git a/gcc/testsuite/c-c++-common/pr95821-3.c b/gcc/testsuite/c-c++-common/pr95821-3.c
new file mode 100644
index 00000000000..bc929c6044b
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/pr95821-3.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { scan-assembler "memchr" } } */
+
+#include <stddef.h>
+
+char *
+foo (char * __restrict s, char c, char * __restrict other)
+{
+ size_t slen = __builtin_strlen(s);
+ if(slen < 1000)
+ return NULL;
+
+ *other = 0;
+
+ return __builtin_strchr(s, c);
+}
diff --git a/gcc/testsuite/c-c++-common/pr95821-4.c b/gcc/testsuite/c-c++-common/pr95821-4.c
new file mode 100644
index 00000000000..684b41d5b70
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/pr95821-4.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { scan-assembler "memchr" } } */
+
+#include <stddef.h>
+#include <string.h>
+
+char *
+foo (char *s, char c)
+{
+ size_t slen = strlen(s);
+ if(slen < 1000)
+ return NULL;
+
+ return strchr(s, c);
+}
diff --git a/gcc/testsuite/c-c++-common/pr95821-5.c b/gcc/testsuite/c-c++-common/pr95821-5.c
new file mode 100644
index 00000000000..00c1d93b614
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/pr95821-5.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { scan-assembler-not "memchr" } } */
+
+#include <stddef.h>
+#include <string.h>
+
+char *
+foo (char *s, char c, char * other)
+{
+ size_t slen = strlen(s);
+ if(slen < 1000)
+ return NULL;
+
+ *other = 0;
+
+ return strchr(s, c);
+}
+int main() {}
diff --git a/gcc/testsuite/c-c++-common/pr95821-6.c b/gcc/testsuite/c-c++-common/pr95821-6.c
new file mode 100644
index 00000000000..dec839de5ea
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/pr95821-6.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { scan-assembler "memchr" } } */
+
+#include <stddef.h>
+#include <string.h>
+
+char *
+foo (char * __restrict s, char c, char * __restrict other)
+{
+ size_t slen = strlen(s);
+ if(slen < 1000)
+ return NULL;
+
+ *other = 0;
+
+ return strchr(s, c);
+}
diff --git a/gcc/testsuite/c-c++-common/pr95821-7.c b/gcc/testsuite/c-c++-common/pr95821-7.c
new file mode 100644
index 00000000000..9da0fff7250
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/pr95821-7.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { scan-assembler "memchr" } } */
+
+#include <stddef.h>
+#include <string.h>
+
+char *
+foo (char * __restrict s, char c, char * __restrict other)
+{
+ size_t slen = strlen(s);
+ if(slen < 1000 || c == 0)
+ return NULL;
+
+ *other = 0;
+
+ return strchr(s, c);
+}
diff --git a/gcc/testsuite/c-c++-common/pr95821-8.c b/gcc/testsuite/c-c++-common/pr95821-8.c
new file mode 100644
index 00000000000..5eb02c6fea4
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/pr95821-8.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { scan-assembler-not "strchr" } } */
+/* { dg-final { scan-assembler-not "memchr" } } */
+
+#include <stddef.h>
+#include <string.h>
+
+char *
+foo (char * __restrict s, int c, char * __restrict other)
+{
+ size_t slen = strlen(s);
+ if(slen < 1000 || c != 0x100)
+ return NULL;
+
+ *other = 0;
+
+ return strchr(s, c);
+}
diff --git a/gcc/tree-ssa-strlen.cc b/gcc/tree-ssa-strlen.cc
index 1d4c0f78fbf..3c26ea7eb83 100644
--- a/gcc/tree-ssa-strlen.cc
+++ b/gcc/tree-ssa-strlen.cc
@@ -2405,9 +2405,12 @@ strlen_pass::handle_builtin_strlen ()
}
}
-/* Handle a strchr call. If strlen of the first argument is known, replace
- the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
- that lhs of the call is endptr and strlen of the argument is endptr - x. */
+/* Handle a strchr call. If strlen of the first argument is known,
+ replace the strchr (x, 0) call with the endptr or x + strlen,
+ otherwise remember that lhs of the call is endptr and strlen of the
+ argument is endptr - x. If strlen of x is not know but has been
+ computed earlier in the tree then replace strchr (x, c) to
+ memchr (x, c, strlen + 1). */
void
strlen_pass::handle_builtin_strchr ()
@@ -2418,8 +2421,12 @@ strlen_pass::handle_builtin_strchr ()
if (lhs == NULL_TREE)
return;
- if (!integer_zerop (gimple_call_arg (stmt, 1)))
- return;
+ tree chr = gimple_call_arg (stmt, 1);
+ /* strchr only uses the lower char of input so to check if its
+ strchr (s, zerop) only take into account the lower char. */
+ bool is_strchr_zerop
+ = (TREE_CODE (chr) == INTEGER_CST
+ && integer_zerop (fold_convert (char_type_node, chr)));
tree src = gimple_call_arg (stmt, 0);
@@ -2452,32 +2459,96 @@ strlen_pass::handle_builtin_strchr ()
fprintf (dump_file, "Optimizing: ");
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
- if (si != NULL && si->endptr != NULL_TREE)
+ /* Three potential optimizations assume t=strlen (s) has already been
+ computed:
+ 1. strchr (s, chr) where chr is known to be zero -> t
+ 2. strchr (s, chr) where chr is known not to be zero ->
+ memchr (s, chr, t)
+ 3. strchr (s, chr) where chr is not known to be zero or
+ non-zero -> memchr (s, chr, t + 1). */
+ if (!is_strchr_zerop)
{
- rhs = unshare_expr (si->endptr);
- if (!useless_type_conversion_p (TREE_TYPE (lhs),
- TREE_TYPE (rhs)))
- rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
+ /* If its not strchr (s, zerop) then try and convert to
+ memchr since strlen has already been computed. */
+ tree fn = builtin_decl_explicit (BUILT_IN_MEMCHR);
+
+ /* Only need to check length strlen (s) + 1 if chr may be zero.
+ Otherwise the last chr (which is known to be zero) can never
+ be a match. */
+ bool chr_nonzero = false;
+ if (TREE_CODE (chr) == INTEGER_CST
+ && integer_nonzerop (fold_convert (char_type_node, chr)))
+ chr_nonzero = true;
+ else if (TREE_CODE (chr) == SSA_NAME
+ && CHAR_TYPE_SIZE < INT_TYPE_SIZE)
+ {
+ value_range r;
+ /* Try to determine using ranges if (char) chr must
+ be always 0. That is true e.g. if all the subranges
+ have the INT_TYPE_SIZE - CHAR_TYPE_SIZE bits
+ the same on lower and upper bounds. */
+ if (get_range_query (cfun)->range_of_expr (r, chr, stmt)
+ && r.kind () == VR_RANGE)
+ {
+ wide_int mask
+ = wi::mask (CHAR_TYPE_SIZE, true, INT_TYPE_SIZE);
+ for (unsigned i = 0; i < r.num_pairs (); ++i)
+ if ((r.lower_bound (i) & mask)
+ != (r.upper_bound (i) & mask))
+ {
+ chr_nonzero = false;
+ break;
+ }
+ }
+ }
+ if (!chr_nonzero)
+ {
+ tree one = build_int_cst (TREE_TYPE (rhs), 1);
+ rhs = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (rhs),
+ unshare_expr (rhs), one);
+ tree size = make_ssa_name (TREE_TYPE (rhs));
+ gassign *size_stmt = gimple_build_assign (size, rhs);
+ gsi_insert_before (&m_gsi, size_stmt, GSI_SAME_STMT);
+ rhs = size;
+ }
+ if (!update_gimple_call (&m_gsi, fn, 3, src, chr, rhs))
+ return;
}
else
{
- rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
- rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
- TREE_TYPE (src), src, rhs);
- if (!useless_type_conversion_p (TREE_TYPE (lhs),
- TREE_TYPE (rhs)))
- rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
+ if (si != NULL && si->endptr != NULL_TREE)
+ {
+ rhs = unshare_expr (si->endptr);
+ if (!useless_type_conversion_p (TREE_TYPE (lhs),
+ TREE_TYPE (rhs)))
+ rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
+ }
+ else
+ {
+ rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
+ rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
+ TREE_TYPE (src), src, rhs);
+ if (!useless_type_conversion_p (TREE_TYPE (lhs),
+ TREE_TYPE (rhs)))
+ rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
+ }
+ gimplify_and_update_call_from_tree (&m_gsi, rhs);
}
- gimplify_and_update_call_from_tree (&m_gsi, rhs);
+
stmt = gsi_stmt (m_gsi);
update_stmt (stmt);
+
if (dump_file && (dump_flags & TDF_DETAILS) != 0)
{
fprintf (dump_file, "into: ");
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
- if (si != NULL
- && si->endptr == NULL_TREE
+
+ /* Don't update strlen of lhs if search-char wasn't know to be zero. */
+ if (!is_strchr_zerop)
+ return;
+
+ if (si != NULL && si->endptr == NULL_TREE
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
{
si = unshare_strinfo (si);
@@ -2487,6 +2558,10 @@ strlen_pass::handle_builtin_strchr ()
return;
}
}
+
+ if (!is_strchr_zerop)
+ return;
+
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
return;
if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
--
2.34.1
next prev parent reply other threads:[~2022-06-21 18:12 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-06-20 16:35 [PATCH v1] " Noah Goldstein
2022-06-20 17:29 ` Jakub Jelinek
2022-06-20 17:54 ` H.J. Lu
2022-06-20 18:48 ` Noah Goldstein
2022-06-20 19:04 ` Jakub Jelinek
2022-06-20 19:12 ` Noah Goldstein
2022-06-20 19:57 ` Jakub Jelinek
2022-06-20 20:59 ` Noah Goldstein
2022-06-20 21:42 ` [PATCH v2] " Noah Goldstein
2022-06-21 12:01 ` Jakub Jelinek
2022-06-21 18:13 ` Noah Goldstein
2022-07-07 16:26 ` Noah Goldstein
2022-06-21 18:12 ` Noah Goldstein [this message]
2022-07-09 15:59 ` [PATCH v3] " Jeff Law
2022-09-21 22:02 ` Noah Goldstein
2022-09-22 12:22 ` Jakub Jelinek
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=20220621181215.2942551-1-goldstein.w.n@gmail.com \
--to=goldstein.w.n@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hjl.tools@gmail.com \
--cc=jakub@redhat.com \
/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).