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