Advanced Compiler Techniques (Fall 2011)
 

Class Meetings      Instructors     Course Syllabus      Course Project      Grading       Links

NEWS & NOTIFICATIONS:

• [2011/12/22] Final Project Presentation. [Group Order]
• [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!
  • Project Proposal Presentation Order.

CLASS MEETINGS

• Time:  10-12 Thursdays (Class starts at 6:40pm)
• Location:  2-413

Tentative Schedule (subject to change):

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:

• Homework: 20%.
• Midterm: 30%
• Final Project: 40%
• Class Participation: 10%.

LINKS

• Book download.

Last updated: 2022-11-03 12:08:23