The aim of this assignment is to add register spilling and optimise register usage by rearranging expressions in the misc compiler.

We propose to do so by implementing the Sethi-Ullman register allocator, but motivated students can choose another technique. The Sethi-Ullman allocator is described at page 262 of Appel's book, but our view of this algorithm is described in detail below, so you do not really need the book. We propose to split the implementation of this algorithm in three stages:

• first we will write code to compute (and attach to the tree) the need in registers of every node in a tree,
• then we will add register spilling, in order to make sure that the compiler never fails with an error stating that there are no more free registers, and
• finally we will try to decrease the number of registers needed to compile binary expressions by rearranging the evaluation of the operands in cases where a right-to-left evaluation order is better (currently the compiler always evaluates expressions from left to right).

As a starting point, we give you a working implementation of the misc compiler that you had to implement in Prof. Odersky's compilation course. This compiler should be similar to yours, with two exceptions:

• the logical operators (&, | and !) are not implemented as syntactic sugar using if, because that generates pretty bad code; instead, both the logical negation and conjunction are treated as operations and the disjunction is handled as syntactic sugar using De Morgan's laws (as suggested in last semester's course),
• the Code support class was slightly modified to use Java's java.util.BitSet class to remember the set of used registers, and a few methods were added to it.

The three stages of the project are described individually below. We suggest that you do them in the order given here. For every stage, we also give a few implementation hints which should hopefully help you, but feel free to ignore them if you have better ideas.

The aim of the first stage is to write code to compute the register need of every node in the tree. This need is stored directly in the tree as an integer, like the other attributes (position and type).

The register need of a subtree is defined as the number of registers which are needed to compile it. Of course, this need depends on the code generator that is being used, as different implementation techniques can lead to different needs for identical nodes. Therefore, the code which computes the need must precisely follow the code generator. As we will see below, object-oriented techniques can make this relatively easy.

A simple idea to compute the need of the various nodes of a tree is to run the code generator on the tree while pretending that infinitely many registers are available, and track register allocation and deallocation. For example, if during the compilation of some tree the method getRegister is called three times in a row, and then freeRegister is called also three times in a row, it is clear that the need of this node is three.

For your implementation, we suggest that you pursue this idea, by writing a subclass of Generator which performs this fake compilation. To track the register need of a node, one needs to execute some code before and after the compilation of every node. With our current architecture, this is done very easily, by redefining methods gen, genLoad and genCond.

The fake code generator also has to use a different version of class Code, which pretends that infinitely many registers are available (so that getRegister never fails). For efficiency reasons, we also suggest that this version of Code should not produce any code. The easiest way to define this special version of Code is to make a subclass of Code.

Register spilling is the action of temporarily moving the contents of registers on the stack, in order to increase the number of available registers. This is done by compilers in order to avoid running out of registers during code generation.

The Sethi-Ullman approach to spilling is quite simple: when generating code for a node n, we look at its register need. If that need is greater than the number of registers currently available K, we make sure that the situation is not worse for the children of n. That is, we ensure that all children of n get compiled with K available registers too.

One can get an intuition of why this works by making the following observations:

• the register need of a node is always at least as large as the maximum need of its children, i.e. the need is decreasing (albeit not strictly) as we move down the tree,
• when compiling a node, there are two possibilities: either its need is smaller or equal to the number of available registers, in which case everything is fine; or its need is greater, in which case the algorithm makes sure that the number of registers available to every children is the same as the number of registers available for the node itself.

To implement spilling, you have two options: either follow the above algorithm faithfully, or try to find an equivalent solution which can easily be introduced in the misc compiler.

Following the algorithm faithfully means identifying all the locations in the code where a register is used to hold the value of a left sub-tree while compiling a right sub-tree. In these locations, spilling code should be added to store the contents of this register if the need of the right sub-tree cannot be fulfilled with the currently available registers.

There is however an easier solution: as we have seen above, our implementation makes it easy to execute a piece of code just before (and/or after) compiling a node. We can use this trick to implement a slightly modified version of the Sethi-Ullman algorithm, as follows:

• just before producing the code for a node, we check if there are enough free registers to satisfy its need,
• if it is the case, we simply proceed,
• otherwise we check if there is an allocated register to spill, and if it is the case, we spill it,
• finally, once the code for the node has been generated, we un-spill the spilled register, if any.

The aim of the last stage is to try to lower the register usage of binary operations by rearranging them. The idea is very simple: when generating the code for a binary operation, start with the sub-tree which needs the greatest number of registers. This minimises the need of the whole operation because during the computation of the second operand, at least one register is needed to hold the value of the first operand.

This stage is best implemented by writing a visitor which looks at all binary operations and reorder the children if the right one has a greater need in registers than the left one. To perform this reordering, a simple idea is to add a boolean to the node Operations which says whether the children are swapped or not. We provide you with a class Traverser which makes it almost trivial to write this visitor.

When the children are not swapped, code generation works as usual. When they are, the code has to be generated so that the left subtree plays the role of the right operand, and vice versa. In most of the cases, this is trivially done.