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

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

[Prathamesh Kulkarni]

[-- Attachment #1: Type: text/plain, Size: 862 bytes --]

Hi,
This patch folds strstr (s, t) eq/ne s to strcmp (s, t) eq/ne 0 if
strlen (t) is known.
One issue I came across was forwprop1 reverses the order of operands
in eq_expr below:

eg test-case:
_Bool f(char *s, int cond)
{
  char *t1 = __builtin_strstr (s, "hello");
  _Bool t2 = (t1 == s);
  return t2;
}

forwprop1 dump:
f (char * s, int cond)
{
  _Bool t2;
  char * t1;

  <bb 2> [0.0%]:
  t1_3 = __builtin_strstr (s_2(D), "hello");
  t2_4 = s_2(D) == t1_3;
  return t2_4;

}

So I had to check if SSA_NAME_DEF_STMT (rhs2) was call to strstr
rather than rhs1.
I suppose that's OK ?

clang unconditionally transforms
strstr (s, t) == s to strncmp (s, t, strlen (t))
However I am not sure what algorithm glibc's strstr uses, so didn't
attempt to transform
if strlen (t) is unknown. Should we do the transform even if strlen
(t) is unknown ?

Thanks,
Prathamesh

[-- Attachment #2: tcwg-701-2.txt --]
[-- Type: text/plain, Size: 3438 bytes --]

2016-12-05  Prathamesh Kulkarni  <prathamesh.kulkarni@linaro.org>

	* tree-ssa-strlen.c (strlen_optimize_stmt): Fold strstr(s, t) == s to
	strcmp (s, t) == 0.
	(pass_data_strlen): Set todo_flags_finish to TODO_update_ssa.

testsuite/
	* gcc.dg/strlenopt-30.c: New test-case.
diff --git a/gcc/testsuite/gcc.dg/strlenopt-30.c b/gcc/testsuite/gcc.dg/strlenopt-30.c
new file mode 100644
index 0000000..737f37d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/strlenopt-30.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-strlen" } */
+
+_Bool f1(char *s)
+{
+  char *t = "hello";
+  char *t1 = __builtin_strstr (s, t);
+  _Bool t2 = (t1 == s);
+  return t2;
+}
+
+_Bool f2(char *s)
+{
+  char *t = "hello";
+  char *t1 = __builtin_strstr (s, t);
+  _Bool t2 = (t1 != s);
+  return t2;
+}
+
+_Bool f3(char *s, char *t)
+{
+  char *t1 = __builtin_strstr (s, t);
+  _Bool t2 = (t1 == s);
+  return t2;
+}
+
+/* { dg-final { scan-tree-dump-times "__builtin_strcmp" 2 "strlen" } } */
diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
index 339812e..8977e80 100644
--- a/gcc/tree-ssa-strlen.c
+++ b/gcc/tree-ssa-strlen.c
@@ -2302,6 +2302,55 @@ strlen_optimize_stmt (gimple_stmt_iterator *gsi)
 	  else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
 	    handle_pointer_plus (gsi);
 	}
+
+      /* Fold strstr (s, t) == s to strcmp (s, t) == 0.  if strlen (t)
+	 is known.  */
+      else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
+	{
+	  enum tree_code code = gimple_assign_rhs_code (stmt);
+	  if (code == EQ_EXPR || code == NE_EXPR)
+	    {
+	      tree rhs1 = gimple_assign_rhs1 (stmt);
+	      tree rhs2 = gimple_assign_rhs2 (stmt);
+	      if (TREE_CODE (rhs2) == SSA_NAME)
+		{
+		  gcall *call_stmt = dyn_cast<gcall *> (SSA_NAME_DEF_STMT (rhs2));
+		  if (call_stmt
+		      && gimple_call_builtin_p (call_stmt, BUILT_IN_STRSTR))
+		    {
+		      tree arg0 = gimple_call_arg (call_stmt, 0);
+		      if (operand_equal_p (arg0, rhs1, 0))
+			{
+			  /* Check if strlen(arg1) is known.  */
+			  tree arg1 = gimple_call_arg (call_stmt, 1);
+			  int idx = get_stridx (arg1);
+			  strinfo *si = NULL;
+			  if (idx)
+			    si = get_strinfo (idx);
+			  if ((idx < 0)
+			      || (si && (get_string_length (si) != NULL_TREE)))
+			    {
+			      gimple_stmt_iterator gsi = gsi_for_stmt (call_stmt);
+			      tree strcmp_decl = builtin_decl_explicit (BUILT_IN_STRCMP);
+			      gcall *strcmp_call = gimple_build_call (strcmp_decl, 2,
+								      arg0, arg1);
+			      tree strcmp_lhs = make_ssa_name (integer_type_node);
+			      gimple_call_set_lhs (strcmp_call, strcmp_lhs);
+			      update_stmt (strcmp_call);
+			      gsi_remove (&gsi, true);
+			      gsi_insert_before (&gsi, strcmp_call, GSI_SAME_STMT);
+
+			      gsi = gsi_for_stmt (stmt);
+			      tree zero = build_zero_cst (TREE_TYPE (strcmp_lhs));
+			      gassign *ga = gimple_build_assign (lhs, code,
+							strcmp_lhs, zero);
+			      gsi_replace (&gsi, ga, false);
+			    }
+			}
+		    }
+		}
+	    }
+	}
       else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
 	{
 	  tree type = TREE_TYPE (lhs);
@@ -2505,7 +2554,7 @@ const pass_data pass_data_strlen =
   0, /* properties_provided */
   0, /* properties_destroyed */
   0, /* todo_flags_start */
-  0, /* todo_flags_finish */
+  TODO_update_ssa, /* todo_flags_finish */
 };
 
 class pass_strlen : public gimple_opt_pass

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

[Bernd Schmidt]

On 12/05/2016 07:02 PM, Prathamesh Kulkarni wrote:
> This patch folds strstr (s, t) eq/ne s to strcmp (s, t) eq/ne 0 if
> strlen (t) is known.

That's not the same thing, is it?

s = "hello world", t = "hello":
   strstr (s, t) == s, but not strcmp (s, t) == 0.

I think you'd want memcmp (s, t, strlen (t)) == 0.


Bernd

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

[Prathamesh Kulkarni]

On 5 December 2016 at 23:38, Bernd Schmidt <bschmidt@redhat.com> wrote:
> On 12/05/2016 07:02 PM, Prathamesh Kulkarni wrote:
>>
>> This patch folds strstr (s, t) eq/ne s to strcmp (s, t) eq/ne 0 if
>> strlen (t) is known.
>
>
> That's not the same thing, is it?
>
> s = "hello world", t = "hello":
>   strstr (s, t) == s, but not strcmp (s, t) == 0.
>
> I think you'd want memcmp (s, t, strlen (t)) == 0.
Ah indeed! Dunno why I thought strstr (s, t) == strcmp (s, t) :(
Thanks for pointing out!
>
>
> Bernd
>

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

[Prathamesh Kulkarni]

On 5 December 2016 at 23:40, Prathamesh Kulkarni
<prathamesh.kulkarni@linaro.org> wrote:
> On 5 December 2016 at 23:38, Bernd Schmidt <bschmidt@redhat.com> wrote:
>> On 12/05/2016 07:02 PM, Prathamesh Kulkarni wrote:
>>>
>>> This patch folds strstr (s, t) eq/ne s to strcmp (s, t) eq/ne 0 if
>>> strlen (t) is known.
>>
>>
>> That's not the same thing, is it?
>>
>> s = "hello world", t = "hello":
>>   strstr (s, t) == s, but not strcmp (s, t) == 0.
>>
>> I think you'd want memcmp (s, t, strlen (t)) == 0.
> Ah indeed! Dunno why I thought strstr (s, t) == strcmp (s, t) :(
Err, I meant strstr(s, t) == s to strcmp(s, t) == 0.
I will send a patch to fold strstr (s, t) to memcmp (s, t, strlen (t)) == 0.
Thanks for the suggestions.

Regards,
Prathamesh
> Thanks for pointing out!
>>
>>
>> Bernd
>>

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

[Jakub Jelinek]

On Mon, Dec 05, 2016 at 11:32:15PM +0530, Prathamesh Kulkarni wrote:
> So I had to check if SSA_NAME_DEF_STMT (rhs2) was call to strstr
> rather than rhs1.

Then you need to test both whether it is strstr (s, t) == s or
s == strstr (s, t).

> +			      gassign *ga = gimple_build_assign (lhs, code,
> +							strcmp_lhs, zero);

The formatting is wrong here.

> +			      gsi_replace (&gsi, ga, false);
> +			    }
> +			}
> +		    }
> +		}
> +	    }
> +	}
>        else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
>  	{
>  	  tree type = TREE_TYPE (lhs);
> @@ -2505,7 +2554,7 @@ const pass_data pass_data_strlen =
>    0, /* properties_provided */
>    0, /* properties_destroyed */
>    0, /* todo_flags_start */
> -  0, /* todo_flags_finish */
> +  TODO_update_ssa, /* todo_flags_finish */

No, please don't.  Just make sure to build proper SSA right away.

	Jakub

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

[Prathamesh Kulkarni]

[-- Attachment #1: Type: text/plain, Size: 1398 bytes --]

On 5 December 2016 at 23:47, Jakub Jelinek <jakub@redhat.com> wrote:
> On Mon, Dec 05, 2016 at 11:32:15PM +0530, Prathamesh Kulkarni wrote:
>> So I had to check if SSA_NAME_DEF_STMT (rhs2) was call to strstr
>> rather than rhs1.
>
> Then you need to test both whether it is strstr (s, t) == s or
> s == strstr (s, t).
>
>> +                           gassign *ga = gimple_build_assign (lhs, code,
>> +                                                     strcmp_lhs, zero);
>
> The formatting is wrong here.
>
>> +                           gsi_replace (&gsi, ga, false);
>> +                         }
>> +                     }
>> +                 }
>> +             }
>> +         }
>> +     }
>>        else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
>>       {
>>         tree type = TREE_TYPE (lhs);
>> @@ -2505,7 +2554,7 @@ const pass_data pass_data_strlen =
>>    0, /* properties_provided */
>>    0, /* properties_destroyed */
>>    0, /* todo_flags_start */
>> -  0, /* todo_flags_finish */
>> +  TODO_update_ssa, /* todo_flags_finish */
>
> No, please don't.  Just make sure to build proper SSA right away.
Hi,
Thanks for the suggestions, I have tried to modify the patch accordingly.
Does this version look OK ?
Bootstrap+tested on x86_64-unknown-linux-gnu with --enable-languages=all,ada
Cross tested on arm*-*-*, aarch64*-*-*.

Thanks,
Prathamesh
>
>         Jakub

[-- Attachment #2: tcwg-701-5.txt --]
[-- Type: text/plain, Size: 4900 bytes --]

2016-12-07  Prathamesh Kulkarni  <prathamesh.kulkarni@linaro.org>

	* tree-ssa-strlen.c (strlen_optimize_stmt): Fold strstr(s, t) == s to
	memcmp (s, t, strlen (t)) == 0.
	Include tree-into-ssa.h.

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

diff --git a/gcc/testsuite/gcc.dg/strlenopt-30.c b/gcc/testsuite/gcc.dg/strlenopt-30.c
new file mode 100644
index 0000000..603e23c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/strlenopt-30.c
@@ -0,0 +1,42 @@
+/* { 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 *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 f5(char *s, char *t)
+{
+  void foo(char *);
+
+  char *t1 = __builtin_strstr (s, t);
+  foo (t1);
+  return (t1 == s);
+}
+
+/* { dg-final { scan-tree-dump-times "__builtin_memcmp" 4 "strlen" } } */
+/* { dg-final { scan-tree-dump-times "__builtin_strlen" 1 "strlen" } } */
diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
index 339812e..b7f4cee 100644
--- a/gcc/tree-ssa-strlen.c
+++ b/gcc/tree-ssa-strlen.c
@@ -45,6 +45,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "ipa-chkp.h"
 #include "tree-hash-traits.h"
 #include "builtins.h"
+#include "tree-into-ssa.h"
 
 /* A vector indexed by SSA_NAME_VERSION.  0 means unknown, positive value
    is an index into strinfo vector, negative value stands for
@@ -2302,7 +2303,94 @@ 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))
+
+      /* Fold strstr (s, t) == s to memcmp (s, t, strlen (t)) == 0.
+	 if var holding return value of strstr has single use.  */
+
+      else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
+	{
+	  enum tree_code code = gimple_assign_rhs_code (stmt);
+	  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)
+		{
+		  gcall *call_stmt = dyn_cast<gcall *> (SSA_NAME_DEF_STMT (rhs1));
+		  if (!call_stmt)
+		    {
+		      call_stmt = dyn_cast<gcall *> (SSA_NAME_DEF_STMT (rhs2));
+		      tree tmp = rhs1;
+		      rhs1 = rhs2;
+		      rhs2 = tmp;
+		    }
+
+		  tree call_lhs;
+		  if (call_stmt
+		      && gimple_call_builtin_p (call_stmt, BUILT_IN_STRSTR)
+		      && (call_lhs = gimple_call_lhs (call_stmt))
+		      && has_single_use (call_lhs))
+		    {
+		      tree arg0 = gimple_call_arg (call_stmt, 0);
+		      if (operand_equal_p (arg0, rhs2, 0))
+			{
+			  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;
+			      tree strlen_decl;
+			      gimple *strlen_call;
+
+			      strlen_decl = builtin_decl_explicit (BUILT_IN_STRLEN);
+			      strlen_call = gimple_build_call (strlen_decl, 1,
+							       arg1);
+			      arg1_len = make_ssa_name (size_type_node);
+			      gimple_call_set_lhs (strlen_call, arg1_len);
+			      update_stmt (strlen_call);
+			      gsi = gsi_for_stmt (call_stmt);
+			      gsi_insert_before (&gsi, strlen_call, GSI_SAME_STMT);
+			    }
+
+			  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_call_set_lhs (memcmp_call, memcmp_lhs);
+			  update_stmt (memcmp_call);
+			  gsi_remove (&gsi, true);
+			  gsi_insert_before (&gsi, memcmp_call, GSI_SAME_STMT);
+
+			  gsi = gsi_for_stmt (stmt);
+			  tree zero = build_zero_cst (TREE_TYPE (memcmp_lhs));
+			  gassign *ga = gimple_build_assign (lhs, code,
+							     memcmp_lhs, zero);
+			  gsi_replace (&gsi, ga, false);
+			  update_ssa (TODO_update_ssa);
+			}
+		    }
+		}
+	    }
+	}
+    else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
 	{
 	  tree type = TREE_TYPE (lhs);
 	  if (TREE_CODE (type) == ARRAY_TYPE)

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

[Jakub Jelinek]

On Wed, Dec 07, 2016 at 05:02:46PM +0530, Prathamesh Kulkarni wrote:
> +			  if (arg1_len == NULL_TREE)
> +			    {
> +			      gimple_stmt_iterator gsi;
> +			      tree strlen_decl;
> +			      gimple *strlen_call;
> +
> +			      strlen_decl = builtin_decl_explicit (BUILT_IN_STRLEN);
> +			      strlen_call = gimple_build_call (strlen_decl, 1,
> +							       arg1);
> +			      arg1_len = make_ssa_name (size_type_node);
> +			      gimple_call_set_lhs (strlen_call, arg1_len);
> +			      update_stmt (strlen_call);
> +			      gsi = gsi_for_stmt (call_stmt);
> +			      gsi_insert_before (&gsi, strlen_call, GSI_SAME_STMT);
> +			    }

Why?  If the strlen isn't readily available, do you really think it is
always a win to replace one call with 2 calls?  The string you want to do
strlen on can be huge, the haystack could be empty or very short, etc.
I'd just punt if strlen isn't known.
> +
> +			  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_call_set_lhs (memcmp_call, memcmp_lhs);
> +			  update_stmt (memcmp_call);
> +			  gsi_remove (&gsi, true);
> +			  gsi_insert_before (&gsi, memcmp_call, GSI_SAME_STMT);
> +
> +			  gsi = gsi_for_stmt (stmt);
> +			  tree zero = build_zero_cst (TREE_TYPE (memcmp_lhs));
> +			  gassign *ga = gimple_build_assign (lhs, code,
> +							     memcmp_lhs, zero);
> +			  gsi_replace (&gsi, ga, false);
> +			  update_ssa (TODO_update_ssa);

And this is certainly even more wrong than the old TODO_update_ssa at the
end of the pass, now you'll do it for every single replacement in the
function.  Why do you need it?  The old call stmt has gimple_vdef and
gimple_vuse, so just copy those over, see how e.g.
replace_call_with_call_and_fold in gimple-fold.c does that.
If you don't add strlen, you need to move the vdef/vuse from stmt to
memcmp_call, if you really want to add strlen (see above note though),
then that call should have a vuse added (same vuse as the stmt originally
had).

	Jakub

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

[Prathamesh Kulkarni]

[-- Attachment #1: Type: text/plain, Size: 3464 bytes --]

On 7 December 2016 at 17:36, Jakub Jelinek <jakub@redhat.com> wrote:
> On Wed, Dec 07, 2016 at 05:02:46PM +0530, Prathamesh Kulkarni wrote:
>> +                       if (arg1_len == NULL_TREE)
>> +                         {
>> +                           gimple_stmt_iterator gsi;
>> +                           tree strlen_decl;
>> +                           gimple *strlen_call;
>> +
>> +                           strlen_decl = builtin_decl_explicit (BUILT_IN_STRLEN);
>> +                           strlen_call = gimple_build_call (strlen_decl, 1,
>> +                                                            arg1);
>> +                           arg1_len = make_ssa_name (size_type_node);
>> +                           gimple_call_set_lhs (strlen_call, arg1_len);
>> +                           update_stmt (strlen_call);
>> +                           gsi = gsi_for_stmt (call_stmt);
>> +                           gsi_insert_before (&gsi, strlen_call, GSI_SAME_STMT);
>> +                         }
>
> Why?  If the strlen isn't readily available, do you really think it is
> always a win to replace one call with 2 calls?  The string you want to do
> strlen on can be huge, the haystack could be empty or very short, etc.
> I'd just punt if strlen isn't known.
>> +
>> +                       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_call_set_lhs (memcmp_call, memcmp_lhs);
>> +                       update_stmt (memcmp_call);
>> +                       gsi_remove (&gsi, true);
>> +                       gsi_insert_before (&gsi, memcmp_call, GSI_SAME_STMT);
>> +
>> +                       gsi = gsi_for_stmt (stmt);
>> +                       tree zero = build_zero_cst (TREE_TYPE (memcmp_lhs));
>> +                       gassign *ga = gimple_build_assign (lhs, code,
>> +                                                          memcmp_lhs, zero);
>> +                       gsi_replace (&gsi, ga, false);
>> +                       update_ssa (TODO_update_ssa);
>
> And this is certainly even more wrong than the old TODO_update_ssa at the
> end of the pass, now you'll do it for every single replacement in the
> function.  Why do you need it?  The old call stmt has gimple_vdef and
> gimple_vuse, so just copy those over, see how e.g.
> replace_call_with_call_and_fold in gimple-fold.c does that.
> If you don't add strlen, you need to move the vdef/vuse from stmt to
> memcmp_call, if you really want to add strlen (see above note though),
> then that call should have a vuse added (same vuse as the stmt originally
> had).
Hi,
Thanks for the suggestions. In attached patch, I dropped the transform
if strlen (t) is unknown.
Since strstr is marked pure, so IIUC call_stmt for strstr shouldn't
have vdef assoicated with it ?
(gimple_vdef for call_stmt returned NULL for test-cases I tried it
with). Moving gimple_vuse
from call_stmt to memcmp_call worked for me.
Does the patch look OK ?
Bootstrap+tested on x86_64-unknown-linux-gnu with --enable-langauges=all,ada
Cross-tested on arm*-*-*, aarch64*-*-*.

Thanks,
Prathamesh
>
>         Jakub

[-- Attachment #2: tcwg-701-7.diff --]
[-- Type: text/plain, Size: 3904 bytes --]

diff --git a/gcc/testsuite/gcc.dg/strlenopt-30.c b/gcc/testsuite/gcc.dg/strlenopt-30.c
new file mode 100644
index 0000000..329bc25
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/strlenopt-30.c
@@ -0,0 +1,44 @@
+/* { 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");
+}
+
+/* Do not perform transform, since strlen (t)
+   is unknown.  */
+
+__attribute__((no_icf))
+_Bool f4(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 f5(char *s)
+{
+  void foo(char *);
+
+  char *t1 = __builtin_strstr (s, "hello");
+  foo (t1);
+  return (t1 == s);
+}
+
+/* { dg-final { scan-tree-dump-times "__builtin_memcmp" 3 "strlen" } } */
diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
index 339812e..06b07b0 100644
--- a/gcc/tree-ssa-strlen.c
+++ b/gcc/tree-ssa-strlen.c
@@ -2302,7 +2302,81 @@ 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))
+
+      /* Fold strstr (s, t) == s to memcmp (s, t, strlen (t)) == 0.
+	 if strlen (t) is known and var holding return value of strstr
+	 has single use.  */
+
+      else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
+	{
+	  enum tree_code code = gimple_assign_rhs_code (stmt);
+	  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)
+		{
+		  gcall *call_stmt = dyn_cast<gcall *> (SSA_NAME_DEF_STMT (rhs1));
+		  if (!call_stmt)
+		    {
+		      call_stmt = dyn_cast<gcall *> (SSA_NAME_DEF_STMT (rhs2));
+		      tree tmp = rhs1;
+		      rhs1 = rhs2;
+		      rhs2 = tmp;
+		    }
+
+		  tree call_lhs;
+		  if (call_stmt
+		      && gimple_call_builtin_p (call_stmt, BUILT_IN_STRSTR)
+		      && (call_lhs = gimple_call_lhs (call_stmt))
+		      && has_single_use (call_lhs))
+		    {
+		      tree arg0 = gimple_call_arg (call_stmt, 0);
+		      if (operand_equal_p (arg0, rhs2, 0))
+			{
+			  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);
+			      gsi = gsi_for_stmt (stmt);
+			      tree zero = build_zero_cst (TREE_TYPE (memcmp_lhs));
+			      gassign *ga = gimple_build_assign (lhs, code,
+								 memcmp_lhs,
+								 zero);
+			      gsi_replace (&gsi, ga, false);
+			    }
+			}
+		    }
+		}
+	    }
+	}
+    else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
 	{
 	  tree type = TREE_TYPE (lhs);
 	  if (TREE_CODE (type) == ARRAY_TYPE)

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

[Jakub Jelinek]

On Fri, Dec 09, 2016 at 05:36:41PM +0530, Prathamesh Kulkarni wrote:
> --- a/gcc/tree-ssa-strlen.c
> +++ b/gcc/tree-ssa-strlen.c
> @@ -2302,7 +2302,81 @@ 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))
> +
> +      /* Fold strstr (s, t) == s to memcmp (s, t, strlen (t)) == 0.
> +	 if strlen (t) is known and var holding return value of strstr
> +	 has single use.  */
> +
> +      else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
> +	{
> +	  enum tree_code code = gimple_assign_rhs_code (stmt);
> +	  if (code == EQ_EXPR || code == NE_EXPR)

This way you handle _8 = _5 == _7;, but not if (_5 == _7) bar ();.  Shouldn't you
also handle GIMPLE_COND similarly (of course, the rhs1 and rhs2 grabbing
and code grabbing is different for GIMPLE_COND.  But the rest should be
the same, except again that you don't want to replace the GIMPLE_COND, but
adjust it.  Maybe also COND_EXPR in gimple_assign (_9 = _5 == _7 ? _10 : _11;).

> +	    {
> +	      tree rhs1 = gimple_assign_rhs1 (stmt);
> +	      tree rhs2 = gimple_assign_rhs2 (stmt);
> +	      if (TREE_CODE (rhs1) == SSA_NAME
> +		  && TREE_CODE (rhs2) == SSA_NAME)
> +		{
> +		  gcall *call_stmt = dyn_cast<gcall *> (SSA_NAME_DEF_STMT (rhs1));
> +		  if (!call_stmt)
> +		    {
> +		      call_stmt = dyn_cast<gcall *> (SSA_NAME_DEF_STMT (rhs2));
> +		      tree tmp = rhs1;
> +		      rhs1 = rhs2;
> +		      rhs2 = tmp;

We use std::swap (rhs1, rhs2); in this case these days.

> +		    }
> +
> +		  tree call_lhs;
> +		  if (call_stmt
> +		      && gimple_call_builtin_p (call_stmt, BUILT_IN_STRSTR)
> +		      && (call_lhs = gimple_call_lhs (call_stmt))
> +		      && has_single_use (call_lhs))

This might not optimize if you have:
  _5 = foo ();
  _7 = __builtin_strstr (_5, "abcd");
  _8 = _5 == _7;

Or even you could have:
  _5 = __builtin_strstr (...);
  _7 = __builtin_strstr (_5, "abcd");
  _8 = _5 == _7;

So I wonder if you shouldn't do:
		  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)
			  && gimple_call_lhs (g) == rhs1
			  && has_single_use (rhs1)
			  && gimple_call_arg (g, 0) == rhs2)
			{
			  call_stmt = g;
			  break;
			}
		      std::swap (rhs1, rhs2);
		    }
		  if (call_stmt)
...

I think you don't need operand_equal_p, because SSA_NAMEs should just
be the same pointer if they are the same thing.
The above way you handle both orderings.  Perhaps also it is big enough to
be done in a separate function, which you call with the code/rhs1/rhs2 and
stmt for the EQ/NE_EXPR is_gimple_assign as well as for COND_EXPR and
GIMPLE_COND.

	Jakub

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

[Prathamesh Kulkarni]

[-- Attachment #1: Type: text/plain, Size: 4284 bytes --]

On 9 December 2016 at 17:59, Jakub Jelinek <jakub@redhat.com> wrote:
> On Fri, Dec 09, 2016 at 05:36:41PM +0530, Prathamesh Kulkarni wrote:
>> --- a/gcc/tree-ssa-strlen.c
>> +++ b/gcc/tree-ssa-strlen.c
>> @@ -2302,7 +2302,81 @@ 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))
>> +
>> +      /* Fold strstr (s, t) == s to memcmp (s, t, strlen (t)) == 0.
>> +      if strlen (t) is known and var holding return value of strstr
>> +      has single use.  */
>> +
>> +      else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
>> +     {
>> +       enum tree_code code = gimple_assign_rhs_code (stmt);
>> +       if (code == EQ_EXPR || code == NE_EXPR)
>
> This way you handle _8 = _5 == _7;, but not if (_5 == _7) bar ();.  Shouldn't you
> also handle GIMPLE_COND similarly (of course, the rhs1 and rhs2 grabbing
> and code grabbing is different for GIMPLE_COND.  But the rest should be
> the same, except again that you don't want to replace the GIMPLE_COND, but
> adjust it.  Maybe also COND_EXPR in gimple_assign (_9 = _5 == _7 ? _10 : _11;).
>
>> +         {
>> +           tree rhs1 = gimple_assign_rhs1 (stmt);
>> +           tree rhs2 = gimple_assign_rhs2 (stmt);
>> +           if (TREE_CODE (rhs1) == SSA_NAME
>> +               && TREE_CODE (rhs2) == SSA_NAME)
>> +             {
>> +               gcall *call_stmt = dyn_cast<gcall *> (SSA_NAME_DEF_STMT (rhs1));
>> +               if (!call_stmt)
>> +                 {
>> +                   call_stmt = dyn_cast<gcall *> (SSA_NAME_DEF_STMT (rhs2));
>> +                   tree tmp = rhs1;
>> +                   rhs1 = rhs2;
>> +                   rhs2 = tmp;
>
> We use std::swap (rhs1, rhs2); in this case these days.
>
>> +                 }
>> +
>> +               tree call_lhs;
>> +               if (call_stmt
>> +                   && gimple_call_builtin_p (call_stmt, BUILT_IN_STRSTR)
>> +                   && (call_lhs = gimple_call_lhs (call_stmt))
>> +                   && has_single_use (call_lhs))
>
> This might not optimize if you have:
>   _5 = foo ();
>   _7 = __builtin_strstr (_5, "abcd");
>   _8 = _5 == _7;
>
> Or even you could have:
>   _5 = __builtin_strstr (...);
>   _7 = __builtin_strstr (_5, "abcd");
>   _8 = _5 == _7;
>
> So I wonder if you shouldn't do:
>                   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)
>                           && gimple_call_lhs (g) == rhs1
>                           && has_single_use (rhs1)
>                           && gimple_call_arg (g, 0) == rhs2)
>                         {
>                           call_stmt = g;
>                           break;
>                         }
>                       std::swap (rhs1, rhs2);
>                     }
>                   if (call_stmt)
> ...
>
> I think you don't need operand_equal_p, because SSA_NAMEs should just
> be the same pointer if they are the same thing.
> The above way you handle both orderings.  Perhaps also it is big enough to
> be done in a separate function, which you call with the code/rhs1/rhs2 and
> stmt for the EQ/NE_EXPR is_gimple_assign as well as for COND_EXPR and
> GIMPLE_COND.
Hi Jakub,
Thanks for the suggestions. It didn't occur to me to check for gimple_cond.
I have tried to do the changes in the attached version.
I am not sure if I have handled cond_expr correctly.
IIUC, if gimple_assign has code cond_expr, then the condition is
stored in gimple_assign_rhs1,
however it's not a single operand but a tree of the form "op1 cond_code op2".
Is that correct ?

However I am not able to write a test-case that generates cond_expr in the IL.
I tried:
t1 = strstr (s, t);
(t1 == s)  ? foo() : bar ();
and other such variants but it seems the ?: operator is getting
lowered to gimple_cond instead.

Bootstrap+tested on x86_64-unknown-linux-gnu
and cross-tested on arm*-*-*, aarch64*-*-*.
Does it look OK ?

Thanks,
Prathamesh
>
>         Jakub

[-- Attachment #2: tcwg-701-9.txt --]
[-- Type: text/plain, Size: 6124 bytes --]

2016-12-13  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.

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..a4a0ae1 100644
--- a/gcc/tree-ssa-strlen.c
+++ b/gcc/tree-ssa-strlen.c
@@ -2222,6 +2222,93 @@ handle_char_store (gimple_stmt_iterator *gsi)
   return true;
 }
 
+/* Try to fold strstr (s, t) == s to memcmp (s, t, strlen (t)) == 0.  */
+
+static void
+fold_strstr_to_memcmp(enum tree_code code, tree rhs1, tree rhs2, gimple *stmt)
+{
+  gimple *call_stmt = NULL;
+  for (int pass = 0; pass < 2; pass++)
+    {
+      gimple *g = SSA_NAME_DEF_STMT (rhs1);
+      if (g
+	  && gimple_call_builtin_p (g, BUILT_IN_STRSTR)
+	  && has_single_use (rhs1)
+	  && gimple_call_arg (as_a<gcall *> (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_SET_CODE (cond, EQ_EXPR);
+		      TREE_OPERAND (cond, 0) = memcmp_lhs;
+		      TREE_OPERAND (cond, 1) = zero;
+		      update_stmt (stmt);
+		    }
+		  else
+		    {
+		      gsi = gsi_for_stmt (stmt);
+		      tree lhs = gimple_assign_lhs (stmt);
+		      gassign *ga = gimple_build_assign (lhs, code, memcmp_lhs,
+							 zero);
+		      gsi_replace (&gsi, ga, false);
+		    }
+		}
+	      else
+		{
+		  gcond *cond = as_a<gcond *> (stmt);
+		  gimple_cond_set_lhs (cond, memcmp_lhs);
+		  gimple_cond_set_rhs (cond, zero);
+		  gimple_cond_set_code (cond, EQ_EXPR);
+		  update_stmt (cond);
+		}
+	    }
+	}
+    }
+}
+
 /* Attempt to optimize a single statement at *GSI using string length
    knowledge.  */
 
