llvm dev - May 2018 - DSE: Remove useless stores between malloc & memset

Hello,

I would like to find a way to do this removal properly. I found DSE and
"eliminateNoopStore" can be useful for this thing.

What I mean?
int *test = malloc(15 * sizeof(int));
test[10] = 12; < ----- remove this store
memset(test,0,sizeof(int) * 15);

I already checked the function "eliminateNoopStore".
Looks good, I think I would be to get the value ("A") we store to, is
from
malloc. Then a pointer capture analysis would be performed. These steps
should not be hard.

The problem: how to do the detection that the value "A" is later
zeroed
using memset? Traverse over all uses of "A"? Can you recommend me the
proper way how to check this?

Thank you

p.s: In the future it could be used for proper malloc + memset folding to
calloc, currently it is a bit suboptimal.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180517/bfc008ea/attachment.html>

On 5/17/2018 8:58 AM, Dávid Bolvanský via llvm-dev
wrote:
> Hello,
>
> I would like to find a way to do this removal properly. I found DSE 
> and "eliminateNoopStore" can be useful for this thing.
>
> What I mean?
> int *test = malloc(15 * sizeof(int));
> test[10] = 12; < ----- remove this store
> memset(test,0,sizeof(int) * 15);
This is classic dead store elimination, and it's already handled by DSE. 
At least, we optimize the following testcase:

#include <stdlib.h>
#include <string.h>
void bar(int*);
void f() {
   int *test = malloc(15 * sizeof(int));
   test[10] = 12;
   memset(test,0,sizeof(int) * 15);
   bar(test);
}

You should be able to look at the existing code to understand how it's 
handled (using MemoryDependenceAnalysis).

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

"memory accesses between the malloc and the memset without an expensive
linear scan of the block/function"

(1) do you mean just use "memoryIsNotModifiedBetween" function in DSE
to
check it?

x = maloc(..);
memset(x, ...)

(2) GetUnderlyingObject would give me Value * (from malloc) ?

Also another case:

memset(s, 0, len); // len > 1
return strlen(s); // optimize to 0

(3) How to check memset and strlen pairs? I have a strlen call, I have a
"Value *" for "s". What is the best way to construct memset
+ strlen pairs?

(4) Can this be somehow generalized (and not only for strlen)? So
GetStringLength in ValueTracking would be taught about this info (string is
empty after memset)

(5) new malloc memset folding /  memset + strlen case should be implemented
in DSE, right?

