CS 4120: Introduction to Compilers
Fall 2013

Programming Assignment 5: Optimization

due: Wednesday, November 20

In this assignment, you will generate optimized code for the Cubex programming language.


Your submission will have the same three parts as before:

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:

Required Optimizations

For this assignment, there are three optimizations that you are required to implement:
  1. Memory Deallocation: apply live-variable analysis to freeing memory early (particularly freeing "input" so that large inputs can be processed without being stored).
  2. Common subexpression elimination: avoid multiple computations of identical subexpressions (particularly for method and interface-table lookup).
  3. 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.


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:

  1. Statements
  2. Non-generic functions
  3. Generic functions
  4. Non-Generic classes without inheritance
  5. Generic classes without inheritance
  6. Generic classes with single interface inheritance
  7. Generic classes with single interface inheritance + interface method implementations
  8. Generic classes with class inheritance
  9. 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:

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:

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.


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