[prev in list] [next in list] [prev in thread] [next in thread]
List: cfe-dev
Subject: Re: [cfe-dev] C++11 and enhacned devirtualization
From: John McCall <rjmccall () apple ! com>
Date: 2015-07-16 21:03:29
Message-ID: 162B7813-9114-44EF-93C7-0B5C3676DA65 () apple ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
> On Jul 16, 2015, at 11:46 AM, Richard Smith <richard@metafoo.co.uk> wrote:
> On Thu, Jul 16, 2015 at 11:29 AM, John McCall <rjmccall@apple.com \
> <mailto:rjmccall@apple.com>> wrote:
> > On Jul 15, 2015, at 10:11 PM, Hal Finkel <hfinkel@anl.gov \
> > <mailto:hfinkel@anl.gov>> wrote:
> > Hi everyone,
> >
> > C++11 added features that allow for certain parts of the class hierarchy to be \
> > closed, specifically the 'final' keyword and the semantics of anonymous \
> > namespaces, and I think we take advantage of these to enhance our ability to \
> > perform devirtualization. For example, given this situation:
> > struct Base {
> > virtual void foo() = 0;
> > };
> >
> > void external();
> > struct Final final : Base {
> > void foo() {
> > external();
> > }
> > };
> >
> > void dispatch(Base *B) {
> > B->foo();
> > }
> >
> > void opportunity(Final *F) {
> > dispatch(F);
> > }
> >
> > When we optimize this code, we do the expected thing and inline 'dispatch' into \
> > 'opportunity' but we don't devirtualize the call to foo(). The fact that we know \
> > what the vtable of F is at that callsite is not exploited. To a lesser extent, we \
> > can do similar things for final virtual methods, and derived classes in anonymous \
> > namespaces (because Clang could determine whether or not a class (or method) \
> > there is effectively final).
> > One possibility might be to @llvm.assume to say something about what the vtable \
> > ptr of F might be/contain should it be needed later when we emit the initial IR \
> > for 'opportunity' (and then teach the optimizer to use that information), but I'm \
> > not at all sure that's the best solution. Thoughts?
>
> The problem with any sort of @llvm.assume-encoded information about memory contents \
> is that C++ does actually allow you to replace objects in memory, up to and \
> including stuff like:
> {
> MyClass c;
>
> // Reuse the storage temporarily. UB to access the object through ‘c' now.
> c.~MyClass();
> auto c2 = new (&c) MyOtherClass();
>
> // The storage has to contain a ‘MyClass' when it goes out of scope.
> c2->~MyOtherClass();
> new (&c) MyClass();
> }
>
> The standard frontend devirtualization optimizations are permitted under a couple \
> of different language rules, specifically that: 1. If you access an object through \
> an l-value of a type, it has to dynamically be an object of that type (potentially \
> a subobject). 2. Object replacement as above only "forwards" existing formal \
> references under specific conditions, e.g. the dynamic type has to be the same, \
> ‘const' members have to have the same value, etc. Using an unforwarded reference \
> (like the name of the local variable ‘c' above) doesn't formally refer to a valid \
> object and thus has undefined behavior.
> You can apply those rules much more broadly than the frontend does, of course; but \
> those are the language tools you get.
> Right. Our current plan for modelling this is:
>
> 1) Change the meaning of the existing !invariant.load metadata (or add another \
> parallel metadata kind) so that it allows load-load forwarding (even if the memory \
> is not known to be unmodified between the loads) if:
invariant.load currently allows the load to be reordered pretty aggressively, so I \
think you need a new metadata.
> a) both loads have !invariant.load metadata with the same operand, and
> b) the pointer operands are the same SSA value (being must-alias is not sufficient)
> 2) Add a new intrinsic "i8* @llvm.invariant.barrier(i8*)" that produces a new \
> pointer that is different for the purpose of !invariant.load. (Some other \
> optimizations are permitted to look through the barrier.)
> In particular, "new (&c) MyOtherClass()" would be emitted as something like this:
>
> %1 = call @operator new(size, %c)
> %2 = call @llvm.invariant.barrier(%1)
> call @MyOtherClass::MyOtherClass(%2)
> %vptr = load %2
> %known.vptr = icmp eq %vptr, @MyOtherClass::vptr, !invariant.load !MyBaseClass.vptr
> call @llvm.assume(%known.vptr)
Hmm. And all v-table loads have this invariant metadata?
I am concerned about mixing files with and without barriers.
John.
[Attachment #5 (unknown)]
<html><head><meta http-equiv="Content-Type" content="text/html \
charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; \
-webkit-line-break: after-white-space;" class=""><div><blockquote type="cite" \
class=""><div class="">On Jul 16, 2015, at 11:46 AM, Richard Smith <<a \
href="mailto:richard@metafoo.co.uk" class="">richard@metafoo.co.uk</a>> \
wrote:</div><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div \
class="gmail_quote">On Thu, Jul 16, 2015 at 11:29 AM, John McCall <span dir="ltr" \
class=""><<a href="mailto:rjmccall@apple.com" target="_blank" \
class="">rjmccall@apple.com</a>></span> wrote:<br class=""><blockquote \
class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"><span class="">> On Jul 15, 2015, at 10:11 PM, Hal Finkel \
<<a href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>> wrote:<br \
class=""> ><br class="">
> Hi everyone,<br class="">
><br class="">
> C++11 added features that allow for certain parts of the class hierarchy to be \
closed, specifically the 'final' keyword and the semantics of anonymous namespaces, \
and I think we take advantage of these to enhance our ability to perform \
devirtualization. For example, given this situation:<br class=""> ><br class="">
> struct Base {<br class="">
> virtual void foo() = 0;<br class="">
> };<br class="">
><br class="">
> void external();<br class="">
> struct Final final : Base {<br class="">
> void foo() {<br class="">
> external();<br class="">
> }<br class="">
> };<br class="">
><br class="">
> void dispatch(Base *B) {<br class="">
> B->foo();<br class="">
> }<br class="">
><br class="">
> void opportunity(Final *F) {<br class="">
> dispatch(F);<br class="">
> }<br class="">
><br class="">
> When we optimize this code, we do the expected thing and inline 'dispatch' into \
'opportunity' but we don't devirtualize the call to foo(). The fact that we know what \
the vtable of F is at that callsite is not exploited. To a lesser extent, we can do \
similar things for final virtual methods, and derived classes in anonymous namespaces \
(because Clang could determine whether or not a class (or method) there is \
effectively final).<br class=""> ><br class="">
> One possibility might be to @llvm.assume to say something about what the vtable \
ptr of F might be/contain should it be needed later when we emit the initial IR for \
'opportunity' (and then teach the optimizer to use that information), but I'm not at \
all sure that's the best solution. Thoughts?<br class=""> <br class="">
</span>The problem with any sort of @llvm.assume-encoded information about memory \
contents is that C++ does actually allow you to replace objects in memory, up to and \
including stuff like:<br class=""> <br class="">
{<br class="">
MyClass c;<br class="">
<br class="">
// Reuse the storage temporarily. UB to access the object through ‘c' \
now.<br class=""> c.~MyClass();<br class="">
auto c2 = new (&c) MyOtherClass();<br class="">
<br class="">
// The storage has to contain a ‘MyClass' when it goes out of scope.<br \
class=""> c2->~MyOtherClass();<br class="">
new (&c) MyClass();<br class="">
}<br class="">
<br class="">
The standard frontend devirtualization optimizations are permitted under a couple of \
different language rules, specifically that:<br class=""> 1. If you access an object \
through an l-value of a type, it has to dynamically be an object of that type \
(potentially a subobject).<br class=""> 2. Object replacement as above only \
"forwards" existing formal references under specific conditions, e.g. the dynamic \
type has to be the same, ‘const' members have to have the same value, etc. \
Using an unforwarded reference (like the name of the local variable ‘c' above) \
doesn't formally refer to a valid object and thus has undefined behavior.<br \
class=""> <br class="">
You can apply those rules much more broadly than the frontend does, of course; but \
those are the language tools you get.</blockquote><div class=""><br \
class=""></div><div class="">Right. Our current plan for modelling this is:</div><div \
class=""><br class=""></div><div class="">1) Change the meaning of the existing \
!invariant.load metadata (or add another parallel metadata kind) so that it allows \
load-load forwarding (even if the memory is not known to be unmodified between the \
loads) if:</div></div></div></div></div></blockquote><div><br \
class=""></div>invariant.load currently allows the load to be reordered pretty \
aggressively, so I think you need a new metadata.</div><div><br class=""><blockquote \
type="cite" class=""><div class=""><div dir="ltr" class=""><div \
class="gmail_extra"><div class="gmail_quote"><div class=""> a) both loads have \
!invariant.load metadata with the same operand, and</div><div class=""> b) the \
pointer operands are the same SSA value (being must-alias is not \
sufficient)</div><div class="">2) Add a new intrinsic "i8* \
@llvm.invariant.barrier(i8*)" that produces a new pointer that is different for the \
purpose of !invariant.load. (Some other optimizations are permitted to look through \
the barrier.)</div></div></div></div></div></blockquote><blockquote type="cite" \
class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div \
class="gmail_quote"><div class=""><br class=""></div><div class="">In particular, \
"new (&c) MyOtherClass()" would be emitted as something like this:</div><div \
class=""><br class=""></div><div class=""> %1 = call @operator new(size, \
%c)</div><div class=""> %2 = call @llvm.invariant.barrier(%1)</div><div \
class=""> call @MyOtherClass::MyOtherClass(%2)</div><div class=""> %vptr \
= load %2</div><div class=""> %known.vptr = icmp eq %vptr, @MyOtherClass::vptr, \
!invariant.load !MyBaseClass.vptr</div><div class=""> call \
@llvm.assume(%known.vptr)</div></div></div></div></div></blockquote><div><br \
class=""></div>Hmm. And all v-table loads have this invariant metadata?<br \
class=""><div><br class=""></div></div><div>I am concerned about mixing files with \
and without barriers.</div><div><br class=""></div><div>John.</div></body></html>
_______________________________________________
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