CS 432

P4: Code Generation

Objective

The goal of our semester-long project is to gain experience in compiler implementation by constructing a simple compiler. In this phase you will add code generation: translate a valid Decaf AST into linear ILOC code.

Introduction

Add a code generator to your compiler. Drop the test-p4/ folder into your project and extend your compiler so that, after analysis, it emits ILOC for the program. Read the "Operational Semantics" and "Application Binary Interface" (ABI) sections of the language reference carefully first. The rules in the Project Overview apply as always.

Your compiler emits code; it does not run it. When run with --fdump-iloc --stop-after-codegen, your compiler prints the ILOC it generated; that ILOC is executed by the standalone, trusted simulator isim (bundled in test-p4/). isim reads an ILOC program from a file or from standard input, so you can run the compiler and the simulator together in one step:

decaf --fdump-iloc --stop-after-codegen prog.decaf | isim

(The automated harness does the same thing in two steps — it saves the ILOC to a file and then runs isim on that file — which is convenient for inspecting the generated code.)

ILOC provides a large bank of virtual registers here — 2048, far more than any test program needs (physical register allocation comes in P5). How you traverse the AST and track intermediate results is your design.

Assignment

Generate correct ILOC for Decaf programs, following the calling conventions, stack-frame layout, and static-storage rules in the ABI. You are responsible for emitting function prologues/epilogues, laying out parameters and locals, and handling the built-in output functions (print_int, etc.) with the PRINT ILOC instruction as described in the reference.

This phase is more open-ended than the earlier ones: many different ILOC programs are equivalent, so your output need not match the sample below. Grading is almost entirely behavioral — your emitted code is run through isim and checked for the correct program output and return value — so a debug view of the raw ILOC is essential while developing. Keep any developer trace output behind your own switch, and make sure --fdump-iloc prints only the ILOC (the tests assume this). When behavior is underspecified, match decaf-ref.

Notes:

Every assignment should actually write the value to the correct location in memory. Do not attempt to optimize or skip assignments.
You can ignore the PHI instruction (it is for static-single-assignment data-flow analysis, which we are not doing).
Emiting a correct prologue is very important! Local variables will not work unless the base pointer is established from the stack pointer on function entry, and the stack pointer is adjusted by the frame's local size.
You should emit the stack allocator even if the local size is zero. You may need to adjust the frame size in P5 to hold spilled registers.
Recursive (and mutually recursive) functions will not yet work correctly, because virtual registers are reused across calls. This is expected; P5 fixes it by spilling live registers at call sites.
Use --fdump-iloc to inspect your output; pipe it to isim to run it. (decaf-ref also offers --fdump-iloc-tree, a debugging visualization, but you are not required to produce it.)

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

One valid --fdump-iloc rendering (yours may differ and still be correct):

add:
  push BP
  i2i SP => BP
  addI SP, 0 => SP
  loadAI [BP+16] => r0
  loadAI [BP+24] => r1
  add r0, r1 => r2
  i2i r2 => RET
  jump l0
l0:
  i2i BP => SP
  pop BP
  return
main:
  push BP
  i2i SP => BP
  addI SP, -8 => SP
  loadI 3 => r3
  storeAI r3 => [BP-8]
  loadAI [BP-8] => r4
  loadI 2 => r5
  push r5
  push r4
  call add
  addI SP, 16 => SP
  i2i RET => r6
  i2i r6 => RET
  jump l1
l1:
  i2i BP => SP
  pop BP
  return

Piping this to isim prints RETURN VALUE = 5.

Submission

Submit your entire project directory: run /cs/students/cs432/f26/submit.sh p4 from your project root and confirm the P4 assignment on Canvas.

Code Reviews

After this project you will review two other students' submissions and offer constructive feedback per the given rubric, graded separately for effort (see the syllabus). Submit your review on Canvas by the date given in the corresponding assignment.

Grading

This checkpoint is autograded on the tier rubric below (behaviorally, via isim); 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.

Grade	Description	Requirements
A	Exceptional	Generate code for locations and assignments w/ arrays Generate code for function calls w/ parameters Handle all edge cases correctly (e.g., modulus operator and print functions) No compiler warnings or memory leaks All of the below
B	Good	Generate code for boolean literals and expressions Generate code for conditionals, while loops, breaks, and continues Generate code for function calls w/o parameters All of the below
C	Satisfactory	Generate code for all binary and unary integer operators except modulus Generate code for locations and assignments w/o arrays All of the below
D	Deficient	Generate code for integer literals Generate code for return statements Generate code for blocks Generate code for the addition operator
F	Unacceptable	Some evidence of a good-faith attempt

Array code generation is an A-level requirement here. Array support is deliberately tiered differently in each phase: array parsing is C-level (P2), the array semantic checks are B-level and A-level (P3), and array code generation is A-level (P4). 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.

Compilers - Fall 2026