Friedman, Eli via llvm-dev
2018-May-22 23:08 UTC
[llvm-dev] DSE: Remove useless stores between malloc & memset
You might want to look more carefully at how you're constructing the MemoryLocation. The first argument is a pointer, and the second argument is the number of bytes pointed to by that pointer (or MemoryLocation::UnknownSize if the number of bytes accessed isn't known). More generally, copy-pasting code you don't understand isn't a good idea. -Eli On 5/22/2018 4:02 PM, Dávid Bolvanský wrote:> IR: > define i32 @calloc_strlen_write_between() { > %call = tail call noalias i8* @calloc(i32 10, i32 1) > store i8 97, i8* %call, align 1 > %call1 = tail call i32 @strlen(i8* %call) > ret i32 %call1 > } > > > 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; > > if (memoryIsNotModifiedBetween(UnderlyingPointer, CI, AA)) { > Value *Len = ConstantInt::get(CI->getType(), 0); > CI->replaceAllUsesWith(Len); > CI->eraseFromParent(); > return true; > } > return false; > } > > > ------------------------------------------------------ > That IR is still wrongly transformed with this code to ret i32 0 (but > there is write between calloc and strlen). Any suggestions? > > 2018-05-23 0:49 GMT+02:00 Dávid Bolvanský <david.bolvansky at gmail.com > <mailto:david.bolvansky at gmail.com>>: > > It works with > > MemoryLocation MemoryLocation::get(const CallInst *CI) { > AAMDNodes AATags; > CI->getAAMetadata(AATags); > const auto &DL = CI->getModule()->getDataLayout(); > > return MemoryLocation(CI, DL.getTypeStoreSize(CI->getType()), AATags); > } > > Is it fine? :) > > 2018-05-22 23:56 GMT+02:00 Dávid Bolvanský > <david.bolvansky at gmail.com <mailto:david.bolvansky at gmail.com>>: > > Looks like there are many overloads for "get". > http://llvm.org/doxygen/MemoryLocation_8cpp_source.html > <http://llvm.org/doxygen/MemoryLocation_8cpp_source.html> > > But nothing for CallInst. Any suggestions how to do a proper > one? I will look at it too. > > 2018-05-22 23:34 GMT+02:00 Dávid Bolvanský > <david.bolvansky at gmail.com <mailto:david.bolvansky at gmail.com>>: > > 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 <mailto: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 >> <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 > > > > >-- 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/b4fab287/attachment-0001.html>
Dávid Bolvanský via llvm-dev
2018-May-22 23:22 UTC
[llvm-dev] DSE: Remove useless stores between malloc & memset
Yeah, sorry for that. Better "It compiles ok (but maybe incorrect code)", not "It works" as I wrote. 2018-05-23 1:08 GMT+02:00 Friedman, Eli <efriedma at codeaurora.org>:> You might want to look more carefully at how you're constructing the > MemoryLocation. The first argument is a pointer, and the second argument > is the number of bytes pointed to by that pointer (or > MemoryLocation::UnknownSize if the number of bytes accessed isn't known). > > More generally, copy-pasting code you don't understand isn't a good idea. > > -Eli > > > On 5/22/2018 4:02 PM, Dávid Bolvanský wrote: > > IR: > define i32 @calloc_strlen_write_between() { > %call = tail call noalias i8* @calloc(i32 10, i32 1) > store i8 97, i8* %call, align 1 > %call1 = tail call i32 @strlen(i8* %call) > ret i32 %call1 > } > > > 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; > > if (memoryIsNotModifiedBetween(UnderlyingPointer, CI, AA)) { > Value *Len = ConstantInt::get(CI->getType(), 0); > CI->replaceAllUsesWith(Len); > CI->eraseFromParent(); > return true; > } > return false; > } > > > ------------------------------------------------------ > That IR is still wrongly transformed with this code to ret i32 0 (but > there is write between calloc and strlen). Any suggestions? > > 2018-05-23 0:49 GMT+02:00 Dávid Bolvanský <david.bolvansky at gmail.com>: > >> It works with >> >> MemoryLocation MemoryLocation::get(const CallInst *CI) { >> AAMDNodes AATags; >> CI->getAAMetadata(AATags); >> const auto &DL = CI->getModule()->getDataLayout(); >> >> return MemoryLocation(CI, DL.getTypeStoreSize(CI->getType()), AATags); >> } >> >> Is it fine? :) >> >> 2018-05-22 23:56 GMT+02:00 Dávid Bolvanský <david.bolvansky at gmail.com>: >> >>> Looks like there are many overloads for "get". http://llvm.org/doxygen >>> /MemoryLocation_8cpp_source.html >>> >>> But nothing for CallInst. Any suggestions how to do a proper one? I will >>> look at it too. >>> >>> 2018-05-22 23:34 GMT+02:00 Dávid Bolvanský <david.bolvansky at gmail.com>: >>> >>>> 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/libpthr >>>> ead.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 >>>>> >>>>> >>>> >>> >> > > -- > 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/20180523/b8db7b11/attachment.html>
Dávid Bolvanský via llvm-dev
2018-May-22 23:56 UTC
[llvm-dev] DSE: Remove useless stores between malloc & memset
Can you review https://reviews.llvm.org/D47237? My tests look ok but I am still not sure about MemoryLocation::get(const CallInst *CI) if implemented correctly. This is my first patch for DSE, so I am aware of "DSE" things I don't know yet but I like to learn new things :) 2018-05-23 1:22 GMT+02:00 Dávid Bolvanský <david.bolvansky at gmail.com>:> Yeah, sorry for that. Better "It compiles ok (but maybe incorrect code)", > not "It works" as I wrote. > > 2018-05-23 1:08 GMT+02:00 Friedman, Eli <efriedma at codeaurora.org>: > >> You might want to look more carefully at how you're constructing the >> MemoryLocation. The first argument is a pointer, and the second argument >> is the number of bytes pointed to by that pointer (or >> MemoryLocation::UnknownSize if the number of bytes accessed isn't known). >> >> More generally, copy-pasting code you don't understand isn't a good idea. >> >> -Eli >> >> >> On 5/22/2018 4:02 PM, Dávid Bolvanský wrote: >> >> IR: >> define i32 @calloc_strlen_write_between() { >> %call = tail call noalias i8* @calloc(i32 10, i32 1) >> store i8 97, i8* %call, align 1 >> %call1 = tail call i32 @strlen(i8* %call) >> ret i32 %call1 >> } >> >> >> 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; >> >> if (memoryIsNotModifiedBetween(UnderlyingPointer, CI, AA)) { >> Value *Len = ConstantInt::get(CI->getType(), 0); >> CI->replaceAllUsesWith(Len); >> CI->eraseFromParent(); >> return true; >> } >> return false; >> } >> >> >> ------------------------------------------------------ >> That IR is still wrongly transformed with this code to ret i32 0 (but >> there is write between calloc and strlen). Any suggestions? >> >> 2018-05-23 0:49 GMT+02:00 Dávid Bolvanský <david.bolvansky at gmail.com>: >> >>> It works with >>> >>> MemoryLocation MemoryLocation::get(const CallInst *CI) { >>> AAMDNodes AATags; >>> CI->getAAMetadata(AATags); >>> const auto &DL = CI->getModule()->getDataLayout(); >>> >>> return MemoryLocation(CI, DL.getTypeStoreSize(CI->getType()), AATags); >>> } >>> >>> Is it fine? :) >>> >>> 2018-05-22 23:56 GMT+02:00 Dávid Bolvanský <david.bolvansky at gmail.com>: >>> >>>> Looks like there are many overloads for "get". http://llvm.org/doxygen >>>> /MemoryLocation_8cpp_source.html >>>> >>>> But nothing for CallInst. Any suggestions how to do a proper one? I >>>> will look at it too. >>>> >>>> 2018-05-22 23:34 GMT+02:00 Dávid Bolvanský <david.bolvansky at gmail.com>: >>>> >>>>> 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/libpthr >>>>> ead.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 >>>>>> >>>>>> >>>>> >>>> >>> >> >> -- >> 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/20180523/82c80117/attachment-0001.html>