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>
Friedman, Eli via llvm-dev
2018-May-22 21:32 UTC
[llvm-dev] DSE: Remove useless stores between malloc & memset
It looks like the memoryIsNotModifiedBetween assumes the second argument is a store, or some other instruction supported by MemoryLocation::get. If you're passing in something else, you'll have to compute the MemoryLocation some other way. (Generally, if you're asking a question about an assertion, please include the whole stack trace; it's hard to guess what's happening otherwise.) -Eli On 5/22/2018 2:16 PM, Dávid Bolvanský wrote:> * 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 > <mailto: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 > <mailto: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 > <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 > > >-- 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/d2db1581/attachment-0001.html>
Dávid Bolvanský via llvm-dev
2018-May-22 21:34 UTC
[llvm-dev] DSE: Remove useless stores between malloc & memset
Full stack trace: opt: /home/xbolva00/LLVM/llvm/include/llvm/ADT/Optional.h:176: T* llvm::Optional<T>::getPointer() [with T = llvm::MemoryLocation]: Assertion `Storage.hasVal' failed. Stack dump: 0. Program arguments: opt aaa.ll -dse -S 1. Running pass 'Function Pass Manager' on module 'aaa.ll'. 2. Running pass 'Dead Store Elimination' on function '@calloc_strlen' LLVMSymbolizer: error reading file: No such file or directory #0 0x000056135ebe698a (opt+0x212198a) #1 0x000056135ebe4cf4 (opt+0x211fcf4) #2 0x000056135ebe4e32 (opt+0x211fe32) #3 0x00007f6e35b14150 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x13150) #4 0x00007f6e3481b0bb gsignal /build/glibc-itYbWN/glibc-2.26/signal/../sysdeps/unix/sysv/linux/raise.c:51:0 #5 0x00007f6e3481cf5d abort /build/glibc-itYbWN/glibc-2.26/stdlib/abort.c:92:0 #6 0x00007f6e34812f17 __assert_fail_base /build/glibc-itYbWN/glibc-2.26/assert/assert.c:92:0 #7 0x00007f6e34812fc2 (/lib/x86_64-linux-gnu/libc.so.6+0x2efc2) #8 0x000056135e962b80 (opt+0x1e9db80) #9 0x000056135e969260 (opt+0x1ea4260) #10 0x000056135e96a6e0 (opt+0x1ea56e0) #11 0x000056135e61d561 (opt+0x1b58561) #12 0x000056135e61d5d9 (opt+0x1b585d9) #13 0x000056135e61cbb7 (opt+0x1b57bb7) #14 0x000056135d175216 (opt+0x6b0216) #15 0x00007f6e348051c1 __libc_start_main /build/glibc-itYbWN/glibc-2.26/csu/../csu/libc-start.c:342:0 #16 0x000056135d1f404a (opt+0x72f04a) 2018-05-22 23:32 GMT+02:00 Friedman, Eli <efriedma at codeaurora.org>:> It looks like the memoryIsNotModifiedBetween assumes the second argument > is a store, or some other instruction supported by MemoryLocation::get. If > you're passing in something else, you'll have to compute the MemoryLocation > some other way. > > (Generally, if you're asking a question about an assertion, please include > the whole stack trace; it's hard to guess what's happening otherwise.) > > -Eli > > > On 5/22/2018 2:16 PM, Dávid Bolvanský wrote: > > * 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 >>> >>> >> > > -- > 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/08935635/attachment.html>