Schedule

Date	Leader	Topic
August 30		Welcome & Overview On Proebsting’s Law Kevin Scott
September 2	Labor Day
September 4	Adrian	Performance and Measurement Producing Wrong Data Without Doing Anything Obviously Wrong! Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, and Peter F. Sweeney. ASPLOS 2009. SIGPLAN Empirical Evaluation Guidelines
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 Type-Based Alias Analysis Amer Diwan, Kathryn S. McKinley, and J. Eliot B. Moss.
October 4	Gautam & Eashan	Basic Block Placement Codestitcher: inter-procedural basic block layout optimization Rahman Lavaee, John Criswell, and Chen Ding. CC 2019.
October 7	Henry & Wen-Ding	Instruction Scheduling Efficient instruction scheduling for a pipelined architecture Philip B. Gibbons and Steven S. Muchnick. CC 1986.
October 9	Horace & Gabriela	Loop Optimization Design Review: BrilDB, by Mark Compiler optimizations for improving data locality Steve Carr, Kathryn S. McKinley, and Chau-Wen Tseng. ASPLOS 1994.
October 11	Adrian out of town
October 14	Fall break
October 16	Adrian	LLVM Overview Design Review: Shrimp, by Sam & Rachit LLVM for Grad Students
October 18	Hongbo	Shared-Memory Parallelism Design Review: Memory, by Ryan & Drew The “Double-Checked Locking is Broken” Declaration David Bacon, Joshua Bloch, Jeff Bogda, Cliff Click, Paul Haahr, Doug Lea, Tom May, Jan-Willem Maessen, Jeremy Manson, John D. Mitchell, Kelvin Nilsen, Bill Pugh, and Emin Gün Sirer.
October 21	Neil & Edwin	Memory Consistency Design Review: Functions & PBT, by Alexa & Greg Threads cannot be implemented as a library Hans-J. Boehm. PLDI 2005.
October 23	Drew & Josh	Thread-Level Speculation Design Review: Autograd, by Qian & Horace POSH: a TLS compiler that exploits program structure Wei Liu, James Tuck, Luis Ceze, Wonsun Ahn, Karin Strauss, Jose Renau, and Josep Torrellas. PPoPP 2006.
October 25	Dietrich	Profiling Design Review: Bril2C, by Wen-Ding Efficient path profiling Thomas Ball and James R. Larus. MICRO 1996.
October 28	Rachit	Dynamic Languages An efficient implementation of SELF, a dynamically-typed object-oriented language based on prototypes C. Chambers, D. Ungar, and E. Lee. OOPSLA 1989.
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 Reconsidering custom memory allocation Emery D. Berger, Benjamin G. Zorn, and Kathryn S. McKinley. OOPSLA 2002.
November 6		Garbage Collection
November 8	Mark & Qian	GC & Reference Counting A Unified Theory of Garbage Collection David F. Bacon, Perry Cheng, and V. T. Rajan. OOPSLA 2004.
November 11	Siqiu	Modern Garbage Collection Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance Stephen M. Blackburn and Kathryn S. McKinley. PLDI 2008.
November 13	Yi	Conservative Garbage Collection Design Review: Loop Invariant Code Motion, by Rolph & G.C.C. Space efficient conservative garbage collection Hans-J. Boehm. PLDI 1993.
November 15	Adrian out of town
November 18	Sean	Spatial Architectures Design Review: Stochastic Superoptimization, by Eashan Scaling to the End of Silicon with EDGE Architectures Doug Burger, Stephen W. Keckler, Kathryn S. McKinley, Mike Dahlin, Lizy K. John, Calvin Lin, Charles R. Moore, James Burrill, Robert G. McDonald, William Yoder, and the TRIPS Team. IEEE Computer in 2004. A spatial path scheduling algorithm for EDGE architectures Katherine E. Coons, Xia Chen, Doug Burger, Kathryn S. McKinley, and Sundeep K. Kushwaha. ASPLOS 2006.
November 20	Katy & Shaojie	Synthesis-Aided Compilers Design Review: Code Layout, by Gautam Chlorophyll: synthesis-aided compiler for low-power spatial architectures Phitchaya Mangpo Phothilimthana, Tikhon Jelvis, Rohin Shah, Nishant Totla, Sarah Chasins, and Rastislav Bodik. PLDI 2014.
November 22	Ryan	Dynamic Binary Translation Design Review: Loop Unrolling, by Shaojie & Yi-Hsiang & Yuan The Transmeta Code Morphing™ Software: using speculation, recovery, and adaptive retranslation to address real-life challenges James C. Dehnert, Brian K. Grant, John P. Banning, Richard Johnson, Thomas Kistler, Alexander Klaiber, and Jim Mattson. CGO 2003.
November 25	Zhijing & Chris	Compiler Fuzzing I Design Review: Auto-Vectorization, by Katy & Henry Finding and understanding bugs in C compilers Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. PLDI 2011.
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 Compiler validation via equivalence modulo inputs Vu Le, Mehrdad Afshari, and Zhendong Su. PLDI 2014.
December 6	Alexa	Automatic Verification Design Review: Path Profiling, by Daniel Provably correct peephole optimizations with Alive Nuno P. Lopes, David Menendez, Santosh Nagarakatte, and John Regehr. PLDI 2015.
December 9	Daniel W. & Sam	Interactive Verification Design Review: Partial Redundancy Elimination, by Siqiu Formal verification of a realistic compiler. Xavier Leroy. CACM in 2009.