thr3ads.net - llvm dev - [llvm-dev] RFC: Emitting empty invariant group for vtable loads [Jan 2017]

If this information is useful, please help other people find it:
Share via:

Piotr Padlewski via llvm-dev

2017-Jan-20 16:07 UTC

[llvm-dev] RFC: Emitting empty invariant group for vtable loads

Hi all,

I would like to propose a new way clang would decorate vtable loads in
order to handle devirtualization better.

I've added *llvm-dev* also, because this can start a discussion about
changing invariant.group to just invariant.

PDF version of this RFC can be found here:

https://drive.google.com/file/d/0B72TmzNsY6Z8ZmpOUnB5dDZfSFU/view?usp=sharing


Background:

Initial old design:

http://lists.llvm.org/pipermail/cfe-dev/2015-July/044227.html

My talk from LLVM Dev Meeting

http://llvm.org/devmtg/2016-11/#talk6

The problem

Clang with -fstrict-vtable-pointers decorates vtable loads with metadata
corresponding to mangled pointer type name like:

void g(A& a){
   a.foo();
}


define void @_Z1gR1A(%struct.A* dereferenceable(8) %a) local_unnamed_addr #0
{
entry:
 %0 = bitcast %struct.A* %a to void (%struct.A*)***
 %vtable = load void (%struct.A*)**, void (%struct.A*)*** %0,
!invariant.group !7
 %1 = load void (%struct.A*)*, void (%struct.A*)** %vtable
 tail call void %1(%struct.A* nonnull %a)
 ret void
}

!7 = !{!"_ZTS1A"}



This works well if the pointer type doesn’t change, but when it does,
devirtualization might not happen like here:

struct A {
   A();
   virtual void foo();
};
struct B : A{
   B();
   virtual void foo();
};
void g(A& a){
   a.foo();
   a.foo();
}
void clobber(A&);
void f() {
     B b;
     clobber(b);
     g(b);
}

The other problem is that when we combine 2 instructions with different
invariant.group metadata, then we pick one of them, because for now we can
have only single !invariant.group metadata.

The solution

I had some initial ideas how it can be solved, like

   1.

   introducing multi invariant groups
   2.

   having sub invariant groups - like inheritance, so we could figure out
   that one group is subgroup of another
   3.

   decorating all loads with base pointer MD (doesn’t work with multiple
   inheritance)


I consulted my ideas with Krzysztof Pszeniczny, and he proposed something
much simpler: we can decorate every invariant.group md with empty metadata.

This should work because the lifetime of the object is strictly defined by
invariant.group.barrier.


If this holds, we can start discussion about if it makes sense to keep
invariant groups, and instead have just “invariant”, that would be
equivalent to having invariant.group with the same metadata.

Do you have some thoughts about this approach? I don’t have a mathematical
proof, but I am confident that it should be valid.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170120/70e62e86/attachment.html>

Piotr Padlewski via llvm-dev

2017-Jan-24 19:39 UTC

head link

[llvm-dev] RFC: Emitting empty invariant group for vtable loads

Hi,
I would really like to hear some feedback about this.

Piotr

