[v1] tree-optimization/95821 - Convert strlen + strchr to memchr
Commit Message
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
Comments
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
>
new file mode 100644
@@ -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);
+}
new file mode 100644
@@ -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);
+}
new file mode 100644
@@ -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);
+}
new file mode 100644
@@ -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);
+}
new file mode 100644
@@ -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() {}
new file mode 100644
@@ -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);
+}
@@ -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))