PR79715: Special case strcpy/strncpy for dse

PR79715: Special case strcpy/strncpy for dse

[Prathamesh Kulkarni]

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

Hi,
The attached patch adds special-casing for strcpy/strncpy to dse pass.
Bootstrapped+tested on x86_64-unknown-linux-gnu.
OK for GCC 8 ?

Thanks,
Prathamesh

[-- Attachment #2: pr79715-1.diff --]
[-- Type: text/plain, Size: 1869 bytes --]

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c
new file mode 100644
index 0000000..1a832ca
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dse-details" } */
+
+void f(const char *s)
+{
+  unsigned n = __builtin_strlen (s) + 1;
+  char *p = __builtin_malloc (n);
+  __builtin_strcpy (p, s);
+  __builtin_free (p);
+}
+
+/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strcpy" "dse1" } } */
diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
index 53feaf3..6d3c3c3 100644
--- a/gcc/tree-ssa-dse.c
+++ b/gcc/tree-ssa-dse.c
@@ -97,6 +97,8 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write)
 	  case BUILT_IN_MEMCPY:
 	  case BUILT_IN_MEMMOVE:
 	  case BUILT_IN_MEMSET:
+	  case BUILT_IN_STRNCPY:
+	  case BUILT_IN_STRCPY:
 	    {
 	      tree size = NULL_TREE;
 	      if (gimple_call_num_args (stmt) == 3)
@@ -395,6 +397,8 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt)
     {
     case BUILT_IN_MEMCPY:
     case BUILT_IN_MEMMOVE:
+    case BUILT_IN_STRNCPY:
+    case BUILT_IN_STRCPY:
       {
 	int head_trim, tail_trim;
 	compute_trims (ref, live, &head_trim, &tail_trim, stmt);
@@ -713,6 +717,7 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
 	  case BUILT_IN_MEMCPY:
 	  case BUILT_IN_MEMMOVE:
 	  case BUILT_IN_MEMSET:
+	  case BUILT_IN_STRNCPY:
 	    {
 	      /* Occasionally calls with an explicit length of zero
 		 show up in the IL.  It's pointless to do analysis
@@ -723,7 +728,10 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
 		  delete_dead_call (gsi);
 		  return;
 		}
-
+	    }
+	  /* fallthru  */
+	  case BUILT_IN_STRCPY:
+	    {
 	      gimple *use_stmt;
 	      enum dse_store_status store_status;
 	      m_byte_tracking_enabled

Re: PR79715: Special case strcpy/strncpy for dse

[Jakub Jelinek]

On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote:
> Hi,
> The attached patch adds special-casing for strcpy/strncpy to dse pass.
> Bootstrapped+tested on x86_64-unknown-linux-gnu.
> OK for GCC 8 ?

What is special on strcpy/strncpy?  Unlike memcpy/memmove/memset, you don't
know the length they store (at least not in general), you don't know the
value, all you know is that they are for the first argument plain store
without remembering the pointer or anything based on it anywhere except in
the return value.
I believe stpcpy, stpncpy, strcat, strncat at least have the same behavior.
On the other side, without knowing the length of the store, you can't treat
it as killing something (ok, some calls like strcpy or stpcpy store at least
the first byte).

> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c
> new file mode 100644
> index 0000000..1a832ca
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c
> @@ -0,0 +1,12 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-dse-details" } */
> +
> +void f(const char *s)
> +{
> +  unsigned n = __builtin_strlen (s) + 1;
> +  char *p = __builtin_malloc (n);
> +  __builtin_strcpy (p, s);
> +  __builtin_free (p);
> +}
> +
> +/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strcpy" "dse1" } } */
> diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
> index 53feaf3..6d3c3c3 100644
> --- a/gcc/tree-ssa-dse.c
> +++ b/gcc/tree-ssa-dse.c
> @@ -97,6 +97,8 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write)
>  	  case BUILT_IN_MEMCPY:
>  	  case BUILT_IN_MEMMOVE:
>  	  case BUILT_IN_MEMSET:
> +	  case BUILT_IN_STRNCPY:
> +	  case BUILT_IN_STRCPY:
>  	    {
>  	      tree size = NULL_TREE;
>  	      if (gimple_call_num_args (stmt) == 3)
> @@ -395,6 +397,8 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt)
>      {
>      case BUILT_IN_MEMCPY:
>      case BUILT_IN_MEMMOVE:
> +    case BUILT_IN_STRNCPY:
> +    case BUILT_IN_STRCPY:
>        {
>  	int head_trim, tail_trim;
>  	compute_trims (ref, live, &head_trim, &tail_trim, stmt);
> @@ -713,6 +717,7 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
>  	  case BUILT_IN_MEMCPY:
>  	  case BUILT_IN_MEMMOVE:
>  	  case BUILT_IN_MEMSET:
> +	  case BUILT_IN_STRNCPY:
>  	    {
>  	      /* Occasionally calls with an explicit length of zero
>  		 show up in the IL.  It's pointless to do analysis
> @@ -723,7 +728,10 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
>  		  delete_dead_call (gsi);
>  		  return;
>  		}
> -
> +	    }
> +	  /* fallthru  */
> +	  case BUILT_IN_STRCPY:
> +	    {
>  	      gimple *use_stmt;
>  	      enum dse_store_status store_status;
>  	      m_byte_tracking_enabled


	Jakub

Re: PR79715: Special case strcpy/strncpy for dse

[Prathamesh Kulkarni]

On 28 February 2017 at 15:40, Jakub Jelinek <jakub@redhat.com> wrote:
> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote:
>> Hi,
>> The attached patch adds special-casing for strcpy/strncpy to dse pass.
>> Bootstrapped+tested on x86_64-unknown-linux-gnu.
>> OK for GCC 8 ?
>
> What is special on strcpy/strncpy?  Unlike memcpy/memmove/memset, you don't
> know the length they store (at least not in general), you don't know the
> value, all you know is that they are for the first argument plain store
> without remembering the pointer or anything based on it anywhere except in
> the return value.
> I believe stpcpy, stpncpy, strcat, strncat at least have the same behavior.
> On the other side, without knowing the length of the store, you can't treat
> it as killing something (ok, some calls like strcpy or stpcpy store at least
> the first byte).
Well, I assumed a store to dest by strcpy (and friends), which gets
immediately freed would count
as a dead store since free would kill the whole memory block pointed
to by dest ?

For the test-case:
void f (unsigned n, char *s2)
{
  char *p = __builtin_malloc (n);
  __builtin_strcpy (p, s2);
  __builtin_free (p);
}

With patch, similar to memcpy, in dse_classify_store when temp equals
__builtin_free (p),
stmt_kills_ref_p (temp, ref) returns true (the condition for case
BUILT_IN_FREE) which causes the loop to break
and dse_classify_store returns DSE_STORE_DEAD.

Thanks,
Prathamesh
>
>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c
>> new file mode 100644
>> index 0000000..1a832ca
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c
>> @@ -0,0 +1,12 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-dse-details" } */
>> +
>> +void f(const char *s)
>> +{
>> +  unsigned n = __builtin_strlen (s) + 1;
>> +  char *p = __builtin_malloc (n);
>> +  __builtin_strcpy (p, s);
>> +  __builtin_free (p);
>> +}
>> +
>> +/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strcpy" "dse1" } } */
>> diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
>> index 53feaf3..6d3c3c3 100644
>> --- a/gcc/tree-ssa-dse.c
>> +++ b/gcc/tree-ssa-dse.c
>> @@ -97,6 +97,8 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write)
>>         case BUILT_IN_MEMCPY:
>>         case BUILT_IN_MEMMOVE:
>>         case BUILT_IN_MEMSET:
>> +       case BUILT_IN_STRNCPY:
>> +       case BUILT_IN_STRCPY:
>>           {
>>             tree size = NULL_TREE;
>>             if (gimple_call_num_args (stmt) == 3)
>> @@ -395,6 +397,8 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt)
>>      {
>>      case BUILT_IN_MEMCPY:
>>      case BUILT_IN_MEMMOVE:
>> +    case BUILT_IN_STRNCPY:
>> +    case BUILT_IN_STRCPY:
>>        {
>>       int head_trim, tail_trim;
>>       compute_trims (ref, live, &head_trim, &tail_trim, stmt);
>> @@ -713,6 +717,7 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
>>         case BUILT_IN_MEMCPY:
>>         case BUILT_IN_MEMMOVE:
>>         case BUILT_IN_MEMSET:
>> +       case BUILT_IN_STRNCPY:
>>           {
>>             /* Occasionally calls with an explicit length of zero
>>                show up in the IL.  It's pointless to do analysis
>> @@ -723,7 +728,10 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
>>                 delete_dead_call (gsi);
>>                 return;
>>               }
>> -
>> +         }
>> +       /* fallthru  */
>> +       case BUILT_IN_STRCPY:
>> +         {
>>             gimple *use_stmt;
>>             enum dse_store_status store_status;
>>             m_byte_tracking_enabled
>
>
>         Jakub

Re: PR79715: Special case strcpy/strncpy for dse

[Jeff Law]

On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote:
> On 28 February 2017 at 15:40, Jakub Jelinek <jakub@redhat.com> wrote:
>> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote:
>>> Hi,
>>> The attached patch adds special-casing for strcpy/strncpy to dse pass.
>>> Bootstrapped+tested on x86_64-unknown-linux-gnu.
>>> OK for GCC 8 ?
>>
>> What is special on strcpy/strncpy?  Unlike memcpy/memmove/memset, you don't
>> know the length they store (at least not in general), you don't know the
>> value, all you know is that they are for the first argument plain store
>> without remembering the pointer or anything based on it anywhere except in
>> the return value.
>> I believe stpcpy, stpncpy, strcat, strncat at least have the same behavior.
>> On the other side, without knowing the length of the store, you can't treat
>> it as killing something (ok, some calls like strcpy or stpcpy store at least
>> the first byte).
> Well, I assumed a store to dest by strcpy (and friends), which gets
> immediately freed would count
> as a dead store since free would kill the whole memory block pointed
> to by dest ?
Yes.  But does it happen often in practice?  I wouldn't mind exploring 
this for gcc-8, but I'd like to see real-world code where this happens.

jeff

Re: PR79715: Special case strcpy/strncpy for dse

[Richard Biener]

On Tue, 28 Feb 2017, Jeff Law wrote:

> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote:
> > On 28 February 2017 at 15:40, Jakub Jelinek <jakub@redhat.com> wrote:
> > > On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote:
> > > > Hi,
> > > > The attached patch adds special-casing for strcpy/strncpy to dse pass.
> > > > Bootstrapped+tested on x86_64-unknown-linux-gnu.
> > > > OK for GCC 8 ?
> > > 
> > > What is special on strcpy/strncpy?  Unlike memcpy/memmove/memset, you
> > > don't
> > > know the length they store (at least not in general), you don't know the
> > > value, all you know is that they are for the first argument plain store
> > > without remembering the pointer or anything based on it anywhere except in
> > > the return value.
> > > I believe stpcpy, stpncpy, strcat, strncat at least have the same
> > > behavior.
> > > On the other side, without knowing the length of the store, you can't
> > > treat
> > > it as killing something (ok, some calls like strcpy or stpcpy store at
> > > least
> > > the first byte).
> > Well, I assumed a store to dest by strcpy (and friends), which gets
> > immediately freed would count
> > as a dead store since free would kill the whole memory block pointed
> > to by dest ?
> Yes.  But does it happen often in practice?  I wouldn't mind exploring this
> for gcc-8, but I'd like to see real-world code where this happens.

Actually I don't mind for "real-world code" - the important part is
that I believe it's reasonable to assume it can happen from some C++
abstraction and optimization.

Richard.

Re: PR79715: Special case strcpy/strncpy for dse

[Prathamesh Kulkarni]

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

On 1 March 2017 at 13:24, Richard Biener <rguenther@suse.de> wrote:
> On Tue, 28 Feb 2017, Jeff Law wrote:
>
>> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote:
>> > On 28 February 2017 at 15:40, Jakub Jelinek <jakub@redhat.com> wrote:
>> > > On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote:
>> > > > Hi,
>> > > > The attached patch adds special-casing for strcpy/strncpy to dse pass.
>> > > > Bootstrapped+tested on x86_64-unknown-linux-gnu.
>> > > > OK for GCC 8 ?
>> > >
>> > > What is special on strcpy/strncpy?  Unlike memcpy/memmove/memset, you
>> > > don't
>> > > know the length they store (at least not in general), you don't know the
>> > > value, all you know is that they are for the first argument plain store
>> > > without remembering the pointer or anything based on it anywhere except in
>> > > the return value.
>> > > I believe stpcpy, stpncpy, strcat, strncat at least have the same
>> > > behavior.
>> > > On the other side, without knowing the length of the store, you can't
>> > > treat
>> > > it as killing something (ok, some calls like strcpy or stpcpy store at
>> > > least
>> > > the first byte).
>> > Well, I assumed a store to dest by strcpy (and friends), which gets
>> > immediately freed would count
>> > as a dead store since free would kill the whole memory block pointed
>> > to by dest ?
>> Yes.  But does it happen often in practice?  I wouldn't mind exploring this
>> for gcc-8, but I'd like to see real-world code where this happens.
>
> Actually I don't mind for "real-world code" - the important part is
> that I believe it's reasonable to assume it can happen from some C++
> abstraction and optimization.
Hi,
I have updated the patch to include stp[n]cpy and str[n]cat.
In initialize_ao_ref_for_dse for strncat, I suppose for strncat we
need to treat size as NULL_TREE
instead of setting it 2nd arg since we cannot know size (in general)
after strncat ?
Patch passes bootstrap+test on x86_64-unknown-linux-gnu.
Cross-tested on arm*-*-*, aarch64*-*-*.

Thanks,
Prathamesh
>
> Richard.

[-- Attachment #2: pr79715-2.txt --]
[-- Type: text/plain, Size: 3786 bytes --]

2017-04-24  Prathamesh Kulkarni  <prathamesh.kulkarni@linaro.org>

	* tree-ssa-dse.c (initialize_ao_ref_for_dse): Add cases for
	BUILT_IN_STRNCPY, BUILT_IN_STRCPY, BUILT_IN_STPNCPY, BUILT_IN_STPCPY,
	BUILT_IN_STRNCAT, BUILT_IN_STRCAT.
	(maybe_trim_memstar_call): Likewise.
	(dse_dom_walker::dse_optimize_stmt): Likewise.

testsuite/
	* gcc.dg/tree-ssa/pr79715.c: New test.

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c
new file mode 100644
index 0000000..2cd4c99
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr79715.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dse-details" } */
+
+void f1(const char *s)
+{
+  unsigned n = __builtin_strlen (s) + 1;
+  char *p = __builtin_malloc (n);
+  __builtin_strcpy (p, s);
+  __builtin_free (p);
+}
+
+void f2(const char *s, unsigned n)
+{
+  char *p = __builtin_malloc (n);
+  __builtin_strncpy (p, s, n);
+  __builtin_free (p);
+}
+
+void f3(const char *s, unsigned n)
+{
+  char *p = __builtin_malloc (n);
+  __builtin_stpncpy (p, s, n);
+  __builtin_free (p);
+}
+
+void f4(char *s, char *t)
+{
+  __builtin_strcat (s, t);
+  __builtin_free (s);
+}
+
+void f5(char *s, char *t, unsigned n)
+{
+  __builtin_strncat (s, t, n);
+  __builtin_free (s);
+}
+
+/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strcpy" "dse1" } } */
+/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strncpy" "dse1" } } */
+/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_stpncpy" "dse1" } } */
+/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strcat" "dse1" } } */
+/* { dg-final { scan-tree-dump "Deleted dead call: __builtin_strncat" "dse1" } } */
diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
index 90230ab..752b2fa 100644
--- a/gcc/tree-ssa-dse.c
+++ b/gcc/tree-ssa-dse.c
@@ -92,15 +92,24 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write)
   /* It's advantageous to handle certain mem* functions.  */
   if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
     {
+      tree size = NULL_TREE;
       switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
 	{
 	  case BUILT_IN_MEMCPY:
 	  case BUILT_IN_MEMMOVE:
 	  case BUILT_IN_MEMSET:
+	  case BUILT_IN_STRNCPY:
+	  case BUILT_IN_STRCPY:
+	  case BUILT_IN_STPNCPY:
+	  case BUILT_IN_STPCPY:
 	    {
-	      tree size = NULL_TREE;
 	      if (gimple_call_num_args (stmt) == 3)
 		size = gimple_call_arg (stmt, 2);
+	    }
+	  /* fallthrough.  */
+	  case BUILT_IN_STRCAT:
+	  case BUILT_IN_STRNCAT:
+	    {
 	      tree ptr = gimple_call_arg (stmt, 0);
 	      ao_ref_init_from_ptr_and_size (write, ptr, size);
 	      return true;
@@ -395,6 +404,12 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt)
     {
     case BUILT_IN_MEMCPY:
     case BUILT_IN_MEMMOVE:
+    case BUILT_IN_STRNCPY:
+    case BUILT_IN_STRCPY:
+    case BUILT_IN_STPNCPY:
+    case BUILT_IN_STPCPY:
+    case BUILT_IN_STRNCAT:
+    case BUILT_IN_STRCAT:
       {
 	int head_trim, tail_trim;
 	compute_trims (ref, live, &head_trim, &tail_trim, stmt);
@@ -714,6 +729,9 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
 	  case BUILT_IN_MEMCPY:
 	  case BUILT_IN_MEMMOVE:
 	  case BUILT_IN_MEMSET:
+	  case BUILT_IN_STRNCPY:
+	  case BUILT_IN_STPNCPY:
+	  case BUILT_IN_STRNCAT:
 	    {
 	      /* Occasionally calls with an explicit length of zero
 		 show up in the IL.  It's pointless to do analysis
@@ -724,7 +742,12 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
 		  delete_dead_call (gsi);
 		  return;
 		}
-
+	    }
+	  /* fallthru  */
+	  case BUILT_IN_STRCPY:
+	  case BUILT_IN_STPCPY:
+	  case BUILT_IN_STRCAT:
+	    {
 	      gimple *use_stmt;
 	      enum dse_store_status store_status;
 	      m_byte_tracking_enabled

Re: PR79715: Special case strcpy/strncpy for dse

[Jeff Law]

On 04/24/2017 03:05 AM, Prathamesh Kulkarni wrote:
> On 1 March 2017 at 13:24, Richard Biener<rguenther@suse.de>  wrote:
>> On Tue, 28 Feb 2017, Jeff Law wrote:
>>
>>> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote:
>>>> On 28 February 2017 at 15:40, Jakub Jelinek<jakub@redhat.com>  wrote:
>>>>> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote:
>>>>>> Hi,
>>>>>> The attached patch adds special-casing for strcpy/strncpy to dse pass.
>>>>>> Bootstrapped+tested on x86_64-unknown-linux-gnu.
>>>>>> OK for GCC 8 ?
>>>>> What is special on strcpy/strncpy?  Unlike memcpy/memmove/memset, you
>>>>> don't
>>>>> know the length they store (at least not in general), you don't know the
>>>>> value, all you know is that they are for the first argument plain store
>>>>> without remembering the pointer or anything based on it anywhere except in
>>>>> the return value.
>>>>> I believe stpcpy, stpncpy, strcat, strncat at least have the same
>>>>> behavior.
>>>>> On the other side, without knowing the length of the store, you can't
>>>>> treat
>>>>> it as killing something (ok, some calls like strcpy or stpcpy store at
>>>>> least
>>>>> the first byte).
>>>> Well, I assumed a store to dest by strcpy (and friends), which gets
>>>> immediately freed would count
>>>> as a dead store since free would kill the whole memory block pointed
>>>> to by dest ?
>>> Yes.  But does it happen often in practice?  I wouldn't mind exploring this
>>> for gcc-8, but I'd like to see real-world code where this happens.
>> Actually I don't mind for "real-world code" - the important part is
>> that I believe it's reasonable to assume it can happen from some C++
>> abstraction and optimization.
> Hi,
> I have updated the patch to include stp[n]cpy and str[n]cat.
> In initialize_ao_ref_for_dse for strncat, I suppose for strncat we
> need to treat size as NULL_TREE
> instead of setting it 2nd arg since we cannot know size (in general)
> after strncat ?
The problem isn't the size, strncat will write the appropriate number of 
characters, just like strncpy, stpncpy.  The problem is that we don't 
know where the write will start.  I'll touch further on this.


> Patch passes bootstrap+test on x86_64-unknown-linux-gnu.
> Cross-tested on arm*-*-*, aarch64*-*-*.
> 
> Thanks,
> Prathamesh
>> Richard.
> 
> pr79715-2.txt
> 
> 
> 2017-04-24  Prathamesh Kulkarni<prathamesh.kulkarni@linaro.org>
> 
> 	* tree-ssa-dse.c (initialize_ao_ref_for_dse): Add cases for
> 	BUILT_IN_STRNCPY, BUILT_IN_STRCPY, BUILT_IN_STPNCPY, BUILT_IN_STPCPY,
> 	BUILT_IN_STRNCAT, BUILT_IN_STRCAT.
> 	(maybe_trim_memstar_call): Likewise.
> 	(dse_dom_walker::dse_optimize_stmt): Likewise.
> 
> testsuite/
> 	* gcc.dg/tree-ssa/pr79715.c: New test.
I'd still be surprised if this kind of think happens in the real world, 
even with layers of abstraction & templates.



> diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
> index 90230ab..752b2fa 100644
> --- a/gcc/tree-ssa-dse.c
> +++ b/gcc/tree-ssa-dse.c
> @@ -92,15 +92,24 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref *write)
>     /* It's advantageous to handle certain mem* functions.  */
>     if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
>       {
> +      tree size = NULL_TREE;
>         switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
>   	{
>   	  case BUILT_IN_MEMCPY:
>   	  case BUILT_IN_MEMMOVE:
>   	  case BUILT_IN_MEMSET:
> +	  case BUILT_IN_STRNCPY:
> +	  case BUILT_IN_STRCPY:
> +	  case BUILT_IN_STPNCPY:
> +	  case BUILT_IN_STPCPY:
>   	    {
> -	      tree size = NULL_TREE;
>   	      if (gimple_call_num_args (stmt) == 3)
>   		size = gimple_call_arg (stmt, 2)This part seems reasonable.  We know the size for strncpy, stpncpy which 
we extract from argument #3.  For strcpy and stpcpy we'd have NULL for 
the size which is perfect.  In all 4 cases the write starts at offset 0 
in the destination string.
.



> +	    }
> +	  /* fallthrough.  */
> +	  case BUILT_IN_STRCAT:
> +	  case BUILT_IN_STRNCAT:
> +	    {
>   	      tree ptr = gimple_call_arg (stmt, 0);
>   	      ao_ref_init_from_ptr_and_size (write, ptr, size);
For str[n]cat, I think this is going to result in WRITE not accurately 
reflecting what bytes are going to be written -- write.offset would have 
to account for the length of the destination string.

I don't see a way in the ao_ref structure to indicate that the offset of 
a write is unknown.

I'm really hesitant to allow handling of str[n]cat given the inaccuracy 
in how WRITE is initialized.

To handle str[n]cat I think you have to either somehow indicate the 
offset is unknown or arrange to get the offset set correctly.

I realize this isn't important for the case where the object dies 
immediately via free(), but it seems bad to allow this as-is.


>   	      return true;
> @@ -395,6 +404,12 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap live, gimple *stmt)
>       {
>       case BUILT_IN_MEMCPY:
>       case BUILT_IN_MEMMOVE:
> +    case BUILT_IN_STRNCPY:
> +    case BUILT_IN_STRCPY:
> +    case BUILT_IN_STPNCPY:
> +    case BUILT_IN_STPCPY:
> +    case BUILT_IN_STRNCAT:
> +    case BUILT_IN_STRCAT:
For strcpy, stpcpy and strcat I don't see how you can do trimming 
without knowing something about the source string.

For str[n]cat we'd need a correctly initialized structure for the memory 
write, which we don't have because the offset does not account for the 
length of the destination string.

The only trimming possibility I see is for strncpy and stpncpy where we 
could trim from the either end.  I think you should remove the other cases.


>         {
>   	int head_trim, tail_trim;
>   	compute_trims (ref, live, &head_trim, &tail_trim, stmt);
> @@ -714,6 +729,9 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
>   	  case BUILT_IN_MEMCPY:
>   	  case BUILT_IN_MEMMOVE:
>   	  case BUILT_IN_MEMSET:
> +	  case BUILT_IN_STRNCPY:
> +	  case BUILT_IN_STPNCPY:
> +	  case BUILT_IN_STRNCAT:
I don't think you can support strncat here because we don't have a valid 
offset within the write descriptor.

>   	    {
>   	      /* Occasionally calls with an explicit length of zero
>   		 show up in the IL.  It's pointless to do analysis
> @@ -724,7 +742,12 @@ dse_dom_walker::dse_optimize_stmt (gimple_stmt_iterator *gsi)
>   		  delete_dead_call (gsi);
>   		  return;
>   		}
> -
> +	    }
> +	  /* fallthru  */
> +	  case BUILT_IN_STRCPY:
> +	  case BUILT_IN_STPCPY:
> +	  case BUILT_IN_STRCAT:
Similarly here, I don't think you can support strcat because we don't 
have a valid write descriptor.

Jeff

Re: PR79715: Special case strcpy/strncpy for dse

[Richard Biener]

On April 28, 2017 8:14:56 PM GMT+02:00, Jeff Law <law@redhat.com> wrote:
>On 04/24/2017 03:05 AM, Prathamesh Kulkarni wrote:
>> On 1 March 2017 at 13:24, Richard Biener<rguenther@suse.de>  wrote:
>>> On Tue, 28 Feb 2017, Jeff Law wrote:
>>>
>>>> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote:
>>>>> On 28 February 2017 at 15:40, Jakub Jelinek<jakub@redhat.com> 
>wrote:
>>>>>> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni
>wrote:
>>>>>>> Hi,
>>>>>>> The attached patch adds special-casing for strcpy/strncpy to dse
>pass.
>>>>>>> Bootstrapped+tested on x86_64-unknown-linux-gnu.
>>>>>>> OK for GCC 8 ?
>>>>>> What is special on strcpy/strncpy?  Unlike memcpy/memmove/memset,
>you
>>>>>> don't
>>>>>> know the length they store (at least not in general), you don't
>know the
>>>>>> value, all you know is that they are for the first argument plain
>store
>>>>>> without remembering the pointer or anything based on it anywhere
>except in
>>>>>> the return value.
>>>>>> I believe stpcpy, stpncpy, strcat, strncat at least have the same
>>>>>> behavior.
>>>>>> On the other side, without knowing the length of the store, you
>can't
>>>>>> treat
>>>>>> it as killing something (ok, some calls like strcpy or stpcpy
>store at
>>>>>> least
>>>>>> the first byte).
>>>>> Well, I assumed a store to dest by strcpy (and friends), which
>gets
>>>>> immediately freed would count
>>>>> as a dead store since free would kill the whole memory block
>pointed
>>>>> to by dest ?
>>>> Yes.  But does it happen often in practice?  I wouldn't mind
>exploring this
>>>> for gcc-8, but I'd like to see real-world code where this happens.
>>> Actually I don't mind for "real-world code" - the important part is
>>> that I believe it's reasonable to assume it can happen from some C++
>>> abstraction and optimization.
>> Hi,
>> I have updated the patch to include stp[n]cpy and str[n]cat.
>> In initialize_ao_ref_for_dse for strncat, I suppose for strncat we
>> need to treat size as NULL_TREE
>> instead of setting it 2nd arg since we cannot know size (in general)
>> after strncat ?
>The problem isn't the size, strncat will write the appropriate number
>of 
>characters, just like strncpy, stpncpy.  The problem is that we don't 
>know where the write will start.  I'll touch further on this.
>
>
>> Patch passes bootstrap+test on x86_64-unknown-linux-gnu.
>> Cross-tested on arm*-*-*, aarch64*-*-*.
>> 
>> Thanks,
>> Prathamesh
>>> Richard.
>> 
>> pr79715-2.txt
>> 
>> 
>> 2017-04-24  Prathamesh Kulkarni<prathamesh.kulkarni@linaro.org>
>> 
>> 	* tree-ssa-dse.c (initialize_ao_ref_for_dse): Add cases for
>> 	BUILT_IN_STRNCPY, BUILT_IN_STRCPY, BUILT_IN_STPNCPY,
>BUILT_IN_STPCPY,
>> 	BUILT_IN_STRNCAT, BUILT_IN_STRCAT.
>> 	(maybe_trim_memstar_call): Likewise.
>> 	(dse_dom_walker::dse_optimize_stmt): Likewise.
>> 
>> testsuite/
>> 	* gcc.dg/tree-ssa/pr79715.c: New test.
>I'd still be surprised if this kind of think happens in the real world,
>
>even with layers of abstraction & templates.
>
>
>
>> diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
>> index 90230ab..752b2fa 100644
>> --- a/gcc/tree-ssa-dse.c
>> +++ b/gcc/tree-ssa-dse.c
>> @@ -92,15 +92,24 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref
>*write)
>>     /* It's advantageous to handle certain mem* functions.  */
>>     if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
>>       {
>> +      tree size = NULL_TREE;
>>         switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
>>   	{
>>   	  case BUILT_IN_MEMCPY:
>>   	  case BUILT_IN_MEMMOVE:
>>   	  case BUILT_IN_MEMSET:
>> +	  case BUILT_IN_STRNCPY:
>> +	  case BUILT_IN_STRCPY:
>> +	  case BUILT_IN_STPNCPY:
>> +	  case BUILT_IN_STPCPY:
>>   	    {
>> -	      tree size = NULL_TREE;
>>   	      if (gimple_call_num_args (stmt) == 3)
>>   		size = gimple_call_arg (stmt, 2)This part seems reasonable.  We
>know the size for strncpy, stpncpy which 
>we extract from argument #3.  For strcpy and stpcpy we'd have NULL for 
>the size which is perfect.  In all 4 cases the write starts at offset 0
>
>in the destination string.
>.
>
>
>
>> +	    }
>> +	  /* fallthrough.  */
>> +	  case BUILT_IN_STRCAT:
>> +	  case BUILT_IN_STRNCAT:
>> +	    {
>>   	      tree ptr = gimple_call_arg (stmt, 0);
>>   	      ao_ref_init_from_ptr_and_size (write, ptr, size);
>For str[n]cat, I think this is going to result in WRITE not accurately 
>reflecting what bytes are going to be written -- write.offset would
>have 
>to account for the length of the destination string.
>
>I don't see a way in the ao_ref structure to indicate that the offset
>of 
>a write is unknown.

You can't make offset entirely unknown but you can use, for strcat, offset zero, size and max_size -1.  It matters that the access range is correct.  This is similar to how we treat array accesses with variable index.

>
>I'm really hesitant to allow handling of str[n]cat given the inaccuracy
>
>in how WRITE is initialized.
>
>To handle str[n]cat I think you have to either somehow indicate the 
>offset is unknown or arrange to get the offset set correctly.
>
>I realize this isn't important for the case where the object dies 
>immediately via free(), but it seems bad to allow this as-is.
>
>
>>   	      return true;
>> @@ -395,6 +404,12 @@ maybe_trim_memstar_call (ao_ref *ref, sbitmap
>live, gimple *stmt)
>>       {
>>       case BUILT_IN_MEMCPY:
>>       case BUILT_IN_MEMMOVE:
>> +    case BUILT_IN_STRNCPY:
>> +    case BUILT_IN_STRCPY:
>> +    case BUILT_IN_STPNCPY:
>> +    case BUILT_IN_STPCPY:
>> +    case BUILT_IN_STRNCAT:
>> +    case BUILT_IN_STRCAT:
>For strcpy, stpcpy and strcat I don't see how you can do trimming 
>without knowing something about the source string.
>
>For str[n]cat we'd need a correctly initialized structure for the
>memory 
>write, which we don't have because the offset does not account for the 
>length of the destination string.
>
>The only trimming possibility I see is for strncpy and stpncpy where we
>
>could trim from the either end.  I think you should remove the other
>cases.
>
>
>>         {
>>   	int head_trim, tail_trim;
>>   	compute_trims (ref, live, &head_trim, &tail_trim, stmt);
>> @@ -714,6 +729,9 @@ dse_dom_walker::dse_optimize_stmt
>(gimple_stmt_iterator *gsi)
>>   	  case BUILT_IN_MEMCPY:
>>   	  case BUILT_IN_MEMMOVE:
>>   	  case BUILT_IN_MEMSET:
>> +	  case BUILT_IN_STRNCPY:
>> +	  case BUILT_IN_STPNCPY:
>> +	  case BUILT_IN_STRNCAT:
>I don't think you can support strncat here because we don't have a
>valid 
>offset within the write descriptor.
>
>>   	    {
>>   	      /* Occasionally calls with an explicit length of zero
>>   		 show up in the IL.  It's pointless to do analysis
>> @@ -724,7 +742,12 @@ dse_dom_walker::dse_optimize_stmt
>(gimple_stmt_iterator *gsi)
>>   		  delete_dead_call (gsi);
>>   		  return;
>>   		}
>> -
>> +	    }
>> +	  /* fallthru  */
>> +	  case BUILT_IN_STRCPY:
>> +	  case BUILT_IN_STPCPY:
>> +	  case BUILT_IN_STRCAT:
>Similarly here, I don't think you can support strcat because we don't 
>have a valid write descriptor.
>
>Jeff

Re: PR79715: Special case strcpy/strncpy for dse

[Jeff Law]

On 05/01/2017 12:17 PM, Richard Biener wrote:
> On April 28, 2017 8:14:56 PM GMT+02:00, Jeff Law <law@redhat.com> wrote:
>> On 04/24/2017 03:05 AM, Prathamesh Kulkarni wrote:
>>> On 1 March 2017 at 13:24, Richard Biener<rguenther@suse.de>  wrote:
>>>> On Tue, 28 Feb 2017, Jeff Law wrote:
>>>>
>>>>> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote:
>>>>>> On 28 February 2017 at 15:40, Jakub Jelinek<jakub@redhat.com>
>> wrote:
>>>>>>> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni
>> wrote:
>>>>>>>> Hi,
>>>>>>>> The attached patch adds special-casing for strcpy/strncpy to dse
>> pass.
>>>>>>>> Bootstrapped+tested on x86_64-unknown-linux-gnu.
>>>>>>>> OK for GCC 8 ?
>>>>>>> What is special on strcpy/strncpy?  Unlike memcpy/memmove/memset,
>> you
>>>>>>> don't
>>>>>>> know the length they store (at least not in general), you don't
>> know the
>>>>>>> value, all you know is that they are for the first argument plain
>> store
>>>>>>> without remembering the pointer or anything based on it anywhere
>> except in
>>>>>>> the return value.
>>>>>>> I believe stpcpy, stpncpy, strcat, strncat at least have the same
>>>>>>> behavior.
>>>>>>> On the other side, without knowing the length of the store, you
>> can't
>>>>>>> treat
>>>>>>> it as killing something (ok, some calls like strcpy or stpcpy
>> store at
>>>>>>> least
>>>>>>> the first byte).
>>>>>> Well, I assumed a store to dest by strcpy (and friends), which
>> gets
>>>>>> immediately freed would count
>>>>>> as a dead store since free would kill the whole memory block
>> pointed
>>>>>> to by dest ?
>>>>> Yes.  But does it happen often in practice?  I wouldn't mind
>> exploring this
>>>>> for gcc-8, but I'd like to see real-world code where this happens.
>>>> Actually I don't mind for "real-world code" - the important part is
>>>> that I believe it's reasonable to assume it can happen from some C++
>>>> abstraction and optimization.
>>> Hi,
>>> I have updated the patch to include stp[n]cpy and str[n]cat.
>>> In initialize_ao_ref_for_dse for strncat, I suppose for strncat we
>>> need to treat size as NULL_TREE
>>> instead of setting it 2nd arg since we cannot know size (in general)
>>> after strncat ?
>> The problem isn't the size, strncat will write the appropriate number
>> of
>> characters, just like strncpy, stpncpy.  The problem is that we don't
>> know where the write will start.  I'll touch further on this.
>>
>>
>>> Patch passes bootstrap+test on x86_64-unknown-linux-gnu.
>>> Cross-tested on arm*-*-*, aarch64*-*-*.
>>>
>>> Thanks,
>>> Prathamesh
>>>> Richard.
>>>
>>> pr79715-2.txt
>>>
>>>
>>> 2017-04-24  Prathamesh Kulkarni<prathamesh.kulkarni@linaro.org>
>>>
>>> 	* tree-ssa-dse.c (initialize_ao_ref_for_dse): Add cases for
>>> 	BUILT_IN_STRNCPY, BUILT_IN_STRCPY, BUILT_IN_STPNCPY,
>> BUILT_IN_STPCPY,
>>> 	BUILT_IN_STRNCAT, BUILT_IN_STRCAT.
>>> 	(maybe_trim_memstar_call): Likewise.
>>> 	(dse_dom_walker::dse_optimize_stmt): Likewise.
>>>
>>> testsuite/
>>> 	* gcc.dg/tree-ssa/pr79715.c: New test.
>> I'd still be surprised if this kind of think happens in the real world,
>>
>> even with layers of abstraction & templates.
>>
>>
>>
>>> diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c
>>> index 90230ab..752b2fa 100644
>>> --- a/gcc/tree-ssa-dse.c
>>> +++ b/gcc/tree-ssa-dse.c
>>> @@ -92,15 +92,24 @@ initialize_ao_ref_for_dse (gimple *stmt, ao_ref
>> *write)
>>>      /* It's advantageous to handle certain mem* functions.  */
>>>      if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
>>>        {
>>> +      tree size = NULL_TREE;
>>>          switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt)))
>>>    	{
>>>    	  case BUILT_IN_MEMCPY:
>>>    	  case BUILT_IN_MEMMOVE:
>>>    	  case BUILT_IN_MEMSET:
>>> +	  case BUILT_IN_STRNCPY:
>>> +	  case BUILT_IN_STRCPY:
>>> +	  case BUILT_IN_STPNCPY:
>>> +	  case BUILT_IN_STPCPY:
>>>    	    {
>>> -	      tree size = NULL_TREE;
>>>    	      if (gimple_call_num_args (stmt) == 3)
>>>    		size = gimple_call_arg (stmt, 2)This part seems reasonable.  We
>> know the size for strncpy, stpncpy which
>> we extract from argument #3.  For strcpy and stpcpy we'd have NULL for
>> the size which is perfect.  In all 4 cases the write starts at offset 0
>>
>> in the destination string.
>> .
>>
>>
>>
>>> +	    }
>>> +	  /* fallthrough.  */
>>> +	  case BUILT_IN_STRCAT:
>>> +	  case BUILT_IN_STRNCAT:
>>> +	    {
>>>    	      tree ptr = gimple_call_arg (stmt, 0);
>>>    	      ao_ref_init_from_ptr_and_size (write, ptr, size);
>> For str[n]cat, I think this is going to result in WRITE not accurately
>> reflecting what bytes are going to be written -- write.offset would
>> have
>> to account for the length of the destination string.
>>
>> I don't see a way in the ao_ref structure to indicate that the offset
>> of
>> a write is unknown.
> 
> You can't make offset entirely unknown but you can use, for strcat, offset zero, size and max_size -1.  It matters that the access range is correct.  This is similar to how we treat array accesses with variable index.
I suspect with a size/maxsize of -1 other code in DSE would probably 
reject the ao_ref.  Though that's probably easier to solve in a way that 
would allow removal of the dead strcat/strncat calls, but not muck up 
other things.

jeff

Re: PR79715: Special case strcpy/strncpy for dse

[Martin Sebor]

On 04/24/2017 03:05 AM, Prathamesh Kulkarni wrote:
> On 1 March 2017 at 13:24, Richard Biener <rguenther@suse.de> wrote:
>> On Tue, 28 Feb 2017, Jeff Law wrote:
>>
>>> On 02/28/2017 05:59 AM, Prathamesh Kulkarni wrote:
>>>> On 28 February 2017 at 15:40, Jakub Jelinek <jakub@redhat.com> wrote:
>>>>> On Tue, Feb 28, 2017 at 03:33:11PM +0530, Prathamesh Kulkarni wrote:
>>>>>> Hi,
>>>>>> The attached patch adds special-casing for strcpy/strncpy to dse pass.
>>>>>> Bootstrapped+tested on x86_64-unknown-linux-gnu.
>>>>>> OK for GCC 8 ?
>>>>>
>>>>> What is special on strcpy/strncpy?  Unlike memcpy/memmove/memset, you
>>>>> don't
>>>>> know the length they store (at least not in general), you don't know the
>>>>> value, all you know is that they are for the first argument plain store
>>>>> without remembering the pointer or anything based on it anywhere except in
>>>>> the return value.
>>>>> I believe stpcpy, stpncpy, strcat, strncat at least have the same
>>>>> behavior.
>>>>> On the other side, without knowing the length of the store, you can't
>>>>> treat
>>>>> it as killing something (ok, some calls like strcpy or stpcpy store at
>>>>> least
>>>>> the first byte).
>>>> Well, I assumed a store to dest by strcpy (and friends), which gets
>>>> immediately freed would count
>>>> as a dead store since free would kill the whole memory block pointed
>>>> to by dest ?
>>> Yes.  But does it happen often in practice?  I wouldn't mind exploring this
>>> for gcc-8, but I'd like to see real-world code where this happens.
>>
>> Actually I don't mind for "real-world code" - the important part is
>> that I believe it's reasonable to assume it can happen from some C++
>> abstraction and optimization.
> Hi,
> I have updated the patch to include stp[n]cpy and str[n]cat.
> In initialize_ao_ref_for_dse for strncat, I suppose for strncat we
> need to treat size as NULL_TREE
> instead of setting it 2nd arg since we cannot know size (in general)
> after strncat ?
> Patch passes bootstrap+test on x86_64-unknown-linux-gnu.
> Cross-tested on arm*-*-*, aarch64*-*-*.

I think I made a mistake when I opened PR79715: I used the wrong
-fdump-tree- option and was looking at the wrong dump.  It turns
out that the test case there is optimized as I expected, except
by a later pass, and has been since r233267.  I resolved the bug
as fixed before I realized that this patch (that I've been meaning
to review) is for that bug, except that it enables the optimization
to take place earlier.  That sounds like a fine idea to me but now
that I closed the bug I wonder if it should be done under a different
bug.  This is just a suggestion and if you don't want to take the
time to raise a new bug for I don't mind if you reopen bug 79715.
Sorry if I made things more complicated than they need to be.

Martin