<div dir="ltr">Yeah, sorry for that. Better "It compiles ok (but maybe incorrect code)", not "It works" as I wrote.</div><div class="gmail_extra"><br><div class="gmail_quote">2018-05-23 1:08 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_8185826331694245796moz-cite-prefix">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).<br>
<br>
More generally, copy-pasting code you don't understand isn't a
good idea.<span class="HOEnZb"><font color="#888888"><br>
<br>
-Eli</font></span><div><div class="h5"><br>
<br>
On 5/22/2018 4:02 PM, Dávid Bolvanský wrote:<br>
</div></div></div><div><div class="h5">
<blockquote type="cite">
<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>(<wbr>GetUnderlyingObject(Dst, DL));<br>
if (!UnderlyingPointer)<br>
return false;<br>
if (!isStringFromCalloc(Dst, TLI))<br>
return false;<br>
<br>
if (memoryIsNotModifiedBetween(<wbr>UnderlyingPointer, CI, AA)) {<br>
Value *Len = ConstantInt::get(CI->getType()<wbr>, 0);<br>
CI->replaceAllUsesWith(Len);<br>
CI->eraseFromParent();<br>
return true;<br>
}<br>
return false;<br>
}
<div><br>
</div>
<div><br>
</div>
<div>------------------------------<wbr>------------------------</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()->getDataLayout<wbr>();<br>
<br>
return MemoryLocation(CI, DL.getTypeStoreSize(CI->getTyp<wbr>e()),
AATags);<br>
}
<div><br>
</div>
<div>Is it fine? :) </div>
</div>
<div class="m_8185826331694245796HOEnZb">
<div class="m_8185826331694245796h5">
<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.ht<wbr>ml</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_8185826331694245796m_-7725043753438901422HOEnZb">
<div class="m_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-7725043753438901422m_1114758970894209448HOEnZb">
<div class="m_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-7725043753438901422m_1114758970894209448m_2789134658292105332HOEnZb"><font color="#888888"><br>
<br>
-Eli</font></span>
<div>
<div class="m_8185826331694245796m_-7725043753438901422m_1114758970894209448m_2789134658292105332h5"><br>
<br>
On 5/22/2018 2:16 PM,
Dávid Bolvanský wrote:<br>
</div>
</div>
</div>
<div>
<div class="m_8185826331694245796m_-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">Thank you for advice</pre>
</div>
</div>
<div class="m_8185826331694245796m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128HOEnZb">
<div class="m_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139HOEnZb"><font color="#888888"><br>
<br>
-Eli</font></span>
<div>
<div class="m_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-7725043753438901422m_1114758970894209448m_2789134658292105332m_6541513188302750128m_3282544529915536139m_7569404264700124646HOEnZb"><font color="#888888"><br>
<br>
-Eli</font></span>
<div>
<div class="m_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-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_8185826331694245796m_-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>
</blockquote>
<p><br>
</p>
<pre class="m_8185826331694245796moz-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>