llvm dev - May 2013 - [LLVMdev] [cfe-dev] "load groups" IR feature to improve C++ devirtualization

On 9 May 2013 19:13, John McCall <rjmccall at apple.com> wrote:
> On May 9, 2013, at 6:34 PM, Nick Lewycky <nlewycky at google.com>
wrote:
> > I'm looking into how we can improve devirtualization in clang, and
there
> a language in C++ feature I'd like to take advantage of which would let
us
> perform elimination of more vptr loads. In this code:
> >
> >   Cls *p = new Cls;
> >   p->virtual_method1();
> >   p->method_changing_vptr();  // uses placement new to legally
change
> the vptr
> >   p->virtual_method2();  // invalid!
> >   Cls *q = p;
> >   q->virtual_method2();  // this must get a new vptr lookup.
>
I bungled my example, and I want to fix that first. I was thinking:

  Derived *p = new Derived;
  p->virtual_method1();
  p->method_changing_vptr();  // uses placement new to legally change the
vptr to Base
  p->virtual_method2();  // invalid!
  Base *q = p;
  q->virtual_method2();  // this must get a new vptr lookup.

which doesn't address your concerns.

This is not how I understand the [basic.life] rules.  The question
is
> whether a pointer value, reference, or name is formally forwarded to point
> to the new object.  Because the dynamic type is different, the pointer
> value held in 'p' is not updated.  Copying that value into
'q' does not
> change the fact that the pointer value still refers to a non-existent
> object.
>
I'm actually okay with the simple copy not forming a new object pointer.
However, "Base *q = reinterpret_cast<Base*>(p);" really ought
to.

It is unclear what, exactly, under the rules constitutes forming a
valid
> pointer to the newly-constructed object except using the result of the
> new-expression itself.  I think an explicit cast might, ignoring all
> "object-ness" of the source pointer and simply treating it
formally as a
> pointer to some storage that you are casting to the type of an object
> stored there?
>
I want to make optimizations to the program that people can't object to
through a cursory reading of the standard, which is made difficult by the
standard being contradictory on many relevant points here. Ultimately I've
chosen to be very liberal about what I'm allowing to be considered a newly
formed valid pointer.

BTW, Richard came up with a wonderful example. What do you make of this?:

  char alignas(A, B) buffer[max(sizeof(A), sizeof(B))];
  A *a = reinterpret_cast<A*>(buffer);
  B *b = reinterpret_cast<B*>(buffer);
  new(buffer) A;
  a->vfn();
  new(buffer) B;
  b->vfn();

Valid?

Nick
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130509/06228a9a/attachment.html>

Hi Nick,

Won't this approach run into problems with inlining, unrolling, or just
about anything that duplicates code?  Suppose I have a bunch of loads of the
same load group in the body of the loop, but update the pointer they're
dereferencing on the backedge.  If that loop gets unrolled, all the loads in the
unrolled copies will have the same load group, but it would not be correct to
replace loads from the first iteration with loads from the second iteration.

--Owen


