Cooper: Engineering a Compiler, 2e Lecture Slides
Lectures from "Advanced Compiler Construction" at Rice University
Core Lectures
- Introduction
- The IBM Fortran H Compiler
- Terminology, Principles, & Concerns, I with lessons from local value numbering (EaC2e Section 8.4.1)
- Terminology, Principles, & Concerns, II with lessons from superlocal value numbering (EaC2e Section 8.5.1)
- Terminology, Principles, & Concerns, III with lessons from dominance (EaC2e Section 9.2.1) and DVNT (EaC2e Section 10.5.2)
- Terminology, Principles, & Concerns, IV with lessons from live analysis (EaC2e Sections 8.6.1 and 9.2.2) and global block positioning (EaC2e Section 8.6.2)
- A Taxonomy of Optimizations (EaC2e Section 10.1)
Papers on Compilers
- The Bliss-11 Compiler, not in PowerPoint
- The Dynamo System
- The IBM Fortran H Compiler (duplicate copy)
- The IBM PL.8 Compiler
- The Deutsch-Schiffman Smalltalk-80 System
Data-Flow Analysis
- Introduction to Data-Flow Analysis
- Def-Use Chains
- Proliferation of Data-Flow Problems
- Building SSA, I
- Building SSA, II
- Using SSA
- Interval Analysis
- Alternative Intro to DFA, based on availability and global common subexpression elimination
Optimizations
- Useless Code Elimination, the "DEAD" algorithm from EaC2e Section 10.2.1
- Eliminating Useless Control Flow, the "CLEAN" algorithm from EaC2e Section 10.2.2
- Constant Propagation on SSA Form, the Wegman-Zadeck algorithms
- Loop Invariant Code Motion, a classic approach
- Lazy Code Motion
- Code Motion of Control Structures, the Cytron-Lowry-Zadeck Algorithm
- Algebraic Reassociation of Expressions, slanted toward improving Lazy Code Motion
- Code Replication & Code Consolidation
- Operator Strength Reduction on SSA Form
- 31. Loop-oriented Optimizations
- Profile-Guided Code Positioning, (Some of this material has moved, at Rice, into the
undergraduate course because most of this material appears in EaC2e Chapter 8.)
- Optimizations to Reduce Code Size
- Compiling for Reduced Energy Consumption, (very preliminary)
- The Partitioning Algorithm for Detecting Congruent (Redundant) Expressions
- Eliminating Array Bounds Checks
Interprocedural Analysis and Optimization
- Overview of Interprocedural Analysis and Optimization (two lectures)
- Older lecture on Interprocedural Analysis with different selection of material
- Older lecture on Interprocedural Optimziation with different selection of material
Code Generation Issues
- Graph Coloring Register Allocation, beyond the lecture from the undergraduate course
- Combining Scheduling and Register Allocation
- The Koblenz/Callahan Allocator, a hierarchical coloring approach
- Peephole Optimization, as a standalone optimization (rather than an instruction selection mechanism)
Adaptive Behavior
The work in this section is highly biased toward work at Rice. Some of it may be of interest, but if you teach this material, you may want to add other perspectives.
- Adaptive Tile Size Selection in the MIPSPro Compiler, presentation by Todd Waterman at LACSI Symposium, 2003
- History of work on Adaptive Sequence Finding at Rice
- 2003 Lecture with More Detailed Results on Finding Optimization Sequences
- Evolving the Next Generation of Compilers, keynote talk from CGO 2004
- Moving Adaptation into Individual Optimizations, keynote talk from SMART 2010
Miscellany
- Ten Hardware Features That Affect Optimization, a dated lecture, but one that was a good idea. An updated version would be fun to give and informative for students. We include it here as a suggestion.
- The Last Lecture
- Miscellaneous Slides, a collection of slides that get stuck into random places in the course