Advanced Compiler Techniques (Fall 2011)
 

Class Meetings      Instructors     Course Syllabus      Course Project      Grading       Links


NEWS & NOTIFICATIONS:


CLASS MEETINGS

Tentative Schedule (subject to change):

Date Topic Homework Project Schedule Reading List
9/8 Course Introduction/Compiler Review (Slides)      
9/15 [Dragon S8.4-8.5, S8.7, S9.2] Introduction to Optimization (Slides),     [Backus'57
9/22 [Dragon S9.2] Data Flow Analysis(Slides) HW#1 Solutions    
9/29 [Dragon S9.3] DFA Foundations (Slides)   Project Introduction []
10/6 No Class (Holiday)      
10/13 DFA Foundations (continue) HW#2 Solutions    
10/20 [Dragon S9.3-9.5] Partial Redundancy Elimination (Slides) HW#3 Solutions Project Proposal due  
10/27 No Class (Instructor Out of Town)      
11/3 [Dragon S9.6-9.7] Loops (Slides)
Project Proposal Presentation
HW#4 Solutions    
11/10 [Tiger S9.1-9.3,  Extra Readings Cytron'91, Kennedy'99 (Chow'97 )] SSA & its Applications (Slides) HW#5  Solutions   [Cytron'91]
11/17 Interprocedural Analysis (Slides), Midterm Review  (Sample Midterm, Solution)      
11/24 Midterm Exam   Progress Report due  
12/1 Pointer Analysis (Slides)      
12/8 Guest Lecture by Prof. Yifeng Chen: Program optimization for GPU  
12/15 Parallelism and Locality (Slides)      
12/22 Final Project Presentation   Final Report due  

INSTRUCTORS

Yao Guo
1428 Science Building
Telephone: 6275-3496
Email: yaoguo 'at' sei.pku.edu.cn

Office Hours: 4-5:30 Tuesdays, or by appointment (Email preferred).

TA: TBD


COURSE SYLLABUS

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.

Topics Covered:

  1. Compiler techniques review: lexical & syntax analysis, intermediate representation (AST), etc.
  2. Introduction to compiler analysis & optimization.
  3. Data flow analysis: basic concepts (basic blocks, CFG, DFG, Def-Use Set), mathematic foundation (semi-lattice, formal representation), etc.
  4. Basic compiler optimizations: constant propagation, basic loop optimization, partial redundancy elimination, SSA (static single assignment) and its application.
  5. Pointer analysis: introduction, flow-insensitive analysis, context-sensitive/insensitive analysis, speed optimization, recent progress.
  6. Localization & parallelization: program localization optimization, parallelization optimization, optimization for multi-core/many-core.
  7. Advance topics: (based on students' interests) register allocation, dynamic compilation, garbage collection, etc.

Recommended Text:

  1. (Dragon Book) Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, & Tools (Second Edition), Addison-Wesley, 2007.

Reference Text:

  1. (Whale Book) Steven Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufman Publishers, 1997
  2. (Tiger Book)Andrew W. Appel and Jens Palsberg, Compiler Implementation in Java (2nd Ed.), Cambridge University Press, 2002
  3. (Ark Book) Keith D. Cooper, Linda Torczon, Engineering a Compiler, Morgan Kaufman Publishers, 2003

Supplemental Readings:

  1. [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.
  2. [Static Analysis] Michael I. Schwartzbach, Lecture Notes on Static Analysis (slides)
  3. [Cytron'91] [SSA] Cytron, R., et al., Efficiently computing static single assignment form and the control dependence graph. TOPLAS, 1991. 13(4): p. 451-490.
  4. [Kennedy'99] [SSA Application] Kennedy et. al., Partial redundancy elimination in SSA form, in TOPLAS 1999.
  5. [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. 273-286.
  6. [SSA extra] Brandis, M.M. and H. Mossenbock, Single-pass generation of static single-assignment form for structured languages. TOPLAS, 1994. 16(6): p. 1684-1698.
  7. [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.

COURSE PROJECT

Detailed Project Information.


COURSE GRADING

Grading will be based on the following components:


LINKS


Last updated: 2011-12-22 18:02:17