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
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