[prev in list] [next in list] [prev in thread] [next in thread]
List: cfe-dev
Subject: Re: [cfe-dev] [LLVMdev] Clang devirtualization proposal
From: Richard Smith <richard () metafoo ! co ! uk>
Date: 2015-07-23 21:21:42
Message-ID: CAOfiQq=tRcTO7Fuxnh3KBaQMfvUxNn83O6-vCxqMwzPdafJTpw () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
On Thu, Jul 23, 2015 at 11:42 AM, Piotr Padlewski <prazek@google.com> wrote:
> HI,
> Yep, our proposal doesn't cover it, because this load ; icmp ; assume;
> will land global initilizer function, and main will not see it.
> At least if foo would be called multiple times, then we would only have
> one load from vtable, but unfortunatelly we will not be able to inline, or
> make direct call to it with this approach.
> I think that this case is rare enough to solve it right now.
>
> Piotr
>
> On Thu, Jul 23, 2015 at 10:30 AM, Geoff Berry <gberry@codeaurora.org>
> wrote:
>
> > Hi Piotr,
> >
> >
> >
> > You may be interested in a recent patch I posted:
> > http://reviews.llvm.org/D11043
> > <https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D11043&d=AwM \
> > FaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=CnzuN65ENJ1H9py9XLiRvC_UQz6u3oG6GUNn7_wosSM&m=JLBFM \
> > HsMRUHs511X66Fr1fopHJ5WsTkKXLZ9GtX-koY&s=5EY4grsmJL7GyufHaG_GcSgPmas2OC8dUU-0BD8tM5g&e=>
> >
> > This patch addresses a de-virtualization case that I'm not sure would be
> > handled by your current proposal, namely that of a virtual call where the
> > ‘this' object is a global variable.
> >
> > For example:
> >
> >
> >
> > struct A {
> >
> > A();
> >
> > virtual void foo();
> >
> > };
> >
> > void g(A * a) {
> >
> > a->foo();
> >
> > }
> >
> >
> >
> > A a;
> >
> > int main() {
> >
> > g(&a);
> >
>
We could in principle emit the load/icmp/assume for a's vptr here, but I'm
concerned that this is not actually sound in general. Consider:
struct A;
extern A a;
void *p = &a; // emit load/icmp/assume here?
struct A { virtual void f(); };
A a;
If we emit an assume on the vptr at the point where the address of a is
taken, we get:
@a = global %A zeroinitializer
void @global_init() {
load @a
%x = icmp @a, @A.vtable
call @llvm.assume(%x)
store @a, @p
call @A::A(@a)
}
... where the assume call can be folded to "call @llvm.assume(i1 false)",
which (presumably) can be reduced further to "unreachable" (oops). (In
Geoff's example, this is sound only because we're guaranteed that 'a' is
initialized before we enter 'main', but an optimization that only fires for
code within 'main' doesn't sound very useful.)
We could support this with something weaker than the current
load/icmp/assume pattern: we could imagine an instruction/intrinsic that
says "any later load of pointer %p with !invariant.group !g will load the
value %q", but that does not imply that the value %q is currently stored in
%p. It's not clear to me whether that has sufficient value to be worthwhile.
}
> >
> >
> >
> > It might be worth considering if your approach could be extended to
> > handle this case.
> >
> >
> >
> > --
> >
> > Geoff Berry
> >
> > Employee of Qualcomm Innovation Center, Inc.
> >
> > Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a
> > Linux Foundation Collaborative Project
> >
> >
> >
> > *From:* llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu] *On
> > Behalf Of *Piotr Padlewski
> > *Sent:* Wednesday, July 22, 2015 5:56 PM
> > *To:* cfe-dev@cs.uiuc.edu Developers; llvmdev@cs.uiuc.edu
> > *Subject:* [LLVMdev] Clang devirtualization proposal
> >
> >
> >
> > Hi folks,
> >
> > this summer I will work with Richard Smith on clang devirtualization.
> > Check out our proposal:
> >
> >
> >
> >
> > https://docs.google.com/document/d/1f2SGa4TIPuBGm6y6YO768GrQsA8awNfGEJSBFukLhYA/edit?usp=sharing
> > <https://urldefense.proofpoint.com/v2/url?u=https-3A__docs.google.com_document_d_ \
> > 1f2SGa4TIPuBGm6y6YO768GrQsA8awNfGEJSBFukLhYA_edit-3Fusp-3Dsharing&d=AwMFaQ&c=8hUWF \
> > Zcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=-sGvXxkjadRLtXcTi4kOVPumoH-0XOKmk_vgUTcYugY&s=hHoo6tgC-NooXdIwbBwT_D8sIw8fcYF4XvBRI8Lr9Eg&e=>
> >
> >
> >
> > And modified LangRef
> >
> > http://reviews.llvm.org/D11399
> > <https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D11399&d=AwM \
> > FaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=-sGvX \
> > xkjadRLtXcTi4kOVPumoH-0XOKmk_vgUTcYugY&s=L6_vdinD06uAwgm4OJGL5QxKw8Tzfa_4DxPwf3Zj704&e=>
> >
> >
> >
> > You can also check out previous disscussion that was started before our
> > proposal was ready -
> > http://lists.cs.uiuc.edu/pipermail/cfe-dev/2015-July/044052.html
> >
> >
> >
> > Regards
> >
> > Piotr Padlewski
> >
>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev@cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>
>
[Attachment #5 (text/html)]
<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Jul 23, 2015 \
at 11:42 AM, Piotr Padlewski <span dir="ltr"><<a href="mailto:prazek@google.com" \
target="_blank">prazek@google.com</a>></span> wrote:<br><blockquote \
class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"><div dir="ltr">HI,<div>Yep, our proposal doesn't cover \
it, because this load ; icmp ; assume; will land global initilizer function, and main \
will not see it. </div><div>At least if foo would be called multiple times, then we \
would only have one load from vtable, but unfortunatelly we will not be able to \
inline, or make direct call to it with this approach.</div><div>I think that this \
case is rare enough to solve it right \
now.</div><div><br></div><div>Piotr</div></div><div class="gmail_extra"><br><div \
class="gmail_quote"><span class="">On Thu, Jul 23, 2015 at 10:30 AM, Geoff Berry \
<span dir="ltr"><<a href="mailto:gberry@codeaurora.org" \
target="_blank">gberry@codeaurora.org</a>></span> wrote:<br></span><blockquote \
class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple"><div><p \
class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Hi \
Piotr,<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> \
<u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">You \
may be interested in a recent patch I posted: <a \
href="https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D11043& \
d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=CnzuN65ENJ1H9py9XLiRvC_UQz6u3oG6GUNn7_wosS \
M&m=JLBFMHsMRUHs511X66Fr1fopHJ5WsTkKXLZ9GtX-koY&s=5EY4grsmJL7GyufHaG_GcSgPmas2OC8dUU-0BD8tM5g&e=" \
target="_blank">http://reviews.llvm.org/D11043</a><u></u><u></u></span></p><div><div \
class="h5"><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">This \
patch addresses a de-virtualization case that I'm not sure would be handled by your \
current proposal, namely that of a virtual call where the ‘this' object is a global \
variable.<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">For \
example:<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> \
<u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">struct \
A {<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"> \
A();<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"> \
virtual void foo();<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">};<u></u><u></u></span></p><p \
class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">void \
g(A * a) {<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"> \
a->foo();<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">}<u></u><u></u></span></p><p \
class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> \
<u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">A \
a;<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">int \
main() {<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"> \
g(&a);</span></p></div></div></div></div></blockquote></div></div></blockquote><div><br></div><div>We \
could in principle emit the load/icmp/assume for a's vptr here, but I'm \
concerned that this is not actually sound in general. \
Consider:</div><div><br></div><div>struct A;</div><div>extern A a;</div><div>void *p \
= &a; // emit load/icmp/assume here?</div><div>struct A { virtual void f(); \
};</div><div>A a;</div><div><br></div><div>If we emit an assume on the vptr at the \
point where the address of a is taken, we get:</div><div><br></div><div>@a = global \
%A zeroinitializer</div><div>void @global_init() {</div><div> load @a</div><div> \
%x = icmp @a, @A.vtable</div><div> call @llvm.assume(%x)</div><div> store @a, \
@p</div><div> call @A::A(@a)</div><div>}</div><div><br></div><div>... where the \
assume call can be folded to "call @llvm.assume(i1 false)", which \
(presumably) can be reduced further to "unreachable" (oops). (In \
Geoff's example, this is sound only because we're guaranteed that 'a' \
is initialized before we enter 'main', but an optimization that only fires \
for code within 'main' doesn't sound very \
useful.)</div><div><br></div><div>We could support this with something weaker than \
the current load/icmp/assume pattern: we could imagine an instruction/intrinsic that \
says "any later load of pointer %p with !invariant.group !g will load the value \
%q", but that does not imply that the value %q is currently stored in %p. \
It's not clear to me whether that has sufficient value to be \
worthwhile.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 \
.8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="gmail_extra"><div \
class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 \
.8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" \
vlink="purple"><div><div><div class="h5"><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u><u></u></span></p><p \
class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">}<u></u><u></u></span></p><p \
class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> \
<u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">It \
might be worth considering if your approach could be extended to handle this \
case.<u></u><u></u></span></p><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> \
<u></u></span></p><div style="border:dashed #2f6fab 1.0pt;padding:12.0pt 12.0pt \
12.0pt 12.0pt;background:#f9f9f9"><p class="MsoNormal" \
style="line-height:15.6pt;background:#f9f9f9;border:none;padding:0in"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">--<u></u><u></u></span></p><p \
class="MsoNormal" style="line-height:15.6pt;background:#f9f9f9;border:none;padding:0in"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Geoff \
Berry<u></u><u></u></span></p><p class="MsoNormal" \
style="line-height:15.6pt;background:#f9f9f9;border:none;padding:0in"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Employee \
of Qualcomm Innovation Center, Inc.<u></u><u></u></span></p><p class="MsoNormal" \
style="line-height:15.6pt;background:#f9f9f9;border:none;padding:0in"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"> \
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation \
Collaborative Project<u></u><u></u></span></p></div><p class="MsoNormal"><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> \
<u></u></span></p><p class="MsoNormal"><b><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span \
style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <a \
href="mailto:llvmdev-bounces@cs.uiuc.edu" \
target="_blank">llvmdev-bounces@cs.uiuc.edu</a> [mailto:<a \
href="mailto:llvmdev-bounces@cs.uiuc.edu" \
target="_blank">llvmdev-bounces@cs.uiuc.edu</a>] <b>On Behalf Of </b>Piotr \
Padlewski<br><b>Sent:</b> Wednesday, July 22, 2015 5:56 PM<br><b>To:</b> <a \
href="mailto:cfe-dev@cs.uiuc.edu" target="_blank">cfe-dev@cs.uiuc.edu</a> Developers; \
<a href="mailto:llvmdev@cs.uiuc.edu" \
target="_blank">llvmdev@cs.uiuc.edu</a><br><b>Subject:</b> [LLVMdev] Clang \
devirtualization proposal<u></u><u></u></span></p><p class="MsoNormal"><u></u> \
<u></u></p><div><span><div><p class="MsoNormal">Hi \
folks,<u></u><u></u></p></div><div><p class="MsoNormal">this summer I will work with \
Richard Smith on clang devirtualization. Check out our \
proposal:<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> \
<u></u></p></div></span><p class="MsoNormal"><a \
href="https://urldefense.proofpoint.com/v2/url?u=https-3A__docs.google.com_document_d_ \
1f2SGa4TIPuBGm6y6YO768GrQsA8awNfGEJSBFukLhYA_edit-3Fusp-3Dsharing&d=AwMFaQ&c=8 \
hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=-sGvXxkj \
adRLtXcTi4kOVPumoH-0XOKmk_vgUTcYugY&s=hHoo6tgC-NooXdIwbBwT_D8sIw8fcYF4XvBRI8Lr9Eg&e=" \
target="_blank">https://docs.google.com/document/d/1f2SGa4TIPuBGm6y6YO768GrQsA8awNfGEJSBFukLhYA/edit?usp=sharing</a><u></u><u></u></p><div><p \
class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">And modified \
LangRef<u></u><u></u></p></div><div><p class="MsoNormal"><a \
href="https://urldefense.proofpoint.com/v2/url?u=http-3A__reviews.llvm.org_D11399& \
d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMH \
A&m=-sGvXxkjadRLtXcTi4kOVPumoH-0XOKmk_vgUTcYugY&s=L6_vdinD06uAwgm4OJGL5QxKw8Tzfa_4DxPwf3Zj704&e=" \
target="_blank">http://reviews.llvm.org/D11399</a><u></u><u></u></p></div><span><div><p \
class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">You can also \
check out previous disscussion that was started before our proposal was ready - <a \
href="http://lists.cs.uiuc.edu/pipermail/cfe-dev/2015-July/044052.html" \
target="_blank">http://lists.cs.uiuc.edu/pipermail/cfe-dev/2015-July/044052.html</a><u></u><u></u></p></div><div><p \
class="MsoNormal"><u></u> <u></u></p></div><div><p \
class="MsoNormal">Regards<u></u><u></u></p></div><div><p class="MsoNormal">Piotr \
Padlewski<u></u><u></u></p></div></span></div></div></div></div></div></blockquote></div><br></div>
<br>_______________________________________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@cs.uiuc.edu">cfe-dev@cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev" rel="noreferrer" \
target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev</a><br> \
<br></blockquote></div><br></div></div>
_______________________________________________
cfe-dev mailing list
cfe-dev@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic