## Assignment 6: Fer-de-lance: Register Allocation

#### Due: Sun 11/20 at 11:59pm

`git clone `

In this assignment, you’ll be implementing the core analysis and algorithm for register allocation.

This assignment will be a bit different than previous. Rather than adding a new language feature and being graded on your end-to-end compiler, you will be graded on an implementation of the core register allocation algorithms: liveness/conflict analysis and graph coloring.

We break the assignment down into two parts.

We need to analyze the code to determine which variables cannot be stored in the same register (liveness and conflict analysis)

We implement Chaitin’s algorithm for graph coloring to assign (or spilled stack slots) to all variables.

Optionally, you can incorporate this information into your compiler to have a more efficient implementation.

### 1` `Analysis

First need to figure out which variables conflict with each other. We break this down into liveness analysis, which determines when a variable’s value is needed and conflict analysis which determines which variables are live at the same time with possibly different values.

We implement liveness analysis as a compiler pass, annotating all expressions with the free variables live at that point. It has the following type

```
pub fn liveness<Ann>(
e: &SeqExp<Ann>,
params: &HashSet<String>,
live_out: HashSet<String>,
) -> SeqExp<HashSet<String>>
```

The parameter set `params`

are the parameters in the current
function body. You need this information because you should not treat
these parameters as part of your liveness analysis since parameters
are passed into fixed slots on the stack. Next, `live_out`

is the
set of variables whose values are needed after running the expression
`e`

. The output of this function is an expression with the same
structure as `e`

but with each sub-expression annotated with the
variables that are live at that point. So for example, if the input expression were

`let x = 3 in f(x, y, a)`

where `a`

is a parameter and `y`

is not, then
your liveness function would return the expression annotated as
follows given an empty `live_out`

set:

```
Let { ann: {"f, y"}, // Live variables *before* the Let is performed
var: "x",
bound_exp: Imm(Num(3), {"f, y"}),
body: CallClosure {
ann: {"f", "x", "y"} // Live variables *before* the Call is made
fun: Var("f"),
args: [Var("x"), Var("y"), Var("a")],
},
}
```

The inner `CallClosure`

has all of `f`

, `x`

and
`y`

live because `f`

is used as the function and `x`

and `y`

are used as arguments. `a`

is not live since it is a
parameter. The `Let`

outer only has `f`

and `y`

live in
it because the `x`

is defined in the let.

The liveness function returns a `SeqExp<HashSet<String>>`

, an
expression annotated with its liveness information. To extract the
liveness information for an expression you can use the `.ann()`

method implemented in `syntax.rs`

.

We implement this as a compiler pass because we can use this liveness information later to optimize how many registers we save.

Next, given our liveness analysis, we go through and determine what
the conflicts are. This generates a graph that will be the
input to our graph coloring function.
The `conflicts`

function has the following type.

`conflicts(e: &SeqExp<HashSet<String>>) -> Graph<String>`

`Ann`

that you
will ignore here (it is used to pass unique numbers later).The output of the conflicts function is a `Graph<String>`

representing the conflicts between variables. The `Graph`

datatype is provided in the `graph.rs`

module, and represents an
undirected graph. Each method is documented with a brief
description. Note that other than `Graph::new()`

, these are all
methods on a graph, so for instance to insert a vertex `v`

into a
graph `g`

using the `insert_vertex`

method, you invoke the
method as `g.insert_vertex(v)`

.

Make sure you insert all let-bound variables into the graph you produce so that they are all assigned a register, even if they have no conflicts. To ensure that you don’t put any parameters in your output graph, add the variables into your output when you see them bound by a let, rather than when they are used.

By Rice’s theorem, perfect liveness/conflict analysis is impossible. However, you should make an effort to be somewhat precise. In particular, you will not receive full credit by just saying all variables conflict with each other. In particular your conflict analysis handles examples like the following one from lecture:

```
def f(h, a, b):
let x = a + b in
let y = x in
h(x, y)
end
```

In this case, there are two local variables, `x`

and
`y`

in the function, and they do not conflict with each
other. Your conflict analysis should be able to tell that there is no
conflict between `x`

and `y`

to receive full
credit.

### 2` `Graph Coloring

#### 2.1` `Coloring

Now that we have our conflict graph, we attempt to assign each vertex a "color", i.e., register. We implement this with the following signature:

```
fn allocate_registers(
conflicts: Graph<String>,
registers: &[Reg],
) -> HashMap<String, VarLocation>
```

You are given the register interference graph and a slice of registers
to be used in register allocation and you should return a HashMap
mapping the variables in the input graph to a `VarLocation`

,
which is either a register `VarLocation::Reg(r)`

or a stack
offset `VarLocation::Spill(i)`

.

We parameterize the graph coloring algorithm by which registers we are using so that we can test spilling more easily by passing in fewer registers. You may find this useful for incrementally implementing your use of registers as well1For instance you might first use no registers, then use only caller-save registers and finally both caller-save and callee-save registers.

### 3` `List of Deliverables

your

`analysis.rs`

integration tests (

`tests/examples.rs`

)your test input programs (

`examples/*`

files)

### 4` `Grading Standards

This assignment will be solely autograded. There are two kinds of tests:

Liveness/Conflict analysis tests to test the soundness and precision of your analyses

Graph coloring tests that ensure you always give valid register/spill assignments and don’t spill excessively

### 5` `Submission

Wait! Please read the assignment again and verify that you have not forgotten anything!

Please submit your homework to gradescope by the above deadline.1For instance you might first use no registers, then use only caller-save registers and finally both caller-save and callee-save registers