5.5 Register Allocation

5.5.1 Preface: What’s wrong with our language?

With Asm-lang v2, we introduced abstract locations to free the programmer from thinking about physical locations. Unfortunately, our implementation strategy has a severe limitation. While it’s simple and works, it’s extremely slow! Each and every variable assignment or reference accesses memory. While memory accesses have improved a lot compared to old computers due to caching, accessing memory are still orders of magnitude slower than accessing a register when our variable is not in the cache (and, in general, it won’t be in cache). Our compiler will have better performance if we help the machine out by using registers as much as possible.

Assigning variables to registers automatically is a non-trivial task. There’s a reason we started out by compiling to frame variables. There are infinitely many frame variables, but only 16 registers. To assign an abstract location a new frame variable is trivial—just pick a new one, there’s always new one. It’s a simple, systematic algorithm. To assign an abstract location to a register, however, we need to pick a register that isn’t currently in use. Since there’s only 16 registers, we very quickly run out of registers... unless we’re clever.

In general, being clever should be a last resort.

5.5.2 Optimizing Location Assignment

Our Asm-lang v2 compiler is already a trivial implementation of this algorithm. It assumes every abstract location might be needed forever, and is in conflict with every other abstract location. It doesn’t bother trying, and thus fails, to find a register for every abstract location, and so spills everything to the frame. But we want to optimize this process.

In general, we will never do a perfect job, due to Rice’s Theorem. Rice’s Theorem is a huge buzz kill. It tells us, formally, that we cannot decide anything "interesting" about any Turing-complete program. Formally, "interesting" is defined as any property that is not either true for every program, or false for every program. "Decide" means write a program that returns either true or false on all programs. The halting program is an instance of Rice’s Theorem. Rice’s Theorem tells us we will never be able to do a perfect job—not when optimizing, not when analyzing, not when asking whether two programs are equivalent, not when deciding which program is "better". We will only be able to make trade-offs. We want to try to do a better job. Well, not better—we can never decide what is "better" due to Rice’s Theorem. But we’d like to produce code that runs faster, and are willing to trade a more complex and slower compiler for it.

Since register allocation is a modification of our existing abstract location assignment strategy, we already have a source and target language in mind. We start from an existing language Asm-lang v2/locals, which is reproduced below:

This language, the output of uncover-locals, records which abstract locations are referenced in the program and thus need to be assigned physical locations. The register allocator takes over from here to perform that assignment.

And we use Asm-lang v2/assignments, reproduced below.

After this, our existing pass replace-locations should handle replacing abstract locations by the assigned physical locations.

An optimization should be seen as a drop-in replacement for some existing functionality, but one that performs "better" (for some definition of "better"). We will replace assign-homes with assign-homes-opt.

procedure (assign-homes-opt p) → nested-asm-lang-v2?

p : asm-lang-v2?

Compiles Asm-lang v2 to Nested-asm-lang v2, replacing each abstract location with a physical location. This version performs graph-colouring register allocation.

5.5.3 Undeadness Analysis

We begin the register allocation by figuring out which locations might still be needed after each instruction. This process is often called liveness analysis, but we refer to it as undeadness analysis for reasons we explain shortly.

A variable (either abstract location or physical location) with a particular value that definitely will be used is considered live, and any variable (with a particular value) that definitely won’t be used is considered dead. Recall that due to Rice’s Theorem, we know it’s generally impossible to decide whether a variable is dead or alive. This means that when writing an analysis, we must assume partial knowledge. The result is that we ignore liveness entirely.

Asm-lang v2/locals is a simple enough language that we can tell whether a variable is dead or alive. Later, when we add new instructions, we will modify the undead analysis and find variables that aren’t necessarily live or dead, and must be assumed to be undead. This is also necessary if we want to handle linking, or separate compilation.

We cannot in general decide the value of a variable at a given instruction. Instead, we focus on analyzing each assignment to a variable, which changes the value of the variable.

We assume that any variable that gets used, or might get used, might not be dead, i.e., we assume it is undead, and consider a variable dead only when we have conclusive proof—like witnessing an instruction driving a new value through its heart, er, storing a new value in its location.

To determine whether a variable is in the undead-out set for an instruction, we analyze the program by looping over the instruction sequence backwards, starting with the last statement. We don’t need to analyze the program backwards, but it’s faster. The loop takes an instruction and its undead-out set. We analyze each instruction with its undead-out set and compute an undead-in set for the instruction, which is the same as the undead-out set of the preceding instruction. That is, the undead-in set for an instruction s_i is the undead-out set for the instruction s_{i-1} in the program.

