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

[Noah Goldstein <goldstein.w.n@gmail.com>]

This patch allows for strchr(x, c) to the replace with memchr(x, c,
strlen(x) + 1) if strlen(x) has already been computed earlier in the
tree.

Handles PR95821: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95821

Since memchr doesn't need to re-find the null terminator it is faster
than strchr.

bootstrapped and tested on x86_64-linux.

		PR tree-optimization/95821

gcc/

	* tree-ssa-strlen.cc (strlen_pass::handle_builtin_strchr): Emit
	memchr instead of strchr if strlen already computed.

gcc/testsuite/

	* c-c++-common/pr95821-1.c: New test.
	* c-c++-common/pr95821-2.c: New test.
	* c-c++-common/pr95821-3.c: New test.
	* c-c++-common/pr95821-4.c: New test.
	* c-c++-common/pr95821-5.c: New test.
	* c-c++-common/pr95821-6.c: New test.
	* c-c++-common/pr95821-7.c: New test.
	* c-c++-common/pr95821-8.c: New test.
---
 gcc/testsuite/c-c++-common/pr95821-1.c | 15 +++++
 gcc/testsuite/c-c++-common/pr95821-2.c | 17 +++++
 gcc/testsuite/c-c++-common/pr95821-3.c | 17 +++++
 gcc/testsuite/c-c++-common/pr95821-4.c | 16 +++++
 gcc/testsuite/c-c++-common/pr95821-5.c | 19 ++++++
 gcc/testsuite/c-c++-common/pr95821-6.c | 18 ++++++
 gcc/testsuite/c-c++-common/pr95821-7.c | 18 ++++++
 gcc/testsuite/c-c++-common/pr95821-8.c | 19 ++++++
 gcc/tree-ssa-strlen.cc                 | 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