CpS 450 Lecture Notes

Inheritance: Code Generation

The full Dream language supports inheritance, and polymorphic behavior. Consider the following classes:

class Parent is
  x: int
 
  initP(newX: int): Parent is
  begin
    x := newX
    initP := me
  end init

  foo() is
  begin
    out.writeint(x)
  end foo

  getX(): int is
  begin
    getX := x
  end getX

end Parent

class Child inherits from Parent is
  y: int

  initC(newX: int, newY: int): Child is
  begin
    initP(newX)
    y := newY
    initC := me
  end init

  getY(): int is
  begin
    getY := y
  end getY

  ~ overrides Parent's foo method
  foo() is
  begin
    out.writeint(getX()+y)
  end foo
end Child

Case Study: Inheritance and Polymorphism in C++

See /examples/codegen/polymorphism/polydemo.cpp and .s

Objects

When you instantiate Child, you must reserve space for all of Parent's instance variables, as well as all of Child's:

This means that when your semantic checker generates offsets for instance variables in the Child class, it must not start at 0: it must start after the parent's offsets.

Polymorphism 

Suppose the main program has a variable p: Parent. Dream allows the following:

p := (new Parent).initP(3)

and

p := (new Child).initC(3, 7)

Now, suppose we have the following:

p.foo()

The compiler has no way of knowing which foo( ) method should be called. That determination must be made at run-time, since if p refers to a Parent, it is Parent_foo that must be invoked, but if p refers to a Child, it is Child_foo that must be invoked.

Virtual Function Table

The standard solution to this problem is to construct virtual function tables. The compiler generates a VFT for each class in the program. A VFT begins with a pointer to the parent's VFT, followed by a list of function pointers:

Consider the following class hierarchy:

Oyd > A > B > C

The function table for a class C begins with function pointers for the methods in Oyd, followed by methods in A, followed by methods in B, followed by methods in C.

In the case of overriding, the parent's method pointer is replaced with the child's method pointer, and no new entry is added in the child's section for the overriden method.

Virtual Function Table Example

The compiler assigns an offset to each method defined in a class as follows:

• The base class methods are numbered beginning at 4

• The child class methods are numbered beginning at the next index available after the parent's methods.

For each class defined in the program, the compiler constructs a table of function pointers, with one entry for each method, like this:

Virtual Function Table for "Oyd" class

Virtual Function Table for "Parent" class

Virtual Function Table for "Child" class

Here's sample assembly code to define the necessary VFT's:

VFTOyd:
        .long   0
        .long   Oyd_toString

VFTParent:
        .long   VFTOyd
        .long   Oyd_toString
        .long   Parent_initP
        .long   Parent_foo
        .long   Parent_getX

VFTChild:
        .long   VFTParent
        .long   Oyd_toString
        .long   Parent_initP
        .long   Child_foo
        .long   Parent_getX
        .long   Child_initC
        .long   Child_getY

Changes to CodeGen for class instantiation

Consider the following expression:

new Child

Before inheritance, here's the code you would generate to instantiate a new instance:

; new Child
pushl $16
pushl $1         ; space for reserved area and 2 ints (x and y)
call calloc
addl $8, %esp    ; pop off parameter
pushl %eax       ; leave pointer returned from malloc on stack

now, you must additionally initialize a pointer to the object's VFT, with the following code:

movl $VFTChild, (%eax)