- Meeting times: Tu-Th 6:30-7:50, location: EBU3B 2154
- Instructor: Sorin Lerner (email: lerner at cs, Office hours: by appointment, email me)
- Textbook: none (we will instead use selected papers from the literature)

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.

Your grade will be determined as follows:

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

- 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.

- 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)