3.3 Iteration 2: Register Allocation
3.3.1 Assignment Summary
The goal of this assignment is to introduce (1) "optimizing" compilation (2) register allocation, a critically 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 via graph-colouring register allocation.
You can use the interrogator to get limited access to the reference solution: https://soft.vub.ac.be/compilers/interrogator?an=a3.
3.3.1.1 Checklist
Completely new passes
3.3.2 Reading
The reading for this week is Register Allocation. As usual, this milestone description links to the documentation for each exercise in the chapter for convenience, but you are responsible for the reading the entire chapter.
3.3.3 Assignment
Here are some useful notes:
For working with sets, you may want to use Sets, e.g. to implement undead-analysis.
We provide a functional graph library, cpsc411/graph-lib, for working with the conflict graph.
With many registers available for register allocation, it might be difficult to keep enough variables live at one time to test spilling. You should use parameterize and current-assignable-registers to reduce the set of registers that are available to the allocator.
The assignment info field has the same structure as the info datatype overall, i.e. it is a list of lists, where the first elements of the nested lists are the keys. This is different from regular association lists in Racket, which are lists of pairs. For the implementation of assignments, you can hence simple use the existing dictionary-like implementation of info cpsc411/info-lib.
For sorting nodes by degree you may want to use sort.
When debugging your register allocator, you might try comparing your allocator to the graph colouring algorithm provided by Racket Generic Graph Library. This provides an implementation of graph colouring, 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.
You may also choose to preserve additional info fields in the output of each pass, which could be used for more advanced testing. If you do, you can use check-assignment in your compiler pipeline to detect bugs in the register allocator.
To represent an arbitrary number of concrete locations (registers or frame variables) you can use Streams
- For this iteration we recommend implementing an helper function that takes care of graph coloring. It is slightly more general than required here, but will future proof your code for iteration 5. The parameters have the following intended meaning:
; graph-coloring
; colors : stream of registers and frame-variables
; initial-assignment : an existing assignment that maps some alocs to concrete locations
; alocs : a set of alocs to be assigned to registers. the intersection
; with the keys from initial-assignment is empty.
; graph : a conflict graph. the nodes of this graph contain the alocs
; to be defined, but can also contain additional nodes.
; -> returns a new assignment that extends the initial assignment
(define (graph-coloring [colors initial-assignment alocs graph])
...)
3.3.4 Validators and interpreters
No changes required.