Empty bases layout closure

[Jim Dehnert]

Pardon me if this has been discussed in the meetings I missed.  I will
try to at least describe what I was thinking.

> Date: Wed, 07 Jul 1999 11:03:32 -0700
> From: Daveed Vandevoorde <daveed at edg.com>
> 
> I am interested in resolving the issue of what to do with empty bases that
> cannot be located at the object's origin (because of the type conflict).
> 
> Empty classes appear in a complete object's layout in one of the following
> ways:
> 	(a) a nonvirtual direct base
> 	(b) a virtual base
> 	(c) a direct member
> 	(d) a nondirect member or nondirect nonvirtual base
> Cases (a-c) can be laid out specifically for the complete object, while
> (d) is  determined by the direct subobject that contains the (d) case.
> (d) is nonetheless important because of the type constraint that two
> empty subobjects of the same type should not be allocated at the same
> address.  I'm leaving case (b) out of this discussion and assume that
> its resolution as it stands today is fine, (but subordinate to prior
> layout decisions).
> 
> An example:
> 
> 	struct E1 {};
> 	struct E2: E1 {};
> 	struct E3 {};
> 	struct E4: E3 {};
> 	struct N1 { E1 n1; }
> 
> 	struct D: E1, E2, N1, E3, E4 {
> 	  E3 e3;
> 	};
> 
> D could be laid out in many ways. An optimal layout could be:
> 	this+0:	base E1, base E3
> 	this+1: base E2, member e3
> 	this+2: base N1, base E4
> However, an algorithm that would reliably generate such optimal layouts is 
> likely hard to describe.
>
> I also think there is value in decribing the layout in terms of an algorithm
> instead of trying to describe the results of that algorithm.

I intended the following process.  Note that I view each subobject as
having size 1, all tail padding.

 1) E1 goes at this+0:  it is first empty subobject.
    This leaves end of data at 0, end of padding at 1.
 2) E2 goes at this+1:  it conflicts with E1 and is shifted.
    This leaves end of (last subobject's) data at 1, end of padding at 2.
 3) N1 goes at this+2:  it conflicts with E1 and E2 and is shifted.
    This leaves end of data at 2, end of padding at 3.
 4) E3 goes at this+0:  it does not conflict with E1.
    This leaves end of data at 2, end of padding at 3.
 5) E4 goes at this+2:  it conflicts with E3 at 0, but not with N1 at
    end of data.  (Note that the intermediate point at 1 is not tried.)
    This leaves end of data at 2, end of padding at 3.
 6) e3 goes at this+3:  it conflicts with E3 at 0, and with E4 at 2.
    This leaves end of data at 3, end of padding at 4.

The end result is size 4 -- not optimal, but straightforard to
accomplish by sequential processing.  This doesn't match any of
Daveed's versions, but matches the size of his case (3).  It simply
assumes that processing order is (a) non-virtual bases, (b) members,
and finally (c) virtual bases, and that for an empty one we first
attempt to put it at 0, and given a conflict we look at end-of-data,
shifting further if necessary.

(Actually, e3 is different -- not a base -- and our rules didn't
contemplate considering 0.  Should they?  Further, I've treated
end-of-data above as at least the beginning of the last object
deposited.  We could well not increment it when a new empty object is
laid down past the end.  If we make these two improvements to my
process, we get the optimal layout with a simple algorithm.  Note that
I would like the end result here to be treated as all tail padding when
it becomes a component itself.  This is probably cleaner in conjunction
with the second improvement.)

> Here are three general approaches to the empty base layout algorithm:
> 
> (1) No reordering at all:
> An empty base can take up zero bytes, but all direct bases and members are 
> allocated in declaration order.  If allocating an element would create a type 
> conflict with a previously allocated empty base, move to the next alignment 
> slot.  This is not compatible with our issues list so far. For the above 
> example, it leads to:
> 	this+0:	base E1
> 	this+1:	base E2 (shift since conflict)
> 	this+2:	base N1 (shift since conflict with E2::E1)
> 	this+3:	base E3 (previous was not empty)
> 	this+4:	base E4	(shift since conflict)
> 	this+5:	member e3 (shift since conflict with E4::E3)
> Not great, but the example is quite artificial.
> 
> (2) Reorder only to origin:
> Same as (1) but if an empty base to be allocated can be allocated at offset
> zero with size zero this is done (in declaration order).  This is more or
> less compatible with what the issues list says so far, except it might be
> read to say that if this fails once, it is never reattempted again.  With 
> the latter constraint the layout of the example would be identical to (1).  
> Without that constraint, you get:
> 	this+0:	base E1, base E3
> 	this+1:	base E2
> 	this+2:	base N1
> 	this+3:	base E4
> 	this+4:	member e4
> 
> (3) Layout empty bases in second pass:
> There are various subalternatives in this option: the pass can be inserted
> before or after the layout of direct members; the location granularity can
> be a byte or the boundaries of already allocated subobjects; and there are
> probably other tweaks that can be made.  In our example the granularity
> doesn't matter since no subobject is larger than a byte.  Assuming that the
> pass occurs after direct member layout, you get:
> 	this+0:	base N1
> 	this+1:	member e3, base E1
> 	this+2:	base E2, base E3
> 	this+3: base E4
> 
> Comments?  Preferences?
> 
> My order of preference is:
> 	(1) As for other decisions, this option has the merits of being
> 	    simple and influencable by the knowledgeable programmer.
> 	(3 with no intrasubobject allocation)
> 	    I also prefer to have the second pass occur after direct member
> 	    layout to increase opportunities (including opportunities that
> 	    could not be emulated by the knowledgeable user of scheme (1)).
> 	(2) I anticipate the added specification complexity may not be worth
> 	    potential gains.
> 	(3 with intrasubobject allocation; i.e. byte-granularity)
> 	    This is a form of interleaving which I think was already unpopular
> 	    when we discussed the allocation of different access-sections.
> 
> 	Daveed
> 
-	    Jim Dehnert		dehnert at sgi.com
				(650)933-4272