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:
- 15% Course Readings and class participation
- 35% Take-home final
- 50% Project
Project
The course project will allow you to get a feel for
what research is like. For the project, you will explore some research
question related to program analysis/optimization, either by reading
papers and writing a report (done individually) or by exploring a
research topic as a project (done in groups). In exceptional cases,
you may work by yourself for a project, but you have to talk to me
about it beforehand. A project/reading 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 presentation or
report will be due at the end of the quarter. You will also have to
checkin with the instructor and/or TA at several points throughout the
quarter. If there is any way of incorporating your current research
into the course project, I encourage you to do so.
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)