[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: Richard Smith <richard () metafoo ! co ! uk>
Date: 2015-07-16 18:46:05
Message-ID: CAOfiQqn5KC_uXwX-3DHZpWARxzNVM1XHS=gnRf5XdTD96-DAVg () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
On Thu, Jul 16, 2015 at 11:29 AM, John McCall <rjmccall@apple.com> wrote:
> > On Jul 15, 2015, at 10:11 PM, Hal Finkel <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:
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)
-- Richard
[Attachment #5 (text/html)]
<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Jul 16, 2015 \
at 11:29 AM, John McCall <span dir="ltr"><<a href="mailto:rjmccall@apple.com" \
target="_blank">rjmccall@apple.com</a>></span> wrote:<br><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">hfinkel@anl.gov</a>> wrote:<br> ><br>
> Hi everyone,<br>
><br>
> 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> ><br>
> struct Base {<br>
> virtual void foo() = 0;<br>
> };<br>
><br>
> void external();<br>
> struct Final final : Base {<br>
> void foo() {<br>
> external();<br>
> }<br>
> };<br>
><br>
> void dispatch(Base *B) {<br>
> B->foo();<br>
> }<br>
><br>
> void opportunity(Final *F) {<br>
> dispatch(F);<br>
> }<br>
><br>
> 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> ><br>
> 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> <br>
</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> <br>
{<br>
MyClass c;<br>
<br>
// Reuse the storage temporarily. UB to access the object through ‘c' now.<br>
c.~MyClass();<br>
auto c2 = new (&c) MyOtherClass();<br>
<br>
// The storage has to contain a ‘MyClass' when it goes out of scope.<br>
c2->~MyOtherClass();<br>
new (&c) MyClass();<br>
}<br>
<br>
The standard frontend devirtualization optimizations are permitted under a couple of \
different language rules, specifically that:<br> 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> 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> <br>
You can apply those rules much more broadly than the frontend does, of course; but \
those are the language tools you get.</blockquote><div><br></div><div>Right. Our \
current plan for modelling this is:</div><div><br></div><div>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> a) both loads have !invariant.load metadata with \
the same operand, and</div><div> b) the pointer operands are the same SSA value \
(being must-alias is not sufficient)</div><div>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><br></div><div>In particular, "new (&c) \
MyOtherClass()" would be emitted as something like \
this:</div><div><br></div><div> %1 = call @operator new(size, %c)</div><div> %2 = \
call @llvm.invariant.barrier(%1)</div><div> call \
@MyOtherClass::MyOtherClass(%2)</div><div> %vptr = load %2</div><div> %known.vptr \
= icmp eq %vptr, @MyOtherClass::vptr, !invariant.load !MyBaseClass.vptr</div><div> \
call @llvm.assume(%known.vptr)</div><div><br></div><div>-- \
Richard</div></div></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