Advanced Compiler Techniques (Fall 2009)
 

Class Meetings      Instructors     Course Syllabus      Course Project      Grading       Links

NEWS & NOTIFICATIONS:

CLASS MEETINGS

Tentative Schedule (subject to change):

Date Topic Homework Project Schedule
9/17 Course Introduction/Compiler Review (Slides)    
9/25 [Dragon S8.4-8.5, S8.7, S9.2] Introduction to Optimization (Slides), Data Flow Analysis(Slides) HW#1 (Solution)  
10/1 No Class (Holiday)    
10/8 No Class (Holiday)    
10/15 [Dragon S9.3] DFA Foundations (Slides)   Project Introduction (Soot Intro, Slides)
10/22 DFA Foundations (cont.) HW#2(Solution)  
10/29 [Dragon S9.3-9.5] Partial Redundancy Elimination (Slides) HW#3(Solution) Project Proposal due 10/29
11/5 Project Proposal Presentation    
11/12 [Dragon S9.6-9.7] Loops (Slides) HW#4(Solutions)  
11/19 [Tiger S9.1-9.3,  Extra Readings Cytron'91, Kennedy'99 (Chow'97 )] SSA & its Applications (Slides) HW#5  
11/26 Interprocedural Analysis (Slides), Midterm Review    
12/3 Midterm Exam (Sample Midterm, Solution)   Progress Report due
12/10 No Class (Instructor Out of Town)    
12/17 Pointer Analysis (Slides)    
12/24 Parallelism and Locality, Optimization for Multi-core/Many-core (Slides)    
12/31 Final Project Presentation   Final Report due (1/6)

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. [Static Analysis] Michael I. Schwartzbach, Lecture Notes on Static Analysis (slides)
  2. [SSA] Cytron, R., et al., Efficiently computing static single assignment form and the control dependence graph. TOPLAS, 1991. 13(4): p. 451-490.
  3. [SSA Application] Kennedy et. al., Partial redundancy elimination in SSA form, in TOPLAS 1999.
  4. [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.
  5. [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.
  6. [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-01-10 11:24:26