Fold strstr (s, t) eq/ne s to strcmp (s, t) eq/ne 0 if strlen (t) is known

Message ID CAAgBjMnf0gMDhtR+8EJffHXOMO-FYpyci4BrjE4pWweC2-6bKA@mail.gmail.com
State New
Headers show

Commit Message

Prathamesh Kulkarni Dec. 14, 2016, 7:57 a.m.
On 13 December 2016 at 17:54, Jakub Jelinek <jakub@redhat.com> wrote:
> On Tue, Dec 13, 2016 at 05:41:09PM +0530, Prathamesh Kulkarni wrote:

>> --- a/gcc/tree-ssa-strlen.c

>> +++ b/gcc/tree-ssa-strlen.c

>> @@ -2222,6 +2222,90 @@ handle_char_store (gimple_stmt_iterator *gsi)

>>    return true;

>>  }

>>

>> +/* Try to fold strstr (s, t) eq/ne s to memcmp (s, t, strlen (t)) eq/ne 0.  */

>> +

>> +static void

>> +fold_strstr_to_memcmp (enum tree_code code, tree rhs1, tree rhs2, gimple *stmt)

>

> You can drop code argument here, see below.  And I'd say it is better to

> do the

>   if (TREE_CODE (rhs1) != SSA_NAME || TREE_CODE (rhs2) != SSA_NAME)

>     return;

> here than repeat it in all the callers.

>

>> +               if (gimple_assign_rhs_code (stmt) == COND_EXPR)

>> +                 {

>> +                   tree cond = gimple_assign_rhs1 (stmt);

>> +                   TREE_SET_CODE (cond, code);

>

> TREE_CODE (cond) is already code, so no need to set it again.

>

>> +               gcond *cond = as_a<gcond *> (stmt);

>> +               gimple_cond_set_lhs (cond, memcmp_lhs);

>> +               gimple_cond_set_rhs (cond, zero);

>> +               gimple_cond_set_code (cond, code);

>

> And gimple_cond_code (cond) == code here too.

>

>> +               update_stmt (cond);

>> +             }

>

> You can perhaps move the update_stmt (stmt); to a single spot after

> all the 3 cases are handled.

>

>> +         if (cond_code == EQ_EXPR || cond_code == NE_EXPR)

>> +           {

>> +             tree rhs1 = TREE_OPERAND (cond, 0);

>> +             tree rhs2 = TREE_OPERAND (cond, 1);

>

> While it is necessary to check cond_code here and in the other spots

> similarly, because otherwise you don't know if it has 2 arguments etc.,

> you can avoid the SSA_NAME tests here.

>

>> +             if (TREE_CODE (rhs1) == SSA_NAME

>> +                 && TREE_CODE (rhs2) == SSA_NAME)

>> +               fold_strstr_to_memcmp (cond_code, rhs1, rhs2, stmt);

>> +           }

>> +       }

>> +     else if (code == EQ_EXPR || code == NE_EXPR)

>> +       {

>> +         tree rhs1 = gimple_assign_rhs1 (stmt);

>> +         tree rhs2 = gimple_assign_rhs2 (stmt);

>> +

>> +         if (TREE_CODE (rhs1) == SSA_NAME

>> +             && TREE_CODE (rhs2) == SSA_NAME)

>

> And here.

>> +           fold_strstr_to_memcmp (code, rhs1, rhs2, stmt);

>> +       }

>> +      }

>> +    else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))

>>       {

>>         tree type = TREE_TYPE (lhs);

>>         if (TREE_CODE (type) == ARRAY_TYPE)

>> @@ -2316,6 +2427,17 @@ strlen_optimize_stmt (gimple_stmt_iterator *gsi)

>>           }

>>       }

>>      }

>> +  else if (gcond *cond = dyn_cast<gcond *> (stmt))

