vtable notes

[Jason Merrill]

The examples from today's discussion:

struct A {virtual void f ();}
  A->A::f

struct B: public A { };
  B::A->A::f

struct C: public A { virtual void f (); }
  C::A->C::f

struct X: { virtual void unique(); }
struct D: public X, public A { };
  D::X->X::unique
  D::A->A::f

struct E: public X, public A { virtual void f (); };
  E::X->X::unique
        E::f
  E::A->thunk E::f A*->E*

struct G: public virtual A { };
  G::A->A::f

struct H: public X, public virtual A { virtual void f (); }
  H::X->X::unique
  H::A->thunk H::f H::A*->H*

struct I: public H { int i; };
  I::X->X::unique
  I::A->thunk H::f I::A*->I::H*

And some thoughts, while this is fresh in my mind:

My design shares the thunks between H and I by putting the offset between A
and <the overriding class> into the secondary vtable for A, one offset per
virtual function.  Under this scheme, we get (at minimum) one thunk per:

  1) location of the vcall offset (for virtual bases)
  2) constant offset (for non-virtual bases)
  3) constant offset * location of vcall offset (for non-virtual bases of
     virtual bases)

Christophe's design proposes three changes:

  A) Add vcall offsets to secondary vtables for non-virtual bases,
     and use them in the calls.

The result of this would be that we would need one thunk per
  
  1) location of the vcall offset

He also proposes

  B) Share equal vcall offsets between functions in non-virtual inheritance

The result of this would be fewer vcall offsets to allocate.

  C) Ensure that the location of the vcall offset is the same for
     all secondary vtables

The result of this would be that we would need one thunk, period.

As I see it, A is a straightforward tradeoff; vtables get larger in the
case of non-virtual multiple inheritance, but we may be able to reduce the
number of thunks we use.  On the other hand, we won't be able to fall
through from a thunk that uses a vcall offset, so we might well end up
using the same thunks as in the existing design.

B is a simple improvement to A, reducing the size of the vtables.

C is the interesting part of Christophe's proposal.  It does sound like the
result would be faster (by about 2 units of speed) than the existing design
for calls through obscure bases in large inheritance structures.  However,
I'm not convinced that there exists a reasonable algorithm for allocating
vcall offsets in order to achieve this result, in the case of diamond
inheritance; even if there is, it would be much more complex than the one
for the current design.  This is why I don't think the change could be made
by tweaking a few words.

Before we discuss performance any further, I'd like Christophe to propose
an allocation strategy to accomplish C.  Or we could just agree to go
forward with the existing design.

Jason