Programming Assignment 5: Optimization
due: Wednesday, November 20
In this assignment, you will generate optimized code for the Cubex programming language.
Deliverables
Your submission will have the same three parts as before:
- An executable jar file containing the Cubex compiler and its sourcecode.
- A preamble file
cubex_lib.h that you can #include in your generated C file.
- A text file as described below.
The Compiler
As in the previous assignments, this program should take a file name as an argument, read that file, check it and print results to the standard output. The possible results are:
- If the input has a lexing, parsing or typing error, the program should print "reject"
- Else, the program should output a C program in the same directory, named
out.c . The C program should adhere to the same constraints as that of PA4 (using the provided small library and makefile), in addition to the required optimizations listed below.
Required Optimizations
For this assignment, there are three optimizations that you are required to implement:
- Memory Deallocation: apply live-variable analysis to freeing memory early (particularly freeing "input" so that large inputs can be processed without being stored).
- Common subexpression elimination: avoid multiple computations of identical subexpressions (particularly for method and interface-table lookup).
- Primitives: avoid allocating objects for integers and booleans not passed by reference.
We have listed the above requirements in increasing order of difficulty; we encourage you to work on them in that order, and we will be placing more emphasis gradewise on the easier optimizations. For each optimization, you should think carefully about what program representation it is best done on (HIR, MIR, or LIR). We suggest working through some example programs to convince yourself that you have the right analysis and program transformations worked out before implementing them.
Staging
This assignment will be graded in a staged mode, which means that you can concentrate on some parts of the assignment and leave others out with a predictable loss of points. Our tests will be organized in the following stages (same as PA4), meaning that programs only consist of the things in that stage and the preceding ones:
- Statements
- Non-generic functions
- Generic functions
- Non-Generic classes without inheritance
- Generic classes without inheritance
- Generic classes with single interface inheritance
- Generic classes with single interface inheritance + interface method implementations
- Generic classes with class inheritance
- Generic classes with multiple interface inheritance
Note: Any stage (including stage 1) may contain code related to Iterable, which
you have to handle to the fullest extent.
The distribution of tests to stages is identical to PA4:
- 80% of the tests will test programs in stages 1-3.
- 10% of the tests will test programs in stages 4 and 5.
- 10% of the tests will test programs in stages 6-9.
For now, assume that each of the 3 required optimizations will be weighted equally within each stage. We'll let you know if this changes.
How to submit
You have to include the complete source code in the jar-file, including inputs for any lexer/parser generators you might use.
You will need a manifest file (MANIFEST.MF) that sets the classpath. Your manifest file should look like this:
Manifest-Version: 1.0
Class-Path: . antlr-4.1-complete.jar
Main-Class: [your-class-name-here]
The following code snippet does this packaging for you (.g4 is the file extension for ANTLR files).
jar cvfm x3c.jar MANIFEST.MF *.class *.java *.g4
The preamble file
Like the generated code, this file may only #include the library files we provided. You can use it to implement all data structures and functions common to all generated programs.
The text file
Finally, we ask that you submit a small text file (.txt) that contains the following information:
- Who you discussed the problem set with. Remember that the solution must be your own, but you can discuss your ideas with others provided you mention that in this file.
- What the distribution of work in your team was like. Who did what?
- Any additional comments you might have about the problem set.
Source control
We recommend that you use some kind of source control. Be aware that your repositories should not be publicly viewable on the web. GitHub offers private repositories for students.
Testing
You should thoroughly test your solutions before turning them in. We will test your submissions with complex examples. The way a test works is that after running
java -jar x3c.jar x3_test1.x3
make
cat x3_test.in | xargs ./a.out > x3_test1_actual.out
the content of x3_test1_actual.out should be equal to x3_test1.out .
In addition to the correctness of your code, you will be graded on various performance measures reflective of the required optimizations.
