| Date | Topic | Reading | Suggested Exercises | Due |
| Introduction | ||||
| Aug 20 (M) | Introduction (PDF) | Ch. 1 | Syllabus and Project 0 | |
| Aug 22 (W) | Undergrad compilers review I (PDF) | Ch 2 | ||
| Aug 24 (F) | Undergrad compilers review II (PDF) | 2.2.1, 2.2.2, 2.3.1, and questions in lecture notes | ||
| OOP and GC | ||||
| Aug 27 (M) | Compiling OO languages (PDF) | |||
| Aug 29 (W) | Garbage collection (PDF) | Garbage Collection Basics, Ch 7 especially Ch 7.6-7.6.3 | 7.4.1, 7.5.2, and questions in Sept 5th lecture notes | |
| Aug 31 (F) | Implementing Garbage Collection(PDF, Example) | Project 1 | ||
| Sept 3 (M) | Labor Day -- No Class | |||
| Register Allocation and Instruction Scheduling | ||||
| Sept 5 (W) | CFG and Liveness (PDF) | Ch 8.4, 9.2-9.25 | 8.4.1, 9.2.1, 9.2.3 | |
| Sept 7 (F) | Register Allocation I (PDF) | Ch 8.8 | 8.8.1 | |
| Sept 10 (M) | Register Allocation II (PDF) | |||
| Sept 12 (W) | Register Allocation III (PDF) | [Briggs] | See Sept 14th slides | |
| Sept 14 (F) | Instruction Scheduling I (PDF) | Ch 10-10.3 | See slides for exercises and 10.2.1, 10.2.3, and 10.3.2 in book | |
| Sept 17 (M) | Instruction Scheduling II (PDF) | Ch 10.4-10.7 | Project 2 | |
| Data-Flow Analysis, Control-Flow Analysis, and Optimizations | ||||
| Sept 19 (W) | Data-Flow Analysis (PDF) | Ch 9 through 9.2 | From book 9.2.1, 9.2.2, 9.2.6 | |
| Sept 21 (F) | Lattice Framework for Data-Flow Analysis (PDF) | Ch 9.3 | ||
| Sept 24 (M) | Lattice Framework for Data-Flow Analysis cont ... | |||
| Sept 26 (W) | Optimizations using Data-Flow Analysis (PDF) | Ch 9.4 | ||
| Sept 28 (F) | At Conference -- No Class | |||
| Oct 1 (M) | Partial Redundancy Elimination (PDF) | Ch 9.5 | 9.5.1, 9.5.2 | Project 3 |
| Oct 3 (W) | Control-Flow, Loops, and Dominators (pdf) | Ch 9.6 | 9.6.1, 9.6.2, for both problems label the control flow graph with the terms header, preheader, exit node, exit edge, and back edge | |
| Oct 5 (F) | Finishing control flow | |||
| Oct 8 (M) | Loop Invariant Code Motion (PDF) | Ch 9.1.7, pg. 641-642, handout | Oct 10 (W) | Induction Variable Detection (PDF) | Ch 9.1.8 |
| Oct 12 (F) | Midterm Review | HW1 (PDF) | ||
| Oct 15 (M) | Midterm Exam (in class) | |||
| Static Single Assignment | ||||
| Oct 17 (W) | Finish induction variable elimination | (1) Write a MiniJava program that benefits from induction variable elimination and show all the steps of performing it. What changes must you make to the Assem to make induction variable elimination work? (2) Perform strength reduction and induction variable elimination on Figure 9.3 in book. | ||
| Oct 19 (F) | SSA (PDF) | Ch 6.2.4, [SSA] | Translate Figures 9.5 and 9.10 in book to SSA. | |
| Oct 22 (M) | Using SSA for Optimization (PDF) | Create an example that benefits from optimizations on SSA. | ||
| Oct 24 (W) | Value Numbering (PDF) | [Alpern and Zadeck 1992] | See slides for suggested exercises. | |
| Parallelism and Locality | ||||
| Oct 26 (F) | Parallelism and Locality (PDF) | Ch 11 through 11.2 | ||
| Oct 29(M) | Array Data Dependence Analysis (PDF) | Ch. 11.3-11.3.4, Ch 11.4-11.6 | 11.3.2, 11.3.3, 11.6.2, 11.6.5, examples in slides | |
| Oct 31 (W) | Loop transformations (PDF) | 11.7.8 | Nov 2 (F) | Transformation Frameworks I (PDF) | Project 4 |
| Nov 5 (M) | Transformation Frameworks II | [Kelly and Pugh 1993] | ||
| Nov 7 (W) | Fourier-Motzkin Elimination (PDF) | Ch 11.3 | ||
| Nov 9 (F) | Parallelization (PDF) | Ch 11.7 | ||
| Nov 12 (M) | Parallelization cont ... | |||
| Nov 14 (W) | Tiling (PDF) | book pgs. 877-880 | ||
| Nov 16 (F) | Run-time reordering transformations | [ Strout et al. 2003] | HW2 | |
| Nov 19 (M) | Fall Recess -- No Class | |||
| Nov 21 (W) | Fall Recess -- No Class | |||
| Nov 23 (F) | Fall Recess -- No Class | |||
| Interprocedural Analysis and Optimization | ||||
| Nov 26 (M) | Interprocedural Analysis (PDF) | Ch 12 through 12.2 | ||
| Nov 28 (W) | Pointer and Alias Analysis I (PDF) | Ch 12.3, Ch 12.4 | Nov 30 (F) | Flow and Context Insensitive Alias Analysis (PDF) | Ch 12.5 |
| Dec 3 (M) | Context-sensitive Alias Analysis | Ch 12.6 | ||
| Emerging Topics | ||||
| Dec 5 (W) | Beyond optimization - Bug Detection (PDF) | Finding Bugs is Easy by Hovemeyer and Pugh | ||
| Dec 7 (F) | Wrap up (PDF) | HW3 (HW3) | ||
| Dec 11 (T) | Final Exam (1:30pm-3:30pm) | |||
A number of these slides originated from a collaboration between Calvin Lin at the University of Texas and E Christopher Lewis at the University of Pennsylvania. They have been modified with their permission.