[PATCH v1] tree-optimization/95821 - Convert strlen + strchr to memchr

[PATCH v1] tree-optimization/95821 - Convert strlen + strchr to memchr

[Noah Goldstein]

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

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))
-- 
2.34.1

Re: [PATCH v1] tree-optimization/95821 - Convert strlen + strchr to memchr

[Jakub Jelinek]

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

Re: [PATCH v1] tree-optimization/95821 - Convert strlen + strchr to memchr

[H.J. Lu]

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
>


-- 
H.J.

Re: [PATCH v1] tree-optimization/95821 - Convert strlen + strchr to memchr

[Noah Goldstein]

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
>

Re: [PATCH v1] tree-optimization/95821 - Convert strlen + strchr to memchr

[Jakub Jelinek]

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

Re: [PATCH v1] tree-optimization/95821 - Convert strlen + strchr to memchr

[Noah Goldstein]

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
>

Re: [PATCH v1] tree-optimization/95821 - Convert strlen + strchr to memchr

[Jakub Jelinek]

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

Re: [PATCH v1] tree-optimization/95821 - Convert strlen + strchr to memchr

[Noah Goldstein]

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
>

[PATCH v2] tree-optimization/95821 - Convert strlen + strchr to memchr

[Noah Goldstein]

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                 | 89 ++++++++++++++++++++------
 9 files changed, 209 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..807624adc94 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,72 @@ 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.  NB: We don't need to test if chr is a non-zero
+             integer const with zero char bits because that is taken into
+             account with is_strchr_zerop.  */
+	      if (!tree_expr_nonzero_p (chr))
+		{
+		  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 +2534,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

Re: [PATCH v2] tree-optimization/95821 - Convert strlen + strchr to memchr

[Jakub Jelinek]

On Mon, Jun 20, 2022 at 02:42:20PM -0700, Noah Goldstein 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.
> 
> bootstrapped and tested on x86_64-linux.
> 
> 		PR tree-optimization/95821

This should be indented by a single tab, not two.
> 
> 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.
> --- 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

Still missing space before ( above.

> +   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)));

The indentation rule is that = should be 2 columns to the right from bool,
so

  bool is_strchr_zerop
    = (TREE_CODE (chr) == INTEGER_CST
       && integer_zerop (fold_convert (char_type_node, chr)));

> +	      /* If its not strchr (s, zerop) then try and convert to
> +		     memchr since strlen has already been computed.  */

This comment still has the second line weirdly indented.

> +	      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.  NB: We don't need to test if chr is a non-zero
> +             integer const with zero char bits because that is taken into
> +             account with is_strchr_zerop.  */
> +	      if (!tree_expr_nonzero_p (chr))

The above is unsafe though.  tree_expr_nonzero_p (chr) will return true
if say VRP can prove it is not zero, but because of the implicit
(char) chr cast done by the function we need something different.
Say if VRP determines that chr is in [1, INT_MAX] or even just [255, 257]
it doesn't mean (char) chr won't be 0.
So, as I've tried to explain in the previous mail, it can be done e.g. with
	      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)
		    {
		      chr_nonzero = true;
		      wide_int mask = wi::mask (CHAR_TYPE_SIZE, true,
						INT_TYPE_SIZE);
		      for (int 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)

	Jakub

[PATCH v3] tree-optimization/95821 - Convert strlen + strchr to memchr

[Noah Goldstein]

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

Re: [PATCH v2] tree-optimization/95821 - Convert strlen + strchr to memchr

[Noah Goldstein]

On Tue, Jun 21, 2022 at 5:01 AM Jakub Jelinek <jakub@redhat.com> wrote:
>
> On Mon, Jun 20, 2022 at 02:42:20PM -0700, Noah Goldstein 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.
> >
> > bootstrapped and tested on x86_64-linux.
> >
> >               PR tree-optimization/95821
>
> This should be indented by a single tab, not two.

Fixed in V3
> >
> > 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.
> > --- 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
>
> Still missing space before ( above.

Sorry, fixed that in V3.
>
> > +   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)));
>
> The indentation rule is that = should be 2 columns to the right from bool,
> so
>

