4/25/10: Your project reports are due May 7th. Your paper should be structured as a conference paper, and should be 8-10 pages in ACM SIGPLAN conference proceedings format (2 column, 10 pt font; an appropriate LaTeX template can be obtained here).

4/13/10: Tomorrow we will discuss program verification. Part of the discussion will focus on the paper "Program Verification as Probabilistic Inference" by Sumit Gulwani and Nebojsa Jojic. The slides for tomorrow's lecture are here

4/8/10: (Most of) the slides from the paper presentations are available on the papers page. If you have not yet sent me your slides, please do so ASAP.

2/25/10: Reminder: your project proposals are due at 5 p.m. tomorrow.

2/19/10: The (last) slides on loop transformation are now up. Also, as a reminder: I will be out of town next week. Professor Midkiff will provide guest lectures on Monday (2/22) and Wednesday (2/24); class is canceled on Friday (2/26).

2/14/10: The latest set of loop transformation slides are up (Lecture 6). We will be skipping slides 29–36 and 52–56, so you do not need to print those. Also, the dates for your paper presentations have been added to the list of papers. Remember to schedule a time in the week preceding your presentation to go over your slides with me.

2/2/10: For the next few weeks, we will be discussing a framework for loop optimization, called the unimodular transformation framework. We will begin by understanding the effects of loop transformations. As background for the next lecture, please read Section II of this paper.

1/31/10: The list of papers that we will be discussing in the latter portion of the course is now available

1/28/10: Lecture 2 has been updated with the corrections from last class, as well as some additional slides (#20 on) about SSA-PRE.

1/24/10: Over the next few lectures, we will be discussing a powerful data-flow analysis called Partial Redundancy Elimination (PRE). For these lectures, you should read this paper; an easier presentation of the same idea is in this handout. We will then discuss how to use SSA principles to perform PRE, as discussed in this paper (you only need to read to page 29).

1/18/10: Another paper that may be useful for understanding dominance frontiers (which we will discuss on Wednesday) is A Simple, Fast Dominance Algorithm by Cooper et al.

1/11/10: The paper that provides the reference material for the first few lectures is "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" by Cytron et al.
Course Description

This course focuses on the techniques used by advanced compilers to optimize and analyze programs. The topics we will cover in this course include:

  1. Dataflow analysis (more advanced analyses, such as partial redundancy elimination)
  2. Static Single Assignment form (how to construct it, how to use it)
  3. Loop transformations (cache models, automatic transformation frameworks)
  4. Pointer analysis (efficient flow insensitive analyses, interprocedural analysis)
  5. Shape analysis
  6. Autotuning
  7. Parallelization
Course Details
Instructor:Milind Kulkarni
milind 'at' purdue 'dot' edu
Office hours: MW 9:30–10:30, and by appointment
EE 324A
Course Information

The first half of the course (roughly, the first three topics) will consist of lectures. The second half of the course will be based around classic and current research papers, discussing interesting topics in compiler research (the list of papers will be available shortly). Each student must choose two papers for which to write a 1-page response. This response must summarize the main ideas of the paper and discuss any shortcomings and possible extensions of the paper.

Each student will also choose a third paper to present in class. The week before your presentation, you should meet with me to review and revise your slides, and to give a practice presentation. If you have not given a research presentation before, this course will serve as training! Each presentation should be 35 minutes, followed by a 15-minute discussion period (appropriate presentation length will factor in to your grade).

The list of papers that you can choose from to present is here

The bulk of your grade will consist of an individual course project. This project can be on any topic you like (including related to your own research), as long as it is connected to the material in the course. I will also provide some ideas if you have trouble coming up with one. You will write a two-page proposal detailing your project idea, and then present the results of your project during one of the last class periods. Your project presentation should be 25 minutes, including questions. The exact dates for when your proposal and presentation will be due are yet to be determined.

You will also submit a final project report, written in the style of a research paper. This should be roughly 8-10 pages, two-column, 10-pt font. Your report should discuss the motivation for your project, survey related work, describe your idea and implementation and provide experimental validation (or theoretical justification, in the case of a theory-oriented project).

Your grade will be calculated as follows: