Review E: Efficiently implementing objects: Questions

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 {
    int x;

    A(int y) {
        x = y;
    }

    int f(int z) {
        return z * x;
    }
}
A's CIR format
0A_VMT
4x
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.)

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.

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.

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.

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 VMT
0Object_VMT
4A_f
8A_g

A's CIR format
0A_VMT
4a
8b

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?

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 x instanceof Container is true.

How can instanceof easily be supported using a VMT? (Just worry about using instanceof for classes — interfaces are another story.)

Review E: Efficiently implementing objects: Solutions

E.1.
A_f LDR R2, [R0, #4]
    MUL R0, R1, R2
    MOV PC, LR
E.2.

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.

E.3.
Hat's CIR format
0Hat_VMT
4dayPurchased
8size

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.

E.4.

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.]

E.5.

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.

E.6.

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.

E.7.

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.