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:
- 30% In-class Midterm
- 30% Take-home final
- 40% Project
Project
The course project will allow you to get a feel for
what implementation and/or research is like in compilers. You will
explore some implementation aspect of a compiler. More details will
be provided in class and in the lecture material.
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)