CS 453 Programming Assignment #6 — MeggyJava for game of life, or arrays and register allocation

Due Tuesday April 30th (by 11:59pm)
Deadline Extended to Thursday May 2nd

Introduction

This assignment can be done with your CS 453 programming partner. For PA4, PA5, and PA6 joint and separate partner reports are required if you are working with a partner (see below for details). The joint report should be put in the README file and the separate reports should be emailed to cs453@cs.colostate.edu. Both are due with the assignment itself. The partner joint and separate reports will be worth 10% of the programming assignment grade for those of you working with a partner.

In this assignment you will be writing a program that parses the full MeggyJava language including array declarations, array references, array assignments, and the length field for arrays. The full language also includes the last piece of Meggy functionality, Meggy.setAuxLEDs().

You will

add the PA6 grammar rules to the parser,
update the type checking visitor to handle the new language features,
update the code generation visitor to handle the new language features,
and provide a register allocation component in the compiler.

You will need to do type checking for arrays, and 20% of the assignment will be the ability of your compiler to perform register allocation.

The Assignment

You should create a jar file, MJ.jar, that can be executed as follows:

   java -jar MJ.jar InputFile.java

You should also provide a register allocation option.

   java -jar MJ.jar --regalloc InputFile.java

Your README needs a paragraph that describes how you did register allocation. We will be comparing the dynamic number of loads and stores in the code generated by your non-register allocating compiler to your register allocating code and there should be a definite reduction. The command line

  java -jar MJSIM.jar -i Infile.java.s

will print out the number of loads and stores that occurred during the simulation. Note that the --help option shows all of the other options for MJSIM.

The input files can be any PA6 MeggyJava program. The PA6GameOfLife.java is a possible test case for the PA6 compiler. The output file named InputFile.java.s should be an AVR assembly program that uses the provided build process to run on the MeggyJr device. Additionally, the InputFile.java.s file must be such that we can run it through the AVR simulator MJSIM.jar.

We will be testing your register allocation by having the simulator count loads and stores when the generated code executes and checking that the number of loads and stores is noticeably less (at least 10%) than the code generated by the non-register allocation version of the your compiler without register allocation or the reference compiler.

EXTRA CREDIT: Any group who generates code that consistently executes fewer load and store instructions than the register-allocated code generated by the reference compiler will receive 10 points extra credit for PA6. The reference compiler MJ.jar is in ~cs453/public/.

Type Checking

Your compiler will need to perform some type checking. The following is a list of error messages that will be expected in addition to the error messages your compiler was expected to handle for previous programming assignments:

    [LINENUM,POSNUM] Array reference to non-array type

    [LINENUM,POSNUM] Index expression type for array reference must be INT or BYTE
    
    [LINENUM,POSNUM] Operator length called on non-array type
    
    [LINENUM,POSNUM] Invalid operand type for new array operator
    
    [LINENUM,POSNUM] Invalid expression type assigned into array

where LINENUM is the line number for the symbol and POSNUM is the position number for the symbol.

Code Generation

The set of instructions you will need include a file declaration at the top of the assembly file (.file "main.java"), instructions in the previously provided avrH.rtl.s and avrF.rtl.s files and the following:

    # Examples of each statement type are provided.
    # Register numbers, constant values, and labels can change.

    # indirect stores and loads
    std    Y+1, r24
    ldd    r24, Y + 3

    # call to malloc and SetAuXLED
    call    malloc
    
    call   _Z10SetAuxLEDsh

Getting Started

The following is a suggested progression for starting this assignment:

Start with your working PA5 compiler.
Get everything working for arrays.
Implement some form of straight-forward register allocation.
Work on besting the register allocation in the reference compiler for some extra credit.

Submitting the Assignment

Make sure you test your implementation thoroughly. You can use the reference compiler in ~cs453/public/MJ.jar to compare against and to view sample outputs.
Only turn in one assignment per group.
Create the MJ.tar file that contains all the source code, two working test cases that you wrote, two test cases with type errors that you wrote, your .cup and .lex files, a README file, and a subversion.txt file.
- The README file should include your usernames, email addresses, group name, a description of what you are testing in the test cases you are submitting, and any information you want the TA to have before grading your assignment. The README file should also include the joint partner report if you are working with a partner (see below for details).
- The subversion.txt file should include output from the following:
```
svn log
svn info
    
```
  Note that svnlook must be issued on the machine where the repository resides.
Submit assignment using checkin utility.
```
~cs453/bin/checkin PA6 PA6.tar
```

Report and Evaluation of Partner Work

The partner joint and separate reports will be worth 10% of the programming assignment grade for those of you working with a partner.

(joint) For each of PA4 through PA6, write a planning paragraph and timeline together and submit with your assignment. Who is going to do what? The plan and the reality. How is the testing going to be done? What actually happened. Timeline for finishing portions of assignment. Meeting schedule.
(separate) Email cs453@cs.colostate.edu for each of PA4 through PA6 an assessment of the partner work by the deadline of the assignment. The assessment should be approximately 1/2 a page with information about the following: What are some organizational strategies that you and your partner are using that are working well? Specifically how did you and your partner divide the work? (e.g., I wrote the type checker for the following set of grammar rules...). How could the division of work between the partners be improved? How could the interaction between the partners be improved?
Your joint and separate evaluations will be graded based on the following criteria: Have all of the relevant questions been addressed in a thoughtful manner. How well do the reports match in terms of the partners both understanding who is doing what. Clarity and succinctness of the writing. There will be a subjective evaluation of how well the partners attempted to make the group programming experience work.

Usual Late Policy

Late assignments will be accepted up to 48 hours past the due date for a 10% deduction. The assignment will not be accepted past this period. Late means anything after 11:59pm on the day the assignment is due, including 12 midnight.

mstrout@cs.colostate.edu .... April 22, 2011, updated April 16, 2013