Site Tools

cc17:assignment_7

Optimization

Introduction

You have now written a complete compiler for eMiniJava and this is the final programming assignment of the course! In this assignment, you will improve your compiler by optimizing the generated code. There are numerous ways to optimize a compiler even for the simple language that was used in this course. To get the full grade of this assignment, you need to at least implement one optimization technique and you need to show that it really works by submitting benchmark(s) that can benefit from your optimizing compiler. As promised, there will be a final competition between the compilers from different groups and the winner will receive a bonus. The winning compiler has the best optimization results (fewest number of bytecode instructions on average) on the library of benchmarks.

Correctness

Please note that optimization should not break the correctness of the generated code. In case that your compiler generates wrong programs because of optimization, you will significantly lose points in this assignment.

Generality

There are various optimization techniques. We covered only a handful of them in the class. In this project, you are not limited to the optimizations covered in class. You are free to implement any optimization that you come across in reading the textbook or other resources. You have to include a write-up (around a page is enough) to demonstrate that your optimization is effective and correct. Your write-up must include an argument to show your optimization is general, meaning it is not a special-case optimization that works only for the benchmarks you provided.

Competition

As we discussed in Lecture 33, optimizations can in general target different goals such as execution time or size of the generated executable file. Since our library of benchmark includes typically small programs, the running time of the generated code is usually insignificant, maybe in order of milliseconds. The fast running times of executables makes it difficult to compare your projects based on their running time in the competition. For that reason, although you can implement an optimization technique that optimizes for execution time (such as loop unrolling) to get the grade, if you want to enter the competition your compiler should only focus on optimization techniques that reduces the size of the generated executables (e.g. available expressions analysis or dead-code elimination).

Benchmarks

The library of benchmarks in the competition includes the benchmarks that you contributed to it and is accessible from here:

/usr/local/pub/hh/cc/benchmarks

For this project you need to submit benchmark(s) to show that your optimization is effective. You are also allowed to add a single benchmark to the competition library. In case you choose to submit a set of benchmarks to show the effectiveness of your compiler, please specify which benchmark you want to submit for the competition. We will also add a set of hidden benchmarks to the final benchmarks that will be used in the competition.

Interface

Since we are not imposing any code structure for your programs, it is extremely important for your compiler to exactly follow a fixed interface as described here. This allows us to uniformly run and test all the projects from different groups of students. Command-line is the primary interface for your users to interact with your compiler. A general form for the command-line interface is as follows:

emjc [options] <source file>

These are the possible options for your compiler. If the user does not provide a correct option, the compiler treats it the same as the –help option.

1. ––help: Prints a synopsis of options
2. ––pp: Pretty-prints the input file to the standard output
3. ––lex: Generates output from lexical analysis as described in Assignment 2.
4. ––ast: Generates output from syntactic analysis as described in Assignment 3.
5. ––name: Generates output from name analysis as described in Assignment 4.
6. ––type: Generates output from type analysis as described in Assignment 5.
7. ––cgen: Generates output from code generation as described in Assignment 6.
8. ––opt: Generates optimized executable program.
9. ––optinfo: Generates optimized executable program with some statistics.

After executing the compiler with the option ––opt for the source file filename.emj the compiler silently generates optimized class files for a valid eMiniJava program. The option ––optinfo has the same effect as ––opt, with the difference that it prints out the number of generated bytecode instructions before and after optimization:

#bytecode before optimization: <number>
#bytecode after optimization:  <number>

If you are not planning to enter the competition, please specify it in your write-up and you can skip implementing the last option.

In the case that the program has errors, your compiler front-end should work as before. It prints out a set of errors (such as unknown identifier) in the following format:

<line>:<column> error:<description>

where <line> and <column> indicate the beginning position of the error, and <description> details the error.