Methods for laying out memories bidirectionally for object oriented applications6631513Abstract There is provided a method for laying out objects corresponding to an object-oriented application. The method including the step of determining whether any two given objects have opposing directionalities. A virtual function table pointer is shared between the two given objects, and the directionalities of the two given objects are changed to mixed, when the two given objects have opposing directionalities. Claims What is claimed is: Description BACKGROUND
[1] Procedure eliminate-transitive-edges (Hierarchy H)
[2] Begin
[3] For each node .chi. .di-elect cons. H do
[4] Let S = {y.vertline.y{character pullout} .chi.
[5] For each y, z .di-elect cons. S do
[6] If z < y then
[7] H .rarw. H - {character pullout}z {character pullout}
.chi.{character pullout}
[8] fi
[9] od
[10] od
[11] end
FIG. 12 is a flow chart of a method for eliminating transitive edges in a class hierarchy graph corresponding to an object oriented program. The graph has nodes representing object classes and edges representing immediate inheritance therebetween. It is determined if a set V is empty, the set V including the nodes in the graph (step 1202). If the set V is empty , then the method is terminated (step 1204). On the other hand, if the set V is not empty, then a node x is removed from the set V (step 1206). It is then determined if a set V' is empty, the set V' including nodes that directly and virtually inherit from the node x (step 1208). If the set V' is empty, then a return is made to the step of determining if the set V is empty (i.e., step 1202) (step 1210). On the other hand, if the set V' is not empty, then a node y is removed from the set V' (step 1212). It is then determined if a set V" is empty, the set V" including the nodes in the set V' other than the node y (step 1214). If the set V" is empty, then a return is made to the step of determining if the set V' is empty (step 1216). On the other hand, if the set V" is not empty, then a node z is removed from the set V" (step 1218). It is then determined if the node y is a base of the node z and not the node z (step 1220). If the node y is a base of the node z and not the node z, then an edge e1 is removed from the graph (step 1222). The edge e1 represents that the node z virtually inherits from the node x. On the other hand, if the node y is not a base of the node z or is the node z, then it is determined if the node z is a base of the node y and not the node y (step 1224). If the node z is a base of the node y and not the node y, then an edge e2 is removed from the graph (step 1226). The edge e2 represents that the node y virtually inherits from the node x. A return is made to the step of determining if the set V" is empty (i.e., step 1214), upon one of removing the edge e1 (i.e., step 1222), removing the edge e2 (i.e., step 1226), and when the node z is not a base of the node y (as determined at step 1224). FIG. 13(a) is a diagram of a class hierarchy. FIG. 13(b) is a diagram of the class hierarchy of FIG. 13(a) after elimination of transitive virtual inheritance edges. FIG. 13(c) is a diagram of the class hierarchy of FIG. 13(a) after elimination of single virtual inheritance as described hereinbelow. Consider the class hierarchy of FIG. 13(a). Then, the application of the above procedure eliminate-transitive-edges will result in the hierarchy of FIG. 13(b), where the following edges have been removed: (d<.sub.v a), (d<.sub.v b), (e<.sub.v b), and (g<.sub.v b). Clearly, global program information is a prerequisite of eliminate-transitive-edges. It should be stressed that eliminate-transitive-edges is merely a graph transformation technique, and not a C++ semantic preserving source-to-source transformation. There are rather subtle semantic differences at the source level between FIG. 13(a) and FIG. 13(b). For example, if a class x virtually inherits from a base class along two paths, one of which is protected and the other is private, then eliminating the protected virtual inheritance path will change the semantics of x. Therefore, this transformation needs to be done after static semantic checking. Conversely, the same example demonstrates a rationale for a program to use transitive inheritance edges. A description of edge devirtualization will now be given. Edge devirtualization, which is the next step in the streamlining of virtual inheritance, corresponds to devitalizing those virtual edges in a hierarchy which do not represent shared inheritance. This semantic preserving transformation is our first space optimization technique. Devirtualizing an edge allows VBPTRs to be eliminated, and it opens opportunities for sharing compiler-generated fields. As a simple example, consider a hierarchy with two classes, x and y, where y virtually inherits from x. Then, the edge (y<.sub.v x), can be devirtualized by replacing it with the edge (y<.sub.r x). Devirtualization was first proposed by D. Bacon, in "Fast and Effective Optimization of Statically Typed Object-Oriented Languages", PhD Thesis, U. of Cal. at Berkeley, December 1997. However, determining when it is legitimate is quite an elusive prospect. For example, (y<.sub.v x) must not be devirtualized if two more classes were to be added to our example, to form the hierarchy shown in FIG. 14. FIG. 14 is a diagram of an example hierarchy in which a single incoming virtual edge which should not be devirtualized. The reason is that there are two subobjects of type y in a z object, and devirtualizing (y<.sub.v x) would also imply two x subobjects in z, which violates virtual inheritance semantics. Indeed, this is a case where the above referenced devirtualization algorithm of D. Bacon fails. Thus, in contrast to prior belief, a virtual base with a single incoming edge cannot be devirtualized without a global examination of the inheritance hierarchy. Specifically, edge (y<.sub.v x) cannot be devirtualized if y is "duplicated". Duplication is a global property as shown by the following definition (hereinafter referred to as "definition 1"): a class y is duplicated in a hierarchy H if there are multiple occurrences of y in the subobject graph of some class z of H. There are multiple occurrences of y in z if, for example, z repeatedly inherits from y "more than once", or if z inherits from y in both a repeated and shared manner. Also, y is duplicated if there is yet another duplicated class u which non-virtually and directly inherits from y. The following procedure (hereinafter referred to as "is-duplicated") is used to determine whether duplication exists according to definition 1 above.
[1] Function is-duplicated (Node y): Boolean
[2] Begin
[3] For each u {character pullout} y do
[4] If is-duplicated(u) then
[5] Return true
[6] fi
[7] For each v{character pullout} y, v .noteq. u do
[8] If HDC (u,v) then
[9] Return true
[10] fi
[11] od
[12] od
[13] Return false
[14] end
FIG. 15 is a flow chart of a method for determining whether a node y is duplicated in a class hierarchy graph corresponding to an object oriented program. The graph has nodes representing object classes and edges representing immediate inheritance therebetween. It is determined if a set V is empty, the set V comprising all the nodes that nonvirtually inherit from the node y (step 1502). If the set V is empty, then the node y is identified as not being duplicated in the graph (step 1504). On the other hand, if the set V is not empty, then a node u is removed from the set V (step 1506), and it is determined if the node u is duplicated in the graph (step 1508). If the node u is not duplicated, then it is determined if a set V' is empty (step 1510). The set V'includes all the nodes that directly inherit from the node y except for the node u. If the set V' is empty, then a return is made to the step of determining if the set V is empty (i.e., step 1502) (step 1512). On the other hand, if the set V' is not empty, then a node v is removed from the set V' (step 1514). It is then determined if the node u and the node v have a common descendant (step 1516). If the node u and the node v do not have a common descendant, then a return is made to the step of determining if the set V' is empty (i.e., 1510) (step 1518). If the node u is duplicated (as determined at step 1508) or the node u and the node v have a common descendant (as determined at step 1516), then the node y is identified as duplicated (step 1520). The following procedure (hereinafter referred to as "HCD") is used to determine whether two classes have a common descendant.
[1] Function HCD (Node v.sub.1, v.sub.2): Boolean
[2] Begin
[3] For each w .di-elect cons. H do
[4] If w .ltoreq. v.sub.1, w .ltoreq. v.sub.2,
[5] Return true
[6] fi
[7] od
[8] Return false
[9] end
FIG. 16 is a flow chart of a method for determining whether two nodes u and v have a common descendant in a class hierarchy graph corresponding to an object oriented program. The graph has nodes representing object classes and edges representing immediate inheritance therebetween. The nodes u and v correspond to classes u and v, respectively. It is determined if a set V is empty, the set V comprising all the nodes in the graph (step 1602). If the set V is empty, then the nodes u and v are identified as not having a common descendant in the graph (step 1604). On the other hand, if the set V is not empty, then a node w is removed from the set V (step 1606). It is then determined if the node w is the node u or the node w inherits from the node u, and if the node w is the node v or the node w inherits from the node v (step 1608). If the node w is not the node u or the node w does not inherit from the node u, and the node w is not the node v or the node w does not inherit from the node v, then a return is made to the step of determining if the set V is empty (i.e., step 1602) (step 1610). On the other hand, if the node w is the node u or the node w inherits from the node u, and the node w is the node v or the node w inherits from the node v, then the nodes u and v are identified as having a common descendant (step 1612). Devirtualization can still be done even if there are multiple incoming virtual edges into a virtual base x. A single virtual inheritance edge is defined in the following definition (hereinafter referred to as "definition 2"): an edge (y<.sub.v x) is considered a single virtual inheritance edge, if y is not duplicated and there is no other y.sup.1 =y, y.sup.1 <.sub.v x, such that there is z, z<y and z<y.sup.1. For example, consider the example of FIG. 17, which is a diagram of multiple incoming virtual edges, some of which may be devirtualized. In FIG. 17, (y.sub.2 <.sub.v x) is the only single virtual inheritance edge. A single virtual inheritance edge (y<.sub.v x) can be safely devirtualized since it's devirtualization preserves the semantics of virtual inheritance. For example, class a in FIG. 13(b) has two incoming virtual edges: (b<.sub.v a) and (h<.sub.v a). Since there are no common descendants to the nonduplicated nodes b and h, both these edges represent single virtual inheritance, and can be devirtualized. Conversely, there are two incoming virtual edges (d<.sub.v c) and (e<.sub.v c) into class c. However, singe g is a common ancestor of d and e, these edges are not a case of single virtual inheritance. The following procedure (hereinafter referred to as "eliminate-single-VI") is used to devirtualize all single virtual inheritance edges. This procedure improves on the result of D. Bacon, described in above referenced article "Fast and Effective Optimization of Statically Typed Object-Oriented Languages", by considering multiple incoming virtual inheritance edges.
[1] Procedure eliminate-single-VI (Hierarchy H)
[2] Begin
[3] For each node x .di-elect cons. H do
[4] Let S = {y.vertline.y {character pullout} x {character
pullout} {character pullout} is-duplicated (y)}
[5] For each y .di-elect cons. S do
[6] For each y.sup.1 .di-elect cons. S, y.sup.1 .noteq. y
do
[7] If HCD (y, y.sup.1) then
HCD (y, y.sup.1) has shared virtual inheritance with x via subobjects of type y and y.sup.1
[8] next y
[9] fi
[10] od
A single virtual inheritance between y and x was detected
[11] H .rarw. H - {character pullout}y {character pullout}
x{character pullout}
[12] H .rarw. H = {character pullout}y {character pullout}
x{character pullout}
[13] od
[14] od
[15] end
FIG. 18 is a flow chart of a method for devirtualizing single virtual inheritance edges in a class hierarchy graph corresponding to an object oriented program. The graph has nodes representing object classes and edges representing immediate inheritance therebetween. It is determined if a set V is empty, the set V comprising all the nodes in the graph (step 1802). If the set V is empty, then the method terminates (step 1804). On the other hand, if the set V is not empty, then a node x is removed from the set V, (step 1806). It is then determined if a set S is empty, the set S comprising all of the nodes in the graph that directly and virtually inherit from the node x and that are not duplicated in the graph (step 1808). If the set S is empty, then a return is made to the step of determining if the set V is empty (i.e., step 1802) (step 1810). On the other hand, if the set S is not empty, then a node y is removed from the set S (step 1812). It is then determined if a set S' is empty, the set S' comprising the nodes in the set S except the node y (step 1814). If the set S' is not empty, then a node y' is removed from the set S' (step 1816), and it is then determined if the node y and the node y' have a common descendant (step 1818). If the nodes y and y' do not have a common descendant, then a return is made to the step of determining if the set S' is empty (i.e., step 1814) (step 1820). On the other hand, if the nodes y and y' have a common descendant, then a return is made to the step of determining if the set S is empty (i.e., step 1808) (step 1822). If the set S' is determined to be empty at step 1814, then an edge e is replaced with an edge e' (step 1824). The edge e represents that the node y directly and virtually inherits from the node x, and the edge e' represents that the node y has a fixed offset with respect to the node x. Upon replacing the edge e, a return is made to the step of determining if the set S is empty (i.e., step 1808) (step 1826). When procedure eliminate-single-VI is applied to FIG. 13(b), edges (b<.sub.v a), (h<.sub.v a), and (f<.sub.v d) are devirtualized resulting in the hierarchy of FIG. 13(c). Consider the subobject graph in FIG. 19, which is a diagram of the subobject graph of class g in FIG. 13(a). There are 6 VPTRs and 10 VBPTRS. After eliminate-single-VI has been applied, the number of VPTRs is reduced by one (to 5) and the number of VBPTRs is reduced by four (to 6). FIG. 20 is a diagram of the subobject graph of class g in FIG. 13(c). In particular, FIG. 20 corresponds to the subobject graph for class g after eliminate-single-VI has been applied to FIG. 13(b). Recall the chain of n classes that was presented in FIG. 10. Initially, an object of class a, required n VPTRs and a quadratic number of VBPTRs. After applying eliminate-single-VI to this chain all inheritance is devirtualized, and an object of class a, requires only one VPTR and no VBPTRs. The size of a y object may be reduced in a number of different ways due to the devirtualizing of an edge (y<.sub.v x). First, the essential VBPTR from y to x is always eliminated. Second, the devirtualization enables sharing between x and y of compiler generated fields. These include one VPTR that may be shared between y and x. Even greater is the saving potential in the inessential VBPTRs from y to the virtual bases of x, which are all eliminated. There are up to n of these. In addition, y's savings occurs every time y is a subobject in some object z. There could be an exponential number in-n of y subobjects in an object z. Another kind of potential savings is the inessential VBPTRs to x in the subobjects derived from y. There are up to n possible classes that are derived from y. Each one of these classes has the potential to have exponential in n number of subobjects derived from y. The final class hierarchy transformation, i.e, inlining virtual bases, will now be given. By inlining we mean that instead of storing a pointer to a virtual base subobject, this subobject can be stored in a fixed offset in the memory layout of the derived class. For an example, let's go back to the subobject graph of FIG. 6. Instead of laying out class e as in FIG. 7, inlining a into b obtains the layout shown in FIG. 21, which is a diagram illustrating inlining a virtual base in the hierarchy of FIG. 5. The new layout eliminates the VBPTR from b to a, and the separate VPTR for a. Inlining is similar to devirtualization in that compiler-generated fields are eliminated since the offset of a virtual base is fixed with respect to a derived class. However, unlike devirtualization, an inlined base may still be shared. In particular, c's subobject in FIG. 21 still retains a VBPTR to a. In addition to reducing space overhead, inlining reduces the time required to access a virtual base, b, and any of its members from the derived class that the base is inlined into since this derived class no longer uses a VBPTR to access b. The potential savings associated with inlining include those of devirtualization. Furthermore, additional inessential VBPTRs may be eliminated. Suppose, for example, that inlining is applied to the hierarchy of FIG. 22, which is a diagram of an n-double-chain shaped virtual inheritance hierarchy. Assume that a.sub.1 is inlined into a.sub.i+1 and b.sub.1 is inlined into b.sub.i+1 for i=1, . . . , n-1. Clearly, a subobject of class a.sub.1 (b.sub.1) does not now need any VBPTRs to a.sub.j (b.sub.j), j<i. Two VBPTRs, one from a.sub.2 to b.sub.1 and the other from b.sub.2 to a.sub.1, are sufficient for any a.sub.i (respectively b.sub.i) to access any virtual base b.sub.j (respectively a.sub.j) 0<j<i. This is because inlining makes the offsets of all b.sub.j (respectively a.sub.j) subobjects fixed with respect to each other, and in particular, fixed with respect to b.sub.1 (a.sub.1). Therefore, the total number of VBPTRs in objects of class c is reduced from (n-1)(n-2) to 2, i.e., from quadratic to a constant. Note that neither procedure eliminate-transitive-edges nor eliminate-single-VI can eliminate any virtual inheritance from the class hierarchy in FIG. 22, which is a diagram illustrating an n-double-chain shaped virtual inheritance hierarchy. That is, this class hierarchy has no transitive or single virtual inheritance edges. As mentioned above, if x is a virtual base that has an immediate duplicated descendant y then x must not be inlined into y. This is because only one virtual base subobject of x occurs in the subobject graph while multiple subobjects of y occur. For example, consider the class hierarchy in FIG. 14. If x were inlined into y which is duplicated in z, then there would be two subobjects of type x in a z object, contradicting the semantics of virtual inheritance. Hereinbelow, two methods are described which implement the inline virtual base transformation. The first method is based on the simple observation that a virtual base can be inlined into at least one of its immediate nonduplicated descendants. Assuming that procedures eliminate-transitive-virtual-edges and eliminate-single-VI were run, a simple procedure (hereinafter referred to as "simple-inline-VB") for selecting a derived class in which to inline a virtual base according to an embodiment of the present invention follows.
[1] Procedure simple-inline-VB (Hierarchy H)
[2] Begin
[3] For each node x .di-elect cons. H do
[4] If exists y .di-elect cons. H, y {character pullout} x and
{character pullout} is-duplicated(y) then
[5] H .rarw. - {character pullout}y {character pullout}
x{character pullout}
[6] H .rarw. = {character pullout}y {character pullout}
x{character pullout}
[7] od
[8] end
FIG. 23 is a flow chart of a method for implementing virtual bases with fixed offsets in a class hierarchy graph corresponding to an object oriented program according to an embodiment of the present invention. The graph has nodes representing object classes and edges representing immediate inheritance therebetween. In the method of FIG. 23, it is determined-if a set N is empty, the set N including all nodes in the graph (step 2302). If the set N is empty, then the method is terminated (step 2304). On the other hand, if the set N is not empty, then a node x is removed from the set N (step 2306). It is then determined if a set Y is empty, the set Y including all nodes in the graph that directly and virtually inherit from the node x (step 2308). If the set Y is empty, then a return is made to the step of determining if the set N is empty (i.e., step 2302) (step 2310). On the other hand, if the set Y is not empty, then a node y is removed from the set Y (step 2312). It is then determined if the node y is duplicated in the graph (step 2314). If the node y is duplicated, then a return is made to the step of determining if the set Y is empty (i.e., step 2308) (step 2316). On the other hand, if the node y is not duplicated, then an edge e is replaced with an edge e' (step 2318). The edge e represents that the node y virtually inherits from the node x, and the edge e' represents that the node x has a fixed offset with respect to the node y (i.e., the node x is inlined into the node y). Upon replacing the edge e, a return is made to the step of determining if the set N is empty (i.e., step 2302) (step 2320). Procedure simple-inline-VB introduced a new kind of inheritance edge. In writing y<.sub.i x we mean that x is an immediate virtual base of y and also that x is inlined into The exists statement in procedure simple-inline-VB is nondeterministic, and it is not clear a priori which descendant to inline into. For example, in the subobject graph shown in FIG. 6, a could be inlined into either b or c, but not into both. It seemed better to inline it into b, since this inlining reduces the size of instances of three classes (b, d and e) as opposed to only two classes c and e if the inlining was into c. A more powerful version of inlining virtual bases is provided in the following procedure (hereinafter referred to as "inline-VB"). It is based on the observation that a virtual base may be inlined into more than one of its nonduplicated subobjects provided that they do not have a common descendant.
[1] Procedure inline-VB (Node v, Hierarchy H)
[2] Begin
[3] Let V .rarw. {u.vertline.u {character pullout} v
{character pullout} {character pullout} is-duplicated(u)}
[4] Let E .rarw. {{character pullout}u.sub.1, u.sub.2
{character pullout}.vertline.u.sub.1, u.sub.2 .di-elect cons. V, HCD
(u.sub.1, u.sub.2)
[5] Let G .rarw. (V,E)
[6] Select S {character pullout} V, S maximal independent
set in G
[7] For each s .di-elect cons. S do
[8] H .rarw. H - {character pullout}s {character pullout}
v{character pullout}
[9] H .rarw. H = {character pullout}s {character pullout}
v{character pullout}
[10] od
[11] end
FIG. 24 is a flow chart of a method for implementing virtual bases with fixed offsets in a class hierarchy graph corresponding to an object oriented program according to another embodiment of the present invention. The graph has nodes representing object classes and edges representing immediate inheritance therebetween. It is determined if a set V' is empty, the set V' including nodes that directly and virtually inherit from a node v in the graph (step 2402). If the set V' is not empty, then a node u is removed from the set V' (step 2404). It is then determined if the node u is duplicated in the graph (step 2406). If the node u is duplicated, then a return is made to the step of determining if the set V' is empty (i.e., step 2402) (step 2408). On the other hand, if the node u is not duplicated, then the node u is added to a set V (step 2410). The set V is initially an empty set of nodes that directly and virtually inherit from the node v and that are not duplicated in the graph. Upon adding the node u to the set V, a return is made to the step of determining if the set V' is empty (i.e., step 2402) (step 2412). If set V' was determined to be empty at step 2402, then it is determined if the set V is empty (step 2414). If the set V is not empty, then a subset S of the set V is selected such that the subset S is a maximal independent set in a set G (step 2416). The set G includes a first ordered pair of the set V and a set E. The set E includes a second ordered pair of a node u1 and a node u2. The nodes u1 and u2 are included in the set V and have a common descendant in the graph. It is then determined if the subset S is empty (step 2418). If the subset S is not empty, then a node s is removed from the subset S (step 2420), and an edge e is replaced with an edge e' (step 2422). The edge e represents that the node s virtually inherits from the node v, and the edge e' represents that the node v has a fixed offset with respect to the node s (i.e., the node v is inlined into the node u). A return is then made to the step of determining if the subset S is empty (step 2424). If the set V is determined to be empty at step 2414 or the subset S is determined to be empty at step 2418, then the method is terminated (step 2426). To understand the procedure, recall that a set of nodes is independent in a graph, if no two nodes in it are connected by an edge. The maximal independent set problem finds an independent set that maximizes the number of its members. This version of inlining covers edge devirtualization: if an (y<.sub.v x) would have been devirtualized by eliminate-single-VI, then in the graph G of inline-VB, node y would have no edges incident on it, and therefore would be part of the maximal independent set. Unfortunately, the maximal independent set problem is known to be NP (non-deterministic polynomial) complete. This was described by M. Garey and D. Johnson, in Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Co., 1979. This means that the best way, at least to the extent known so far, of finding such a set is not significantly better than trying out all possible different sets S. Although this exponential computation time sounds deterring, inline-VB may be feasible in many cases, since it is exponential only in the number of immediate virtual descendants, which could be a small number in practice. A description of how the transformations presented above can be combined together into two cohesive procedures will now be given. For any such procedure, eliminate-transitive-edges should always be applied first to a class hierarchy before either edge devirtualization or inlining. To see this, consider the transitive edge (a<.sub.v d) in FIG. 13(a). Eliminate-transitive-edges enables eliminate-single-VI, since only after the transitive edge (a<.sub.v d) is eliminated, can (a<.sub.v b) be devirtualized. Eliminate-transitive-edges eliminates inferior inlining candidates. Inlining a into d attains the same benefits or less than inlining a into b and, therefore, is inferior. But (a<.sub.v d) is a transitive edge. Procedures eliminate-transitive-edges and eliminate-single-VI should be executed before simple-inline-VB to ensure that only shared bases are inlined. There are two natural ways to combine the above transformations. The first is provided in the following procedure (hereinafter referred to as "streamline-VI"), which has an overall execution time bounded by the complexity of eliminate-single-VI.
[1] Procedure streamline-VI (Hierarchy H)
[2] Begin
[3] eliminate-transitive-edges (H)
[4] eliminate-single-VI (H)
[5] simple-inline-VB (H)
[6] end
FIG. 25 is a flow chart of a method which combines the three above transformations (procedures) to streamline the overall inlining process according to an embodiment of the present invention. First, the procedure eliminate-transitive-edges is performed (step 2502). Next, the procedure eliminate-single-VI is performed (step 2504). Lastly, the procedure simple-inline-VB is performed (step 2506). The second is provided in the following procedure (hereinafter referred to as "streamline-VIA"), which has an overall execution time bounded by the complexity of inline-VB. Since inline-VB will inline single virtual inheritance edges, eliminate-single-VI is not needed in streamline-VIA.
[1] Procedure streamline-VIA (Hierarchy H)
[2] Begin
[3] eliminate-transitive-edges (H)
[4] For each node n in H do
[5] inline-VB (n,H)
[6] od
[7] end
FIG. 26 is a flow chart of a method which combines two of the three above transformations (procedures) to streamline the overall inlining process according to an embodiment of the present invention. First, the procedure eliminate-transitive-edges is performed (step 2602). Lastly, the procedure inline-VB is performed (step 2604). Both the elimination of transitive inheritance edges and edge devirtualization or inline-VB are needed to remove the circle notation which identifies shared bases in a class hierarchy. The application of these procedures makes the circle notation for virtual classes in subobject graphs redundant. Nevertheless, we retain circle notation because it highlights virtual bases. If these procedures have been applied, then shared bases are exactly those nodes in the subobject graph whose in-degree is greater than one. Of the three transformations presented, only eliminate-single-VI is a source-to-source transformation. As noted above, eliminate-transitive-edges must be applied after static semantic checking of the program. Simple-inline-VB and inline-VB must be performed on an intermediate representation of the application as there is no analogous language construct with which to represent inlined inheritance. Therefore, either version of streamline-VI may be applied to an application's intermediate representation. The decision of whether streamline-VI should be invoked when whole program information is available is not a hard one. The procedure streamline-VI will never increase the execution-time or memory consumption of an application. Moreover, the run-time of the first two transformations and the simple-inline-VB are only polynomial. The run-time of inlining-VB depends on the extent of the optimization that is applied. There are, however, good heuristics for the maximal independent set that run in polynomial time. Systems providing whole program information include the IBM Visual Age C++ compiler and Vortex. The former is described by M. Karasick, in "The Architecture of Montana: An Open and Extensible Programming Environment with an Incremental C++ Compiler", Proceedings Foundations of Software Engineering (FSE '98), Orlando, Fla., November 1997; and L. Nackman and J. Barton, in "Base-Class Composition with Multiple Derivation and Virtual Bases", Proceedings of the Sixth Usenix C++ Technical Conference, 1994. Vortex is described by C. Chambers, J. Dean, and D. Grove, in "Whole-Program Optimization of Object-Oriented Languages", Technical Report UW-CSE-96-06-02, U. of Wash., Dept. of Computer Science and Engineering, June 1996. A description of bidirectional layout techniques according to the present invention will now be given. FIG. 27 is a diagram of a hierarchy used to exemplify bidirectional layout according to the present invention. Given the inheritance hierarchy of FIG. 27, the traditional object layout scheme requires only one VPTR for all the classes, except for class c which requires two VPTRs. FIG. 28 is a diagram illustrating bidirectional layout of class c of FIG. 27. We can layout class c using only one VPTR as shown. Suppose that class a, is laid out using negative offsets. That is to say, its VPTR will be at offset zero, and all its data members, user-defined and compiler-generated (other than its VPTR), are laid out in decreasing addresses. This will force what we may call a negative directionality on all classes a.sub.1, . . . , a.sub.9. Similar layout is imposed on the VTBL: functions associated with classes a.sub.1, . . . , a.sub.9 will occupy entries -1, -2, . . . in their table. Classes b.sub.1, . . . , b.sub.9 will still have a positive directionality, with their entries at offsets 0, 1, . . . in their VTBL. Classes a.sub.9 and b.sub.5 are married in class c: they share their VPTR as illustrated in FIG. 29, which is a diagram of a bidirectional layout of the VTBL of class c of FIG. 27. In addition to marrying subobjects that are inherited and have opposite directionality, subobjects that are fields of an object may also be married if they have opposite directionalities; that is, one field has positive directionality and the other field has negative directionality. Consider a class A that has two fields F1 and F2, such that F1 has type class B and F2 has type class C. If the directionality of class B and class C are opposite, then F1 and F2 can be married and share a virtual function table pointer in an A object. This sharing is persistent; that is, F1 and F2 will continue to share a virtual functional table pointer when class A is further derived. Finally, if classes A and B have opposite directionality, then the run-time system could marry an object of type A and an object of type B together to share a virtual function table pointer when objects of these class types are allocated. The directionality of a class x is denoted by X.sup.(x). In the traditional layout, X.sup.(x) =positive for all x. With bidirectional layout, X.sup.(x) can be either positive or negative. If this is the case, then we say that x is "directed". Two more values which X.sup.(x) can assume are mixed and none. Mixed is used if x shares its VPTR with two base classes that are married with each other. None occurs if x and all of its base classes have no virtual functions and consequently x has no need for a VPTR. In both cases we will say that x is undirected. The predicate X.sup.(x) =X.sup.-(y) means that either X.sup.(x) =positive and X.sup.(y) =negative or that X.sup.(x) =negative and X.sup.(y) =positive. The semantics of the different values of X.sup.(x) are summarized in Table 1.
TABLE 1
.chi..sup.(X) a b c d
positive yes no yes 0, 1, . . .
negative yes yes no -1, -2, . . .
mixed yes yes yes . . . , -2, -1, 0, 1, . . .
none no no yes none
The notations used in FIG. 1 are as follows: a: a VPTR at offset zero b: data members in negative offsets c: data members in positive offsets d: indices of VTBL entries In order for bidirectional layout to work in a separate compilation setting, we need an oracle to assign the right directionalities to classes a.sub.1 and b.sub.1 when they are compiled, which could be prior to the compilation of class c. A simple and effective work around is to assign directionalities at random. The following procedure (hereinafter referred to as "assign-initial-directionality") may be used to assign directionalities to classes whose directionality is not determined by their parents. This will insure that with probability 0.5, one VPTR will be saved in class c. We can say that the expected savings is 0.5.times.1=0.5 VPTR.
[1] Procedure assign-initial-directionality (Node n)
[2] Begin
[3] If n has no virtual functions then
[4] .chi..sup.(n) .rarw. none
[5] else
[6] .chi..sup.(n) .rarw. Random(n)
[7] fi
[8] end
FIG. 30 is a flow chart of a method for assigning an initial directionality to a subobject n in an object layout chart corresponding to an object class. The chart includes subobjects of the object class and virtual function table pointers for pointing to virtual function tables of the subobjects. It is determined if the subobject n has any corresponding virtual methods (step 3002). If the subobject n does not have any corresponding virtual methods, then no directionality is assigned to the subobject n (step 3004). On the other hand, if the subobject n has any corresponding virtual methods, then a random directionality is assigned to the subobject n (step 3006). The crucial point in computing this expectation is that the "coin-tosses" in a.sub.1 and b.sub.1 were independent. More generally, an expected savings can be guaranteed if any two selections of directionalities to root classes are independent. It is not necessary however to have independence between any three selections. To implement "pair-wise-independence" random selection we can apply a standard technique of randomized algorithms, such as that described by L. Carter and M. Wegman, in "Universal Classes of Hash Functions", J. Comput. Sys. Sci., 18:143-154, 1979, and then replace the coin tosses by a hash function. In other words, whenever a compiler encounters a class whose directionality is not forced, it applies a hash function, selected at random from a universal class of such functions, to its name. The value of the hash function determines whether the class has positive or negative directionality. Thus, we will use the following procedure (hereinafter referred to as "random") as a pseudo random-number generator. That is, the procedure random will be used to return the pseudo-random directionality assignment of a class.
[1] Function random (Noden)
[2] Begin
[3] If odd (hash(n)) then
[4] Return positive
[5] else
[6] Return negative
[7] fi
[8] end
FIG. 31 is a flow chart of a method for randomly assigning a directionality to a subobject n in an object layout chart corresponding to an object class. The chart includes subobjects of the object class and virtual function table pointers for pointing to virtual function tables of the subobjects. A hash function is applied to the subobject n such that a response of odd or not odd is returned (step 3102). It is then determined if the response of odd is returned (step 3104). If the response of odd is returned, then the directionality of the subobject n is identified as positive (step 3106). On the other hand, if the response of not odd is returned, then the directionality of the subobject n is identified as negative (step 3108). One major advantage of a hash function compared to coin-tosses is that, once it has been selected, its values can be reproduced in independent runs of the compiler. A description of the "ephemeral marriage" of virtual bases according to an embodiment of the present invention will now be given. The phrase "ephemeral marriage" is hereinafter used to refer to the case wherein two virtual subobjects laid out in opposite directions in an object layout chart share the same virtual function table pointer. An ephemeral marriage is not persistent, in contrast to "persistent marriage" described hereinbelow. The use of indirection in the implementation of virtual base subobjects makes it possible to place them anywhere in memory. This degree of freedom, together with bidirectional layout, unfolds saving opportunities beyond those suggested by our motivating example. Let v.sub.1 and v.sub.2 be two virtual bases, direct or indirect, of class u, and suppose that X.sup.(v1) =positive and X.sup.(v2) =negative. Then, between v.sub.1 and v.sub.2 we could save one VPTR, by placing them against each other in the layout of u. We say that v.sub.1 and v.sub.2 are married in u, but in contrast with the marriage of nonvirtual base classes a.sub.9 and b.sub.5, this marriage is ephemeral. Subobjects v.sub.1 and v.sub.2 are not necessarily married with each other in every context in which they occur together. In other words, even though the subobjects of v.sub.1 and v.sub.2 are adjacent in objects of class u, they are not necessarily adjacent if u occurs as a subobject of another class w, w<u. Therefore, it is necessary that u maintains two VBPTRs, one for v.sub.1 and one for v.sub.2. The following procedure (hereinafter referred to as "ephemeral-virtual-base-marriage") is used to provide an ephemeral marriage of virtual bases. The procedure allows for a class to be temporarily married with one of its parents.
[1] Procedure ephemeral-virtual-base-marriage (Node u)
[2] Begin
[3] Let V .rarw. {v.vertline.u {character pullout} v}
[4] If .chi..sup.(u) = positive {character pullout}
.chi..sup.(u) = negative then
[5] V .rarw. U {u}
[6] fi
[7] Let V.sup.+ .rarw. {v .di-elect cons.
V.vertline..chi..sup.(v) = positive}
[8] Let V.sup.- .rarw. {{character pullout}v .di-elect cons.
V.vertline..chi..sup.(v) = negative}
Marry unmarried virtual bases
[9] While V.sup.+ .noteq. .O slashed. {character pullout}
V.sup.- .noteq. .O slashed. do
[10] Select v.sub.1 .di-elect cons. V.sup.+ and v.sub.2
.di-elect cons. V.sup.-
[11] Marry v.sub.1 and v.sub.2
[12] V.sup.+ .rarw. V.sup.+ - v.sub.1
[13] V- .rarw. V.sup.- - v.sub.2
[14] od
[15] end
FIG. 32 is a flow chart of a method for sharing virtual function table pointers between virtual subobjects in an object layout chart corresponding to an object class. The virtual function table pointers point to virtual function tables of the subobjects. It is determined if a directionality of a subobject u is one of positive and negative (step 3202). The subobject u is added to a set V, when the directionality of the subobject u is one of positive and negative (step 3204). The set V includes nodes that are direct virtual bases of the subobject u. The set V also includes the subobject u, if the subobject u is directed. Upon adding the subobject u to the set V or if the directionality of the subobject u is not one of positive and negative (as determined at step 3202), then it is determined if one of sets V+ and V- is empty (step 3206). The set V+ includes subobjects in the set V having positive directionality, and the set V- includes subobjects in the set V having negative directionality. If one of the sets V+ and V- is empty, then the method is terminated (step 3208). On the other hand, if both of the sets V+ and V- are not empty, then a subobject v1 is removed from the set V+ (step 3210), and a subobject v2 is removed from the set V- (step 3212). The subobject v1 is married to the subobject v2 (i.e., the subobject v1 and the subobject v2 share a virtual function table pointer) (step 3214), and a return is made to the step of determining if one of the sets V+ and V- is empty (i.e., step 3206) (step 3216). The procedure assumes that a directionality was already assigned to the class and to all of its parents. In particular, the procedure is expected to be executed after the procedure (presented below) that persistently marries nonvirtual bases. Consider again the hierarchy of FIG. 5. Suppose that X.sup.(a) =positive and that X.sup.(e) =negative. Then, procedure ephemeral-virtual-base-marriage improves further the layout of FIG. 21 obtaining the layout of FIG. 33, which is a diagram illustrating the application of both virtual base inlining and bidirectional layout to class e of the hierarchy of FIG. 5. Advantageously, the layout of FIG. 33 uses only one VPTR and one VBPTR. Moreover, notice that, unlike non-virtual inheritance, if the virtually derived classes of a base are directed, their directionalities may be different. The marriage of two virtual bases requires that their VTBLs are juxtaposed. Since, in general, a class has a different VTBL for every context this class is used, marriage incurs no additional overhead. When classes v.sub.1 and v.sub.2 are married in u, we also place the VTBL of v.sub.1 class in a u context against the VTBL of v.sub.2 in a u context. If the VTBL of, for example, v.sub.1 in a u context happens to be exactly the same as that of a derived class of u, w, then the marriage of v.sub.1 may make it impossible to optimize class space by using only one VTBL for v.sub.1 in w and for v, in u. A description of "persistent marriage" of nonvirtual bases will now be given. The phrase "persistent marriage" is hereinafter used to refer to the case wherein, in an object layout chart of an object x, two nonvirtually inherited subobjects laid out in opposite directions share the same virtual function table pointer and continue to share the same virtual function table pointer when x is further derived. Let us now proceed to the description of bidirectional layout for nonvirtual bases. Let us assume inductively that a directionality was assigned to all classes from which a class u inherits, and that all these classes were laid out already. The questions are then how should u be laid out, what kind of sharing of VPTRs will u have with its parents, and what should X.sup.(u) be. The following procedure (hereinafter referred to as "bidirectional-layout") answers these questions, by detailing how the nonvirtual bases of u are married together in u.
[1] Procedure bidirectional-layout (Node u)
[2] Begin
[3] Let V .rarw. {v.vertline.u {character pullout} v {character
pullout} u {character pullout} v}
[4] Case .vertline.V.vertline. of
[5] 0: //u is a root
[6] assign-initial-directionality (u)
[7] 1://u has exactly one parent
[8] Let v be the single parent of u
[9] If .chi..sup.(v) = none then
[10] assign-initial-directionality(u)
[11] else
[12] .chi..sup.(u) .rarw. .chi..sup.(v)
[13] Share a VPTR with v.
[14] fi
[15] 2: //u has exactly two parents
[16] Let v.sub.1 and v.sub.2 be the two parents of u
[17] If .chi..sup.(v1) = .chi..sup.(v2) =none then
[18] assign-initial-directionality(u)
[19] else if .chi..sup.(v1) = .chi..sup.(v2) then
// a VPTR is saved in the layout of u
[20] .chi..sup.(u) .rarw. mixed
[21] Marry v.sub.1 and v.sub.2
[22] Share VPTR with v.sub.1 //wlog could share with v.sub.2
[23] else if exists i, i = 1, 2 s.t. v.sub.i is directed
then
[24] .chi..sup.(u) .rarw. .chi..sup.v.sub.i.sup.)
[25] Share a VPTR with v.sub.i
[26] else
// one parent is mixed, the other is mixed or none
[27] Let v.sub.i be a parent of u that is mixed
[28] .chi..sup.(u) .rarw. mixed
[29] Share a VPTR with v.sub.i
[30] fi
[31] Otherwise: //u has more than two parents
[32] pairup(u)
[33] esac
[34] end
FIG. 34 is a flow chart of a method for laying out a subobject u in an object layout chart corresponding to an object class. The chart includes subobjects of the object class and virtual function table pointers for pointing to virtual function tables of the subobjects. It is determined if a set V is empty, the set V comprising subobjects that have a fixed offset with respect to the subobject u and that are directly inherited from the subobject u (step 3402). If the set V is empty, then an initial directionality is assigned to the subobject u (step 3404). If the set V is determined to not be empty at step 3402, then it is determined if the set V has only one member (step 3406). If the set V has only the one member, then it is determined if a directionality of a subobject v in the set V is unassigned (step 3408). In this case, the subobject v is a single parent subobject of the subobject u. If the directionality of the subobject v is unassigned, then an initial directionality is assigned to the subobject u (step 3410). On the other hand, if the directionality of the subobject v is assigned, then the directionality of the subobject v is assigned to the subobject u and a virtual function table pointer is shared between the subobjects v and u (step 3412). If the set V is determined to not have only the one member at step 3406, then it is determined if the set V has only two members (step 3414). If the set V has only the two members, then it determined if directionalities of subobjects v1 and v2 in the set V are unassigned (step 3416). In this case, the subobjects v1 and v2 are both parent subobjects of the subobject u. If the directionalities of the subobjects v1 and v2 are assigned, then it is determined if the directionalities of the subobjects v1 and v2 are opposing (step 3418). Opposing is intended to mean that one of the subobjects v1 and v2 is positive and the other is negative. If the directionalities of the subobjects v1 and v2 are not opposing, then it is determined if any of the subobjects v1 and v2 are directed (step 3420). Directed is intended to mean either positive or negative, but not mixed. If any of the subobjects v1 and v2 are not directed, then the directionality of the subobject u is assigned as mixed (step 3422) and a virtual function table pointer is shared between the subobject u and any one of the subobjects v1 and v2 that is mixed (step 3424). In this case, one parent of u has mixed directionality. If the directionalities of the subobjects v1 and v2 in the set V are determined to be unassigned at step 3416, then an initial directionality is assigned to the subobject u (step 3426). If the directionalities of the subobjects v1 and v2 are determined to be opposing at step 3418, then the directionality of the subobject u is assigned as mixed (step 3428). Moreover, the subobject v1 is married to the subobject v2 and a virtual function table pointer is shared between the subobject u and one of the subobjects v1 and v2 (step 3430). If any of the subobjects v1 and v2 are determined to be directed at step 3420, then the directionality of any of the directed subobjects is assigned to the subobject u (step 3432). Moreover, a virtual function table pointer is shared between the subobject u and the subobject v1 or v2 that is directed (step 3434). If it is determined that the set V does not have only the two members at step 3414, then the procedure pairup is performed (step 3436). The method is terminated (step 3438), upon performing any one of steps 3404, 3410, 3412, 3424, 3426, 3430, 3434, and 3436. The cases in procedure bidirectional-layout in which u has no parents, only one parent, or two parents which both have the same directionality are rather pedestrian. The case where X.sup.(v1) =-X.sup.(v2) is the most interesting one since it is the only case in which a VPTR is saved. Note that the procedure favors a none directionality for u. However, as in the vast majority of cases, this is not possible, it tries to make u directed, in order to leave open future optimization opportunities. Class u is assigned a mixed directionality only if there is no other choice. When u has more than two parents, the above procedure bidirectional-layout calls the following procedure hereinafter referred to as "pairup". Procedure pairup simply generalizes the breakdown into different cases in bidirectional-layout when u has two parents. In one embodiment of the present invention, the procedure pairup could be used to completely replace the procedure bidirectional-layout.
[1] Procedure pairup(Node n)
[2] Begin
[3] Let V .rarw. {v.vertline.n {character pullout} v
{character pullout} n {character pullout} v}
[4] Let V.sup.+ .rarw. {v .di-elect cons.
V.vertline..chi..sup.(v) = positive}
[5] Let V.sup.- .rarw. {{character pullout}v .di-elect
cons. V.vertline..chi..sup.(v) negative}
[6] Let V.degree. .rarw. {v .di-elect cons.
V.vertline..chi..sup.(v) = none}
[7] Let V* .rarw. {v .di-elect cons.
V.vertline..chi..sup.(v) mixed}
Marry pairs of opposite direction bases that are not yet married.
[8] While V.sup.+ .noteq. .O slashed. {character pullout}
V.sup.- .noteq. .O slashed. do
[9] Select v.sub.1 .di-elect cons. V.sup.+, .sub.v2
.di-elect cons.V.sup.-
[10] Marry v.sub.1 and v.sub.2
[11] V.sup.+ .rarw.V.sup.+ - v.sub.1
[12] V.sup.- .rarw. V.sup.- -v.sub.2
[13] od
Assign directionality to n and determine sharing
[14] If V.sup.+ .noteq. .O slashed. then
[15] .chi..sup.(n) .rarw. positive
[16] Share a VPTR with v .di-elect cons. V.sup.+
[17] else if V.sup.- .noteq. .O slashed. then
[18] .chi..sup.(n) .rarw. negative
[19] Share a VPTR with v .di-elect cons.V.sup.-
[20] else if V* .noteq. .O slashed. then
[21] .chi..sup.(n) .rarw. mixed
[22] Share a VPTR with v .di-elect cons. V*
[23] else if v .di-elect cons. V {character pullout}
.chi..sup.(v) = positive then
[24] .chi..sup.(n) .rarw. mixed
[25] Share a VPTR with v
[26] else //only V.degree. .noteq. .O slashed.
[27] assign-initial-directionality(n)
[28] fi
[29] end
FIG. 35 is a flow chart of a method for laying out a subobject u in an object layout chart corresponding to an object class according to another embodiment of the present invention. The chart includes subobjects of the object class and virtual function table pointers for pointing to virtual function tables of the subobjects. It is determined if one of sets V+ and V- is empty (step 3502). The set V+ includes subobjects in a set V having positive directionality. The set V- includes subobjects in the set V having negative directionality. The set V includes subobjects that have a fixed offset with respect to the subobject u and are directly inherited from the subobject u. If both of the sets V+ and V- are not empty, then a subobject v1 is removed from the set V+ (step 3504), and a subobject v2 is removed from the set V- (step 3506). The subobject v1 is married to the subobject v2 (i.e., the subobject v1 and the subobject v2 share a virtual function table pointer) (step 3508), and a return is made to the step of determining if one of the sets V+ and V- is empty (step 3510). On the other hand, if one of the sets V+ and V- is empty (as determined at step 3502), then it is determined if the set V+ is empty (3512). If the set V+ is not empty, then a positive directionality is assigned to the subobject u and a virtual function table pointer is shared between the subobject u and a subobject v in the set V+ (step 3514). On the other hand, if the set V+ is empty, then it is determined if the set V- is empty (step 3516). If the set V- is not empty, then a negative directionality is assigned to the subobject u and a virtual function table pointer is shared between the subobject u and a subobject v- in the set V- (step 3518). On the other hand, if the set V- is empty, then it is determined if a set V* is empty (step 3520). The set V* includes subobjects in the set V having mixed directionality. If the set V* is not empty, then a mixed directionality is assigned to the subobject u and a virtual function table pointer is shared between the subobject u and a subobject v* in the set V* (step 3522). If the set V* is empty, then it is determined whether there exists a subobject v in the set V having a positive directionality (step 3524). If so, then a mixed directionality is assigned to the subobject u and a VPTR is shared between the subobjects u and v (step 3526). Otherwise, an initial directionality is assigned to the subobject u (step 3528). The method is terminated upon performing any one of steps 3514, 3518, 3522, 3526, and 3528 (step 3530). FIG. 36 is a flow chart of an overall method in which either of the procedures bidirectional layout or pairup is performed. A topological ordering is assigned to all nodes in a set V, the set V including subobjects in the chart (step 3602). The nodes of a directed graph are topologically ordered if each node has a number whose value is greater than the values of its parents' numbers. It is then determined if the set V is empty (step 3604). If the set V is empty, then the method is terminated (step 3608). On the other hand, if the set V is not empty, then a node u is removed from the set V in topological order (step 3610). Next, either the procedure bidirectional-layout or the procedure pairup is performed (step 3612). Then, the procedure ephemeral marriage is performed (step 3613). A return is then made to the step of determining whether the set V is empty (i.e., step 3604) (step 3614). Up to now, the marrying of subobjects that are inherited and have opposite directionalities has been described. However, the above techniques also apply to subobjects that are fields. Consider a class A that has two fields F1 and F2, such that F1 has type class B and F2 has type class C. If the directionality of class B and class C are opposite, then F1 and F2 can be married and share a virtual function table pointer in an A object. This sharing is persistent; that is, F1 and F2 will continue to share a virtual functional table pointer when class A is further derived. Finally, if classes A and B have opposite directionality, then the run-time system could marry an object of type A and an object of type B together to share a virtual function table pointer when objects of these class types are allocated. To illustrate the potential reduction in space overhead that our techniques can achieve, we introduce, in FIGS. 37, 38 and 40, three canonical ways that multiple inheritance may be used. The canonical examples presented hereinafter and their variants are typical of the way that applications use multiple inheritance. Therefore, we expect that savings, similar to what we have found in our examples, will also be found in real applications. FIG. 37 is a diagram of a binary tree illustrating multiple inheritance of distinct classes. In the traditional memory layout scheme, an object of class c.sub.15 requires a total of 8 VPTRs. Each node can share its VPTRs with, at most, one base class. A lucky assignment of directionalities to classes c.sub.1, . . . , c.sub.8 would reduce that number to as little as 4, which represents a 50% reduction in the compiler generated fields. If all inheritance links in FIG. 37 were virtual then the traditional model requires 49 compiler-generated fields: 15 VPTRs (one for each class as no sharing is allowed), and 34 VBPTRs (20 of which are inessential). Applying procedure eliminate-single-VI, followed by procedure bidirectional layout, may bring this number down to four. FIG. 38 is a diagram of an interface-implementation class hierarchy. The hierarchy represents a typical use of shared inheritance to model programming with interfaces. This is further described by L. Nackman and J. Barton, in "Base-Class Composition with Multiple Derivation and Virtual Bases", The C++ Conference, pp. 57-71, Cambridge, Mass., April 1994; and A. Myers, in "Bidirectional Object Layout for Separate Compilation", Proceedings of the 10.sup.th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOP-SLA '95), pp. 124-139, Austin, Tex., USA, Oct. 15-19 1995 (also published in ACM SIGPLAN Notices 30(10), October 1995). The inheritance hierarchy forms a ladder (in this instance with three steps) where there is an implementation inheritance of c.sub.1, c.sub.2 and c.sub.3 and an interface inheritance of i.sub.1, i.sub.2 and i3 such that the inheritance between implementations and interfaces, and interfaces and interfaces is virtual. The shared inheritance prevents an interface from being represented multiple times in an object of any derived class. In the traditional memory layout scheme, the overhead of multiple inheritance an object of class c.sub.3 requires is 10 compiler generated fields (4 VPTRs and 6 VBPTRs). The one inessential VBPTR points from i.sub.3 to i.sub.1. The methods of the present invention reduce this overhead by 80% to 2 compiler-generated fields: one VPTR and one VBPTR. The layout which achieves this is depicted in FIG. 39, which is an optimized layout of class c.sub.3 of FIG. 38. The layout was obtained by inlining i.sub.1 and i.sub.2, inlining i.sub.2 and i.sub.3, and assigning X.sup.(i1).rarw.negative, X.sup.(c1).rarw.positive. Incidentally, this layout is very similar to the bidirectional optimized layout proposed by A. Meyers for the Theta programming language in the above referenced article entitled "Bidirectional Object Layout for Separate Compilation". The differences are that the layout optimization techniques of the present invention are general purpose, whereas the semantics of multiple inheritance in Theta is that only single inheritance is allowed for implementation inheritance. Finally, FIG., 40 presents a portion of the class hierarchy of the C++ standard I/O library. In particular, FIG. 40 illustrates a double diamond class hierarchy. In the tradition memory layout scheme, an object of class c.sub.7 has 11 compiler-generated fields: 5 VPTRs and 6 VBPTRs. The two inessential VBPTRs point from c.sub.5 and c.sub.6 to c.sub.1. Applying our techniques we see that c.sub.7 can be laid out using only 4 compiler-generated fields. That is, 2 class table points and 2 virtual base pointers as illustrated in FIG. 41, which is a diagram illustrating an optimized layout of class c.sub.7 of FIG. 40. This 63% reduction is made possible by the following optimization steps: (1) Inlining c.sub.1 to c.sub.3. This step represents a saving of four compiler generated fields: one VPTR (due to the sharing of a VPTR between c.sub.3 and c.sub.1); one essential VPTR, pointing from c.sub.3 to c.sub.1 ; and two inessential VPTRs, pointing from c.sub.5 and c.sub.6 to c.sub.1. (2) Inlining c.sub.4 and c.sub.6. This step makes it possible to share a VPTR between c.sub.4 and c.sub.6, and to eliminate the essential VBPTR from c.sub.6 to c.sub.4 for a total saving of two compiler generated fields. Note that we could also have attributed to this step the saving of the two inessential VBPTRs, which were accounted for in the previous step. (3) Assigning directionalities to classes. In particular, we have assigned X.sup.(c1).rarw.positive, which imposed the same directionality on classes c.sub.3, c.sub.4, c.sub.6 and c.sub.7. We also assigned X.sup.(c2).rarw.negative and X.sup.(c5).rarw.negative. This made it possible to marry c.sub.2 and c.sub.3 in c.sub.4 thereby saving one more VPTR. The frugal object layout of FIG. 41 looks even more impressive when considering that it also implements the hierarchy in which all inheritance links in FIG. 40 are made virtual. In this hierarchy, which represents a typical use of shared inheritance for extendible frameworks, the tradition model requires 26 compiler-generated fields for an object of class c.sub.7 : 7 VPTRs, one for each class, and 19 VBPTRs, out of which 8 are essential. Table 2 summarizes the savings provided by the optimization techniques of the present invention in each of the major hierarchy examples used thus far herein.
TABLE 2
Example FIG. # a b
Diamond 5 5 2
Binary Tree 35 8 4
Virtual Binary Tree 35 49 4
Interface 36 10 2
Implementation
Double Diamond 38 11 4
Virtual Double 38 26 4
Diamond
Virtual n-Chain 10 n + (((n - 1) (n - 2))/2) 1
Virtual n-Double 21 n.sup.2 - n + 2 2n - 1
Chain
Our optimization techniques were based on two principal ideas: the inlining of virtual bases whose primary savings is in the number of VBPTRs, and bidirectional object layout which gives rise to a savings in the number of VPTRs. Inlining of virtual bases required preprocessing by elimination of transitive edges. Two procedures were provided above for inlining virtual bases according to the present invention. The simple procedure (simple-inline-VB) is guarantee | ||||||