>> +    {

>> +      enum tree_code code = gimple_cond_code (cond);

>> +      tree lhs = gimple_cond_lhs (stmt);

>> +      tree rhs = gimple_cond_rhs (stmt);

>> +

>> +      if ((code == EQ_EXPR || code == NE_EXPR)

>> +       && TREE_CODE (lhs) == SSA_NAME

>> +       && TREE_CODE (rhs) == SSA_NAME)

>

> And here.

>> +     fold_strstr_to_memcmp (code, lhs, rhs, stmt);

>> +    }

>>

>>    if (gimple_vdef (stmt))

>>      maybe_invalidate (stmt);

>

> Otherwise LGTM, but it would be nice to cover also the COND_EXPR case by a

> testcase (can be done incrementally).

Hi Jakub,
Done the changes in attached version.
Bootstrap+tested on x86_64-unknown-linux-gnu with default languages
and cross-tested on arm*-*-*, aarch64*-*-* with c,c++,fortran.
It it OK to commit ?
I am trying to come up with COND_EXPR test-case.

Thanks,
Prathamesh
>

>         Jakub
2016-12-14  Jakub Jelinek  <jakub@redhat.com>
	    Prathamesh Kulkarni  <prathamesh.kulkarni@linaro.org>

	* tree-ssa-strlen.c (fold_strstr_to_memcmp): New function.
	(strlen_optimize_stmt): Call fold_strstr_to_memcmp.

testsuite/
	* gcc.dg/strlenopt-30.c: New test-case.

Comments

Jakub Jelinek Dec. 14, 2016, 8:03 a.m. | #1
On Wed, Dec 14, 2016 at 01:27:44PM +0530, Prathamesh Kulkarni wrote:
> 2016-12-14  Jakub Jelinek  <jakub@redhat.com>

> 	    Prathamesh Kulkarni  <prathamesh.kulkarni@linaro.org>

> 

> 	* tree-ssa-strlen.c (fold_strstr_to_memcmp): New function.

> 	(strlen_optimize_stmt): Call fold_strstr_to_memcmp.

> 

> testsuite/

> 	* gcc.dg/strlenopt-30.c: New test-case.


Ok, thanks.
But, you wrote the patch, so if you want to give me some credit, put
yourself first at least.

	Jakub
Martin Liška Jan. 23, 2017, 11:40 a.m. | #2
On 12/14/2016 09:03 AM, Jakub Jelinek wrote:
> On Wed, Dec 14, 2016 at 01:27:44PM +0530, Prathamesh Kulkarni wrote:

>> 2016-12-14  Jakub Jelinek  <jakub@redhat.com>

>> 	    Prathamesh Kulkarni  <prathamesh.kulkarni@linaro.org>

>>

>> 	* tree-ssa-strlen.c (fold_strstr_to_memcmp): New function.

>> 	(strlen_optimize_stmt): Call fold_strstr_to_memcmp.

>>

>> testsuite/

>> 	* gcc.dg/strlenopt-30.c: New test-case.

> 

> Ok, thanks.

> But, you wrote the patch, so if you want to give me some credit, put

> yourself first at least.

> 

> 	Jakub

> 


Caused PR79196.

Thanks,
Martin
Jakub Jelinek Jan. 23, 2017, 2:14 p.m. | #3
On Mon, Jan 23, 2017 at 02:58:05PM +0100, Martin Liška wrote:
> As mentioned in the PR, it should be valid to use strncmp instead of memcmp

> because first argument of a strstr can be shorter than a second (known) argument.

> 

> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

> 

> Ready to be installed?

> Martin


> >From 4a9dcb24d82ce1793a281710ce1ddab59f9dd7a8 Mon Sep 17 00:00:00 2001

> From: marxin <mliska@suse.cz>

> Date: Mon, 23 Jan 2017 13:18:37 +0100

> Subject: [PATCH] Fix strstr folding (PR tree-optimization/79196).

> 

> gcc/ChangeLog:

> 

> 2017-01-23  Martin Liska  <mliska@suse.cz>

> 

> 	* tree-ssa-strlen.c (fold_strstr_to_memcmp): Rename

