Review E: Efficiently implementing objects
printable version
E: [1] [2] [3] [4] [5] [6] [7]
Problem E.1
Given the following class definition that the compiler translates
using the CIR format given at right, show how a compiler could translate
the f method into an ARM assembly language subroutine.
class A extends Object { |
|
A_f LDR R2, [R0, #4]
MUL R0, R1, R2
MOV PC, LR
Problem E.2
Compilers for object-oriented languages must support
polymorphism, where instances of a class may act as
instances of a superclass. For example, if Container is a parent class
of Suitcase, then a Container variable can reference
a Suitcase object.
Container bag = new Suitcase(100);What can the compiler do to support polymorphism? (Virtual methods are not part of this question.)
The compiler can ensure that the Suitcase CIR matches with
the Container CIR, by maintaining the same CIR format at its
beginning. Thus, any Container instance
variables would appear in the Suitcase CIR before
Suitcase-specific
instance variables. If the compiler does this placement, then to support
polymorphism it can simply copy the Suitcase CIR address into the
Container variable.
Problem E.3
Suppose the following two class definitions.
class Clothing {
int dayPurchased;
}
class Hat extends Clothing {
int size;
}
Diagram the contents of a Hat class instance record.
Explain the reasoning underlying each choice.
Hat's CIR format | |
| 0 | Hat_VMT |
| 4 | dayPurchased |
| 8 | size |
The first entry is a reference to the VMT, providing run-time
access to information about the type of the object, since at
run-time a Clothing variable may need this information.
The second entry needs to be the instance variable of
Clothing; this allows any Hat object to behave exactly like
a Clothing variable also.
The last entry, then, will be the instance variable for
Hat.
Problem E.4
C++ supports the notion of multiple inheritance, where a class may be a subclass of two other classes. Explain one of the challenges this presents for translating a C++ program using multiple inheritance into assembly language.
Because each memory allocation must be able to masquerade as an instance of its superclass for the purpose of methods the subclass has inherited, the easiest design for a subclass's CIR is to match the superclass's CIR at its beginning. However, the CIR cannot match multiple superclasses' CIRs, so C++ must find a more complex technique for allowing a superclass variable to reference an instance of a subclass.
[A similar problem arises in the context of VMT's: The subclass's VMT most naturally will match the superclass's VMT at its beginning.]
Problem E.5
Explain the primary motivation for introducing VMTs when compiling object-oriented programs, including an illustration of the problem using Java code. Explain how VMTs address the problem efficiently.
Suppose a program has a A variable named
x on which a method f is invoked:
x.f();Though x is an A variable, x might
actually reference an instance of a subclass of A —
let's call it B — that happens to override the f
method. Java specifies that the proper behavior in such a case
is to enter the f method defined in B.
This brings up a question of how to translate the above into code that quickly determines which subroutine should be entered. The compiler generates a VMT for each class tabulating the virtual methods, and an overridden method in a subclass will simply have the corresponding in the VMT reference the new method rather than the superclass's method. Each object has the first four bytes referencing the VMT of the class to which the object actually belongs. For each call to a virtual method, the compiler generates code to look into the object's VMT to determine where to find the beginning of the method.
Problem E.6
Consider the following Java class declaration, for which a compiler generates the VMT and CIR format given at right.
class A extends Object {
int a;
int b;
int f() {
return a;
}
int g() {
return f() + b;
}
}
A's VMT0 Object_VMT4 A_f8 A_g
A's CIR format0 A_VMT4 a8 b
Suppose the compiler were to translate A's g method as
follows.
A_g STMDB SP!, { R4, LR }
LDR R4, [R0, #8]
BL A_f
ADD R0, R0, R4
LDMIA SP!, { R4, LR }
MOV PC, LR
Why is this translation wrong?
Because the f method in A is virtual, a
subclass of A could
override it. If the subclass doesn't also override g, then code
calling the g method on an instance of this subclass would
use A's compiled g method. As translated
here this involves calling A's f method, but in this case
it should be calling the subclass's overriding f method
instead.
Problem E.7
Java includes an instanceof operator, which allows one
to test for the type of what a pointer references. For example,
suppose x is an Object variable, but x actually
references a Suitcase object. If Suitcase is a
subclass of Container, which is naturally a subclass of
Object, then the
is
x instanceof Containertrue.
How can instanceof easily be supported using a VMT? (Just
worry about using instanceof for classes — interfaces
are another story.)
We can make the first entry of each VMT reference the VMT of
the superclass. To determine whether an object is an instance of
a class, we can retrieve the VMT reference in its CIR and see
whether it matches the class in question; if not, we can look
into the VMT's first entry to reach its superclass's VMT and see
whether it matches the class. We continue up the list; once we
reach Object's VMT, we can conclude that the object
does not belong to the class in question.