9 Compiler 3: Register Allocation (Corrected)

9.1 Assignment Summary

The goal of this assignment is to introduce (1) "optimizing" compilation (2) register allocation, perhaps the most important "optimization". In this assignment, you will replace the assign-homes pass with assign-homes-opt, a version that tries hard to put variables into registers instead of in the frame.

This assignment is due Friday January 31, 2020 at 11:59pm.

Assignment Checklist

You should find a new repository in your https://github.students.cs.ubc.ca account named a3_<team ids> with a code skeleton and a support library. You should complete the assignment in that git repository and push it to the GitHub Students instance.

You should first copy your solution to Compiler 2: Values-lang to x64 into the starter code provided. You can start from the code base of any of your team members.

If we patch the code skeleton or library after the release, the most recent version will be available here at a3-skeleton.rkt and a3-compiler-lib.rkt, and the functional graph library a3-graph-lib.rkt. The name of the skeleton is a3-skeleton.rkt to avoid accidentally overwriting your files, but your file in the Git repository should be named a3.rkt.

• Design and implement assign-registers, a compiler from Conflict-lang to Loc-assigned-lang.

• Design and implement conflict-analysis, a compiler from Undead-loc-lang to Conflict-lang.

• Design and implement undead-analysis, a compiler from Loc-locals-lang to Undead-loc-lang.

• Design and implement assign-homes-opt, a compiler from Loc-locals-lang to Loc-assigned-lang.

• Write a paragraph comparing two versions of your compiler: one with assign-homes and one with assign-homes-opt.

9.2 Language Diagram

9.3 Register Allocation

To assign abstract locations (variables) 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 they might both be used at the same time.

We start by designing a language, Conflict-lang, in which we assume someone has told us all the variables that are in use and which other variables they are in conflict with. This is all the information we need to complete register allocation in one step, so we can make progress by assuming we have it, and figuring out how to get it later. In Conflict-lang, the program is annotated with: (1) a list of local variables declarations, like in Loc-locals-lang, and (2) a conflict graph, represented as an association list from a variable to the set of variables with which it conflicts. The language is essentially the same as Loc-locals-lang except for the addition of the conflict graph to the info field.

The (conflicts ((aloc (aloc ...)) ...)) form in the info field represents a conflict graph. Interpreted as an undirected graph, the variables as represented as nodes (also known as vertexes), and conflicts between variables are represented as an edge the variable to each of the variables in the associated set. If there is an edge between any two nodes, then they are in conflict. Interpreted as a dictionary, this form maps each variable to a set of its conflicts.

As in the previous assignment, the info field also contains a declaration of the (locals (aloc ...)) abstract locations that may be used in the program, and (as usual) possibly other non-required but useful information.

The register assignment algorithm takes a Conflict-lang program and produces a Loc-assigned-lang program, annotating the program with an assignment of variables to physical locations in the info field.

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

Exercise 1: Design and implement the parameter? current-assignable-registers, which stores the list of k registers available to the register allocator.

The default should be all registers except the following. You may not use the register rax, since it is used to patch instructions, or rbp, since it contains the frame pointer.

Exercise 2: Design and implement the function assign-registers, which performs graph-coloring register allocation. The source language is Conflict-lang and the target language is Loc-assigned-lang. The pass should attempt to fit each of the variables declared in (locals (aloc ...)) into a free register, and if one cannot be found, should allocate the variable a fresh frame location.

We provide a functional graph library, a3-graph-lib.rkt, for working with the conflict graph.

This algorithm is somewhat tedious to write purely functionally. You may use a single mutable variable in your implementation. Use box, unbox, and set-box! for an idomatic way of using mutable variables in Racket.

It will be difficult to keep enough variables live at one time to test spilling. You should use parameterize and current-assignable-registers to test spilling.

When debugging your register allocator, you might try comparing your allocator to the graph coloring algorithm provided by Racket Generic Graph Library. This provides an implementation of graph coloring, although it does not perform spilling so it will not work in general. You cannot use this library in the implementation of your compiler; it may only be used for testing. Unfortunately, it uses a different representation of graphs, so you will need to write conversion procedures.

