## Lecture 15: Register Allocation

In our compilers so far, we’ve made freewheeling use of the stack to store all of our temporary variables. This has the advantage of being very simple to implement, but it is rather inefficient in both space and time. If we could utilize the general-purpose registers of our system more effectively, then we could access our variables faster (since register accesses are faster than memory accesses) and use less stack space (since fewer variables would be stored on the stack). So how can we do this?

The primary observation we need, which is so obvious it hardly seems noteworthy, is that if a value is going to be used again later, it must not be overwritten yet. Spinning that another way, if two variables are never needed simultaneously, then they can share the same location (whether that’s a stack slot or a register). So our first task is to give a workable definition of “needed simultaneously”, and expand that to a technique for allocating variables to locations that respects these requirements.

### 1` `Liveness analysis

#### 1.1` `Intuition

Consider the simple program fragment

```
let x = 44 * 100 in
let y = 10 in
let z = x + y in
z
```

`x`

and `y`

are both used in the definition of
`z`

, we say that the set of variables `{x, y}`

are
live at the point where we define `z`

. However, on the
last line, neither variable is live, because neither variable is used
again: liveness is a distinct—`if`

-expressions; we’ll come back to those!, so we might
naively think that all variables must be allocated to distinct
locations, and fortunately this is an overly-pessimistic
approximation.#### 1.2` `Warmup: free variables

As a warmup, we start with the notion of free variables, as we defined in Bound and free variables:

\(\mathit{FV}\)[

`x`

] = {x}\(\mathit{FV}\)[

`num`

] = {}\(\mathit{FV}\)[

`let x = e in b`

] = \(\mathit{FV}\)[`e`

] \(\cup\) (\(\mathit{FV}\)[`b`

] \(\setminus\) {x})\(\mathit{FV}\)[

`let rec x = e in b`

] = (\(\mathit{FV}\)[`e`

] \(\cup\) \(\mathit{FV}\)[`b`

]) \(\setminus\) {x}\(\mathit{FV}\)[

`if c: t else: e`

] = \(\mathit{FV}\)[`c`

] \(\cup\) \(\mathit{FV}\)[`t`

] \(\cup\) \(\mathit{FV}\)[`e`

]\(\mathit{FV}\)[

`lam(x): b`

] = \(\mathit{FV}\)[`b`

] \(\setminus\) {x}...

Do Now!

Finish defining the free-variables function for the remaining expression forms in our language.

#### 1.3` `Liveness analysis for statement-based languages

To formulate the standard notion of liveness, we’ll define a set of data-flow equations, which will define a set of five mutually-recursive functions:

\(\mathit{LIVE}_{in}\)[

`s`

] describes the set of variables that are live at the entrance to statement`s`

.\(\mathit{LIVE}_{out}\)[

`s`

] describes the set of variables that are live at the end of sttement`s`

.\(\mathit{DEF}\)[

`s`

] describes the set of variables that are defined by statement`s`

.\(\mathit{USE}\)[

`s`

] describes the set of variables that are used by statement`s`

.\(\mathit{Succ}\)[

`s`

] describes all the statements that can follow statement`s`

.

(The successor function \(\mathit{Succ}\)[\(\cdot\)] is needed because in languages with loops, there may be more than one statement that follows a given statement.)

We can define the other four functions as follows:

\(\mathit{LIVE}_{in}\)[

`s`

] = \(\mathit{USE}\)[`s`

] \(\cup\) (\(\mathit{LIVE}_{out}\)[`s`

] \(\setminus\) \(\mathit{DEF}\)[`s`

]). In words, the variables that must be live at the start of`s`

are all the variables that are used by`s`

, as well as any variables that are live after`s`

, except for any that were defined (or assigned to) by`s`

.\(\mathit{DEF}\)[

`x := e`

] = {`x`

}. An assignment to a variable defines that variable.\(\mathit{USE}\)[

`x := e`

] = \(\mathit{FV}\)[`e`

]. An assignment to a variable uses all the variables on the right-hand side of the assignment.\(\mathit{LIVE}_{out}\)[

`s`

] = \(\bigcup_{t \in Succ[s]}\) \(\mathit{LIVE}_{in}\)[`t`

]. In words, the live variables at the end of`s`

are all the possible live variables at the start of anything that comes after`s`

. If we substitute in this definition of \(\mathit{LIVE}_{out}\)[\(\cdot\)] into the definition of \(\mathit{LIVE}_{in}\)[\(\cdot\)], we can simplify these equations down to just three: live sets, def sets, and use sets.

Notice that the live-out set of a statement depends on the live-in set of its successors, and the live-in set of a statement depends on its live-out set. Accordingly, to figure out the live-in set at the beginning of the program, we have to start at the end of the program and work our way back to the start. Also note that in a typical statement-based langauge with loops, it’s possible that the successor of a statement might actually be one of its predecessors as well! Therefore to solve these equations, we have to iterate: starting from empty sets, we add variables to each of the sets as we go, repeatedly traversing the program until no more sets change. This process is guaranteed to terminate because we only ever add variables to sets, and there are a finite number of variables per program. We call such an analysis monotonic, and this monotonicity is a crucial property of this and many other data-flow analyses that are used in most compilers.

#### 1.4` `Liveness analysis for expression-based languages

However, we have an expression-based language, and moreover, we have already \(\alpha\)-renamed and ANFed our expressions. Accordingly, most of these equations simplify down further: every expression has at most one successor, variables never get reassigned, and no expression is its own (transitive) successor, so we do not need an iterative process to solve our data-flow equations – a single pass will suffice.

Note that we don’t much care about the \(\mathit{DEF}\)[\(\cdot\)] and \(\mathit{USE}\)[\(\cdot\)] functions; they’re just auxiliary functions to help us figure out the \(\mathit{LIVE}_{in}\)[\(\cdot\)] function. Accordingly, our focus will be on understanding that one function.

To figure out liveness for a let-binding, start with the statement-based equation for liveness above,

\(\mathit{LIVE}_{in}\)[`let x = e in b`

] = (\(\mathit{USE}\)[`let x = e in b`

] \(\cup\)
\(\mathit{LIVE}_{out}\)[`let x = e in b`

]) \(\setminus\)
\(\mathit{DEF}\)[`let x = e in b`

],

and modify it to account for the control
flow that’s implied by the let binding. In a sense, we want to
pretend we have `x := e; b`

, and compute liveness information
for the three pieces of this fragment, namely `b`

,
`e`

, and the entire let-binding itself. (Note that the
parentheses here are subtly different from the statement-based
equation above; this is because `b`

could use `x`

.)

\(\mathit{LIVE}_{in}\)[`b`

] is a recursive call to figuring
out liveness, and it will depend on \(\mathit{LIVE}_{out}\)[`b`

], i.e.,
whatever is live in whatever comes after this let-binding in our
overall program.

\(\mathit{LIVE}_{out}\)[`e`

] is the liveness of whatever comes after
`e`

, which is precisely \(\mathit{LIVE}_{in}\)[`b`

].

\(\mathit{LIVE}_{in}\)[`e`

] = \(\mathit{USE}\)[`e`

] \(\cup\)
\(\mathit{LIVE}_{out}\)[`e`

], since \(\mathit{DEF}\)[`e`

] is the empty set.

\(\mathit{USE}\)[`let x = e in b`

] = \(\mathit{USE}\)[`e`

] \(\cup\)
\(\mathit{USE}\)[`b`

], since those are the only subexpressions in this let-expression.

Finally, substitute all these definitions back in to the initial
equation for \(\mathit{LIVE}_{in}\)[`let x = e in b`

]. Since we’re going to
remove `x`

from the final result, it doesn’t matter whether we
include `x`

in \(\mathit{USE}\)[`b`

] or not (remember, we don’t
actually care about that function, except for its aid in computing the
live sets), so we can approximate \(\mathit{USE}\)[\(\cdot\)] with
free-variables, instead. Simplifying a bit, we get

\(\mathit{LIVE}_{in}\)[`let x = e in b`

] = (\(\mathit{FV}\)[`e`

] \(\cup\)
\(\mathit{FV}\)[`b`

] \(\cup\) \(\mathit{LIVE}_{out}\)[`b`

]) \(\setminus\)
{`x`

}.

This is almost the same as the equation for the free-variables
of a let-binding (compare with the equation earlier), but it is subtly
different: it includes the live-out variables of `b`

as well.
To illustrate the difference, consider the program

```
let x = true in
let y = if true: let b = 5 in ~hl:1:s~b~hl:1:e~ else: 6 in
~hl:2:s~x~hl:2:e~
```

Consider the highlighted `~hl:2:s~x~hl:2:e~`

. The live-in
variable set there is clearly {`x`

}.
Now consider the highlighted `~hl:1:s~b~hl:1:e~`

. The
free-variable set there is merely {`b`

}, but the
live-in variable set is {`b`

, `x`

}, because
`x`

is in the live-out set at that point.

Do Now!

Define the live-in function for an if-expression, and confirm that \(\mathit{LIVE}_{in}\)[

`~hl:2:s~x~hl:2:e~`

] propagates back to \(\mathit{LIVE}_{out}\)[`~hl:1:s~b~hl:1:e~`

], such that the live-in set there is indeed {`b`

,`x`

}.

To implement the live-in function in ML, we’ll need to design two functions:

```
let rec live_in_exp e live_out =
... compute the live-in set of e, assuming the live_out set is given...
let live_in_prog p = live_in_exp p []
```

The live-in function for an entire program, naturally, assumes that no variables are live after the program completes.

Exercise

Complete the definition of \(\mathit{LIVE}_{in}\)[\(\cdot\)] for the remaining expression forms. Be careful in how you handle lambdas!

### 2` `Register allocation

The key idea behind register allocation is to preserve the invariant that no two variables that are live at the same time can be allocated to the same location. To do this,

Compute the free variables \(\mathit{FV}\)[\(\cdot\)] for every expression in the program. This can be implemented by a function

`compute_free_vars : tag aexpr -> freevars aexpr`

, where`type freevars = string list`

is the type of sets of free-variables at each expression.Compute the live variables \(\mathit{LIVE}_{in}\)[\(\cdot\)] for every expression in the program. This can be implemented by a function

`compute_live_vars : freevars aexpr -> livevars aexpr`

, where`type livevars = string list`

is the type of sets of live-variables at each expression.Iterate over every function in the now-annotated program. For each function, iterate over every expression within it and build an interference graph whose nodes are variable names and whose edges are each pair of variables (

`x`

,`y`

) that appear in the same liveness set.Color the graphs, such that no edge contains two vertices of the same color.

Allocate locations, one per color.

1Except for variables defined in the branches of
`if`

-expressions; we’ll come back to those!