2017-01-20 17:07 GMT+01:00 Piotr Padlewski <piotr.padlewski at gmail.com>:
> Hi all,
>
> I would like to propose a new way clang would decorate vtable loads in
> order to handle devirtualization better.
>
> I've added *llvm-dev* also, because this can start a discussion about
> changing invariant.group to just invariant.
>
> PDF version of this RFC can be found here:
>
> https://drive.google.com/file/d/0B72TmzNsY6Z8ZmpOUnB5dDZfSFU/
> view?usp=sharing
>
>
> Background:
>
> Initial old design:
>
> http://lists.llvm.org/pipermail/cfe-dev/2015-July/044227.html
>
> My talk from LLVM Dev Meeting
>
> http://llvm.org/devmtg/2016-11/#talk6
>
> The problem
>
> Clang with -fstrict-vtable-pointers decorates vtable loads with metadata
> corresponding to mangled pointer type name like:
>
> void g(A& a){
>    a.foo();
> }
>
>
> define void @_Z1gR1A(%struct.A* dereferenceable(8) %a) local_unnamed_addr
> #0 {
> entry:
>  %0 = bitcast %struct.A* %a to void (%struct.A*)***
>  %vtable = load void (%struct.A*)**, void (%struct.A*)*** %0,
> !invariant.group !7
>  %1 = load void (%struct.A*)*, void (%struct.A*)** %vtable
>  tail call void %1(%struct.A* nonnull %a)
>  ret void
> }
>
> !7 = !{!"_ZTS1A"}
>
>
>
> This works well if the pointer type doesn’t change, but when it does,
> devirtualization might not happen like here:
>
> struct A {
>    A();
>    virtual void foo();
> };
> struct B : A{
>    B();
>    virtual void foo();
> };
> void g(A& a){
>    a.foo();
>    a.foo();
> }
> void clobber(A&);
> void f() {
>      B b;
>      clobber(b);
>      g(b);
> }
>
> The other problem is that when we combine 2 instructions with different
> invariant.group metadata, then we pick one of them, because for now we can
> have only single !invariant.group metadata.
>
> The solution
>
> I had some initial ideas how it can be solved, like
>
>    1.
>
>    introducing multi invariant groups
>    2.
>
>    having sub invariant groups - like inheritance, so we could figure out
>    that one group is subgroup of another
>    3.
>
>    decorating all loads with base pointer MD (doesn’t work with multiple
>    inheritance)
>
>
> I consulted my ideas with Krzysztof Pszeniczny, and he proposed something
> much simpler: we can decorate every invariant.group md with empty metadata.
>
> This should work because the lifetime of the object is strictly defined by
> invariant.group.barrier.
>
>
> If this holds, we can start discussion about if it makes sense to keep
> invariant groups, and instead have just “invariant”, that would be
> equivalent to having invariant.group with the same metadata.
>
> Do you have some thoughts about this approach? I don’t have a mathematical
> proof, but I am confident that it should be valid.
>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170124/8a380aa0/attachment-0001.html>

Hal Finkel via llvm-dev

2017-Jan-25 23:03 UTC

head link

[llvm-dev] RFC: Emitting empty invariant group for vtable loads

Hi Piotr,

I think makes sense. Modulo bitcasts, the invariant is identified by a 
particular pointer SSA value. Given that you can't sensibly have two 
nonequivalent invariants associated with the same pointer SSA value 
simultaneously, there's no need to also identify the invariant with a 
metadata string as well. When we need a new "identifier" for the 
pointed-to value, we get one using invariant.group.barrier.

  -Hal


