[llvm-dev] DSE: Remove useless stores between malloc & memset

[Friedman, Eli via llvm-dev]

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>