Fixed in V3.
>   bool is_strchr_zerop
>     = (TREE_CODE (chr) == INTEGER_CST
>        && integer_zerop (fold_convert (char_type_node, chr)));
>
> > +           /* If its not strchr (s, zerop) then try and convert to
> > +                  memchr since strlen has already been computed.  */
>
> This comment still has the second line weirdly indented.

Sorry, have emacs with 4-space tabs so things that look right arent
as they seem :/

Fixed in V3 I believe.
>
> > +           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.  NB: We don't need to test if chr is a non-zero
> > +             integer const with zero char bits because that is taken into
> > +             account with is_strchr_zerop.  */
> > +           if (!tree_expr_nonzero_p (chr))
>
> The above is unsafe though.  tree_expr_nonzero_p (chr) will return true
> if say VRP can prove it is not zero, but because of the implicit
> (char) chr cast done by the function we need something different.
> Say if VRP determines that chr is in [1, INT_MAX] or even just [255, 257]
> it doesn't mean (char) chr won't be 0.
> So, as I've tried to explain in the previous mail, it can be done e.g. with

Added your code in V3. Thanks for the help.
>               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)
>                     {
>                       chr_nonzero = true;
>                       wide_int mask = wi::mask (CHAR_TYPE_SIZE, true,
>                                                 INT_TYPE_SIZE);
>                       for (int 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)
>
>         Jakub
>

Re: [PATCH v2] tree-optimization/95821 - Convert strlen + strchr to memchr

[Noah Goldstein]

On Tue, Jun 21, 2022 at 11:13 AM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> On Tue, Jun 21, 2022 at 5:01 AM Jakub Jelinek <jakub@redhat.com> wrote:
> >
> > On Mon, Jun 20, 2022 at 02:42:20PM -0700, Noah Goldstein 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.
> > >
> > > bootstrapped and tested on x86_64-linux.
> > >
> > >               PR tree-optimization/95821
> >
> > This should be indented by a single tab, not two.
>
> Fixed in V3
> > >
> > > 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.
> > > --- 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
> >
> > Still missing space before ( above.
>
> Sorry, fixed that in V3.
> >
> > > +   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)));
> >
> > The indentation rule is that = should be 2 columns to the right from bool,
> > so
> >
>
> Fixed in V3.
> >   bool is_strchr_zerop
> >     = (TREE_CODE (chr) == INTEGER_CST
> >        && integer_zerop (fold_convert (char_type_node, chr)));
> >
> > > +           /* If its not strchr (s, zerop) then try and convert to
> > > +                  memchr since strlen has already been computed.  */
> >
> > This comment still has the second line weirdly indented.
>
> Sorry, have emacs with 4-space tabs so things that look right arent
> as they seem :/
>
> Fixed in V3 I believe.
> >
> > > +           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.  NB: We don't need to test if chr is a non-zero
> > > +             integer const with zero char bits because that is taken into
> > > +             account with is_strchr_zerop.  */
> > > +           if (!tree_expr_nonzero_p (chr))
> >
> > The above is unsafe though.  tree_expr_nonzero_p (chr) will return true
> > if say VRP can prove it is not zero, but because of the implicit
> > (char) chr cast done by the function we need something different.
> > Say if VRP determines that chr is in [1, INT_MAX] or even just [255, 257]
> > it doesn't mean (char) chr won't be 0.
> > So, as I've tried to explain in the previous mail, it can be done e.g. with
>
> Added your code in V3. Thanks for the help.
> >               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)
> >                     {
> >                       chr_nonzero = true;
> >                       wide_int mask = wi::mask (CHAR_TYPE_SIZE, true,
> >                                                 INT_TYPE_SIZE);
> >                       for (int 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)
> >
> >         Jakub
> >

Ping 1

Re: [PATCH v3] tree-optimization/95821 - Convert strlen + strchr to memchr

[Jeff Law]

On 6/21/2022 12:12 PM, 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.
>
> 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.
Given Jakub's involvement to-date and the fact this touches 
tree-ssa-strlen.cc I think Jakub should have final ACK/NAK on this.

jeff

Re: [PATCH v3] tree-optimization/95821 - Convert strlen + strchr to memchr

[Noah Goldstein]

On Sat, Jul 9, 2022 at 8:59 AM Jeff Law via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
>
>
> On 6/21/2022 12:12 PM, 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.
> >
> > 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.
> Given Jakub's involvement to-date and the fact this touches
> tree-ssa-strlen.cc I think Jakub should have final ACK/NAK on this.
>
> jeff
>

Ping.

Re: [PATCH v3] tree-optimization/95821 - Convert strlen + strchr to memchr

[Jakub Jelinek]

On Tue, Jun 21, 2022 at 11:12:15AM -0700, Noah Goldstein 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.
> 
> 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.

Sorry for the delay.

> --- /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" } } */

Please don't scan assembler, whether memchr will expand
to a call or be expanded inline etc. is not known.
Better use "-O2 -fdump-tree-optimize" in dg-options
and scan the optimized dump for "memchr \\\(".
Ditto for other tests.

> @@ -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

-> s + t
rather than
-> t
actually.

> +	        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

nor instead of 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

must be always non-zero ?

> +		     have the INT_TYPE_SIZE - CHAR_TYPE_SIZE bits
> +		     the same on lower and upper bounds.  */

That is actually not enough, see below.

> +		  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);

