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

*Answer all questions.*

*Time allowed: 2 hours*

*Total number of points: 100*

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.

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.

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.

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:

`eax`

: contains the`this`

parameter, and the function result`ebx`

: contains the first formal parameter`ecx`

: contains the second formal parameter`edx`

: contains the third formal parameter

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; } }

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 small-degree nodes: simplification of unhinted nodes; coalescing of hinted nodes (if this is possible, and will not produce a high-degree node); freezing of other hinted nodes.
- For high-degree nodes: aggressive coalescing of unhinted nodes (if this is possible); spilling of other unhinted nodes; coalescing of hinted nodes (if this is possible); freezing of other hinted nodes.

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

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.

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.