On Tue, Jul 28, 2015 at 10:58 AM, Philip Reames <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. 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. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150729/c59553d9/attachment.html>
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>
On 07/31/2015 02:47 PM, Philip Reames wrote:> > > 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.Sorry, ignore the above. I got to the part below and forgot to update this before sending. I hadn't yet internalized the bit about not being able to reason about disjoint abstract locations when I wrote this.> >> >> 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 > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150731/2ab734ed/attachment.html>