> 	to fold_strstr_to_strncmp and fold the pattern to strncmp

> 	instead of memcmp.


Please write it as:
	PR tree-optimization/79196
	* tree-ssa-strlen.c (fold_strstr_to_memcmp): Rename to ...
	(fold_strstr_to_strncmp): ... this.  Fold the pattern to strncmp
	instead of memcmp.

> 	(strlen_optimize_stmt): Call the renamed function.

> 

> gcc/testsuite/ChangeLog:

> 

> 2017-01-23  Martin Liska  <mliska@suse.cz>

> 

> 	* gcc.dg/asan/pr79196.c: New test.

> 	* gcc.dg/strlenopt-30.c: Update scanned pattern.


Ok, thanks.

	Jakub

Patch hide | download patch | download mbox

diff --git a/gcc/testsuite/gcc.dg/strlenopt-30.c b/gcc/testsuite/gcc.dg/strlenopt-30.c
new file mode 100644
index 0000000..089b3a2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/strlenopt-30.c
@@ -0,0 +1,63 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-strlen" } */
+
+__attribute__((no_icf))
+_Bool f1(char *s)
+{
+  return __builtin_strstr (s, "hello") == s;
+}
+
+__attribute__((no_icf))
+_Bool f2(char *s)
+{
+  return s == __builtin_strstr (s, "hello");
+}
+
+__attribute__((no_icf))
+_Bool f3(char *s)
+{
+  return s != __builtin_strstr (s, "hello");
+}
+
+__attribute__((no_icf))
+_Bool f4()
+{
+  char *foo_f4(void);
+  char *t1 = foo_f4();
+  char *t2 = __builtin_strstr (t1, "hello");
+  _Bool t3 = t2 == t1;
+  return t3;
+}
+
+__attribute__((no_icf))
+void f5(char *s)
+{
+  char *t1 = __builtin_strstr (s, "hello");
+  void foo_f5(void);
+  if (t1 != s)
+    foo_f5();
+}
+
+/* Do not perform transform, since strlen (t)
+   is unknown.  */
+
+__attribute__((no_icf))
+_Bool f6(char *s, char *t)
+{
+  return __builtin_strstr (s, t) == s;
+}
+
+/* Do not perform transform in this case, since
+   t1 doesn't have single use.  */
+
+__attribute__((no_icf))
+_Bool f7(char *s)
+{
+  void foo_f7(char *);
+
+  char *t1 = __builtin_strstr (s, "hello");
+  foo_f7 (t1);
+  return (t1 == s);
+}
+
+/* { dg-final { scan-tree-dump-times "__builtin_memcmp" 5 "strlen" } } */
diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
index 339812e..67075f0 100644
--- a/gcc/tree-ssa-strlen.c
+++ b/gcc/tree-ssa-strlen.c
@@ -2222,6 +2222,90 @@  handle_char_store (gimple_stmt_iterator *gsi)
   return true;
 }
 