9.4 Undead and Conflict Analysis

For the next two passes, we switch perspectives and work top-down, as it’s difficult to explain them bottom-up.

We have just assumed that we know which variables are in conflict. This allowed us to make progress, but now now we need to discharge that assumption and build conflict graphs.

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 and (2) will still be used after that instruction.

Instead, we assume we have information about which variables might be used after an instruction. We ignore their values, and approximate conflicts. We compute a conflict graph by creating a conflict between every variable that gets a new value and every variable that might be live and might have a different value.

To figure out conflicts, we’ll need to figure out which variables might be live, or, are not definitely dead.

9.4.1 Undeadness Analysis

A variable (with a particular value) that definitely will be used is considered live, and variable (with a particular value) that definitely won’t be used is considered dead. Due to Rice’s Theorem, we know it’s generally impossible to tell whether a variable is dead or alive. This means that when writing an analysis, we must assume partial knowledge. We ignore liveness entirely.

We also cannot know the values of variables. Instead, we focus on assignments to variables, which change the values of variables.

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.

We collect the undead variables into sets. The undead-out set of an instruction is a set of (aloc ...). The set represents the variables that, after executing the instruction associated with the set, are undead.

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 making 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, but it’s 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 removed from the undead-in set.

To start the loop, we need a default undead-out set for the last instruction; the default undead-out set for Loc-locals-lang is empty. In general, the default set may not be empty, because we may have to assume that some values are live after the program. For example, in Paren-x64, we assume rax is live out.

The analysis collects the undead-out sets for each instructions 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.

We collect the undead info in a new info field. Below, we design Undead-loc-lang. The language is essentially the same as Conflict-lang except for the info field.

Exercise 3: Design and implement the function undead-analysis, which decorates a program with its list of undead-in sets; only the info field of the program is modified. The source language is Loc-locals-lang and the target language is Undead-loc-lang.

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

Challenge 1: Design and implement the function bury-dead, which removes assignments to unused abstract locations. The source language is Undead-loc-lang and the target language is Undead-loc-lang. (Optimizations often have the same source and target language.)

An assignment to a variable is dead if it is not in the undead-out set for the instruction.

9.4.2 Conflict Analysis

Now, we can figure out which variables are 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 must assume that all variables in the undead-out set have different values. We know that x.1 cannot be in the same physical location as any variables in the undead-out set. If x.2 is undead-out at this instruction, and we try to put x.1 and in the same physical location as x.2, then the value of x.2 would have been overwritten by the value of (+ x.1 x.2).

We can do slightly better, as one instruction does tell us that two values will be the same. A move instruction is an instruction that simply defines the value of one variables to be that of another, such as (set! x.1 x.2). We do not consider these two variables in conflicts. Even if x.2 is in the undead-out set, it’s value has not changed.

Exercise 4: Design and implement the function conflict-analysis, which decorates a program with its conflict graph. The source language is Undead-loc-lang and the target language is Conflict-lang program.

For working with sets, you may want to use Sets.

9.5 Optimizing assign-homes

We can now assign registers for all Loc-locals-lang programs from last week. By assigning variables to registers, patch-instructions will be able to produce much faster code because it will not need to move values to and from memory on every single instruction.

Exercise 5: Define assign-homes-opt, which can be used as a drop-in replacement for assign-homes. The interface is the same as assign-home: the source language is Loc-locals-lang and the target language is Loc-assigned-lang.

Run your test suite and ensure you get the same outputs whether you use assign-homes or assign-homes-opt.

Exercise 6: Create two versions of your compiler by defining two functions, compiler-a2 and compiler-a3. The source language should be Values-lang and the target should be x64-linux, represented as a string. compiler-a2 should use assign-homes, while compiler-a3 should use assign-home-opt instead. You should use parameterize and current-pass-list.

Write a paragraph comparing the two compilers. Consider the following questions:

• What are benefits and the disadvantages of each?

• Is one "optimal", and if so, in what sense?

• Try running the same programs compiled with each compiler. Are there any surprises?