2018-05-17 21:36 GMT+02:00 Friedman, Eli <efriedma at codeaurora.org>:
> The fundamental problem with trying to do that sort of transform in
> instcombine is that you don't have access to MemoryDependenceAnalysis
or
> MemorySSA; you need a data structure like that to figure out whether there
> are any memory accesses between the malloc and the memset without an
> expensive linear scan of the block/function.  (You can sort of get around
> the problem in simple cases by adding arbitrary limits to the number of you
> scan, but it doesn't generalize well.)
>
> -Eli
>
>
> On 5/17/2018 12:17 PM, Dávid Bolvanský wrote:
>
> As we talked in https://reviews.llvm.org/D45344, the problem was dead
> stores. And I know why :D There was just -instcombine pass. I forgot to do
> -dse before -instcombine so this is why I did custom "store
removal" code
> there.
>
> I would like to finish malloc + llvm.memset folding. Yes, you told you
> would like to see the whole foldMallocMemset in DSE but extend it for
> llvm.memset in InstCombine... is it really so bad to do?
> We have standard malloc + memset folding there, so a  few  new lines
> should not do bad things.
>
> If I reopen D45344, reupload patch with removed my custom "store
removal"
> code, It could be ok, no? The patch as is worked/works for me for malloc
> + llvm.memset folding, I would just add -dse to tests to handle dead
stores.
>
>
>
> 2018-05-17 21:00 GMT+02:00 Friedman, Eli <efriedma at
codeaurora.org>:
>
>> On 5/17/2018 8:58 AM, Dávid Bolvanský via llvm-dev wrote:
>>
>>> Hello,
>>>
>>> I would like to find a way to do this removal properly. I found DSE
and
>>> "eliminateNoopStore" can be useful for this thing.
>>>
>>> What I mean?
>>> int *test = malloc(15 * sizeof(int));
>>> test[10] = 12; < ----- remove this store
>>> memset(test,0,sizeof(int) * 15);
>>>
>>
>> This is classic dead store elimination, and it's already handled by
DSE.
>> At least, we optimize the following testcase:
>>
>> #include <stdlib.h>
>> #include <string.h>
>> void bar(int*);
>> void f() {
>>   int *test = malloc(15 * sizeof(int));
>>   test[10] = 12;
>>   memset(test,0,sizeof(int) * 15);
>>   bar(test);
>> }
>>
>> You should be able to look at the existing code to understand how
it's
>> handled (using MemoryDependenceAnalysis).
>>
>> -Eli
>>
>> --
>> Employee of Qualcomm Innovation Center, Inc.
>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a
>> Linux Foundation Collaborative Project
>>
>>
>
> --
> Employee of Qualcomm Innovation Center, Inc.
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180521/7d2454cb/attachment-0001.html>

memoryIsNotModifiedBetween is precisely the sort of expensive walk we 
shouldn't be doing... I'm surprised it hasn't caused any serious
issues
yet.  Ideally, what we should be doing is using MemorySSA to find a 
dependency from the memset: if the closest dependency is the malloc, 
there aren't any stores between the memset and the malloc.  (But we 
aren't using MemorySSA in DSE yet; see https://reviews.llvm.org/D40480.)

But yes, memoryIsNotModifiedBetween has the right meaning.

-Eli

On 5/21/2018 7:48 AM, Dávid Bolvanský wrote:
> "memory accesses between the malloc and the memset without an 
> expensive linear scan of the block/function"
>
> (1) do you mean just use "memoryIsNotModifiedBetween" function in
DSE
> to check it?
>
> x = maloc(..);
> memset(x, ...)
>
> (2) GetUnderlyingObject would give me Value * (from malloc) ?
>
> Also another case:
>
> memset(s, 0, len); // len > 1
> return strlen(s); // optimize to 0
>
> (3) How to check memset and strlen pairs? I have a strlen call, I have 
> a "Value *" for "s". What is the best way to construct
memset +
> strlen pairs?
>
> (4) Can this be somehow generalized (and not only for strlen)? So 
> GetStringLength in ValueTracking would be taught about this info 
> (string is empty after memset)
>
> (5) new malloc memset folding /  memset + strlen case should be 
> implemented in DSE, right?
>
> 2018-05-17 21:36 GMT+02:00 Friedman, Eli <efriedma at codeaurora.org 
> <mailto:efriedma at codeaurora.org>>:
>
>     The fundamental problem with trying to do that sort of transform
>     in instcombine is that you don't have access to
>     MemoryDependenceAnalysis or MemorySSA; you need a data structure
>     like that to figure out whether there are any memory accesses
>     between the malloc and the memset without an expensive linear scan
>     of the block/function. (You can sort of get around the problem in
>     simple cases by adding arbitrary limits to the number of you scan,
>     but it doesn't generalize well.)
>
>     -Eli
>
>
>     On 5/17/2018 12:17 PM, Dávid Bolvanský wrote:
>>     As we talked in https://reviews.llvm.org/D45344
>>     <https://reviews.llvm.org/D45344>, the problem was dead
stores.
>>     And I know why :D There was just -instcombine pass. I forgot to
>>     do -dse before -instcombine so this is why I did custom "store
>>     removal" code there.
>>
>>     I would like to finish malloc + llvm.memset folding. Yes, you
>>     told you would like to see the whole foldMallocMemset in DSE but
>>     extend it for llvm.memset in InstCombine... is it really so bad
>>     to do?
>>     We have standard malloc + memset folding there, so a  few  new
>>     lines should not do bad things.
>>
>>     If I reopen D45344, reupload patch with removed my custom
"store
>>     removal" code, It could be ok, no? The patch as is
worked/works
>>     for me for malloc + llvm.memset folding, I would just add -dse to
>>     tests to handle dead stores.
>>
>>
>>
>>     2018-05-17 21:00 GMT+02:00 Friedman, Eli <efriedma at
codeaurora.org
>>     <mailto:efriedma at codeaurora.org>>:
>>
>>         On 5/17/2018 8:58 AM, Dávid Bolvanský via llvm-dev wrote:
>>
>>             Hello,
>>
>>             I would like to find a way to do this removal properly. I
>>             found DSE and "eliminateNoopStore" can be useful
for this
>>             thing.
>>
>>             What I mean?
>>             int *test = malloc(15 * sizeof(int));
>>             test[10] = 12; < ----- remove this store
>>             memset(test,0,sizeof(int) * 15);
>>
>>
>>         This is classic dead store elimination, and it's already
>>         handled by DSE. At least, we optimize the following testcase:
>>
>>         #include <stdlib.h>
>>         #include <string.h>
>>         void bar(int*);
>>         void f() {
>>           int *test = malloc(15 * sizeof(int));
>>           test[10] = 12;
>>           memset(test,0,sizeof(int) * 15);
>>           bar(test);
>>         }
>>
>>         You should be able to look at the existing code to understand
>>         how it's handled (using MemoryDependenceAnalysis).
>>
>>         -Eli
>>
>>         -- 
>>         Employee of Qualcomm Innovation Center, Inc.
>>         Qualcomm Innovation Center, Inc. is a member of Code Aurora
>>         Forum, a Linux Foundation Collaborative Project
>>
>>
>
>     -- 
>     Employee of Qualcomm Innovation Center, Inc.
>     Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a
Linux Foundation Collaborative Project
>
>
-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180521/6ec2e2cd/attachment.html>