+/* Try to fold strstr (s, t) eq/ne s to memcmp (s, t, strlen (t)) eq/ne 0.  */
+
+static void
+fold_strstr_to_memcmp (tree rhs1, tree rhs2, gimple *stmt)
+{
+  if (TREE_CODE (rhs1) != SSA_NAME
+      || TREE_CODE (rhs2) != SSA_NAME)
+    return;
+
+  gimple *call_stmt = NULL;
+  for (int pass = 0; pass < 2; pass++)
+    {
+      gimple *g = SSA_NAME_DEF_STMT (rhs1);
+      if (gimple_call_builtin_p (g, BUILT_IN_STRSTR)
+	  && has_single_use (rhs1)
+	  && gimple_call_arg (g, 0) == rhs2)
+	{
+	  call_stmt = g;
+	  break;
+	}
+      std::swap (rhs1, rhs2);
+    }
+
+  if (call_stmt)
+    {
+      tree arg0 = gimple_call_arg (call_stmt, 0);
+
+      if (arg0 == rhs2)
+	{
+	  tree arg1 = gimple_call_arg (call_stmt, 1);
+	  tree arg1_len = NULL_TREE;
+	  int idx = get_stridx (arg1);
+
+	  if (idx)
+	    {
+	      if (idx < 0)
+		arg1_len = build_int_cst (size_type_node, ~idx);
+	      else
+		{
+		  strinfo *si = get_strinfo (idx);
+		  if (si)
+		    arg1_len = get_string_length (si);
+		}
+	    }
+
+	  if (arg1_len != NULL_TREE)
+	    {
+	      gimple_stmt_iterator gsi = gsi_for_stmt (call_stmt);
+	      tree memcmp_decl = builtin_decl_explicit (BUILT_IN_MEMCMP);
+	      gcall *memcmp_call = gimple_build_call (memcmp_decl, 3,
+						      arg0, arg1, arg1_len);
+	      tree memcmp_lhs = make_ssa_name (integer_type_node);
+	      gimple_set_vuse (memcmp_call, gimple_vuse (call_stmt));
+	      gimple_call_set_lhs (memcmp_call, memcmp_lhs);
+	      gsi_remove (&gsi, true);
+	      gsi_insert_before (&gsi, memcmp_call, GSI_SAME_STMT);
+	      tree zero = build_zero_cst (TREE_TYPE (memcmp_lhs));
+
+	      if (is_gimple_assign (stmt))
+		{
+		  if (gimple_assign_rhs_code (stmt) == COND_EXPR)
+		    {
+		      tree cond = gimple_assign_rhs1 (stmt);
+		      TREE_OPERAND (cond, 0) = memcmp_lhs;
+		      TREE_OPERAND (cond, 1) = zero;
+		    }
+		  else
+		    {
+		      gimple_assign_set_rhs1 (stmt, memcmp_lhs);
+		      gimple_assign_set_rhs2 (stmt, zero);
+		    }
+		}
+	      else
+		{
+		  gcond *cond = as_a<gcond *> (stmt);
+		  gimple_cond_set_lhs (cond, memcmp_lhs);
+		  gimple_cond_set_rhs (cond, zero);
+		}
+	      update_stmt (stmt);
+	    }
+	}
+    }
+}
+
 /* Attempt to optimize a single statement at *GSI using string length
    knowledge.  */
 
@@ -2302,7 +2386,23 @@  strlen_optimize_stmt (gimple_stmt_iterator *gsi)
 	  else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
 	    handle_pointer_plus (gsi);
 	}
-      else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
+    else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
+      {
+	enum tree_code code = gimple_assign_rhs_code (stmt);
+	if (code == COND_EXPR)
+	  {
+	    tree cond = gimple_assign_rhs1 (stmt);
+	    enum tree_code cond_code = TREE_CODE (cond);
+
+	    if (cond_code == EQ_EXPR || cond_code == NE_EXPR)
+	      fold_strstr_to_memcmp (TREE_OPERAND (cond, 0),
+				     TREE_OPERAND (cond, 1), stmt);
+	  }
+	else if (code == EQ_EXPR || code == NE_EXPR)
+	  fold_strstr_to_memcmp (gimple_assign_rhs1 (stmt),
+				 gimple_assign_rhs2 (stmt), stmt);
+      }
+    else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
 	{
 	  tree type = TREE_TYPE (lhs);
 	  if (TREE_CODE (type) == ARRAY_TYPE)
@@ -2316,6 +2416,13 @@  strlen_optimize_stmt (gimple_stmt_iterator *gsi)
 	    }
 	}
     }
+  else if (gcond *cond = dyn_cast<gcond *> (stmt))
+    {
+      enum tree_code code = gimple_cond_code (cond);
+      if (code == EQ_EXPR || code == NE_EXPR)
+	fold_strstr_to_memcmp (gimple_cond_lhs (stmt),
+			       gimple_cond_rhs (stmt), stmt);
+    }
 
   if (gimple_vdef (stmt))
     maybe_invalidate (stmt);