CS 432

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. For the Ensure and Allocate functions, the pseudocode in the book (Figure 13.1) is sufficient. For the main routine, you may find the following minor revision helpful:

# perform register allocation for the given block
allocateRegisters(block):

    for each instruction i in block:

        for each read vr in i:              # make sure operands are in registers
            pr = Ensure(vr)
            replace vr with pr in i
            class.Next[pr] = Dist(vr)
            if class.Next[pr] == INFINITY:
                class.Name[pr] = INVALID
                class.Next[pr] = -1
                class.Free[pr] = true
                push(class, pr)

        for each written vr in i:           # open up a register for the result
            pr = Allocate(vr)
            replace vr with pr in i
            class.Next[pr] = Dist(vr)

        if i is a CALL instruction:         # spill any live registers at function calls
            for each physical register pr:
                if class.Name[pr] is a virtual register:
                    store contents of pr
                    class.Name[pr] = INVALID
                    class.Next[pr] = -1
                    class.Free[pr] = true
                    push(pr)

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 pseudocode above includes this new functionality.

Note that we only have a single register class that we need to worry about during this allocation (e.g., general-purpose integer registers), so there is no need to create a "Class" struct; just keep the data structures locally in MyLocalRegisterAllocator. I recommend just using arrays for most of the structures because they do not need to dynamically resize and the number of physical registers will be small. For register spilling, you will need to track the offsets of each spilled virtual register; I recommend using a map from virtual register ids to stack offsets.

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 and it enables easier conversion to x86 and Y86 because we can assume that some of the registers are always available for hard-coded translation idioms.

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:

Submission

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: