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

*Answer all questions.*

*Time allowed: 2 hours*

*Total number of points: 100*

Any typechecking algorithm has to allow for the scope of variables,
in particular `let`

statements
and `if`

statements.

a) Give an example of a program which requires the type checker to keep track of variable scope.

b) Explain how a type checker deals with variable scope.

c) Discuss how your answer to part (b) will depend on whether the symbol table is stored mutably or immutably.

Java requires the byte code generated by a Java compiler to include type information.

C++ does not require the machine code generated by a C++ compiler to include type information.

a) Give one advantage and one disadvantage of Java's requirement.

b) Describe how this requirement might affect a Java 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 fact (n : Integer) : Integer { let tmp1 : Boolean = (n <= 1); if (tmp1) { return 1; } else { let tmp2 : Integer = n-1; let tmp3 : Integer = this.fact (tmp2); let tmp4 : Integer = tmp3 * n; return tmp4; } }

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 languages with multiple inheritance can use
*hashing* or *global graph coloring*
as the implementation of vtable layout.

a) Explain the hashing implementation of vtable layout.

b) Explain the global graph coloring implementation of vtable layout.

c) Give one advantage and one disadvantage of hashing over global graph coloring.

Some SML compilers use implicit boxing for their implementation of generics. Generic Java uses explicit boxing.

a) Describe the implicit boxing implementation of generics.

b) Describe the explicit boxing implementation of generics.

c) Give one advantage and one disadvantage of implicit boxing 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.