Wrong indentation, = should be 2 columns left of wide_int.

> +		      for (unsigned i = 0; i < r.num_pairs (); ++i)
> +			if ((r.lower_bound (i) & mask)
> +			    != (r.upper_bound (i) & mask))
> +			  {
> +			    chr_nonzero = false;
> +			    break;
> +			  }

This else if actually can't do what it indends to, because
chr_nonzero is initialized to false at the start and in the loop you
also just set it to false, so it is always false.
You need to add chr_nonzero = true; before the for loop above.
With that, all the above test proves is that there is no range like
[15, 257] where it would include 256 in the middle of the range or
at the end.  But the above doesn't clear chr_nonzero on ranges like
[0, 32] or [256, 511] where (char) chr can still be zero.
So, the test should be:
			if ((r.lower_bound (i) & mask)
			    != (r.upper_bound (i) & mask)
			    || (r.lower_bound (i) & ~mask) == 0)
or so, that will rule out also the above ranges and if one just has ranges
like:
[1, 32] U [48, 56] U [257, 511]
all is fine, (char) chr is non-zero.

But this also shows that the testsuite coverage is insufficient because
nothing caught this.
I don't see almost any tests where the second argument to strchr would be
constant (ideally check for all of 0, ~0 & ~(unsigned char) ~0, ' ',
(~0 & ~(unsigned char) ~0) + ' ') - I see you have one test with
if (c != 0x100) return else strchr which effectively is strchr (, 0x100)
and one if (c != 0) return else strchr which has c range of ~[0, 0] with
which you can't do much (just can verify that we don't treat that as
(char) c can't be zero).  Beyond the tests with constant strchr arguments
(and I think you want to check in each case if there is
"= slen\[a-zA-Z.0-9_]* \\\+ 1;"
or not (and how many times if you e.g. stick more tests into one source
file, ideally all where you want the + 1 and in another one all that should
not have it)) it would be nice to have at least some tests where you
test the above problematic cases, say something like:
  if (c < 256)
    {
      if (c < 1 || c > 64)
	return ...;
    }
  else
    {
      if (c < 257 || c > 511)
	return ...;
    }
...
  strchr (..., c);
c above should be (needs to be verified in the debugger) [1, 64] U [257, 511]
and so chr_nonzero.  Similarly construct cases like [1, 32] U [48, 56] U [257, 511]
(chr_nonzero) or [0, 32] U [256, 511] (unknown whether c is zero or
non-zero) or [15, 257] (unknown too).

	Jakub