Empty base optimization, sharing vptrs

[Matt Austern]

I'm trying to work out exactly when we're allowed to allocate zero
space for an empty base object, and when we're allowed to share a vptr
between a full object and a base class subobject.  Here are my
assumptions.  I'd appreciate it if people could point out places where
my assumptions are overly aggressive.

The major assumption I'm making about class layout is that we're accessing
virtual bases through an offset in the vtable rather than through a pointer
in the class itself, so the only hidden member in an object is its vptr.

NONPOLYMORPHIC BASES

We may allocate any number of empty base subobjects at the same location
(the beginning of the complete object) except when, because of repeated
inheritance, we'd have multiple subobjects of the same type allocated in
the same place.

NON-VIRTUAL POLYMORPHIC BASES

The first immediate base subobject (not necessarily the leftmost
immediate base, since we're allowed to reorder base classes) may share
its vptr with the complete object.  We may allocate any number of
non-virtual polymorphic base subobjects at offset zero, provided that
all but one are empty except for their vptrs and that none of these
base classes have any non-virtual base classes in common themselves.
(It's OK if they do have virtual bases in common.)

VIRTUAL BASES

We may allocate any number of empty virtual base subobjects at offset 0,
and they will share the complete object's vptr.  Non-empty virtual base
subobjects get allocated at the end of the complete object.

There's one case where a base class B can be treated as empty (except
for a vptr) even if it has data members: the case when all of the data
members are inherited from virtual bases.



(Oh, another point.  I don't have a proof, but my guess is that
finding an optimal space-minimizing solution to the class layout
problem is equivalent to the travelling salesman problem.  I'm not
going to try.  What I'm going to present tomorrow is a heuristic
that I think should usually do better than just declaration order.)


			--Matt