On 01/24/2017 01:39 PM, Piotr Padlewski via llvm-dev
wrote:> Hi,
> I would really like to hear some feedback about this.
>
> Piotr
>
> 2017-01-20 17:07 GMT+01:00 Piotr Padlewski <piotr.padlewski at gmail.com
> <mailto:piotr.padlewski at gmail.com>>:
>
>     Hi all,
>
>     I would like to propose a new way clang would decorate vtable
>     loads in order to handle devirtualization better.
>
>     I've added *llvm-dev* also, because this can start a discussion
>     about changing invariant.group to just invariant.
>
>     PDF version of this RFC can be found here:
>
>    
https://drive.google.com/file/d/0B72TmzNsY6Z8ZmpOUnB5dDZfSFU/view?usp=sharing
>    
<https://drive.google.com/file/d/0B72TmzNsY6Z8ZmpOUnB5dDZfSFU/view?usp=sharing>
>
>
>         Background:
>
>     Initial old design:
>
>     http://lists.llvm.org/pipermail/cfe-dev/2015-July/044227.html
>     <http://lists.llvm.org/pipermail/cfe-dev/2015-July/044227.html>
>
>     My talk from LLVM Dev Meeting
>
>     http://llvm.org/devmtg/2016-11/#talk6
>     <http://llvm.org/devmtg/2016-11/#talk6>
>
>
>         The problem
>
>     Clang with -fstrict-vtable-pointers decorates vtable loads with
>     metadata corresponding to mangled pointer type name like:
>
>     voidg(A& a){   a.foo();}
>
>     define void at _Z1gR1A(%struct.A* dereferenceable(8) %a)
>     local_unnamed_addr #0{entry: %0= bitcast %struct.A* %a to
>     void(%struct.A*)*** %vtable = load void(%struct.A*)**,
>     void(%struct.A*)*** %0, !invariant.group !7 %1= load
>     void(%struct.A*)*, void(%struct.A*)** %vtable tail call
>     void%1(%struct.A* nonnull %a) ret void}!7= !{!"_ZTS1A"}
>
>     This works well if the pointer type doesn’t change, but when it
>     does, devirtualization might not happen like here:
>
>     structA {   A();virtualvoidfoo();};structB :
>     A{   B();virtualvoidfoo();};voidg(A&
>     a){   a.foo();   a.foo();}voidclobber(A&);voidf() {     B
>     b;     clobber(b);     g(b);}
>
>     The other problem is that when we combine 2 instructions with
>     different invariant.group metadata, then we pick one of them,
>     because for now we can have only single !invariant.group metadata.
>
>
>       The solution
>
>     I had some initial ideas how it can be solved, like
>
>     1.
>
>         introducing multi invariant groups
>
>     2.
>
>         having sub invariant groups - like inheritance, so we could
>         figure out that one group is subgroup of another
>
>     3.
>
>         decorating all loads with base pointer MD (doesn’t work with
>         multiple inheritance)
>
>     I consulted my ideas with Krzysztof Pszeniczny, and he proposed
>     something much simpler: we can decorate every invariant.group md
>     with empty metadata.
>
>     This should work because the lifetime of the object is strictly
>     defined by invariant.group.barrier.
>
>     If this holds, we can start discussion about if it makes sense to
>     keep invariant groups, and instead have just “invariant”, that
>     would be equivalent to having invariant.group with the same metadata.
>
>     Do you have some thoughts about this approach? I don’t have a
>     mathematical proof, but I am confident that it should be valid.
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170125/7a93830a/attachment.html>

Richard Smith via llvm-dev

2017-Jan-30 17:38 UTC

head link

[llvm-dev] RFC: Emitting empty invariant group for vtable loads

On 20 Jan 2017 8:07 am, "Piotr Padlewski" <piotr.padlewski at
gmail.com> wrote:

Hi all,

I would like to propose a new way clang would decorate vtable loads in
order to handle devirtualization better.

I've added *llvm-dev* also, because this can start a discussion about
changing invariant.group to just invariant.

PDF version of this RFC can be found here:

https://drive.google.com/file/d/0B72TmzNsY6Z8ZmpOUnB5dDZfSFU/
view?usp=sharing


Background:

Initial old design:

http://lists.llvm.org/pipermail/cfe-dev/2015-July/044227.html

My talk from LLVM Dev Meeting

http://llvm.org/devmtg/2016-11/#talk6

The problem

Clang with -fstrict-vtable-pointers decorates vtable loads with metadata
corresponding to mangled pointer type name like:

void g(A& a){
   a.foo();
}


define void @_Z1gR1A(%struct.A* dereferenceable(8) %a) local_unnamed_addr #0
{
entry:
 %0 = bitcast %struct.A* %a to void (%struct.A*)***
 %vtable = load void (%struct.A*)**, void (%struct.A*)*** %0,
!invariant.group !7
 %1 = load void (%struct.A*)*, void (%struct.A*)** %vtable
 tail call void %1(%struct.A* nonnull %a)
 ret void
}

!7 = !{!"_ZTS1A"}



This works well if the pointer type doesn’t change, but when it does,
devirtualization might not happen like here:

