| Message ID | 20220620163536.2653437-1-goldstein.w.n@gmail.com |
|---|---|
| State | New |
| Headers | show |
| Series | [v1] tree-optimization/95821 - Convert strlen + strchr to memchr | expand |
On Mon, Jun 20, 2022 at 09:35:36AM -0700, Noah Goldstein via Gcc-patches wrote: > 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. Do you have a GCC Copyright assignment on file, or do you want to submit this under DCO ( https://gcc.gnu.org/dco.html )? If the latter, there should be a Signed-off-by: line, both in the mail and later commit. > > bootstrapped and tested on x86_64-linux. > > gcc/ > As it fixes a GCC bugzilla bug, the ChangeLog entry should start with PR tree-optimization/95821 line. > * tree-ssa-strlen.cc: Emit memchr instead of strchr if strlen > already computed. All the indented lines in ChangeLog should be indented by tab. You are modifying strlen_pass::handle_builtin_strchr function, so after tree-ssa-strlen.cc there should be that function name in parens: * tree-ssa-strlen.cc (strlen_pass::handle_builtin_strchr): Emit memchr ... > > gcc/testsuite/ > > * c-c++-common/pr95821-1.c > * c-c++-common/pr95821-2.c > * c-c++-common/pr95821-3.c > * c-c++-common/pr95821-4.c > * c-c++-common/pr95821-5.c > * c-c++-common/pr95821-6.c All the above lines should end with ": New test." after .c > --- a/gcc/tree-ssa-strlen.cc > +++ b/gcc/tree-ssa-strlen.cc How does the patch relate to the one that H.J. attached in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95821#c4 ? > @@ -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). */ Space before ( even in comments. > void > strlen_pass::handle_builtin_strchr () > @@ -2418,8 +2421,8 @@ 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); > + bool is_strchr_zerop = integer_zerop (chr); > > tree src = gimple_call_arg (stmt, 0); > > @@ -2452,32 +2455,56 @@ 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) > + 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 if strlen has already been computed. */ Again, space before (. The second line is weirdly formatted, should be indented below If. > + tree fn = builtin_decl_explicit (BUILT_IN_MEMCHR); > + 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; I think we should differentiate more. If integer_nonzerop (chr) or perhaps better tree_expr_nonzero_p (chr), then it is better to optimize t = strlen (x); ... p = strchr (x, c); to t = strlen (x); ... p = memchr (x, c, t); the t + 1 is only needed if c might be zero. > + /* Don't update strlen of lhs if search-char was non-zero. */ Wasn't known to be zero is the right thing. Jakub
On Mon, Jun 20, 2022 at 10:29 AM Jakub Jelinek <jakub@redhat.com> wrote: > > On Mon, Jun 20, 2022 at 09:35:36AM -0700, Noah Goldstein via Gcc-patches wrote: > > 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. > > Do you have a GCC Copyright assignment on file, or do you want to submit Noah works for Intel and he should be covered. > this under DCO ( https://gcc.gnu.org/dco.html )? If the latter, there > should be a Signed-off-by: line, both in the mail and later commit. > > > > bootstrapped and tested on x86_64-linux. > > > > gcc/ > > > > As it fixes a GCC bugzilla bug, the ChangeLog entry should start with > PR tree-optimization/95821 > line. > > * tree-ssa-strlen.cc: Emit memchr instead of strchr if strlen > > already computed. > > All the indented lines in ChangeLog should be indented by tab. > You are modifying strlen_pass::handle_builtin_strchr function, so after > tree-ssa-strlen.cc there should be that function name in parens: > * tree-ssa-strlen.cc (strlen_pass::handle_builtin_strchr): Emit > memchr ... > > > > > gcc/testsuite/ > > > > * c-c++-common/pr95821-1.c > > * c-c++-common/pr95821-2.c > > * c-c++-common/pr95821-3.c > > * c-c++-common/pr95821-4.c > > * c-c++-common/pr95821-5.c > > * c-c++-common/pr95821-6.c > > All the above lines should end with ": New test." after .c > > > --- a/gcc/tree-ssa-strlen.cc > > +++ b/gcc/tree-ssa-strlen.cc > > How does the patch relate to the one that H.J. attached in > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95821#c4 ? Both patches are very similar. Mine has a bug. > > @@ -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). */ > > Space before ( even in comments. > > > > > void > > strlen_pass::handle_builtin_strchr () > > @@ -2418,8 +2421,8 @@ 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); > > + bool is_strchr_zerop = integer_zerop (chr); > > > > tree src = gimple_call_arg (stmt, 0); > > > > @@ -2452,32 +2455,56 @@ 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) > > + 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 if strlen has already been computed. */ > > Again, space before (. The second line is weirdly formatted, should > be indented below If. > > > + tree fn = builtin_decl_explicit (BUILT_IN_MEMCHR); > > + 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; > > I think we should differentiate more. If integer_nonzerop (chr) > or perhaps better tree_expr_nonzero_p (chr), then it is better > to optimize t = strlen (x); ... p = strchr (x, c); to > t = strlen (x); ... p = memchr (x, c, t); > the t + 1 is only needed if c might be zero. > > > + /* Don't update strlen of lhs if search-char was non-zero. */ > > Wasn't known to be zero is the right thing. > > Jakub >
On Mon, Jun 20, 2022 at 10:29 AM Jakub Jelinek <jakub@redhat.com> wrote: > > On Mon, Jun 20, 2022 at 09:35:36AM -0700, Noah Goldstein via Gcc-patches wrote: > > 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. > > Do you have a GCC Copyright assignment on file, or do you want to submit > this under DCO ( https://gcc.gnu.org/dco.html )? If the latter, there > should be a Signed-off-by: line, both in the mail and later commit. > > > > bootstrapped and tested on x86_64-linux. > > > > gcc/ > > > > As it fixes a GCC bugzilla bug, the ChangeLog entry should start with > PR tree-optimization/95821 > line. > > * tree-ssa-strlen.cc: Emit memchr instead of strchr if strlen > > already computed. > > All the indented lines in ChangeLog should be indented by tab. > You are modifying strlen_pass::handle_builtin_strchr function, so after > tree-ssa-strlen.cc there should be that function name in parens: > * tree-ssa-strlen.cc (strlen_pass::handle_builtin_strchr): Emit > memchr ... > > > > > gcc/testsuite/ > > > > * c-c++-common/pr95821-1.c > > * c-c++-common/pr95821-2.c > > * c-c++-common/pr95821-3.c > > * c-c++-common/pr95821-4.c > > * c-c++-common/pr95821-5.c > > * c-c++-common/pr95821-6.c > > All the above lines should end with ": New test." after .c > > > --- a/gcc/tree-ssa-strlen.cc > > +++ b/gcc/tree-ssa-strlen.cc > > How does the patch relate to the one that H.J. attached in > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95821#c4 ? > > > @@ -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). */ > > Space before ( even in comments. > > > > > void > > strlen_pass::handle_builtin_strchr () > > @@ -2418,8 +2421,8 @@ 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); > > + bool is_strchr_zerop = integer_zerop (chr); > > > > tree src = gimple_call_arg (stmt, 0); > > > > @@ -2452,32 +2455,56 @@ 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) > > + 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 if strlen has already been computed. */ > > Again, space before (. The second line is weirdly formatted, should > be indented below If. > > > + tree fn = builtin_decl_explicit (BUILT_IN_MEMCHR); > > + 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; > > I think we should differentiate more. If integer_nonzerop (chr) > or perhaps better tree_expr_nonzero_p (chr), then it is better > to optimize t = strlen (x); ... p = strchr (x, c); to > t = strlen (x); ... p = memchr (x, c, t); What do you mean by differentiate more? More comments? Or seperate the logic more? > the t + 1 is only needed if c might be zero. > > > + /* Don't update strlen of lhs if search-char was non-zero. */ > > Wasn't known to be zero is the right thing. > > Jakub >
On Mon, Jun 20, 2022 at 11:48:24AM -0700, Noah Goldstein wrote: > > I think we should differentiate more. If integer_nonzerop (chr) > > or perhaps better tree_expr_nonzero_p (chr), then it is better > > to optimize t = strlen (x); ... p = strchr (x, c); to > > t = strlen (x); ... p = memchr (x, c, t); > What do you mean by differentiate more? More comments? Or > seperate the logic more? Different code, don't add the 1 to the strlen value whenever you know that chr can't be possibly 0 (either it is a non-zero constant, or the compiler can prove it won't be zero at runtime otherwise). Because if c is not 0, then memchr (x, c, strlen (x)) == memchr (x, c, strlen (x) + 1), either c is among the first strlen (x) chars, or it will return NULL because x[strlen (x)] == 0. It actually is slightly more complicated, strchr second argument is int, but we just care about the low 8 bits. For TREE_CODE (chr) == INTEGER_CST, it is still trivial, say integer_nonzerop (fold_convert (char_type_node, chr)) or equivalent using wide-int.h APIs. For SSA_NAMEs, we'd need get_zero_bits API, but we only have get_nonzero_bits, but we could say at least handle the case where get_ssa_name_range_info gives a VR_RANGE or set of them where none of the ranges include integral multiplies of 256. But for start perhaps just handling INTEGER_CST chr would be good enough. Jakub
On Mon, Jun 20, 2022 at 12:04 PM Jakub Jelinek <jakub@redhat.com> wrote: > > On Mon, Jun 20, 2022 at 11:48:24AM -0700, Noah Goldstein wrote: > > > I think we should differentiate more. If integer_nonzerop (chr) > > > or perhaps better tree_expr_nonzero_p (chr), then it is better > > > to optimize t = strlen (x); ... p = strchr (x, c); to > > > t = strlen (x); ... p = memchr (x, c, t); > > What do you mean by differentiate more? More comments? Or > > seperate the logic more? > > Different code, don't add the 1 to the strlen value whenever you know > that chr can't be possibly 0 (either it is a non-zero constant, > or the compiler can prove it won't be zero at runtime otherwise). > Because if c is not 0, then memchr (x, c, strlen (x)) == memchr (x, c, strlen (x) + 1), > either c is among the first strlen (x) chars, or it will return NULL > because x[strlen (x)] == 0. > > It actually is slightly more complicated, strchr second argument is int, > but we just care about the low 8 bits. > For TREE_CODE (chr) == INTEGER_CST, it is still trivial, > say integer_nonzerop (fold_convert (char_type_node, chr)) > or equivalent using wide-int.h APIs. > For SSA_NAMEs, we'd need get_zero_bits API, but we only have > get_nonzero_bits, but we could say at least handle the case where > get_ssa_name_range_info gives a VR_RANGE or set of them where none of > the ranges include integral multiplies of 256. > But for start perhaps just handling INTEGER_CST chr would be good enough. Got it. Will have that in V2. We could also make the initial: bool is_strchr_zerop = integer_zerop (chr); Only check the lower 8 bits. > > Jakub >
On Mon, Jun 20, 2022 at 12:12:53PM -0700, Noah Goldstein wrote: > Got it. Will have that in V2. Thanks. > > We could also make the initial: > bool is_strchr_zerop = integer_zerop (chr); > > Only check the lower 8 bits. Sure. Though, in that case it is just an optimization, it is ok to not to optimize strchr (x, 256); as strchr (x, 0);, but it is not ok to optimize strchr (x, 256); into memchr (x, 256, strlen (x)); so for the strlen (x) vs. strlen (x) + 1 decision it is needed for correctness. Jakub
On Mon, Jun 20, 2022 at 10:29 AM Jakub Jelinek <jakub@redhat.com> wrote: > > On Mon, Jun 20, 2022 at 09:35:36AM -0700, Noah Goldstein via Gcc-patches wrote: > > 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. > > Do you have a GCC Copyright assignment on file, or do you want to submit > this under DCO ( https://gcc.gnu.org/dco.html )? If the latter, there > should be a Signed-off-by: line, both in the mail and later commit. > > > > bootstrapped and tested on x86_64-linux. > > > > gcc/ > > > > As it fixes a GCC bugzilla bug, the ChangeLog entry should start with > PR tree-optimization/95821 > line. > > * tree-ssa-strlen.cc: Emit memchr instead of strchr if strlen > > already computed. > > All the indented lines in ChangeLog should be indented by tab. > You are modifying strlen_pass::handle_builtin_strchr function, so after > tree-ssa-strlen.cc there should be that function name in parens: > * tree-ssa-strlen.cc (strlen_pass::handle_builtin_strchr): Emit > memchr ... Fixed in v2. > > > > > gcc/testsuite/ > > > > * c-c++-common/pr95821-1.c > > * c-c++-common/pr95821-2.c > > * c-c++-common/pr95821-3.c > > * c-c++-common/pr95821-4.c > > * c-c++-common/pr95821-5.c > > * c-c++-common/pr95821-6.c > > All the above lines should end with ": New test." after .c Fixed in V2. > > > --- a/gcc/tree-ssa-strlen.cc > > +++ b/gcc/tree-ssa-strlen.cc > > How does the patch relate to the one that H.J. attached in > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95821#c4 ? > > > @@ -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). */ > > Space before ( even in comments. Fixed in V2. > > > > > void > > strlen_pass::handle_builtin_strchr () > > @@ -2418,8 +2421,8 @@ 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); > > + bool is_strchr_zerop = integer_zerop (chr); > > > > tree src = gimple_call_arg (stmt, 0); > > > > @@ -2452,32 +2455,56 @@ 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) > > + 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 if strlen has already been computed. */ > > Again, space before (. The second line is weirdly formatted, should > be indented below If. Fixed in V2. > > > + tree fn = builtin_decl_explicit (BUILT_IN_MEMCHR); > > + 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; > > I think we should differentiate more. If integer_nonzerop (chr) > or perhaps better tree_expr_nonzero_p (chr), then it is better > to optimize t = strlen (x); ... p = strchr (x, c); to > t = strlen (x); ... p = memchr (x, c, t); > the t + 1 is only needed if c might be zero. Done in V2. Also added the optimizations if chr has zero-char bits. Right now: t=strlen (s); strchr (s, 0) -> t; strchr (s, 256) -> t; strchr (s, 1234) -> memchr (s, 1234, t); strchr (s, non_zero) -> memchr (s, non_zero, t); strchr (s, unknown) -> memchr (s, unknown, t + 1); > > > + /* Don't update strlen of lhs if search-char was non-zero. */ > > Wasn't known to be zero is the right thing. Fixed in V2. > > Jakub >
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/tree-ssa-strlen.cc b/gcc/tree-ssa-strlen.cc index 1d4c0f78fbf..d959a530ea0 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,8 @@ 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); + bool is_strchr_zerop = integer_zerop (chr); tree src = gimple_call_arg (stmt, 0); @@ -2452,32 +2455,56 @@ 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) + 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 if strlen has already been computed. */ + tree fn = builtin_decl_explicit (BUILT_IN_MEMCHR); + 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 was non-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 +2514,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))
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. gcc/ * tree-ssa-strlen.cc: Emit memchr instead of strchr if strlen already computed. gcc/testsuite/ * c-c++-common/pr95821-1.c * c-c++-common/pr95821-2.c * c-c++-common/pr95821-3.c * c-c++-common/pr95821-4.c * c-c++-common/pr95821-5.c * c-c++-common/pr95821-6.c --- 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/tree-ssa-strlen.cc | 69 +++++++++++++++++++------- 7 files changed, 152 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