PR79715: Special case strcpy/strncpy for dse

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

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

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

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

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.