On May 9, 2013, at 9:22 PM, Nick Lewycky <nlewycky at google.com> wrote:
> On 9 May 2013 19:13, John McCall <rjmccall at apple.com> wrote:
> On May 9, 2013, at 6:34 PM, Nick Lewycky <nlewycky at google.com>
wrote:
> > I'm looking into how we can improve devirtualization in clang, and
there a language in C++ feature I'd like to take advantage of which would
let us perform elimination of more vptr loads. In this code:
> >
> >   Cls *p = new Cls;
> >   p->virtual_method1();
> >   p->method_changing_vptr();  // uses placement new to legally
change the vptr
> >   p->virtual_method2();  // invalid!
> >   Cls *q = p;
> >   q->virtual_method2();  // this must get a new vptr lookup.
> 
> I bungled my example, and I want to fix that first. I was thinking:
> 
>   Derived *p = new Derived;
>   p->virtual_method1();
>   p->method_changing_vptr();  // uses placement new to legally change
the vptr to Base
>   p->virtual_method2();  // invalid!
>   Base *q = p;
>   q->virtual_method2();  // this must get a new vptr lookup.
> 
> which doesn't address your concerns.
> 
> This is not how I understand the [basic.life] rules.  The question is
whether a pointer value, reference, or name is formally forwarded to point to
the new object.  Because the dynamic type is different, the pointer value held
in 'p' is not updated.  Copying that value into 'q' does not
change the fact that the pointer value still refers to a non-existent object.
> 
> I'm actually okay with the simple copy not forming a new object
pointer. However, "Base *q = reinterpret_cast<Base*>(p);" really
ought to.
> 
> It is unclear what, exactly, under the rules constitutes forming a valid
pointer to the newly-constructed object except using the result of the
new-expression itself.  I think an explicit cast might, ignoring all
"object-ness" of the source pointer and simply treating it formally as
a pointer to some storage that you are casting to the type of an object stored
there?
> 
> I want to make optimizations to the program that people can't object to
through a cursory reading of the standard, which is made difficult by the
standard being contradictory on many relevant points here. Ultimately I've
chosen to be very liberal about what I'm allowing to be considered a newly
formed valid pointer.
> 
> BTW, Richard came up with a wonderful example. What do you make of this?:
> 
>   char alignas(A, B) buffer[max(sizeof(A), sizeof(B))];
>   A *a = reinterpret_cast<A*>(buffer);
>   B *b = reinterpret_cast<B*>(buffer);
>   new(buffer) A;
>   a->vfn();
>   new(buffer) B;
>   b->vfn();
> 
> Valid?
> 
> Nick
> 
> _______________________________________________
> 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/20130509/3fe0865d/attachment.html>

On 9 May 2013 22:37, Owen Anderson <resistor at mac.com> wrote:
> Hi Nick,
>
> Won't this approach run into problems with inlining, unrolling, or just
> about anything that duplicates code?  Suppose I have a bunch of loads of
> the same load group in the body of the loop, but update the pointer
they're
> dereferencing on the backedge.  If that loop gets unrolled, all the loads
> in the unrolled copies will have the same load group, but it would not be
> correct to replace loads from the first iteration with loads from the
> second iteration.
>
No, @llvm.load.group returns a new group each time it's run. We'll
unroll/inline/duplicate that call with the rest of the loads.

Nick

On May 9, 2013, at 9:22 PM, Nick Lewycky <nlewycky at google.com>
wrote:
>
> On 9 May 2013 19:13, John McCall <rjmccall at apple.com> wrote:
>
>> On May 9, 2013, at 6:34 PM, Nick Lewycky <nlewycky at google.com>
wrote:
>> > I'm looking into how we can improve devirtualization in clang,
and
>> there a language in C++ feature I'd like to take advantage of which
would
>> let us perform elimination of more vptr loads. In this code:
>> >
>> >   Cls *p = new Cls;
>> >   p->virtual_method1();
>> >   p->method_changing_vptr();  // uses placement new to legally
change
>> the vptr
>> >   p->virtual_method2();  // invalid!
>> >   Cls *q = p;
>> >   q->virtual_method2();  // this must get a new vptr lookup.
>>
>
> I bungled my example, and I want to fix that first. I was thinking:
>
>   Derived *p = new Derived;
>   p->virtual_method1();
>   p->method_changing_vptr();  // uses placement new to legally change
the
> vptr to Base
>   p->virtual_method2();  // invalid!
>   Base *q = p;
>   q->virtual_method2();  // this must get a new vptr lookup.
>
> which doesn't address your concerns.
>
> This is not how I understand the [basic.life] rules.  The question is
>> whether a pointer value, reference, or name is formally forwarded to
point
>> to the new object.  Because the dynamic type is different, the pointer
>> value held in 'p' is not updated.  Copying that value into
'q' does not
>> change the fact that the pointer value still refers to a non-existent
>> object.
>>
>
> I'm actually okay with the simple copy not forming a new object
pointer.
> However, "Base *q = reinterpret_cast<Base*>(p);" really
ought to.
>
> It is unclear what, exactly, under the rules constitutes forming a valid
>> pointer to the newly-constructed object except using the result of the
>> new-expression itself.  I think an explicit cast might, ignoring all
>> "object-ness" of the source pointer and simply treating it
formally as a
>> pointer to some storage that you are casting to the type of an object
>> stored there?
>>
>
> I want to make optimizations to the program that people can't object to
> through a cursory reading of the standard, which is made difficult by the
> standard being contradictory on many relevant points here. Ultimately
I've
> chosen to be very liberal about what I'm allowing to be considered a
newly
> formed valid pointer.
>
> BTW, Richard came up with a wonderful example. What do you make of this?:
>
>   char alignas(A, B) buffer[max(sizeof(A), sizeof(B))];
>   A *a = reinterpret_cast<A*>(buffer);
>   B *b = reinterpret_cast<B*>(buffer);
>   new(buffer) A;
>   a->vfn();
>   new(buffer) B;
>   b->vfn();
>
> Valid?
>
> Nick
>
> _______________________________________________
> 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/20130510/3013d69d/attachment.html>

