CS 415: Compilers
Project 3: A Pascal Subset Code Generator
Due date: Monday, May 5

Announcements

• Bonus points policy updated.
• 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 r2at runtime? Assume that the loadinstruction has a latency of 5 cycles, and loadIa latency of 1 cycle. Since their is no hardware interlock for the output dependence on r2, the loadI 2 => r2instruction will finish before the load r1 => r2instruction and write the value 2 into register r2. However, after 5 cycles, the load instruction will finish and will overwrite the value 2 in r2with 5. So, for three cycles, r2will 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 may assume that your input programs for this project do not have any parsing or static semantics errors (e.g., no type errors). We will only test your program with semantic error cases for bonus points calculation. If you integrate syntax/semantic error checking component, you get 20% bonus points. If you integrate register allocation component, you have to specify how to invoke it in your readme file, and you get 25% bonus points. If you do both, you can get 30% bonus points. Note that the condition for getting bonus points is that your code can pass all test cases for project 3. You will not get bonus points if any of the test cases fail. You do not get penalty for these optimizations either (no negative points).

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_2014/projects/proj3 . A basic version of scan.l (correct) 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.

1. 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.yfrom your Project 2 solution accordingly .
2. instrutil.h andinstrutil.c . *** DO NOT MODIFY ***
3. You should modify your own Makefile from the second project to include the files instrutil.h , instrutil.c , or use the providedMakefile

In order to test your compiler, we have provided some initial test cases in ~zz124/cs415_2014/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 emitCommentfor this purpose (please see the sample parse.y).

Due Date

The code generator is due at 11:59 pm on Monday May 5, 2014that is, one minute before midnight.

If you have specific, overriding, personal reasons why these dates are unreasonable, you should discuss them directly with the instructor beforethe 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 receiveno creditfor the entire project if your code generator does not compile and execute on the ilab machines.