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. 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 (1-2 page) reflection paper, answering the following questions:

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

Be sure to address all of the above questions in as much detail as you wish, but do not ramble. Concise answers are preferred over verbose ones.

Submission

DUE DATE: Friday, December 9, 23:59 EDT (11:59PM)

Please submit your .java file and your reflection paper to the appropriate assignments on Canvas.

Your reflection paper should be in a standard document format: plain text and PDF are preferred, but OpenDocument and MS Word files are also acceptable.

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: