CSE 231: Advanced Compilers

Course Syllabus

Overview

In this course, we will explore the basic techniques that are the cornerstone of a variety of program analysis tools, including optimizing compilers, just-in-time compilers, program verifiers, bug fingers, code refactoring tools, garbage collectors, and runtime monitoring systems. These techniques may come in handy, no matter what field of CS you end up working in.

At the same time, you will get a feeling for what research is like in the area of program analysis and compilers by reading research papers, and getting your feet wet in a small research project. If you haven't picked an area of research to work in, being exposed to some research will help you make a better decision. If you have already picked an area of research to work in, seeing what research is like in other fields of CS will broaden your perspective.

Grading

Your grade will be determined as follows:

20% Assignments
10% Course Readings and class participation
20% Take-home final
50% Project

Project

The course project will allow you to get some hands-on experience. There will be two parts to the project:

A mini-project, due about 3 weeks into the class. I this part, you will be given a very simple analysis to implement. The goal of this part is to get you familiar with the compiler infrastructure we will be using in the class.
The project per se, in which you will explore some research topic in the area of program analysis and compilation. The project will be done in teams of 2 to 3. In exceptional cases, you may work by yourself, but you have to talk to me about it beforehand. A project proposal will be due a few weeks into the class, and there will be several milestones along the way, to make sure that you are making good progress. A project report will be due at the end of the quarter. You will also give two presentations on your project: one short presentation at the midway point in the quarter, and a final project presentation at the end of the quarter.

Course Readings

For each paper that you are given to read, you will write a review. The reviews will consist of three parts:

A two sentence summary of the paper. This is intentionally a short summary. It will require you to boil down the paper to its essence.
Three interesting points about the paper, in bullet form. You can, for example, point out strengths, point out weaknesses, compare with other approaches.
Questions that you have about the paper, to help us determine how class time should be spent.

Course Topics

Introduction (1.5 lectures)

course outline
discussion of issues related to program analysis and program transformations
tour of common optimizations

Program Analysis (2.5 lectures)

dataflow analysis as set of equations at program points
dataflow functions
lattice theoretic formulation of dataflow information
solution techniques: iteration, chaotic iteration
monotonicity and termination
must vs. may information
bit vector analyses, GEN and KILL sets
direction of analysis

Rhodium (1 lecture)
Program Representations (1 lecture)

Issues that arise in the design of program representations
High-level, medium-level, and low-level representations
Abstract Syntax Tree
Control Flow Graph
Dataflow Graph
Static Single Assignment
Whirlwind's program representation

Loops and loop transformations (1 lecture)

Definition of loops
Loop invariant code motion
Code hoisting, sinking

Program Representations, revisited (1 lecture)

Control Dependence Graph
Program Dependence Graph

Interprocedural Analysis (1.5 lectures)

context sensitive vs. insensitive
summarization strategies
call strings (k-CFA) approach
transfer function approach

Pointer Analysis (1.5 lectures)

Simple intraprocedural flow-sensitive pointer analysis
Going to interproc: Wilson and Lam (and partial transfer functions)
Going to flow-insensitive: Andersen's pointer analysis
Scaling even further: Steensgaard's pointer analysis
Regaining some precision: One-level flow analysis

Program Analyses for Program Verification (1 lecture)

RHS (as background for ESP)
ESP
Predicate Abstraction (BLAST)

Correctness (2 lectures)

Abstract interpretation
Correctness of transformations

Ordering Analyses and Transformations (1 lecture)
Set Constraint Analyses (1 lecture)
Garbage Collection (1 lecture)