On May 9, 2013, at 9:22 PM, Nick Lewycky <nlewycky at google.com>
wrote:
> On 9 May 2013 19:13, John McCall <rjmccall at apple.com> wrote:
> This is not how I understand the [basic.life] rules.  The question is
whether a pointer value, reference, or name is formally forwarded to point to
the new object.  Because the dynamic type is different, the pointer value held
in 'p' is not updated.  Copying that value into 'q' does not
change the fact that the pointer value still refers to a non-existent object.
> 
> I'm actually okay with the simple copy not forming a new object
pointer. However, "Base *q = reinterpret_cast<Base*>(p);" really
ought to.
Yes, I agree that it ought to.
> It is unclear what, exactly, under the rules constitutes forming a valid
pointer to the newly-constructed object except using the result of the
new-expression itself.  I think an explicit cast might, ignoring all
"object-ness" of the source pointer and simply treating it formally as
a pointer to some storage that you are casting to the type of an object stored
there?
> 
> I want to make optimizations to the program that people can't object to
through a cursory reading of the standard, which is made difficult by the
standard being contradictory on many relevant points here. Ultimately I've
chosen to be very liberal about what I'm allowing to be considered a newly
formed valid pointer.
Being conservative is fair.  My point was just that it has absolutely nothing to
do with being held in a named pointer variable.  Also, this is C++, so you
almost certainly need to be able to track the object-ness of values across
inlining in order to have much hope of meaningful optimization.  And potentially
not just across inlining, but through memory — who actually allocates
polymorphic values and doesn't use smart pointers these days?
> BTW, Richard came up with a wonderful example. What do you make of this?:
> 
>   char alignas(A, B) buffer[max(sizeof(A), sizeof(B))];
>   A *a = reinterpret_cast<A*>(buffer);
>   B *b = reinterpret_cast<B*>(buffer);
>   new(buffer) A;
>   a->vfn();
>   new(buffer) B;
>   b->vfn();
> 
> Valid?
Let's answer a simpler question.  Why is this valid?

    A *a = reinterpret_cast<A*>(buffer);
    new(buffer) A;
    a->vfn();

My initial interpretation is that the initial value of 'a' is a
type-punned pointer that refers to an object of type char[n].  The lifetime of
that object ends when we reuse its storage for a new object of type A.  (This is
okay to do to any type;  additionally, since the char[n] object does not have a
non-trivial destructor, we are not required to put a char[n] object back before
it goes out of scope.)  This leaves the name 'buffer' referring only to
allocated storage.  The lifetime of the A object begins after the constructor
completes.  'a' does not automatically refer to the new object because
the type of the object it refers to does not match the type of the object now
created there.  So, what's the theory that allows us to use 'a' here
as if it referred to the new object?

To be clear, I think we obviously have to permit both of these examples.

The only additional complication with Richard's example is that yet another
object comes into existence.  I don't see that as fundamentally changing
anything.

John.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130510/99568e57/attachment.html>

