PA6: Decaf Register Allocation
Objective
The goal of our semester-long project is to gain experience in compiler implementation by constructing a simple compiler.
The goal of this part of the project is to implement a bottom-up register allocation algorithm, preparing ILOC for conversion to machine code.
Introduction
The semester-long project for this course is to build a compiler for the Decaf language. In this project, you will implement register allocation for Decaf, which will be the fifth phase in our compiler. You will do this using a simple bottom-up greedy allocation algorithm.
You should download the project starter files from the "Files" tab in Canvas. The starter files include many new .java files as well as .class files representing compiled solutions.
Before you begin writing code, you should spend some time reading through all of the infrastructure files provided in the starter files. Our compiler this semester is a large project. Your solution will need to interface with several other classes, and you will need to thoroughly read through those classes to understand their interactions. Also, there are utility functions that you may find useful.
If you have questions about the existing code, please ask them on the Piazza forum (see the link on the sidebar in Canvas).
For this project, you will be implementing MyLocalRegisterAllocator
.
The task of this class is to modify an ILOCProgram
that uses an
arbitrary number of virtual registers, restricting it to only use a certain
number of registers (presumably matching the number of physical registers
available on the target architecture).
Assignment
WARNING: You should only proceed with actual development once you are SURE you understand exactly what your task is and how your code should interact with the rest of the system.
For this particular project, you should pay special attention to the following classes:
ILOCFunction
- This class has been extended to perform conversion to/from a control-flow graph (CFG) representation.ILOCBasicBlock
- Represents a basic block of ILOC instructions, which is the basic component of a CFG.RenumberRegistersAndLabels
- Re-numbers all registers and labels in an ILOC program for consistency; it also de-shares object instances, making latter modifications easier.
Implement the MyLocalRegisterAllocator
class. You should use a simple,
bottom-up register allocation routine similar to the one described in EAC
13.3.2 to convert the original (virtual) register IDs to a fewer number of
(physical) register IDs. Here is a slightly expanded version of the pseudocode
from Figure 13.1:
# perform register allocation for the given block allocateRegisters(block): for each physical register reg: name[reg] = -1 # contents of reg (virtual id or -1) next[reg] = INF # index of next reference (default: infinity) for each virtual register vr: loc[vr] = -1 # location of vr (physical id or BP offset or -1) spilled[vr] = false # is vr currently spilled? for each instruction i in block: for each read vr in i: # make sure operands are in registers reg = ensure(vr) replace vr with reg in i next[reg] = index of next reference of name[reg] if next[reg] == INF: free(reg) for each written vr in i: # open up a register for the result reg = allocate(vr) replace vr with reg in i next[reg] = index of next reference of name[reg] if next[reg] == INF: free(reg) if i is a CALL instruction: # spill any live registers at function calls for each physical register reg: if reg is currently holding a virtual register value: spill(reg) # make sure the given virtual register resides in a physical register ensure(vr): if vr is in a register and isn't spilled: reg = loc[vr] # no need to do anything else if vr is spilled: # re-load spilled value offset = loc[vr] reg = allocate(vr) emit code to load spilled value from BP+offset into reg spilled[vr] = false else: reg = allocate(vr) # otherwise, make space return reg # make sure there is a physical register available to use for the given virtual register allocate(vr): if there is an available physical register: reg = next free physical register # just allocate else: find physical register reg with highest next[reg] value spill(reg) # spill to make room loc[vr] = reg # establish binding name[reg] = vr return reg # free up the given physical register by spilling its value to the stack spill(reg): vr = name[reg] emit code to store spilled value from reg to BP+offset for new offset loc[vr] = offset spilled[vr] = true name[reg] = -1 next[reg] = INF # free up the given physical register (without spilling it) free(reg): if name[reg] != -1: loc[name[reg]] = -1 name[reg] = -1 next[reg] = INF
This routine will work on a single basic block at a time. Normally, this would not yield a globally-valid allocation without taking into account liveness analysis. However, because we have taken pains to emit code in SSA form and to load/store variables every time they are used, no virtual registers will be live at the entrance and exit of each basic block. Thus, this local register allocation scheme works globally for our purposes.
As an additional benefit, we can now add a mechanism that finally will make
recursive functions work properly. Previously, there was no way to avoid having
recursive calls clobber the registers from concurrent invocations. Now, we can
spill all live registers whenever we CALL
a function. This is
conservative and is not necessary in all cases but again it works nicely for
our purposes, allowing us to use recursive functions without directly modifying
the ILOC interpreter.
The revised DecafCompiler
for this project now calls the
RenumberRegistersAndLabels
routine to de-share
ILOCOperand
instances. This is important so that the register
allocator can make changes to a single operand without immediately changing any
other locations where that operand may be referenced. After that, it calls the
register allocator, telling it to reduce the number of registers down to four
(4). This number is perhaps a bit overly restrictive (most architectures have at
least eight physical general-purpose registers), but it makes testing and
debugging easier.
NOTE: The ILOC generation code from the last project generated virtual register IDs starting at 1; however, for the purposes of this project it is more convenient to start at 0. Thus, reducing to four registers means reducing to r0-r3, as can be seen in the example below.
Sample Input
add: loadAI [bp+8] => r1 loadAI [bp+12] => r2 add r1, r2 => r3 i2i r3 => ret jump l1 // return (x+y) l1: return main: loadI 3 => r4 storeAI r4 => [bp-4] // a = 3 loadAI [bp-4] => r5 loadI 2 => r6 param r6 param r5 call add i2i ret => r7 i2i r7 => ret jump l2 // return add(a, 2) l2: return
Sample Output
add: loadAI [bp+8] => r0 loadAI [bp+12] => r1 add r0, r1 => r0 i2i r0 => ret jump l1 // return (x+y) l1: return main: loadI 3 => r0 storeAI r0 => [bp-4] // a = 3 loadAI [bp-4] => r0 loadI 2 => r1 param r1 param r0 call add i2i ret => r0 i2i r0 => ret jump l2 // return add(a, 2) l2: return
Reflection
One of the goals of this course is to encourage introspection and thoughtful, deliberate development processes. For this project, you will compose a short (2-3 paragraphs) reflection, answering any (or all) of the following questions as appropriate:
- How does this project fit into the overall picture of our semester-long compiler project? Why is it important?
- Describe your design and development process. Did you use a formal software development method?
- What aspects of this project proved to be the most rewarding?
- What aspects of this project proved to be the most challenging? How did you overcome these challenges?
- How do you know your submission is correct? Briefly describe your testing regimen.
- If you had to start the project again from scratch, what would you do differently?
- What concepts from our theoretical class material or techniques from our classroom activities did you apply in this project?
- Suppose you weren’t using any of the concepts or techniques we’ve covered in class this semester; how would your solution to this project be different?
- What other areas of computer science (or CS courses you’ve taken) impacted your solution to this project?
- Do you have any other feedback about this project?
Include as much detail as you can, but do not ramble. Concise answers are preferred over verbose ones. Your reflection will be graded on a five-point scale:
Insightful | 5 |
4 | |
Superficial | 3 |
2 | |
Deficient | 1 |
No submission | 0 |
Submission
DUE DATE: Friday, December 8, 23:59 EDT (11:59PM)
Please submit your MyLocalRegisterAllocator.java
file and your
reflection to the appropriate assignments on Canvas.
Code Reviews
Because this is the last project of the semester, there will be no code review.
Grading
Here is the grading breakdown for this project:
Automated tests | 80 |
Instructor review | 15 |
Reflection paper | 5 |
TOTAL | 100 |