<div dir="ltr">IR:<div><div>define i32 @calloc_strlen_write_between() {</div><div> %call = tail call noalias i8* @calloc(i32 10, i32 1) </div><div> store i8 97, i8* %call, align 1</div><div> %call1 = tail call i32 @strlen(i8* %call)</div><div> ret i32 %call1</div><div>}</div></div><div><br></div><div><br></div>static bool eliminateStrlen(CallInst *CI, BasicBlock::iterator &BBI,<br>AliasAnalysis *AA, MemoryDependenceResults *MD,<br>const DataLayout &DL, const TargetLibraryInfo *TLI,<br>InstOverlapIntervalsTy &IOL,<br>DenseMap<Instruction *, size_t> *InstrOrdering) {<br><br>// Must be a strlen.<br>LibFunc Func;<br>Function *Callee = CI->getCalledFunction();<br>if (!TLI->getLibFunc(*Callee, Func) || !TLI->has(Func) ||<br>Func != LibFunc_strlen)<br>return false;<br><br>Value *Dst = CI->getOperand(0);<br>Instruction *UnderlyingPointer =<br>dyn_cast<Instruction>(GetUnderlyingObject(Dst, DL));<br>if (!UnderlyingPointer)<br>return false;<br>if (!isStringFromCalloc(Dst, TLI))<br>return false;<br><br>if (memoryIsNotModifiedBetween(UnderlyingPointer, CI, AA)) {<br>Value *Len = ConstantInt::get(CI->getType(), 0);<br>CI->replaceAllUsesWith(Len);<br>CI->eraseFromParent();<br>return true;<br>}<br>return false;<br>}<div><br></div><div><br></div><div>------------------------------------------------------</div><div>That IR is still wrongly transformed with this code to ret i32 0 (but there is write between calloc and strlen). Any suggestions?</div></div><div class="gmail_extra"><br><div class="gmail_quote">2018-05-23 0:49 GMT+02:00 Dávid Bolvanský <span dir="ltr"><<a href="mailto:david.bolvansky@gmail.com" target="_blank">david.bolvansky@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>It works with</div><div><br></div>MemoryLocation MemoryLocation::get(const CallInst *CI) {<br>AAMDNodes AATags;<br>CI->getAAMetadata(AATags);<br>const auto &DL = CI->getModule()-><wbr>getDataLayout();<br><br>return MemoryLocation(CI, DL.getTypeStoreSize(CI-><wbr>getType()), AATags);<br>}<div><br></div><div>Is it fine? :) </div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">2018-05-22 23:56 GMT+02:00 Dávid Bolvanský <span dir="ltr"><<a href="mailto:david.bolvansky@gmail.com" target="_blank">david.bolvansky@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Looks like there are many overloads for "get". <a href="http://llvm.org/doxygen/MemoryLocation_8cpp_source.html" target="_blank">http://llvm.org/doxygen<wbr>/MemoryLocation_8cpp_source.<wbr>html</a><div><br></div><div>But nothing for CallInst. Any suggestions how to do a proper one? I will look at it too.</div></div><div class="m_-7725043753438901422HOEnZb"><div class="m_-7725043753438901422h5"><div class="gmail_extra"><br><div class="gmail_quote">2018-05-22 23:34 GMT+02:00 Dávid Bolvanský <span dir="ltr"><<a href="mailto:david.bolvansky@gmail.com" target="_blank">david.bolvansky@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Full stack trace:<div><br></div><div><span><div>opt: /home/xbolva00/LLVM/llvm/inclu<wbr>de/llvm/ADT/Optional.h:176: T* llvm::Optional<T>::getPointer(<wbr>) [with T = llvm::MemoryLocation]: Assertion `Storage.hasVal' failed.</div></span><div>Stack dump:</div><div>0.<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332gmail-Apple-tab-span" style="white-space:pre-wrap"> </span>Program arguments: opt aaa.ll -dse -S </div><div>1.<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332gmail-Apple-tab-span" style="white-space:pre-wrap"> </span>Running pass 'Function Pass Manager' on module 'aaa.ll'.</div><div>2.<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332gmail-Apple-tab-span" style="white-space:pre-wrap"> </span>Running pass 'Dead Store Elimination' on function '@calloc_strlen'</div><div>LLVMSymbolizer: error reading file: No such file or directory</div><div>#0 0x000056135ebe698a (opt+0x212198a)</div><div>#1 0x000056135ebe4cf4 (opt+0x211fcf4)</div><div>#2 0x000056135ebe4e32 (opt+0x211fe32)</div><div>#3 0x00007f6e35b14150 __restore_rt (/lib/x86_64-linux-gnu/libpthr<wbr>ead.so.0+0x13150)</div><div>#4 0x00007f6e3481b0bb gsignal /build/glibc-itYbWN/glibc-2.26<wbr>/signal/../sysdeps/unix/sysv/l<wbr>inux/raise.c:51:0</div><div>#5 0x00007f6e3481cf5d abort /build/glibc-itYbWN/glibc-2.26<wbr>/stdlib/abort.c:92:0</div><div>#6 0x00007f6e34812f17 __assert_fail_base /build/glibc-itYbWN/glibc-2.26<wbr>/assert/assert.c:92:0</div><div>#7 0x00007f6e34812fc2 (/lib/x86_64-linux-gnu/libc.so<wbr>.6+0x2efc2)</div><div>#8 0x000056135e962b80 (opt+0x1e9db80)</div><div>#9 0x000056135e969260 (opt+0x1ea4260)</div><div>#10 0x000056135e96a6e0 (opt+0x1ea56e0)</div><div>#11 0x000056135e61d561 (opt+0x1b58561)</div><div>#12 0x000056135e61d5d9 (opt+0x1b585d9)</div><div>#13 0x000056135e61cbb7 (opt+0x1b57bb7)</div><div>#14 0x000056135d175216 (opt+0x6b0216)</div><div>#15 0x00007f6e348051c1 __libc_start_main /build/glibc-itYbWN/glibc-2.26<wbr>/csu/../csu/libc-start.c:342:0</div><div>#16 0x000056135d1f404a (opt+0x72f04a)</div></div><div><br></div></div><div class="m_-7725043753438901422m_1114758970894209448HOEnZb"><div class="m_-7725043753438901422m_1114758970894209448h5"><div class="gmail_extra"><br><div class="gmail_quote">2018-05-22 23:32 GMT+02:00 Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128moz-cite-prefix">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.<br>
<br>
(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.)<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332HOEnZb"><font color="#888888"><br>
<br>
-Eli</font></span><div><div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332h5"><br>
<br>
On 5/22/2018 2:16 PM, Dávid Bolvanský wrote:<br>
</div></div></div><div><div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332h5">
<blockquote type="cite">
<div dir="ltr">* <span style="color:rgb(0,0,0);white-space:pre-wrap">if (isStringFromCalloc(Dst, TLI)) should be </span><span style="color:rgb(0,0,0);white-space:pre-wrap">if (!isStringFromCalloc(Dst, TLI))</span>
<div><span style="color:rgb(0,0,0);white-space:pre-wrap">
</span></div>
<div><font color="#000000"><span style="white-space:pre-wrap">but still asserting...</span></font></div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">2018-05-22 23:06 GMT+02:00 Dávid
Bolvanský <span dir="ltr"><<a href="mailto:david.bolvansky@gmail.com" target="_blank">david.bolvansky@gmail.com</a>></span>:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Can you help a bit?
<div><br>
</div>
<div>I try to work with DSE but I got the following
assert:</div>
<div>
<div>opt: /home/xbolva00/LLVM/llvm/inclu<wbr>de/llvm/ADT/Optional.h:176:
T* llvm::Optional<T>::getPointer(<wbr>) [with T
= llvm::MemoryLocation]: Assertion `Storage.hasVal'
failed.</div>
</div>
<div><br>
</div>
<div>
<pre style="color:rgb(0,0,0);word-wrap:break-word;white-space:pre-wrap">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>(GetUnder<wbr>lyingObject(Dst, DL));
if (!UnderlyingPointer)
return false;
if (isStringFromCalloc(Dst, TLI))
return false;
errs() << "before\n";
if (memoryIsNotModifiedBetween(Un<wbr>derlyingPointer, CI, AA)) { <--- CRASH
errs() << "after\n";
}
return false;
}</pre>
<pre style="color:rgb(0,0,0);word-wrap:break-word;white-space:pre-wrap">Do you know what is wrong here? I followed the "example" (in eliminateNoopStore) how to use "memoryIsNotModifiedBetween".</pre>
<pre style="color:rgb(0,0,0);word-wrap:break-word;white-space:pre-wrap"></pre>
<pre style="color:rgb(0,0,0);word-wrap:break-word;white-space:pre-wrap">Thank you for advice</pre>
<pre style="color:rgb(0,0,0);word-wrap:break-word;white-space:pre-wrap"></pre>
</div>
</div>
<div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128HOEnZb">
<div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128h5">
<div class="gmail_extra"><br>
<div class="gmail_quote">2018-05-21 21:06 GMT+02:00
Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span>:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646moz-cite-prefix">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
<a class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646moz-txt-link-freetext" href="https://reviews.llvm.org/D40480" target="_blank">https://reviews.llvm.org/D4048<wbr>0</a>.)<br>
<br>
But yes, memoryIsNotModifiedBetween has the
right meaning.<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139HOEnZb"><font color="#888888"><br>
<br>
-Eli</font></span>
<div>
<div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139h5"><br>
<br>
On 5/21/2018 7:48 AM, Dávid Bolvanský
wrote:<br>
</div>
</div>
</div>
<div>
<div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139h5">
<blockquote type="cite">
<div dir="ltr"><span style="font-size:12.8px">"memory
accesses between the malloc and the
memset</span><span style="font-size:12.8px"> without an
expensive linear scan of the
block/function" </span>
<div><span style="font-size:12.8px"><br>
</span></div>
<div><span style="font-size:12.8px">(1)
do you mean just use
"memoryIsNotModifiedBetween"
function in DSE to check it?</span>
<div><br>
</div>
<div>x = maloc(..);</div>
<div>memset(x, ...) </div>
<div><br>
</div>
<div>(2) GetUnderlyingObject would
give me Value * (from malloc) ?</div>
<div>
<div><span style="font-size:12.8px"><br>
</span></div>
<div><span style="font-size:12.8px">Also
another case:</span></div>
<div><span style="font-size:12.8px"><br>
</span></div>
<div><span style="font-size:12.8px">memset(s,
0, len); // len > 1</span></div>
<div><span style="font-size:12.8px">return
strlen(s); // optimize to 0</span></div>
<div><span style="font-size:12.8px"><br>
</span></div>
<div><span style="font-size:12.8px">(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?</span></div>
<div><span style="font-size:12.8px"><br>
</span></div>
<div><span style="font-size:12.8px">(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)</span></div>
<div><span style="font-size:12.8px"><br>
</span></div>
<div><span style="font-size:12.8px">(5)
new malloc memset folding /
memset + strlen case should be
implemented in DSE, right?</span></div>
</div>
</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">2018-05-17
21:36 GMT+02:00 Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span>:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646m_6141790905467921389moz-cite-prefix">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.)<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646HOEnZb"><font color="#888888"><br>
<br>
-Eli</font></span>
<div>
<div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646h5"><br>
<br>
On 5/17/2018 12:17 PM, Dávid
Bolvanský wrote:<br>
</div>
</div>
</div>
<div>
<div class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646h5">
<blockquote type="cite">
<div dir="ltr">As we talked
in <a href="https://reviews.llvm.org/D45344" target="_blank">https://reviews.llvm.org/D4534<wbr>4</a>,
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.
<div><br>
</div>
<div>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? </div>
<div>We have standard
malloc + memset folding
there, so a few new
lines should not do bad
things.</div>
<div><br>
</div>
<div>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.<br>
<div><br>
</div>
<div><br>
</div>
</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">2018-05-17
21:00 GMT+02:00
Friedman, Eli <span dir="ltr"><<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span>:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>On
5/17/2018 8:58 AM,
Dávid Bolvanský via
llvm-dev wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hello,<br>
<br>
I would like to
find a way to do
this removal
properly. I found
DSE and
"eliminateNoopStore"
can be useful for
this thing.<br>
<br>
What I mean?<br>
int *test =
malloc(15 *
sizeof(int));<br>
test[10] = 12;
< ----- remove
this store<br>
memset(test,0,sizeof(int) * 15);<br>
</blockquote>
<br>
</span> This is
classic dead store
elimination, and it's
already handled by
DSE. At least, we
optimize the following
testcase:<br>
<br>
#include
<stdlib.h><br>
#include
<string.h><br>
void bar(int*);<br>
void f() {<span><br>
int *test =
malloc(15 *
sizeof(int));<br>
test[10] = 12;<br>
</span>
memset(test,0,sizeof(int)
* 15);<br>
bar(test);<br>
}<br>
<br>
You should be able to
look at the existing
code to understand how
it's handled (using
MemoryDependenceAnalysis).<span class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646m_6141790905467921389HOEnZb"><font color="#888888"><br>
<br>
-Eli<br>
<br>
-- <br>
Employee of
Qualcomm
Innovation Center,
Inc.<br>
Qualcomm
Innovation Center,
Inc. is a member
of Code Aurora
Forum, a Linux
Foundation
Collaborative
Project<br>
<br>
</font></span></blockquote>
</div>
<br>
</div>
</blockquote>
<p><br>
</p>
<pre class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646m_6141790905467921389moz-signature" cols="72">--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</blockquote>
<p><br>
</p>
<pre class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646moz-signature" cols="72">--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</blockquote>
<p><br>
</p>
<pre class="m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128moz-signature" cols="72">--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
</div></div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>