<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 2:38 PM, 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 2:03 PM, 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"><div style="word-wrap:break-word" class=""><div class=""><div class=""><div class="h5"><blockquote type="cite" class=""><div class="">On Jul 16, 2015, at 11:46 AM, Richard Smith <<a href="mailto:richard@metafoo.co.uk" target="_blank" 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" target="_blank" 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 class=""><br class=""></div></div></div>invariant.load currently allows the load to be reordered pretty aggressively, so I think you need a new metadata.</div></div></blockquote><div class=""><br class=""></div><div class="">Our thoughts were:</div><div class="">1) The existing !invariant.load is redundant because it's exactly equivalent to a call to @llvm.invariant.start and a load.</div></div></div></div></div></blockquote><div><br class=""></div>No, that would not be arbitrarily hoistable.</div><div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class="">2) The new semantics are a more strict form of the old semantics, so no special action is required to upgrade old IR.</div><div class="">... so changing the meaning of the existing metadata seemed preferable to adding a new, similar-but-not-quite-identical, form of the metadata. But either way seems fine.</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><span 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 class=""><br class=""></div></span>Hmm.  And all v-table loads have this invariant metadata?</div></div></blockquote><div class=""><br class=""></div><div class="">That's the idea (but it's not essential that they do, we just lose optimization power if not).</div><div class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class="">I am concerned about mixing files with and without barriers.</div></div></blockquote><div class=""><br class=""></div><div class="">I think we'd need to always generate the barrier (even at -O0, to support LTO between non-optimized and optimized code). I don't think we can support LTO between IR using the metadata and old IR that didn't contain the relevant barriers. How important is that use case?</div></div></div></div></div></blockquote><div><br class=""></div><div>Well, all current IR does not contain the barrier, so this would be a statement that current C++ IR will never be correctly LTO-able with future C++ IR.  That is generally something we try to avoid, yes.</div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class="">We were probably going to put this behind a -fstrict-something flag, at least to start off with, so we can create a transition period where we generate the barrier by default but don't generate the metadata if necessary.</div></div></div></div>
</div></blockquote></div><br class=""><div class="">If this goes into the function flags, perhaps there’s a way to prevent LTO between functions that disagree about the flag.</div><div class=""><br class=""></div><div class="">John.</div></body></html>