CSC548 Midterm exam: Spring 2001 exam

This is a closed-book, closed-note exam.

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Question 1 (10 points)

One of the components of a type checker is the symbol table.

a) Explain the role of a symbol table in typechecking.

b) Give one advantage and one disadvantage of using an immutable representation of a symbol table rather than a mutable representation.

Question 2 (10 points)

Tiger uses a low-level intermediate language (close to machine code); Hobbes uses a high-level intermediate language (close to the source code).

Give one advantage and one disadvantage of using high-level intermediate languages over low-level intermediate languages.

Question 3 (10 points)

One difference between RISC and CISC architectures is the number of available registers.

Explain how the difference in numbers of registers effects the register allocation phase of a compiler.

Question 4 (20 points)

a) Calculate the interference graph for the following program. To do this, you should annotate the program with the live variables at each point, then translate the live variable sets into an interference graph.

b) Add precolored nodes for registers to the graph. There are four registers: eax, ebx, ecx and edx, which are all caller-save. The following calling convention is being used:

The code generator copies arguments into parameters in left-to-right order.

Arithmetic operations such as + and * are inlined, and are not method calls.

c) Add hints (move edges) to the graph. Do not include hints for arithmetic operations.

  method fib (n : Integer) : Integer {
    let tmp1 : Boolean = (n <= 1);
    if (tmp1) {
      return 1;
    } else {
      let tmp2 = n-1;
      let tmp3 = fib (tmp2);
      let tmp4 = n-2;
      let tmp5 = fib (tmp4);
      return tmp3 + tmp5;

Question 5 (20 points)

For the following interference graph with hints (move edges), show how a graph coloring algorithm can 3-color the graph (with colors A, B and C).

The algorithm should use the following steps:

For each step, explain which step you are using, and draw the transformed graph.

Question 5 cont.

Question 5 cont.

Question 6 (15 points)

Object oriented langauges with single inheritance can use prefixing as the implementation of vtable layout, but languages with multiple inheritance cannot.

a) Explain the prefixing implementation of vtable layout.

b) Give an example of why prefixing does not work in the presence of multiple inheritance.

c) Describe a technique for vtable layout which does work for multiple inheritance.

Question 7 (15 points)

C++ uses expansion for its implementation of generics. Generic Java uses explicit boxing.

a) Describe the expansion implementation of generics.

b) Describe the explicit boxing implementation of generics.

c) Give one advantage and one disadvantage of expansion over explicit boxing.


You can use this sheet as scrap paper.


You can use this sheet as scrap paper.


You can use this sheet as scrap paper.