Date Leader Topic
August 30 Welcome & Overview
September 2 Labor Day
September 4 Adrian Performance and Measurement
September 6 Representing Programs
  • Concrete syntax, abstract syntax trees, instructions, control flow graphs, and basic blocks.
  • An introduction to Bril.
  • Derive the algorithm for forming basic blocks and CFGs thereof from flat lists of instructions. Then implement them for Bril.
  • For more reading, try Chapter 2 of Static Program Analysis by Anders Møller and Michael I. Schwartzbach.
  • Homework: Implement a CFG extractor. Convince yourself it's correct.
September 9 PL retreat
September 11 Local Analysis & Optimization
  • Report back on your CFG extractor.
  • Derive algorithms for simple dead code elimination: deleting globally unused instructions and locally "killed" instructions.
  • Local vs. global reasoning.
  • Homework: Implement "trivial" dead code elimination, in which you delete instructions that are never used before they are reassigned. Remember to iterate to convergence.
September 13 Local Value Numbering
  • Consider the common thread between dead code elimination (DCE), copy propagation, and common subexpression elimination.
  • Value numbering is a general framework for understanding & optimizing computations.
  • If you can deeply understand the mystical metaphysics of value numbering, you will have gotten most of what you need to get out of this part of 6120.
  • For more context and an alternate presentation, see these slides from Phil Gibbons at CMU.
  • Homework: Implement local value numbering. Make sure it eliminates some common subexpressions. Try pairing it with trivial dead code elimination as a post-processing step.
September 16 Extending Value Numbering
  • LVN can subsume constant folding, copy propagation, and algebraic identities. You will need to extend it with language semantics.
  • Write complete pseudocode for the base LVN algorithm, and work out where the "extension points" need to be to capture those optimizations.
  • Homework: Extend your LVN implementation to optimize the trickier examples given in class.
September 18 Data Flow
  • Follow up from last time: annotate the LVN pseudocode with extension points.
  • Reaching definitions are an example of a global property that require you to look at an entire CFG.
  • Terminology: definition, use, available, kills.
  • The data flow framework.
  • Instantiating the the data flow framework for reaching definitions.
  • The worklist algorithm for solving data flow.
  • For a longer introduction to data flow, see the CS 4120 notes.
  • For more on fixed point algorithms for solving data flow, see Section 5.3 of Static Program Analysis.
September 20 Adrian out of town
September 23 Instantiating Data Flow
  • More on solving data flow equations with a worklist algorithm.
  • The requirements for a general data flow analysis.
  • Demonstrating a simple generic implementation.
  • More examples of things you can do with the data flow framework.
  • Homework: Implement at least one data flow analysis. For bonus “points,” implement a generic solver that supports multiple analyses.
September 25 Global Analysis
  • Dominators & post-dominators.
  • An algorithm for finding dominators.
  • Reducible control flow & natural loops.
  • Loop-invariant code motion.
  • Homework: Implement the algorithm for finding domintors. For bonus “points,” also try computing the dominance tree and the domination frontier.
September 27 Static Single Assignment (SSA)
  • Defining SSA.
  • Derive the algorithms for converting to and from SSA.
  • An application: global value numbering.
  • Homework: Implement the “into SSA” and “out of SSA” transformations on Bril functions.
September 30 Alias Analysis
  • Stating the alias analysis problem. May alias & must alias.
  • Instantiating data flow for intraprocedural alias analysis.
  • Heap models.
  • Scalable & precise alias analysis remains an open problem. For much more, see Pointer Analysis, a tutorial by Yannis Smaragdakis and George Balatsouras.
October 2 Yuan Alias-Based Optimization
October 4 Gautam & Eashan Basic Block Placement
October 7 Henry & Wen-Ding Instruction Scheduling
October 9 Horace & Gabriela Loop Optimization
  • Design Review: BrilDB, by Mark
October 11 Adrian out of town
October 14 Fall break
October 16 Adrian LLVM Overview
  • Design Review: Shrimp, by Sam & Rachit
October 18 Hongbo Shared-Memory Parallelism
  • Design Review: Memory, by Ryan & Drew
October 21 Neil & Edwin Memory Consistency
October 23 Drew & Josh Thread-Level Speculation
  • Design Review: Autograd, by Qian & Horace
October 25 Dietrich Profiling
  • Design Review: Bril2C, by Wen-Ding
October 28 Rachit Dynamic Languages
October 30 Phil Tracing
  • Trace-based just-in-time type specialization for dynamic languages
    Andreas Gal, Brendan Eich, Mike Shaver, David Anderson, David Mandelin, Mohammad R. Haghighat, Blake Kaplan, Graydon Hoare, Boris Zbarsky, Jason Orendorff, Jesse Ruderman, Edwin W. Smith, Rick Reitmaier, Michael Bebenita, Mason Chang, and Michael Franz. PLDI 2009.
November 1 Sameer Meta-JITs
  • One VM to rule them all
    Thomas Würthinger, Christian Wimmer, Andreas Wöß, Lukas Stadler, Gilles Duboscq, Christian Humer, Gregor Richards, Doug Simon, and Mario Wolczko. Onward! 2013.
November 4 Oliver Memory Allocation
November 6 Garbage Collection
November 8 Mark & Qian GC & Reference Counting
November 11 Siqiu Modern Garbage Collection
November 13 Yi Conservative Garbage Collection
November 15 Adrian out of town
November 18 Sean Spatial Architectures
November 20 Katy & Shaojie Synthesis-Aided Compilers
November 22 Ryan Dynamic Binary Translation
November 25 Zhijing & Chris Compiler Fuzzing I
November 27 Thanksgiving break
November 29 Thanksgiving break
December 2 Snow Day!
December 4 Rolph & Greg Compiler Fuzzing II
  • Design Review: MemPass, by Eashan & Sameer
December 6 Alexa Automatic Verification
December 9 Daniel W. & Sam Interactive Verification
  • Design Review: Partial Redundancy Elimination, by Siqiu