struct A {
   A();
   virtual void foo();
};
struct B : A{
   B();
   virtual void foo();
};
void g(A& a){
   a.foo();
   a.foo();
}
void clobber(A&);
void f() {
     B b;
     clobber(b);
     g(b);
}

The other problem is that when we combine 2 instructions with different
invariant.group metadata, then we pick one of them, because for now we can
have only single !invariant.group metadata.

The solution

I had some initial ideas how it can be solved, like

   1.

   introducing multi invariant groups
   2.

   having sub invariant groups - like inheritance, so we could figure out
   that one group is subgroup of another
   3.

   decorating all loads with base pointer MD (doesn’t work with multiple
   inheritance)


The original idea was that the metadata would indicate the class that
introduced the vptr; that seems like it should work ok with multiple
inheritance. Is there a problem with that approach? (We may still be able
to remove it entirely, which could still be preferable.)

I consulted my ideas with Krzysztof Pszeniczny, and he proposed something
much simpler: we can decorate every invariant.group md with empty metadata.

This should work because the lifetime of the object is strictly defined by
invariant.group.barrier.


If this holds, we can start discussion about if it makes sense to keep
invariant groups, and instead have just “invariant”, that would be
equivalent to having invariant.group with the same metadata.

Do you have some thoughts about this approach? I don’t have a mathematical
proof, but I am confident that it should be valid.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170130/25b92c10/attachment.html>

Piotr Padlewski via llvm-dev

2017-Jan-30 19:07 UTC

head link

[llvm-dev] RFC: Emitting empty invariant group for vtable loads

2017-01-30 18:38 GMT+01:00 Richard Smith <richard at metafoo.co.uk>:
> On 20 Jan 2017 8:07 am, "Piotr Padlewski" <piotr.padlewski at
gmail.com>
> wrote:
>
> Hi all,
>
> I would like to propose a new way clang would decorate vtable loads in
> order to handle devirtualization better.
>
> I've added *llvm-dev* also, because this can start a discussion about
> changing invariant.group to just invariant.
>
> PDF version of this RFC can be found here:
>
> https://drive.google.com/file/d/0B72TmzNsY6Z8ZmpOUnB5dDZfSFU
> /view?usp=sharing
>
>
> Background:
>
> Initial old design:
>
> http://lists.llvm.org/pipermail/cfe-dev/2015-July/044227.html
>
> My talk from LLVM Dev Meeting
>
> http://llvm.org/devmtg/2016-11/#talk6
>
> The problem
>
> Clang with -fstrict-vtable-pointers decorates vtable loads with metadata
> corresponding to mangled pointer type name like:
>
> void g(A& a){
>    a.foo();
> }
>
>
> define void @_Z1gR1A(%struct.A* dereferenceable(8) %a) local_unnamed_addr
> #0 {
> entry:
>  %0 = bitcast %struct.A* %a to void (%struct.A*)***
>  %vtable = load void (%struct.A*)**, void (%struct.A*)*** %0,
> !invariant.group !7
>  %1 = load void (%struct.A*)*, void (%struct.A*)** %vtable
>  tail call void %1(%struct.A* nonnull %a)
>  ret void
> }
>
> !7 = !{!"_ZTS1A"}
>
>
>
> This works well if the pointer type doesn’t change, but when it does,
> devirtualization might not happen like here:
>
> struct A {
>    A();
>    virtual void foo();
> };
> struct B : A{
>    B();
>    virtual void foo();
> };
> void g(A& a){
>    a.foo();
>    a.foo();
> }
> void clobber(A&);
> void f() {
>      B b;
>      clobber(b);
>      g(b);
> }
>
> The other problem is that when we combine 2 instructions with different
> invariant.group metadata, then we pick one of them, because for now we can
> have only single !invariant.group metadata.
>
> The solution
>
> I had some initial ideas how it can be solved, like
>
>    1.
>
>    introducing multi invariant groups
>    2.
>
>    having sub invariant groups - like inheritance, so we could figure out
>    that one group is subgroup of another
>    3.
>
>    decorating all loads with base pointer MD (doesn’t work with multiple
>    inheritance)
>
>
> The original idea was that the metadata would indicate the class that
> introduced the vptr; that seems like it should work ok with multiple
> inheritance. Is there a problem with that approach? (We may still be able
> to remove it entirely, which could still be preferable.)
>
>You are referring to the last point, right? So it is possible to decorate
with the base class type (the introducing vptr class, which will be only
one for every vfunction). But there is problem with it. Consider example:

