Friedman, Eli via llvm-dev
2018-May-21 19:06 UTC
[llvm-dev] DSE: Remove useless stores between malloc & memset
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>
Dávid Bolvanský via llvm-dev
2018-May-22 21:06 UTC
[llvm-dev] DSE: Remove useless stores between malloc & memset
Can you help a bit?
I try to work with DSE but I got the following assert:
opt: /home/xbolva00/LLVM/llvm/include/llvm/ADT/Optional.h:176: T*
llvm::Optional<T>::getPointer() [with T = llvm::MemoryLocation]: Assertion
`Storage.hasVal' failed.
static bool eliminateStrlen(CallInst *CI, BasicBlock::iterator &BBI,
AliasAnalysis *AA, MemoryDependenceResults *MD,
const DataLayout &DL, const TargetLibraryInfo
*TLI,
InstOverlapIntervalsTy &IOL,
DenseMap<Instruction *, size_t>
*InstrOrdering) {
// Must be a strlen.
LibFunc Func;
Function *Callee = CI->getCalledFunction();
if (!TLI->getLibFunc(*Callee, Func) || !TLI->has(Func) ||
Func != LibFunc_strlen)
return false;
Value *Dst = CI->getOperand(0);
Instruction *UnderlyingPointer
dyn_cast<Instruction>(GetUnderlyingObject(Dst, DL));
if (!UnderlyingPointer)
return false;
if (isStringFromCalloc(Dst, TLI))
return false;
errs() << "before\n";
if (memoryIsNotModifiedBetween(UnderlyingPointer, CI, AA)) { <--- CRASH
errs() << "after\n";
}
return false;
}
Do you know what is wrong here? I followed the "example" (in
eliminateNoopStore) how to use "memoryIsNotModifiedBetween".
Thank you for advice
2018-05-21 21:06 GMT+02:00 Friedman, Eli <efriedma at codeaurora.org>:
> 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>:
>
>> 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
>>
>>
>
> --
> 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/20180522/e6b1022e/attachment.html>
Dávid Bolvanský via llvm-dev
2018-May-22 21:16 UTC
[llvm-dev] DSE: Remove useless stores between malloc & memset
* if (isStringFromCalloc(Dst, TLI)) should be if (!isStringFromCalloc(Dst, TLI)) but still asserting... 2018-05-22 23:06 GMT+02:00 Dávid Bolvanský <david.bolvansky at gmail.com>:> Can you help a bit? > > I try to work with DSE but I got the following assert: > opt: /home/xbolva00/LLVM/llvm/include/llvm/ADT/Optional.h:176: T* > llvm::Optional<T>::getPointer() [with T = llvm::MemoryLocation]: > Assertion `Storage.hasVal' failed. > > static bool eliminateStrlen(CallInst *CI, BasicBlock::iterator &BBI, > AliasAnalysis *AA, MemoryDependenceResults *MD, > const DataLayout &DL, const TargetLibraryInfo *TLI, > InstOverlapIntervalsTy &IOL, > DenseMap<Instruction *, size_t> *InstrOrdering) { > > // Must be a strlen. > LibFunc Func; > Function *Callee = CI->getCalledFunction(); > if (!TLI->getLibFunc(*Callee, Func) || !TLI->has(Func) || > Func != LibFunc_strlen) > return false; > > Value *Dst = CI->getOperand(0); > Instruction *UnderlyingPointer = dyn_cast<Instruction>(GetUnderlyingObject(Dst, DL)); > if (!UnderlyingPointer) > return false; > if (isStringFromCalloc(Dst, TLI)) > return false; > errs() << "before\n"; > if (memoryIsNotModifiedBetween(UnderlyingPointer, CI, AA)) { <--- CRASH > errs() << "after\n"; > } > return false; > } > > Do you know what is wrong here? I followed the "example" (in eliminateNoopStore) how to use "memoryIsNotModifiedBetween". > > > Thank you for advice > > > > 2018-05-21 21:06 GMT+02:00 Friedman, Eli <efriedma at codeaurora.org>: > >> 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>: >> >>> 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 >>> >>> >> >> -- >> 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/20180522/34e7bd94/attachment.html>