[LLVMdev] [cfe-dev] Clang devirtualization proposal

[Philip Reames]

On 07/29/2015 09:32 AM, Reid Kleckner wrote:
> On Tue, Jul 28, 2015 at 10:58 AM, Philip Reames 
> <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote:
>
>     Having read through the proposal, I feel like I missing some of
>     the background to understand the problem you're trying to solve.
>
>     My mental model is that construction of an object creates a new
>     abstract location in an infinite heap with each object infinitely
>     far apart.  Destruction of the object destroys the abstract
>     location.  As a result, destructing one object and constructing
>     another produce unique incomparable abstract locations.  The fact
>     the two abstract locations might happen to share a physical
>     address is irrelevant.
>
>     If I'm understanding the proposal correctly, this model works for
>     most code.  The key optimization you appear to want to perform is
>     to recognize the fact that these two abstract locations occupy the
>     same memory.  In particular, you want to be able to return
>     mustalias for alias(loc1, loc2).  Another way of saying this is
>     that you want to reason about abstract locations as defined by
>     allocation/deallocation events rather than
>     construction/destruction events.  Is that a fair summary?
>
>     What I'm not clear on is *why* recognizing the two abstract
>     locations share a physical address is important.  Given that the
>     contents of the abstract location before construction or after
>     destruction are undefined (right?), what optimization does
>     recognizing the mustalias relation enable?
>
>
> I think this is incorrect. LLVM's model is closer to the second model, 
> and we need something like the first model to prevent erroneous 
> devirtualization.
>
> The corner case for C++ is when the optimizer observes that two 
> abstract objects share the same physical memory location. In practice, 
> this could happen if the memory allocator becomes visible to the 
> optimizer through inlining. For illustration, do placement new into 
> the stack memory of another object. This is illustrated in example 2 
> of the proposal:
>
> struct MyClass {
>   virtual void foo();
> };
> struct MyOtherClass : MyClass {
>   virtual void foo();
> };
> int main() {
>   MyClass c;
>   c.foo();
>   // Reuse the storage temporarily.  UB to access the object through ‘c’
>   c.~MyClass();
>   auto c2 = new (&c) MyOtherClass();
>   c2->foo(); //fine, we have new pointer
>   // c.foo() // UB, the type has changed
>   // The storage has to contain a ‘MyClass’ when it goes out of scope.
>   c2->~MyOtherClass();
>   new (&c) MyClass(); // we have to get back to previous type because 
> calling destructor using c would be UB
> }
>
> Without @llvm.invariant.group.barrier, LLVM will probably replace %c2 
> with %c here, since they are trivially the same.
>
> With @llvm.invariant.group.barrier, the result of placement new will 
> be a distinct SSA value that LLVM can't reason about, and we won't 
> accidentally devirtualize c2->foo() to MyClass::foo.
So, to phrase this differently, the @llvm.invariant.group.barrier is 
responsible for introducing a new abstract memory location and the 
optimizer is agreeing to never exploit the fact the new abstract memory 
location is in fact at the same address?

Where in the execution would this new abstract location be introduced?  
Is it immediately before the placement new?  If so, that would seem 
consistent.

>
> There is, however, a small problem with this model. If the code 
> happened to do this:
>
>   ...
>   auto c2 = new (&c) MyOtherClass();
>   assert(c2 == &c);
>   ...
>
> LLVM might once again replace %c2 with %c, causing bad devirtualization.
Is this well defined C++?  My reading would be that it is.  If this was 
realloc, it clearly wouldn't be, but I'm not sure placement new has the 
same restrictions.

Assuming that it is well defined C, this was exactly the counter example 
I was missing and the reason that reasoning about abstract locations per 
object doesn't work.  Thanks.

Given that, I can see why we're stuck with a single abstract location 
for the storage and need to add and remove the invariantness of a 
particular location.  I'll go take another read through the proposal 
with that in mind.

Philip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150731/52341297/attachment.html>