CS 432

P5: Decaf Register Allocation

Objective

The goal of our semester-long project is to gain experience in compiler implementation by constructing a simple compiler. In this final phase you will implement a bottom-up register allocator that rewrites ILOC to use a fixed number of physical registers, preparing it for conversion to machine code.

Introduction

Add register allocation to your compiler. Drop the test-p5/ folder into your project. Your P4 code uses as many virtual registers as it needs (the simulator provides 2048); this phase transforms it to use only a fixed number of physical registers (matching a target architecture). The revised driver reduces to four (4) registers by default; the count is set with -r N / --registers N, where N may range from 2 to 32. Programs that assign to an array element need N >= 3, because the array-store instruction reads three registers at once. The rules in the Project Overview apply as always.

How this phase is graded. Register allocation is the last phase, so there is no stop flag. Run the compiler and the simulator together (isim reads an ILOC program from a file or from standard input):

decaf -r N --fdump-iloc-alloc prog.decaf | isim -r N

Here isim -r N both executes the allocated code and verifies that it uses only the physical registers R0 … R(N-1) and leaves no virtual registers behind. An allocator that exceeds N registers or leaves a virtual register therefore fails observably — there is no way to pass by coincidence. (The automated harness runs these same two stages via a temporary file.) How you implement the allocation is your design.

Assignment

Implement a simple, bottom-up local register allocator as described in EAC 13.3.2 and in class. It operates on one basic block at a time; because P4 code is emitted so that no virtual register is live across a basic block boundary, this local approach is globally valid for our purposes. The core idea is to keep a mapping from physical registers to the virtual registers they currently hold, and, as you scan each instruction:

• ensure each read operand is in a physical register (loading it back from its spill slot if it was spilled), and free a physical register once its value has no future use;
• allocate a physical register for each written operand, spilling the value whose next use is farthest away when no register is free;
• before every CALL, spill all live registers. This conservative step is what finally makes recursive (and mutually recursive) functions work, since it prevents a callee from clobbering a caller's live values.

Spilling stores a value to a stack slot and reloads it on the next use, so you will track a map from virtual register to stack offset and grow each function's stack frame accordingly (by adjusting the frame's stack-allocation instruction). There is a single register class, so simple fixed-size arrays are adequate for the bookkeeping. If you are not given enough physical registers to complete allocation even with spilling, emit an error message and abort.

Complete Compiler

After this phase your compiler produces code that is nearly ready for a "real" machine — all that remains is translation to true machine code. A companion reference tool (iloc2y86) converts emitted ILOC into Y86 assembly, which you can assemble with yas and run on your CS 261 Y86 interpreter (or the reference y86ref). This "closes the loop" between CS 261 and CS 432: along the way you have built major components of two large pieces of systems software (an interpreter and a compiler). The Y86 back end is an ungraded bonus — ask me if you would like to try it. Congratulations on completing this non-trivial accomplishment, and good luck as you finish at JMU and begin your career!

Sample Input

def int add(int x, int y)
{
    return x + y;
}

def int main()
{
    int a;
    a = 3;
    return add(a, 2);
}

Sample Output

Allocated ILOC for -r 4 (virtual registers replaced by R0…R3; yours may differ and still be correct):

add:
  push BP                               // prologue
  i2i SP => BP
  addI SP, 0 => SP                      // allocate space for local variables (0 bytes)
  loadAI [BP+16] => R0
  loadAI [BP+24] => R1
  add R0, R1 => R0
  i2i R0 => RET
  jump l1                               // return (x+y)
l1:
  i2i BP => SP                          // epilogue
  pop BP
  return

main:
  push BP                               // prologue
  i2i SP => BP
  addI SP, -8 => SP                     // allocate space for local variables (8 bytes)
  loadI 3 => R0
  storeAI R0 => [BP-8]                  // a = 3
  loadAI [BP-8] => R0
  loadI 2 => R1
  push R1
  push R0
  call add
  addI SP, 16 => SP                     // de-allocate space for parameters (16 bytes)
  i2i RET => R0
  i2i R0 => RET
  jump l2                               // return add(a, 2)
l2:
  i2i BP => SP                          // epilogue
  pop BP
  return

Submission

Submit your entire project directory: run /cs/students/cs432/f26/submit.sh p5 from your project root and confirm the P5 assignment on Canvas. Because this is the last project of the semester, there is no code review.

Grading

This checkpoint is autograded on the tier rubric below (behaviorally, via isim -r N); your grade is the highest tier whose requirements all pass. Tests are cumulative and mostly not provided to you in advance, so write your own.

Note that the D-level tests run and gate like the others, so a basic virtual-to-physical conversion is the minimum working behavior. The rubric shows the base grade possible if your submission meets the criteria listed; most items are assessed by automated testing using cases mostly NOT provided in advance.

I will also examine your submission manually for acceptable style and documentation and for the use of any unsafe functions. Deficiencies may earn a numerical deduction, and egregious ones a half- or full-letter deduction. If you are unsure of my standards, review the style guide and list of unsafe functions from CS 261.