►Lecture 15: Register Allocation
Lecture 15: Register Allocation
1 Liveness analysis
1.1 Intuition
1.2 Warmup:   free variables
1.3 Liveness analysis for statement-based languages
1.4 Liveness analysis for expression-based languages
2 Register allocation
8.10

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
Because 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—and more refined—property from scope. This is a good thing! Because we’ve ANF’ed our code, every variable’s scope extends to the end of the overall expression1Except for variables defined in the branches of 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:

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:

(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:

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,

1Except for variables defined in the branches of if-expressions; we’ll come back to those!