Techniques (Fall 2011)
Course Project Grading
- [2011/12/22] Final Project Presentation. [Group
- [2011/11/10] Midterm date: 2011/11/24
(in-class, open-book, open-notes)
- [2011/11/03] Homework#3 due today. Project
Proposals due today. Proposal Presentation in Class!
- Time: 10-12 Thursdays
(Class starts at 6:40pm)
- Location: 2-413
Tentative Schedule (subject to change):
Introduction/Compiler Review (Slides)
||[Dragon S8.4-8.5, S8.7,
S9.2] Introduction to Optimization (Slides),
||[Dragon S9.2] Data Flow
||[Dragon S9.3] DFA
||DFA Foundations (continue)
Partial Redundancy Elimination (Slides)
||Project Proposal due
(Instructor Out of Town)
Project Proposal Presentation
Extra Readings Cytron'91,
Kennedy'99 (Chow'97 )] SSA & its Applications (Slides)
||Interprocedural Analysis (Slides),
||Progress Report due
||Pointer Analysis (Slides)
||Guest Lecture by Prof.
Yifeng Chen: Program optimization for
and Locality (Slides)
||Final Project Presentation
||Final Report due
1428 Science Building
Email: yaoguo 'at' sei.pku.edu.cn
Office Hours: 4-5:30 Tuesdays, or by appointment (Email preferred).
Built upon basic compiler knowledge, this course
covers advanced materials on compiler principles and techniques, including
data-flow analysis, basic compiler optimizations, SSA, pointer analysis,
localization and parallelization optimization, and recent progresses on program
analysis & optimization. Students are required to work on a project to implement a new analysis or optimization, or use
materials learned in class to solve a practical problem.
Prerequisite: undergraduate course on
compiler principles or techniques.
- Compiler techniques review: lexical
& syntax analysis, intermediate representation (AST), etc.
- Introduction to compiler analysis &
- Data flow analysis: basic concepts
(basic blocks, CFG, DFG, Def-Use Set), mathematic foundation (semi-lattice, formal representation), etc.
- Basic compiler optimizations:
constant propagation, basic loop optimization, partial redundancy
elimination, SSA (static single assignment) and its application.
- Pointer analysis: introduction,
flow-insensitive analysis, context-sensitive/insensitive analysis, speed
optimization, recent progress.
- Localization & parallelization:
program localization optimization, parallelization optimization,
optimization for multi-core/many-core.
- Advance topics: (based on students'
interests) register allocation, dynamic compilation, garbage collection,
- (Dragon Book) Aho, Lam, Sethi, & Ullman, Compilers:
Principles, Techniques, & Tools (Second Edition), Addison-Wesley, 2007.
- (Whale Book) Steven Muchnick,
Advanced Compiler Design and Implementation,
Morgan Kaufman Publishers, 1997
- (Tiger Book), Compiler
Implementation in Java (2nd Ed.), Cambridge University Press,
- (Ark Book) Keith D. Cooper, Linda Torczon,
Engineering a Compiler, Morgan Kaufman Publishers, 2003
- [Backus'57]] [Fortran Compiler]
Backus, Beeber, Best, Goldberg, Haibt, Herrick, Nelson, Sayre, Sheridan,
Stern, Ziller, Hughes, and Nutt,
The Fortran Automatic Coding System, Proceedings of the Western Joint
Computer Conference, pp. 187-198, Los Angeles, CA, February, 1957.
- [Static Analysis]
Michael I. Schwartzbach,
Lecture Notes on Static
- [Cytron'91] [SSA] Cytron, R., et al.,
Efficiently computing static single
assignment form and the control dependence graph. TOPLAS, 1991. 13(4):
- [Kennedy'99] [SSA Application]
Kennedy et. al., Partial redundancy
elimination in SSA form, in TOPLAS 1999.
- [Chow'97] [SSA extra] Chow, F., et al.,
A new algorithm for partial redundancy
elimination based on SSA form, in PLDI. 1997, ACM New York, NY, USA. p.
- [SSA extra] Brandis, M.M. and H. Mossenbock,
Single-pass generation of static
single-assignment form for structured languages. TOPLAS, 1994. 16(6): p.
- [SSA extra] Knobe, K. and V. Sarkar,
Array SSA form and its use in
parallelization, in POPL. 1998, ACM New York, NY, USA. p. 107-120.
Grading will be based on the following
- Homework: 20%.
- Midterm: 30%
- Final Project: 40%
- Class Participation: 10%.