@@ -2302,7 +2389,34 @@ 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)
+	      {
+		tree rhs1 = TREE_OPERAND (cond, 0);
+		tree rhs2 = TREE_OPERAND (cond, 1);
+		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)
+	      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 +2430,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)
+	fold_strstr_to_memcmp (code, lhs, rhs, stmt);
+    }
 
   if (gimple_vdef (stmt))
     maybe_invalidate (stmt);

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

[Jakub Jelinek]

On Tue, Dec 13, 2016 at 03:08:17PM +0530, Prathamesh Kulkarni wrote:
> Thanks for the suggestions. It didn't occur to me to check for gimple_cond.
> I have tried to do the changes in the attached version.
> I am not sure if I have handled cond_expr correctly.
> IIUC, if gimple_assign has code cond_expr, then the condition is
> stored in gimple_assign_rhs1,
> however it's not a single operand but a tree of the form "op1 cond_code op2".
> Is that correct ?

Yes.  gimple_assign_rhs1 will be in what you are looking for EQ_EXPR or
NE_EXPR tree, its TREE_CODE will be this code you want to check, and
TREE_OPERAND (exp, 0) and TREE_OPERAND (exp, 1) the rhs1 and rhs2 you use
elsewhere.

> However I am not able to write a test-case that generates cond_expr in the IL.
> I tried:
> t1 = strstr (s, t);
> (t1 == s)  ? foo() : bar ();
> and other such variants but it seems the ?: operator is getting
> lowered to gimple_cond instead.

