Re: [RFA] [tree-optimization/80576] Handle non-constant sizes in DSE

[Martin Sebor <msebor@gmail.com>]

On 8/16/19 12:15 PM, Jeff Law wrote:
> On 8/16/19 12:09 PM, Marc Glisse wrote:
>> On Fri, 16 Aug 2019, Jeff Law wrote:
>>
>>> This patch improves our ability to detect dead stores by handling cases
>>> where the size memcpy, memset, strncpy, etc call is not constant.  This
>>> addresses some, but not all, of the issues in 80576.
>>>
>>> The key here is when the size is not constant we can make conservative
>>> decisions that still give us a chance to analyze the code for dead
>>> stores.
>>>
>>> Remember that for dead store elimination, we're trying to prove that
>>> given two stores, the second store overwrites (partially or fully) the
>>> same memory locations as the first store.  That makes the first store
>>> either partially or fully dead.
>>>
>>> When we encounter the first store, we set up a bitmap of bytes written
>>> by that store (live_bytes).  We then look at subsequent stores and clear
>>> the appropriate entries in the bitmap.
>>>
>>> If the first store has a nonconstant length argument we can use the
>>> range of the length argument (max) and the size of the destination
>>> object to make a conservative estimation of how many bytes are written.
>>>
>>> For the second store the conservative thing to do for a non-constant
>>> length is to use the minimum of the range of the length argument.
>>
>> So I guess it won't handle things like
>>
>> void f(char*p,int n){
>>    __builtin_memset(p,3,n);
>>    __builtin_memset(p,7,n);
>> }
>>
>> where we know nothing about the length, except that it is the same? Or
>> do you look at symbolic ranges?
> Nope.  I think ao_ref can represent that, so it'd just be a matter of
> recording "n" as the length, then verifying that the second call's
> length is "n" as well.  That makes the first call dead.  We'd have to
> bypass the byte tracking in that case, but I think that's trivial
> because we already have a means to do that when the sizes are too large.
> 
>>
>>> This doesn't come up a lot in practice.  But it also happens to put some
>>> of the infrastructure in place to handle strcpy and strcpy_chk which are
>>> needed to fully resolve 80576.
>>>
>>> Bootstrapped and regression tested on x86, x86_64, ppc64le, ppc64,
>>> ppc32, aarch64, sparc, s390x and probably others.  Also verified that
>>> the tests work on the various *-elf targets in my tester.
>>>
>>> OK for the trunk?
>>
>> ENOPATCH
> Opps.    Attached.

It's an improvement and I realize you said it doesn't handle
everything and that you don't think it comes up a lot, but...
I would actually expect the following example (from the bug)
not to be that uncommon:

   void g (char *s)
   {
     char a[8];
     __builtin_strcpy (a, s);
     __builtin_memset (a, 0, sizeof a);
     f (a);
   }

or at least to be more common than the equivalent alternative
the improvement does optimize:

   void g (char *s)
   {
     char a[8];
     __builtin_memcpy (a, s,  __builtin_strlen (s));
     __builtin_memset (a, 0, 8);
     f (a);
   }

It seems that making the first one work should be just a matter
of handling strcpy analogously (the string length doesn't matter).

As an aside, the new tests make me realize that -Wstringop-overflow
should be enhanced to detect this problem (i.e., a consider
the largest size in a PHI).

Martin