Cooper: Engineering a Compiler, 2e Lecture Slides

Lectures from "Advanced Compiler Construction" at Rice University

Core Lectures

  1. Introduction

  2. The IBM Fortran H Compiler

  3. Terminology, Principles, & Concerns, I with lessons from local value numbering (EaC2e Section 8.4.1)

  4. Terminology, Principles, & Concerns, II with lessons from superlocal value numbering (EaC2e Section 8.5.1)

  5. Terminology, Principles, & Concerns, III with lessons from dominance (EaC2e Section 9.2.1) and DVNT (EaC2e Section 10.5.2)

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

  7. A Taxonomy of Optimizations (EaC2e Section 10.1)

  8. Papers on Compilers

  9. The Bliss-11 Compiler, not in PowerPoint

  10. The Dynamo System

  11. The IBM Fortran H Compiler (duplicate copy)

  12. The IBM PL.8 Compiler

  13. The Deutsch-Schiffman Smalltalk-80 System

  14. Data-Flow Analysis

  15. Introduction to Data-Flow Analysis

  16. Def-Use Chains

  17. Proliferation of Data-Flow Problems

  18. Building SSA, I

  19. Building SSA, II

  20. Using SSA

  21. Interval Analysis

  22. Alternative Intro to DFA, based on availability and global common subexpression elimination

  23. Optimizations

  24. Useless Code Elimination, the "DEAD" algorithm from EaC2e Section 10.2.1

  25. Eliminating Useless Control Flow, the "CLEAN" algorithm from EaC2e Section 10.2.2

  26. Constant Propagation on SSA Form, the Wegman-Zadeck algorithms

  27. Loop Invariant Code Motion, a classic approach

  28. Lazy Code Motion

  29. Code Motion of Control Structures, the Cytron-Lowry-Zadeck Algorithm

  30. Algebraic Reassociation of Expressions, slanted toward improving Lazy Code Motion

  31. Code Replication & Code Consolidation

  32. Operator Strength Reduction on SSA Form

  33. 31. Loop-oriented Optimizations

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

  35. Optimizations to Reduce Code Size

  36. Compiling for Reduced Energy Consumption, (very preliminary)

  37. The Partitioning Algorithm for Detecting Congruent (Redundant) Expressions

  38. Eliminating Array Bounds Checks

  39. Interprocedural Analysis and Optimization

  40. Overview of Interprocedural Analysis and Optimization (two lectures)

  41. Older lecture on Interprocedural Analysis with different selection of material

  42. Older lecture on Interprocedural Optimziation with different selection of material

  43. Code Generation Issues

  44. Graph Coloring Register Allocation, beyond the lecture from the undergraduate course

  45. Combining Scheduling and Register Allocation

  46. The Koblenz/Callahan Allocator, a hierarchical coloring approach

  47. Peephole Optimization, as a standalone optimization (rather than an instruction selection mechanism)

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

  49. Adaptive Tile Size Selection in the MIPSPro Compiler, presentation by Todd Waterman at LACSI Symposium, 2003

  50. History of work on Adaptive Sequence Finding at Rice

  51. 2003 Lecture with More Detailed Results on Finding Optimization Sequences

  52. Evolving the Next Generation of Compilers, keynote talk from CGO 2004

  53. Moving Adaptation into Individual Optimizations, keynote talk from SMART 2010

  54. Miscellany

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

  56. The Last Lecture

  57. Miscellaneous Slides, a collection of slides that get stuck into random places in the course