2.4 Milestone 3: Register Allocation
2.4.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.
You can use the interrogator to get limited access to the reference solution: https://soft.vub.ac.be/compilers/interrogator?an=a3.
2.4.1.1 Learning Objectives
2.4.1.2 Assignment Checklist
Completely new passes
2.4.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.
2.4.3 Exercises
Exercise 1: Implement undead-analysis. You may want to see racket/set for working with sets.
For working with sets, you may want to use Sets
Exercise 2: Implement conflict-analysis. We provide a functional graph library, cpsc411/graph-lib, for working with the conflict graph.
Exercise 3: Implement assign-registers to perform graph-colouring register allocation with spilling. You should reference current-assignable-registers.
You may want to use sort.
It might be difficult to keep enough variables live at one time to test spilling. You should use parameterize and current-assignable-registers to test spilling.
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.
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.
Exercise 4: Implement assign-homes-opt, which has the same interface and performs the same function as assign-homes, but uses register allocation instead of assigning all abstract locations to frame variables.
assign-homes-opt should be a drop-in replacement for assign-homes.
Run your test suite and ensure you get the same outputs whether you use assign-homes or assign-homes-opt.