Introduction

The goal of the final project is to give you in-depth knowledge of some compiler analyses and optimizations. You can pick between two options for the final project. In the first option, you will survey research papers in an area of compiler optimizations. In the second option, you will implement some optimizations. Within both project there is a lot of flexibility so you can tailor the project to suit your particular interests.

Project 1: In-depth reading

In this project you will survey an area of compiler optimizations and write a paper describing and evaluating the important ideas. Your paper should include the following:

• Description of the important ideas, in particular, the important intuitions.
• Discussion of time complexity, performance (measured and/or anticipated), practicality, and applicability of these ideas.
• How these ideas compare to each other
• Which of these ideas would you recommend incorporating in a compiler and why. In addition, if the recommended ideas interact, how would you organize them in an optimizer.

Some possible areas that you can survey are:

• Interprocedural analysis
• Pointer analysis
• Array dependence analysis
• Parallelization
• Run-time optimizations
• Garbage collection
• Anything else that particularly interests you

Obviously, I don?t expect you to read all the literature on any area since there are tens if not hundreds of papers on each of the above mentioned areas. I expect you to narrow down your survey to a more manageable size (for instance, pointer analysis of C programs).

You may work in groups on this project, but of course, group submissions must be more substantial than individual submissions.

Deliverables

Your proposal will be a one-page document giving the area you will be surveying along with a list of papers that you will read. If you later wish to change the papers you should consult with me first.

Your final submission will be your survey paper. If it is a group submission then you must mark (or note) each member?s contribution.

Project 2: Implementation

In this project, you will implement one or more compiler optimizations or analyses in a Java framework (see class web page for description and code of the framework). The number of optimizations and analyses you need to implement depends on the complexity of the analyses and optimizations you have chosen.

You may work in groups on this project, but of course, group submissions must be more substantial than individual submissions.

Deliverables

Your proposal will be a one-page document enumerating the optimizations and analyses that you plan to implement.

Your final submission will have two components:

• A document enumerating and briefly describing what you have implemented (this need not be much more than the proposal).
• The source code for your analyses and optimizations along with any test cases you use (this must be submitted on paper and via email).

Deadlines

Proposal due: February 13^th 1998

Project due: March 9^th 1998