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
