CS 415: Compilers
Project 3: A Pascal Subset Code Generator
Due date: Thursday, April 28 Saturday, April 30

Announcements

Deadline extended to Saturday 4/30 11:59pm EDT.
Project 3 available.

Project Description

You will write a syntax directed translation scheme that will generate ILOC code for the language (Pascal Subset) introduced in the second project. You should test the correctness of your generated ILOC code by running it on our ILOC simulator on the ilab cluster.

ILOC simulator

The current ILOC simulator does not implement a Write-After-Write interlock. Using a register-register model where every computed value is assigned a new virtual register, no two assignments of values to the same virtual register should occur. For example

loadI 1028 => r1 // Assume MEM(1028) == 5
load r1 => r2
loadI 2 => r2 // output dependence on r2

What is the value of r2 at runtime? Assume that the load instruction has a latency of 5 cycles, and loadI a latency of 1 cycle. Since there is no hardware interlock for the output dependence on r2 , the loadI 2 => r2 instruction will finish before the load r1 => r2 instruction and write the value 2 into register r2. However, after 5 cycles, the load instruction will finish and will overwrite the value 2 in r2 with 5. So, for three cycles, r2 will contain the correct value (2), before being overwriten by the wrong value (5).

Again, since the register-register model uses new virtual registers for every computed value, you should never generate output dependences within single basic blocks thereby avoiding the WAW interlock problem of the current simulator.

Code Shape Requirements

Your code should use the register-register model that exposes the maximal opportunities for register allocation. In other words, each new value should reside in a separate virtual register, if possible. The function NextRegister will return a new (fresh) register number.
Array references do not reside in virtual registers across statement boundaries. Array references always lead to memory accesses (LOAD or STORE) A read and write of a scalar variable within a single basic block may lead to a reference to a corresponding virtual register. The same scalar variable may be assigned to different virtual registers across different basic blocks. The first reference to a scalar variable in a basic block will result in generating a LOAD or STORE instruction. After that, the scalar variable "lives" in its virtual register, and the virtual register needs to be written back to the memory location of its scalar variable at the end of the basic block if the variable has been modified. Assignments to scalar variables that live in registers are implemented as register-register transfers (use the i2i ILOC instruction ).
All variables are statically allocated, i.e., there is no need for activation records. The static area starts at memory location 1024. Addresses above are reserved for register spilling. The register r0 should always contain the starting address (namely 1024) of the static area.
You may only use the following ILOC instructions. All these instructions are implemented in our ILOC simulator.
- no operation: nop .
- arithemtic: add, sub, mult .
- logical: and, or, xor .
- memory: load, loadI, loadAO, loadAI, store, storeAO, storeAI .
- control flow: br, cbr, cmp_LT, cmp_LE, cmp_EQ, cmp_NE .
- register transfer: i2i .
- I/O: output .
Please see files instrutil.h and instrutil.c for details about the required formats. Procedures emit, NextRegister, and NextLabel are also defined within these files.
You may want to generate nop instructions as targets of branches and conditional branches, e.g., L1: nop .
Boolean values are represented as 4 bytes entities with 0 == FALSE and 1 == TRUE. Therefore, regular load and store instruction can be used.
The evaluation of an exp will always result in an integer or boolean value, while the evaluation of an condexp will always result in a boolean (0 or 1) value. An ILOC cmp_ instruction writes a boolean value into its target register.
The function NextLabel will generate a new (fresh) label each time it is called.

Provided Code

You are expected to extend your solution for the second project (Front End) for the code generation part.

You will need to modify files parse.y , attr.h , attr.c , symtab.h , symtab.c , and Makefile . Sample files that generate an illustrating (incomplete functionalities) code generator are available in ~zz124/cs415_2016/projects/proj3 . A basic version of scan.l and parse.y (Only *use* it as an example for code generation purposes, it does not use the grammar specified in project 2) can be found in this directory. Please copy the entire directory over into your own subdirectory under your ilab account.

Parser/Code Generator: parse.y Here is where most of your code will go, as in the second project. Use calls to procedure emit to generate code. This will write the resulting ILOC code into file iloc.out. To use the sample project files, do "make clean" and "make" first. Then run the program by "codegen < testcases/demo1 ". The result will be saved into iloc.out. Please modify your own version of parse.y from your Project 2 solution accordingly .
instrutil.h and instrutil.c . *** DO NOT MODIFY ***
You should modify your own Makefile from the second project to include the files instrutil.h , instrutil.c , or use the provided Makefile

In order to test your compiler, we have provided some initial test cases in ~zz124/cs415_2016/projects/proj3/testcases . Your compiler is not required to emit any comments, but it may be useful for you to do so. You should use the provided procedure emitComment for this purpose (please see the sample parse.y).

Due Date

The code generator is due at 11:59 pm on ~~Thursday April 28~~ Saturday April 30, 2016--that is, one minute before midnight.

Late submission will be not be allowed after May 1st since we need to grade the project immediately. If you have specific, overriding, personal reasons why these dates are unreasonable, you should discuss them directly with the instructor before the deadline.

Submission Procedure

You need to submit through sakai (tar file) the following files: attr.h, attr.c, symtab.h, symtab.c, parse.y, ReadMe . The ReadMe file contains may contain comments that you want the grader to know about.

Grading Criteria

As the Front End, the Code Generation project will be mainly graded on functionality. You will receive no credit for the entire project if your code generator does not compile and execute on the ilab machines .

CS 415: Compilers Project 3: A Pascal Subset Code Generator Due date: Thursday, April 28 Saturday, April 30