struct A {
  virtual void foo();
};
struct B {
  virtual void bar();
};
struct C : A, B {
  virtual void foo();
  virtual void bar();
};
void test(C &c) {
  c.foo();

  c.bar();
}


Right now call to foo and bar will get the same invariant.group, so we will
end up with only one load (the *!invariant.loads* - doesn't play any role
here):

define void @_Z4testR1C(%struct.C* dereferenceable(16) %c) {entry:
  %0 = bitcast %struct.C* %c to void (%struct.C*)***
  %vtable = load void (%struct.C*)**, void (%struct.C*)*** %0,
*!invariant.group* !7
  %1 = load void (%struct.C*)*, void (%struct.C*)** %vtable, !invariant.load !8
  tail call void %1(%struct.C* nonnull %c)

  %vfn2 = getelementptr inbounds void (%struct.C*)*, void
(%struct.C*)** %vtable, i64 1
  %2 = load void (%struct.C*)*, void (%struct.C*)** %vfn2, !invariant.load !8
  tail call void %2(%struct.C* nonnull %c)
  ret void
}

!7 = !{!"_ZTS1C"}
!8 = !{}



If we would decorate vtable load from c.foo() with !invariant.group
!"typeA", and from c.bar() with !"typeB", then

the second one won't be removed:



define void @_Z4testR1C(%struct.C* dereferenceable(16) %c) {entry:
  %0 = bitcast %struct.C* %c to void (%struct.C*)***
  %vtable = load void (%struct.C*)**, void (%struct.C*)*** %0,
*!invariant.group* !0
  %1 = load void (%struct.C*)*, void (%struct.C*)** %vtable, !invariant.load !2
  tail call void %1(%struct.C* nonnull %c)

  %vtable1 = load void (%struct.C*)**, void (%struct.C*)*** %0,
*!invariant.group* !1
  %vfn2 = getelementptr inbounds void (%struct.C*)*, void
(%struct.C*)** %vtable1, i64 1
  %2 = load void (%struct.C*)*, void (%struct.C*)** %vfn2, !invariant.load !2
  tail call void %2(%struct.C* nonnull %c)
  ret void
}

!0 = !{!"_ZTS1A"}
!1 = !{!"_ZTS1B"}
!2 = {}




Piotr



> I consulted my ideas with Krzysztof Pszeniczny, and he proposed something
> much simpler: we can decorate every invariant.group md with empty metadata.
>
> This should work because the lifetime of the object is strictly defined by
> invariant.group.barrier.
>
>
> If this holds, we can start discussion about if it makes sense to keep
> invariant groups, and instead have just “invariant”, that would be
> equivalent to having invariant.group with the same metadata.
>
> Do you have some thoughts about this approach? I don’t have a mathematical
> proof, but I am confident that it should be valid.
>
>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170130/bc3c9c23/attachment-0001.html>

Apparently Analagous Threads

Search for more possibly parallel threads

llvm dev - Jan 2017 - RFC: Emitting empty invariant group for vtable loads

[llvm-dev] RFC: Emitting empty invariant group for vtable loads

[llvm-dev] RFC: Emitting empty invariant group for vtable loads

[llvm-dev] RFC: Emitting empty invariant group for vtable loads

[llvm-dev] RFC: Emitting empty invariant group for vtable loads

[llvm-dev] RFC: Emitting empty invariant group for vtable loads

Apparently Analagous Threads