The complete rule for type header layout is shown in Rule 1. Rule 1 looks like the simple type rule of Figure 7, except that it attempts to merge the supertype headers using the function merge, defined by the rules in Figure 10. Like the rule of Figure 7, Rule 1 makes T1 the primary supertype by aligning its header with that of T.
Rule 1: Type header layout
When a type has no supertypes, the result of the merge is considered to be empty, so the dispatch header for such a type contains just a single dispatch vector with the methods of T, starting from index 0. With this interpretation, Rule 1 covers all cases for type header construction.
The function merge takes a list of types and produces a layout that merges the headers of all the types. There are three cases that the function considers, described in the rules M1, M2, and M3 of Figure 10.
Rule M1 states the obvious base case: merging a single type header yields the type header itself.
Rule M2 actually performs a merge. The antecedent to M2 captures exactly the merge cases described in Figure 9, stating that
<H merge(T
1,...,Tn-1)
If x is non-empty, Rule M2 requires that there be no branches along
the path from Tn to S,
matching the antecedent to
merge case 1. If x
is empty, Rule M2 requires only that S
be a primary supertype of
Tn,
matching the antecedent to merge case 2. The merge result
from Rule M2 similarly matches the results of the two merge cases.
In case 1, using Rule M2 to merge in Tn
does not increase the
size of the type header. In case 2, the size of the type header increases,
but only by the size difference of
and 
.
If rules M1 and M2 fail, Rule M3 must be used: as in Figure 7,
append at the start of the previous merge. This rule
increases the size of the type header by the height of
,
so Rule M2 is always preferable when it can be applied.
The rules for merge are complete, because M3 can always
be applied in the case when M2 cannot.
For the merge rules to be correct, type headers in a primary supertype chain must be aligned with each other. This alignment is guaranteed because rules M2 and M3 keep the result of the previous merge aligned with the last word of the result merge.
Also, embedded type headers must be located at a known offset from
the end of the type header so that supertype conversion works properly;
Rule M1 clearly preserves this property. Rule M3 keeps all embedded type
headers in y at the same offset, and all embedded type headers in
Tn
are offset by the height of y, which is a known constant. Therefore,
M3 preserves the property. Rule M2 is more complex.
Clearly, M2 keeps any embedded headers in and y at the same offset.
Now, consider the embedded information in x.
Rule M2 can satisfy
either of the merge cases of Figure 9.
If it satisfies
case 1, then has the same height as
,
so the dispatch information in x is
located at the same offset in the resulting merge. If Rule M2 satisfies
case 2, then may be larger than ,
but x is empty. Inductively, the known-offset property is preserved by
the combination of Rule 1 and the merge rules.
The order in which the supertypes are merged is important, because it may determine whether Rule M2 can be applied. The indices on the supertypes in Rule 1 can be assigned in an order that allows as much merging as possible. The current Theta implementation does not attempt to find an optimal ordering, since the number of supertypes is usually small. It successively picks supertypes and places them in an ordered list for merge using the following heuristic. At each iteration, it preferentially picks a supertype whose header can be merged into the minimal number of unpicked supertype headers. Thus, it avoids adding a header until it has added any headers that it can be merged into. Usually, there is a supertype that cannot be merged into any other supertype headers. It breaks ties by picking a supertype that can be merged by Rule M2 into the layout of the currently picked supertypes. The picked supertype is appended to the end of the ordered list, and the process repeats.
Andrew C. Myers. Bidirectional Object Layout for Separate Compilation.
Proceedings of OOPSLA '95, pp. 124-139.
Copyright © 1995 Association for Computing Machinery