On 10 May 2013 01:00, John McCall <rjmccall at apple.com> wrote:
> On May 9, 2013, at 9:22 PM, Nick Lewycky <nlewycky at google.com>
wrote:
>
> On 9 May 2013 19:13, John McCall <rjmccall at apple.com> wrote:
>
>> This is not how I understand the [basic.life] rules.  The question is
>> whether a pointer value, reference, or name is formally forwarded to
point
>> to the new object.  Because the dynamic type is different, the pointer
>> value held in 'p' is not updated.  Copying that value into
'q' does not
>> change the fact that the pointer value still refers to a non-existent
>> object.
>>
>
> I'm actually okay with the simple copy not forming a new object
pointer.
> However, "Base *q = reinterpret_cast<Base*>(p);" really
ought to.
>
>
> Yes, I agree that it ought to.
>
>  It is unclear what, exactly, under the rules constitutes forming a valid
>> pointer to the newly-constructed object except using the result of the
>> new-expression itself.  I think an explicit cast might, ignoring all
>> "object-ness" of the source pointer and simply treating it
formally as a
>> pointer to some storage that you are casting to the type of an object
>> stored there?
>>
>
> I want to make optimizations to the program that people can't object to
> through a cursory reading of the standard, which is made difficult by the
> standard being contradictory on many relevant points here. Ultimately
I've
> chosen to be very liberal about what I'm allowing to be considered a
newly
> formed valid pointer.
>
>
> Being conservative is fair.  My point was just that it has absolutely
> nothing to do with being held in a named pointer variable.  Also, this is
> C++, so you almost certainly need to be able to track the object-ness of
> values across inlining in order to have much hope of meaningful
> optimization.  And potentially not just across inlining, but through memory
> — who actually allocates polymorphic values and doesn't use smart
pointers
> these days?
>
You essentially want to have some optimizations fire to clean things up
before we devirtualize? And you want to devirtualize more often? So
demanding. It's not unreasonable, it's just hard. I don't have a way
to
salvage the existing proposal.

Let me propose to extend LLVM's pointers by defining that they are a pair
of object ID and memory address. As a matter of lowering to target ABI, we
only pass the memory addresses not the object IDs, ptrtoint produces an
integer from only the memory address, and inttoptr creates a pointer with
some object ID, but we don't know which one. icmp only compares the memory
address part of these pointers. Bitcast and GEP preserve the object ID.

To create a new object ID, a new intrinsic @llvm.newobject takes and
returns pointers of the same type, where the memory address is the same,
but with a newly allocated object ID. Given "%x = i8* call
@llvm.newobject(i8* %y)", %x and %y are mayalias in BasicAA (TBAA may
decide they're NoAlias anyhow, and that's fine).

The only observer of these object IDs are load instructions annotated with
!llvm.invariant.object metadata. Loads with this annotation that load the
same pointer (including both object ID and memory address) may be assumed
to load the same value no matter what other operations happen in between.

At the C++ level, we state that a pointer's associated vptr is fixed on
first use. Things which break that association emit a call to
@llvm.newobject. That includes pointer casts, and calls to placement new.
Yes, if you call placement new you need to use the newly returned pointer,
or else your program has undefined behaviour.

This proposal is much more rough than the last one and I'd appreciate any
help identifying the problems. Please review!

Nick

> BTW, Richard came up with a wonderful example. What do you make of this?:
>
>   char alignas(A, B) buffer[max(sizeof(A), sizeof(B))];
>   A *a = reinterpret_cast<A*>(buffer);
>   B *b = reinterpret_cast<B*>(buffer);
>   new(buffer) A;
>   a->vfn();
>   new(buffer) B;
>   b->vfn();
>
> Valid?
>
>
> Let's answer a simpler question.  Why is this valid?
>
>     A *a = reinterpret_cast<A*>(buffer);
>     new(buffer) A;
>     a->vfn();
>
> My initial interpretation is that the initial value of 'a' is a
> type-punned pointer that refers to an object of type char[n].  The lifetime
> of that object ends when we reuse its storage for a new object of type A.
>  (This is okay to do to any type;  additionally, since the char[n] object
> does not have a non-trivial destructor, we are not required to put a
> char[n] object back before it goes out of scope.)  This leaves the name
> 'buffer' referring only to allocated storage.  The lifetime of the
A object
> begins after the constructor completes.  'a' does not automatically
refer
> to the new object because the type of the object it refers to does not
> match the type of the object now created there.  So, what's the theory
that
> allows us to use 'a' here as if it referred to the new object?
>
> To be clear, I think we obviously have to permit both of these examples.
>
> The only additional complication with Richard's example is that yet
> another object comes into existence.  I don't see that as fundamentally
> changing anything.
>
> John.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130513/02d4cdd9/attachment.html>