It is, but in some cases tree-if-conv.c turns them back into COND_EXPRs.
I guess you need -ftree-loop-if-convert now, and it has to be in some loop
where the addition of cond_expr would likely turn it into a single bb loop.
You probably want constants or vars, not function calls in the ? :
expressions though.

> +/* Try to fold strstr (s, t) == s to memcmp (s, t, strlen (t)) == 0.  */
> +
> +static void
> +fold_strstr_to_memcmp(enum tree_code code, tree rhs1, tree rhs2, gimple *stmt)

Formatting, space before (.

> +{
> +  gimple *call_stmt = NULL;
> +  for (int pass = 0; pass < 2; pass++)
> +    {
> +      gimple *g = SSA_NAME_DEF_STMT (rhs1);
> +      if (g

I think g should be always non-NULL (except for invalid IL), so probably no
need to check it.

> +	  && gimple_call_builtin_p (g, BUILT_IN_STRSTR)
> +	  && has_single_use (rhs1)
> +	  && gimple_call_arg (as_a<gcall *> (g), 0) == rhs2)

I think gimple_call_arg works fine even with just gimple * argument.
So you can avoid the as_a<gcall *> (g) uglification and just use g.

> +	      if (is_gimple_assign (stmt))
> +		{
> +		  if (gimple_assign_rhs_code (stmt) == COND_EXPR)
> +		    {
> +		      tree cond = gimple_assign_rhs1 (stmt);
> +		      TREE_SET_CODE (cond, EQ_EXPR);

This looks weird.  You are hardcoding EQ_EXPR, while for the
other case below you use code.  So, do you handle properly both
EQ_EXPR and NE_EXPR for this and gimple_cond cases?
Also, for non-COND_EXPR assign you build a new stmt instead of reusing
the existing one, why?

> +		      TREE_OPERAND (cond, 0) = memcmp_lhs;
> +		      TREE_OPERAND (cond, 1) = zero;
> +		      update_stmt (stmt);
> +		    }
> +		  else
> +		    {
> +		      gsi = gsi_for_stmt (stmt);
> +		      tree lhs = gimple_assign_lhs (stmt);
> +		      gassign *ga = gimple_build_assign (lhs, code, memcmp_lhs,
> +							 zero);
> +		      gsi_replace (&gsi, ga, false);
> +		    }
> +		}
> +	      else
> +		{
> +		  gcond *cond = as_a<gcond *> (stmt);
> +		  gimple_cond_set_lhs (cond, memcmp_lhs);
> +		  gimple_cond_set_rhs (cond, zero);
> +		  gimple_cond_set_code (cond, EQ_EXPR);

Likewise here.

	Jakub

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

[Prathamesh Kulkarni]

[-- Attachment #1: Type: text/plain, Size: 3799 bytes --]

On 13 December 2016 at 15:27, Jakub Jelinek <jakub@redhat.com> wrote:
> On Tue, Dec 13, 2016 at 03:08:17PM +0530, Prathamesh Kulkarni wrote:
>> Thanks for the suggestions. It didn't occur to me to check for gimple_cond.
>> I have tried to do the changes in the attached version.
>> I am not sure if I have handled cond_expr correctly.
>> IIUC, if gimple_assign has code cond_expr, then the condition is
>> stored in gimple_assign_rhs1,
>> however it's not a single operand but a tree of the form "op1 cond_code op2".
>> Is that correct ?
>
> Yes.  gimple_assign_rhs1 will be in what you are looking for EQ_EXPR or
> NE_EXPR tree, its TREE_CODE will be this code you want to check, and
> TREE_OPERAND (exp, 0) and TREE_OPERAND (exp, 1) the rhs1 and rhs2 you use
> elsewhere.
>
>> However I am not able to write a test-case that generates cond_expr in the IL.
>> I tried:
>> t1 = strstr (s, t);
>> (t1 == s)  ? foo() : bar ();
>> and other such variants but it seems the ?: operator is getting
>> lowered to gimple_cond instead.
>
> It is, but in some cases tree-if-conv.c turns them back into COND_EXPRs.
> I guess you need -ftree-loop-if-convert now, and it has to be in some loop
> where the addition of cond_expr would likely turn it into a single bb loop.
> You probably want constants or vars, not function calls in the ? :
> expressions though.
>
>> +/* Try to fold strstr (s, t) == s to memcmp (s, t, strlen (t)) == 0.  */
>> +
>> +static void
>> +fold_strstr_to_memcmp(enum tree_code code, tree rhs1, tree rhs2, gimple *stmt)
>
> Formatting, space before (.
>
>> +{
>> +  gimple *call_stmt = NULL;
>> +  for (int pass = 0; pass < 2; pass++)
>> +    {
>> +      gimple *g = SSA_NAME_DEF_STMT (rhs1);
>> +      if (g
>
> I think g should be always non-NULL (except for invalid IL), so probably no
> need to check it.
Ah indeed, thanks for pointing out. I assumed if ssa-var has default definition,
then SSA_NAME_DEF_STMT would be NULL, but it's GIMPLE_NOP.
>
>> +       && gimple_call_builtin_p (g, BUILT_IN_STRSTR)
>> +       && has_single_use (rhs1)
>> +       && gimple_call_arg (as_a<gcall *> (g), 0) == rhs2)
>
> I think gimple_call_arg works fine even with just gimple * argument.
> So you can avoid the as_a<gcall *> (g) uglification and just use g.
>
>> +           if (is_gimple_assign (stmt))
>> +             {
>> +               if (gimple_assign_rhs_code (stmt) == COND_EXPR)
>> +                 {
>> +                   tree cond = gimple_assign_rhs1 (stmt);
>> +                   TREE_SET_CODE (cond, EQ_EXPR);
>
> This looks weird.  You are hardcoding EQ_EXPR, while for the
> other case below you use code.  So, do you handle properly both
> EQ_EXPR and NE_EXPR for this and gimple_cond cases?
> Also, for non-COND_EXPR assign you build a new stmt instead of reusing
> the existing one, why?
>
>> +                   TREE_OPERAND (cond, 0) = memcmp_lhs;
>> +                   TREE_OPERAND (cond, 1) = zero;
>> +                   update_stmt (stmt);
>> +                 }
>> +               else
>> +                 {
>> +                   gsi = gsi_for_stmt (stmt);
>> +                   tree lhs = gimple_assign_lhs (stmt);
>> +                   gassign *ga = gimple_build_assign (lhs, code, memcmp_lhs,
>> +                                                      zero);
>> +                   gsi_replace (&gsi, ga, false);
>> +                 }
>> +             }
>> +           else
>> +             {
>> +               gcond *cond = as_a<gcond *> (stmt);
>> +               gimple_cond_set_lhs (cond, memcmp_lhs);
>> +               gimple_cond_set_rhs (cond, zero);
>> +               gimple_cond_set_code (cond, EQ_EXPR);
>
> Likewise here.
Oops, sorry about that :/
Does this version look OK ?
Bootstrap+test in progress.

Thanks,
Prathamesh
>
>         Jakub

[-- Attachment #2: tcwg-701-10.txt --]
[-- Type: text/plain, Size: 6022 bytes --]

2016-12-13  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.

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..b19dab6 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 (enum tree_code code, tree rhs1, tree rhs2, gimple *stmt)
+{
+  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_SET_CODE (cond, code);
+		      TREE_OPERAND (cond, 0) = memcmp_lhs;
+		      TREE_OPERAND (cond, 1) = zero;
+		      update_stmt (stmt);
+		    }
+		  else
+		    {
+		      gimple_assign_set_rhs1 (stmt, memcmp_lhs);
+		      gimple_assign_set_rhs2 (stmt, zero);
+		      update_stmt (stmt);
+		    }
+		}
+	      else
+		{
+		  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);
+		  update_stmt (cond);
+		}
+	    }
+	}
+    }
+}
+
 /* Attempt to optimize a single statement at *GSI using string length
    knowledge.  */
 
@@ -2302,7 +2386,34 @@ 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)
+	      {
+		tree rhs1 = TREE_OPERAND (cond, 0);
+		tree rhs2 = TREE_OPERAND (cond, 1);
+		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)
+	      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)
+	fold_strstr_to_memcmp (code, lhs, rhs, stmt);
+    }
 
   if (gimple_vdef (stmt))
     maybe_invalidate (stmt);

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

[Jakub Jelinek]

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

	Jakub

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

[Prathamesh Kulkarni]

[-- Attachment #1: Type: text/plain, Size: 3555 bytes --]

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

[-- Attachment #2: tcwg-701-11.txt --]
[-- Type: text/plain, Size: 5568 bytes --]

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.

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

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

[Jakub Jelinek]

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

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

[Martin Liška]

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

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

[Martin Liška]

[-- Attachment #1: Type: text/plain, Size: 265 bytes --]

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

[-- Attachment #2: 0001-Fix-strstr-folding-PR-tree-optimization-79196.patch --]
[-- Type: text/x-patch, Size: 5349 bytes --]

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.
	(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.
---
 gcc/testsuite/gcc.dg/asan/pr79196.c | 17 +++++++++++++++++
 gcc/testsuite/gcc.dg/strlenopt-30.c |  2 +-
 gcc/tree-ssa-strlen.c               | 36 ++++++++++++++++++------------------
 3 files changed, 36 insertions(+), 19 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/asan/pr79196.c

diff --git a/gcc/testsuite/gcc.dg/asan/pr79196.c b/gcc/testsuite/gcc.dg/asan/pr79196.c
new file mode 100644
index 00000000000..66a31b90f30
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/asan/pr79196.c
@@ -0,0 +1,17 @@
+// PR tree-optimization/79196
+// { dg-do run }
+
+int
+__attribute__((noinline))
+test(char *a)
+{
+  if (__builtin_strstr (a, "DROP CONVERSION") == a)
+    return 1;
+
+  return 0;
+}
+
+int main(int argc, char **argv)
+{
+  return test ("x");
+}
diff --git a/gcc/testsuite/gcc.dg/strlenopt-30.c b/gcc/testsuite/gcc.dg/strlenopt-30.c
index 089b3a2341d..a85df686ce2 100644
--- a/gcc/testsuite/gcc.dg/strlenopt-30.c
+++ b/gcc/testsuite/gcc.dg/strlenopt-30.c
@@ -60,4 +60,4 @@ _Bool f7(char *s)
   return (t1 == s);
 }
 
-/* { dg-final { scan-tree-dump-times "__builtin_memcmp" 5 "strlen" } } */
+/* { dg-final { scan-tree-dump-times "__builtin_strncmp" 5 "strlen" } } */
diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
index 2e7ac2c7786..141115ed12b 100644
--- a/gcc/tree-ssa-strlen.c
+++ b/gcc/tree-ssa-strlen.c
@@ -2225,10 +2225,10 @@ 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.  */
+/* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0.  */
 
 static void
-fold_strstr_to_memcmp (tree rhs1, tree rhs2, gimple *stmt)
+fold_strstr_to_strncmp (tree rhs1, tree rhs2, gimple *stmt)
 {
   if (TREE_CODE (rhs1) != SSA_NAME
       || TREE_CODE (rhs2) != SSA_NAME)
@@ -2273,34 +2273,34 @@ fold_strstr_to_memcmp (tree rhs1, tree rhs2, gimple *stmt)
 	  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,
+	      tree strncmp_decl = builtin_decl_explicit (BUILT_IN_STRNCMP);
+	      gcall *strncmp_call = gimple_build_call (strncmp_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);
+	      tree strncmp_lhs = make_ssa_name (integer_type_node);
+	      gimple_set_vuse (strncmp_call, gimple_vuse (call_stmt));
+	      gimple_call_set_lhs (strncmp_call, strncmp_lhs);
 	      gsi_remove (&gsi, true);
-	      gsi_insert_before (&gsi, memcmp_call, GSI_SAME_STMT);
-	      tree zero = build_zero_cst (TREE_TYPE (memcmp_lhs));
+	      gsi_insert_before (&gsi, strncmp_call, GSI_SAME_STMT);
+	      tree zero = build_zero_cst (TREE_TYPE (strncmp_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, 0) = strncmp_lhs;
 		      TREE_OPERAND (cond, 1) = zero;
 		    }
 		  else
 		    {
-		      gimple_assign_set_rhs1 (stmt, memcmp_lhs);
+		      gimple_assign_set_rhs1 (stmt, strncmp_lhs);
 		      gimple_assign_set_rhs2 (stmt, zero);
 		    }
 		}
 	      else
 		{
 		  gcond *cond = as_a<gcond *> (stmt);
-		  gimple_cond_set_lhs (cond, memcmp_lhs);
+		  gimple_cond_set_lhs (cond, strncmp_lhs);
 		  gimple_cond_set_rhs (cond, zero);
 		}
 	      update_stmt (stmt);
@@ -2398,12 +2398,12 @@ strlen_optimize_stmt (gimple_stmt_iterator *gsi)
 	    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);
+	      fold_strstr_to_strncmp (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);
+	  fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt),
+				  gimple_assign_rhs2 (stmt), stmt);
       }
     else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
 	{
@@ -2423,8 +2423,8 @@ strlen_optimize_stmt (gimple_stmt_iterator *gsi)
     {
       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);
+	fold_strstr_to_strncmp (gimple_cond_lhs (stmt),
+				gimple_cond_rhs (stmt), stmt);
     }
 
   if (gimple_vdef (stmt))
-- 
2.11.0

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

[Jakub Jelinek]

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