8 Compiler 3: Register Allocation (Original)

8.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.

8.2 Language Diagram

8.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 we already know all the variables that are in use and which other variables they are in conflict with. 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 represent nodes and there is an edge from each initial variable to each of the variables in the associated set. If there is an edge between any two nodes, then they are deemed to be 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.

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.

8.4 Conflict Analysis

We have just assumed that we know which variables are in conflict, so now we need to discharge that assumption and build conflict graphs.

To figure out when two variables are in conflict, we need to know which variables might be in-use on entry to an instruction. We therefore make an assumption that the input program is decorated with this information, called the undead-in sets. The undead-in sets are a list of sets of variables (undead ((aloc ...) ...)), with each set associated with an instruction in the program. Each undead set represents, on entry to the associated instruction, which variables are undead—variable that might not technically be alive, but aren’t conclusively proven to be dead. The first element of the list represents the set of variables that are undead when the first instruction begins executing, the second element represents the set of undead variables when the second instruction begins executing, and so on. Any variable that is referenced during an instruction is in conflict with every variable in the undead-in set associated with the instruction.

We design Undead-loc-lang to contain the undead-in sets for each instruction in a program. The language is essentially the same as Conflict-lang except for the info field.

Exercise 3: 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.

8.5 Undead Analysis

Again we have made an assumption so again we must discharge it. We must analysis a program to determine which variables are undead. The source language is the same Loc-locals-lang from last week.

To determine whether a variable is in the undead-in set, we analyze the program by looping over the instruction sequence backwards, starting with the last statement. The main part of the analysis takes an instruction and its undead-out set, the set of variables undead after that instruction executes. To start the process, we need a default undead-out set for the last instruction; the default undead-out set for Loc-locals-lang is empty. We analyze each instruction with its undead-out set and compute an undead-in set for the current instruction, which is the same as the undead-out set of the preceding instruction in the instruction sequence. 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. We use the output, the undead-in set, for the info field, and use it as the input for analyzing the previous instruction in the sequence in the next iteration of the loop.

The analysis on a particular instruction knows which variables are undead after that instruction, and computes which are undead before executing the instruction. If a variable is used in the instruction, it ought to be live (but we don’t actually know) and is added to the undead-in set—live is a subset of undead. If a variable is overwritten in the instruction, it is dead at that point and removed from the undead-in set.

Loc-locals-lang 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.

Exercise 4: 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.

8.6 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?