Each iteration of the loop performs the following analysis on a particular instruction. We start by assuming the undead-in set is the same as the undead-out set, then update it depending on what happens in the instruction. If a variable is used in the instruction, it ought to be live—we don’t actually know, since that instruction’s result itself might not be used, but the variable is at least acting like its live—and is added to the undead-in set. If a variable is assigned, i.e., its value is overwritten, in the instruction, it is definitely dead at that point, and we remove it from the undead-in set.

To start the loop, this algorithm requires a default undead-out set for the last instruction; the default undead-out set for Asm-lang v2/locals is empty. In general, the default set may not be empty, because we may assume that some values are live after the program. For example, in Paren-x64 v1, we assume rax is live out.

This algorithm creates the undead-out sets for each instruction so that later passes can associate each instruction with its undead-out set. There are many ways to associate the undead-out sets with instructions. A simple way is to create a data structure that maps each set to an instruction.

You’ll need to design the template for traversing tail and effect trees simultaneously with an undead-set tree yourself.

To describe the output of the analysis, we define a new administrative language. We collect the undead-set tree a new info field. Below, we define Asm-lang v2/undead. The only change compared to Asm-lang v2/locals is in the info field, so we typeset the difference in the info field.

procedure (undead-analysis p) → asm-lang-v2/undead?

p : asm-lang-v2/locals?

Performs undeadness analysis, decorating the program with undead-set tree. Only the info field of the program is modified.

Examples:

> (undead-analysis    '(module ((locals (x.1)))       (begin         (set! x.1 42)         (halt x.1))))

'(module    ((locals (x.1)) (undead-out ((x.1) ())))    (begin (set! x.1 42) (halt x.1)))

> (undead-analysis    '(module ((locals (v.1 w.2 x.3 y.4 z.5 t.6 p.1)))       (begin         (set! v.1 1)         (set! w.2 46)         (set! x.3 v.1)         (set! p.1 7)         (set! x.3 (+ x.3 p.1))         (set! y.4 x.3)         (set! p.1 4)         (set! y.4 (+ y.4 p.1))         (set! z.5 x.3)         (set! z.5 (+ z.5 w.2))         (set! t.6 y.4)         (set! p.1 -1)         (set! t.6 (* t.6 p.1))         (set! z.5 (+ z.5 t.6))         (halt z.5))))

'(module    ((locals (v.1 w.2 x.3 y.4 z.5 t.6 p.1))     (undead-out      ((v.1)       (v.1 w.2)       (x.3 w.2)       (p.1 x.3 w.2)       (x.3 w.2)       (y.4 x.3 w.2)       (p.1 y.4 x.3 w.2)       (x.3 w.2 y.4)       (w.2 z.5 y.4)       (y.4 z.5)       (t.6 z.5)       (p.1 t.6 z.5)       (t.6 z.5)       (z.5)       ())))    (begin      (set! v.1 1)      (set! w.2 46)      (set! x.3 v.1)      (set! p.1 7)      (set! x.3 (+ x.3 p.1))      (set! y.4 x.3)      (set! p.1 4)      (set! y.4 (+ y.4 p.1))      (set! z.5 x.3)      (set! z.5 (+ z.5 w.2))      (set! t.6 y.4)      (set! p.1 -1)      (set! t.6 (* t.6 p.1))      (set! z.5 (+ z.5 t.6))      (halt z.5)))

In a realistic compiler, unused variables should be removed be an optimization.

5.5.4 Conflict Analysis

To assign abstract locations to physical locations efficiently, we need to know when any two variables are in conflict, i.e., cannot be assigned to the same physical location because different values might be in those variables at the same time.

We start by defining what a conflict is precisely.

True Definition of Conflict: Any variable that gets a new value during an instruction is in conflict with every variable that (1) has a different value at the same time and (2) will still be used after that instruction.

Unfortunately, due to Rice’s Theorem, we cannot decide either property. We cannot figure out the value of every variable before run time; if we could, compiling would not be necessary. We also do not know which variables are live, only which are undead. Therefore, we can only approximate conflicts.

To approximate conflicts, we ignore values, and once more focus on assignments to variables. An assignment to the variable means the it might take on a new value that might be different from the value of any variable which might be live at that point. We have already approximated liveness via undead-out sets, so what remains is to approximate when a variable takes on a new value. Below, we describe how to approximate conflcits and slightly refine these criteria.

We represent conflicts in a data structure called a conflict graph. Interpreted as an undirected graph, the variables are represented as nodes (also known as vertexes), and conflicts between variables are represented as an edge from the variable to each of the variables in the associated set of conflicts. If there is an edge between any two nodes, then they are in conflict. Interpreted as a dictionary, the conflict graph maps each variable to a set of variables with which it is in conflict.

We create a conflict graph from the undead-out sets as follows. Any variable that is defined during an instruction is in conflict with every variable (except itself) in the undead-out set associated with that instruction. For example, the variable x.1 is defined in (set! x.1 (+ x.1 x.2)), while the variables x.2 and x.1 are referenced. No variable can conflict with itself, since it always has the same value as itself. We approximate the values of variables by assuming each definition assigns a new unique value to the variable, and by assuming each variable in the undead-out set also has a unique value. This approximation tells us that x.1 cannot be assigned the same physical location as any other variable in the undead-out set. If x.2 is undead-out at this instruction, and we try to put x.1 in the same physical location as x.2, then the value of x.2 would be overwritten by the value of (+ x.1 x.2).

We can reduce the number of conflicts, and thus possibly fit more variables into registers, by observing that one instruction does tell us that two values will be the same. A move instruction, such as (set! x.1 x.2), is an instruction that simply defines the value of one variable to be that of another.

To implement conflict analysis, we design the language Asm-lang v2/conflicts to capture the conflict graph. We typeset the difference compared to Asm-lang v2/undead.

The info field is extended with a conflict graph, represented as an association list from a variable to undead-out sets.

As in Asm-lang v2/undead, the info field also contains a declaration of the abstract locations that may be used in the program, and (as usual) possibly other non-required but useful information.

To implement conflict analysis, we simultaneously traverse a program with its undead-set tree, and analyze each instruction according to the approxiate conflict definition above. We start with a graph that initially contains a node for every abstract location in the locals set, and extend the graph with conflicts as we discover them.

procedure (conflict-analysis p) → asm-lang-v2/conflicts?

p : asm-lang-v2/undead?

Decorates a program with its conflict graph.

Examples:

> (conflict-analysis    '(module ((locals (x.1))              (undead-out ((x.1) ())))       (begin         (set! x.1 42)         (halt x.1))))

'(module    ((locals (x.1)) (conflicts ((x.1 ()))))    (begin (set! x.1 42) (halt x.1)))

> (conflict-analysis    '(module ((locals (v.1 w.2 x.3 y.4 z.5 t.6 p.1))              (undead-out               ((v.1)                (v.1 w.2)                (w.2 x.3)                (p.1 w.2 x.3)                (w.2 x.3)                (y.4 w.2 x.3)                (p.1 y.4 w.2 x.3)                (y.4 w.2 x.3)                (z.5 y.4 w.2)                (z.5 y.4)                (t.6 z.5)                (t.6 z.5 p.1)                (t.6 z.5)                (z.5)                ())))       (begin         (set! v.1 1)         (set! w.2 46)         (set! x.3 v.1)         (set! p.1 7)         (set! x.3 (+ x.3 p.1))         (set! y.4 x.3)         (set! p.1 4)         (set! y.4 (+ y.4 p.1))         (set! z.5 x.3)         (set! z.5 (+ z.5 w.2))         (set! t.6 y.4)         (set! p.1 -1)         (set! t.6 (* t.6 p.1))         (set! z.5 (+ z.5 t.6))         (halt z.5))))

'(module    ((locals (v.1 w.2 x.3 y.4 z.5 t.6 p.1))     (conflicts      ((p.1 (z.5 t.6 y.4 x.3 w.2))       (t.6 (p.1 z.5))       (z.5 (p.1 t.6 w.2 y.4))       (y.4 (z.5 x.3 p.1 w.2))       (x.3 (y.4 p.1 w.2))       (w.2 (z.5 y.4 p.1 x.3 v.1))       (v.1 (w.2)))))    (begin      (set! v.1 1)      (set! w.2 46)      (set! x.3 v.1)      (set! p.1 7)      (set! x.3 (+ x.3 p.1))      (set! y.4 x.3)      (set! p.1 4)      (set! y.4 (+ y.4 p.1))      (set! z.5 x.3)      (set! z.5 (+ z.5 w.2))      (set! t.6 y.4)      (set! p.1 -1)      (set! t.6 (* t.6 p.1))      (set! z.5 (+ z.5 t.6))      (halt z.5)))

5.5.5 Register Allocation

Register allocation, as in the step that actually assigns abstract locations to physical locations, takes the set of abstract locations to assign homes, the conflict graph, and some set of assignable registers, and tries to assign the most abstract locations to registers. As usual, Rice’s Theorem tells us we’ll never be able to decide the maximal number of variables we can fit in registers. We’ll have to approximate.

We can simplify the implementation of this algorithm by separting it into two parts: first, sort all abstract locations in degree order, then assign each register in sorted order.

To describe the output of the register allocator, we reuse Asm-lang v2/assignments. Below, we typeset the changes compared to Asm-lang v2/conflicts. Note only the info field changes.

procedure (assign-registers p) → asm-lang-v2/assignments?

p : asm-lang-v2/conflicts

Performs graph-colouring register allocation. The pass attempts to fit each of the abstract location declared in the locals set into a register, and if one cannot be found, assigns it a frame variable instead.

Examples:

> (assign-registers    '(module ((locals (x.1))              (conflicts ((x.1 ()))))      (begin        (set! x.1 42)        (halt x.1))))

'(module    ((locals (x.1)) (conflicts ((x.1 ()))) (assignment ((x.1 r15))))    (begin (set! x.1 42) (halt x.1)))

> (parameterize ([current-assignable-registers '(r9)])     (assign-registers      '(module ((locals (x.1))                (conflicts ((x.1 ()))))        (begin          (set! x.1 42)          (halt x.1)))))

'(module    ((locals (x.1)) (conflicts ((x.1 ()))) (assignment ((x.1 r9))))    (begin (set! x.1 42) (halt x.1)))

> (parameterize ([current-assignable-registers '()])     (assign-registers      '(module ((locals (x.1))                (conflicts ((x.1 ()))))        (begin          (set! x.1 42)          (halt x.1)))))

'(module    ((locals (x.1)) (conflicts ((x.1 ()))) (assignment ((x.1 fv0))))    (begin (set! x.1 42) (halt x.1)))

> (assign-registers    '(module ((locals (v.1 w.2 x.3 y.4 z.5 t.6 p.1))              (conflicts               ((x.3 (z.5 p.1 y.4 v.1 w.2))                (w.2 (z.5 p.1 y.4 v.1 x.3))                (v.1 (w.2 x.3))                (y.4 (t.6 z.5 p.1 w.2 x.3))                (p.1 (t.6 z.5 y.4 w.2 x.3))                (z.5 (t.6 p.1 y.4 w.2 x.3))                (t.6 (z.5 p.1 y.4)))))       (begin         (set! v.1 1)         (set! w.2 46)         (set! x.3 v.1)         (set! p.1 7)         (set! x.3 (+ x.3 p.1))         (set! y.4 x.3)         (set! p.1 4)         (set! y.4 (+ y.4 p.1))         (set! z.5 x.3)         (set! z.5 (+ z.5 w.2))         (set! t.6 y.4)         (set! p.1 -1)         (set! t.6 (* t.6 p.1))         (set! z.5 (+ z.5 t.6))         (halt z.5))))

'(module    ((locals (v.1 w.2 x.3 y.4 z.5 t.6 p.1))     (conflicts      ((x.3 (z.5 p.1 y.4 v.1 w.2))       (w.2 (z.5 p.1 y.4 v.1 x.3))       (v.1 (w.2 x.3))       (y.4 (t.6 z.5 p.1 w.2 x.3))       (p.1 (t.6 z.5 y.4 w.2 x.3))       (z.5 (t.6 p.1 y.4 w.2 x.3))       (t.6 (z.5 p.1 y.4))))     (assignment      ((p.1 r15) (z.5 r14) (y.4 r13) (x.3 r9) (w.2 r8) (t.6 r9) (v.1 r15))))    (begin      (set! v.1 1)      (set! w.2 46)      (set! x.3 v.1)      (set! p.1 7)      (set! x.3 (+ x.3 p.1))      (set! y.4 x.3)      (set! p.1 4)      (set! y.4 (+ y.4 p.1))      (set! z.5 x.3)      (set! z.5 (+ z.5 w.2))      (set! t.6 y.4)      (set! p.1 -1)      (set! t.6 (* t.6 p.1))      (set! z.5 (+ z.5 t.6))      (halt z.5)))

5.5.6 Appendix: Compiler Overview

Figure 3: Overview of Register Allocation Optimization