Advanced Compiler Techniques


Advanced Compiler Techniques (Kompilatorteknik DV2) Fourth Year (D-Level) Course Period 3, February-March 2003 (2AD518)

Instructor: Kostis Sagonas <kostis@csd.uu.se>

Instructor's Office Hours: Tuesdays and Thursdays 14:00 - 15:00

Current student registration list

News:

The course will start in the first week of February. First lecture and registration is on Tuesday February 4th, 15-17, in Polacksbacken, Hus 1, 145. If interested in registering in the course, please show up in the first lecture.

Course Description:

We will study the construction of optimizing compilers with a focus on uniprocessor architectures. The course will cover data-flow analysis, program optimization, and code generation across basic blocks, procedures, and complete programs. Classical topics such as interprocedural and intraprocedural analysis, intermediate representations, register allocation, and scheduling will be presented in the context of modern uniprocessors. The course will also cover dependence analysis and loop transformations: the building blocks for optimizing for memory hierarchies and parallel machines. Finally, the course will cover virtual machines and the efficient implementation of their interpreters, and uniprocessor garbage collector techniques.

Objective:

This course focuses on the interpretation and compilation techniques needed to obtain high performance on modern computer architectures. Program analysis and optimization techniques are presented in class lectures. Programming projects provide experience with implementation issues and allow students to evaluate the impact of each technique in the context of an actual compiler.

Prerequisites:

Kompilatorteknik DV1 or permission of the instructor.

Topics Covered:

Program Representation, Control-Flow and Data-Flow Analyses, Static Single Assignment, Global Optimizations, Partial Redundancy Elimination, Loop Optimizations, Global Register Allocation, Code Scheduling, Control-Flow and LOw-Level Optimizations, Virtual Machines and Interpretation Techniques, Just-In-Time (JIT) Compilation, Runtime System Architectures and Automatic Memory Management Techniques.

Class Schedule:

Num	Date	Time	Place	Topics Covered	Read
1	Tuesday 4/2	15-17	1145	Introduction to Optimizing Compilers	Ch. 1
2	Thursday 6/2	15-17	1212	Control-Flow Analysis	Ch. 7.1-7.5
3	Tuesday 11/2	15-17	1245	Foundations of Data-Flow Analysis	Ch. 8.1-8.5
4	Thursday 13/2	15-17	1145	Reaching Definitions, Available Expressions, and Liveness Analyses. Introduction to Abstract Interpretation.	Slides
5	Tuesday 18/2	15-17	1245	The HiPE Compiler: An Overview
6	Thursday 20/2	15-17	1145	Static Single Assignment Form	Slides Ch. 8.11 Papers 1, 2
7	Tuesday 25/2	15-17	1245	SSA-based Dead Code Elimination & Sparse Conditional Constant Propagation	Slides Ch. 12.6 Paper 3
8	Thursday 27/2	15-17	1245	Partial Redundancy Elimination & Lazy Code Motion	Slides Ch. 13.1, 13.3 Papers 4, 5
9	Tuesday 4/3	15-17	1245	Loop Optimizations	Slides Ch. 13.2, 14.1
10	Thursday 6/3	15-17	1145	Global Register Allocation	Slides Ch. 16
11	Tuesday 11/3	15-17	1145	Code Scheduling	Slides Ch. 17.1-17.5
12	Thursday 13/3	15-17	1145	Control-Flow and Low-Level Optimizations	Slides Ch. 18
13	Tuesday 18/3	15-17	1245	Automatic Memory Management	Slides Paper 7
14	Thursday 20/3	15-17	1146	Virtual Machines, Interpretation Techniques, and Just-In-Time Compilers	Slides

Course Materials:

Steven Muchnick, Advanced Compiler Design & Implementation, Morgan Kaufmann, 1998. (Required.)
Various handouts and research papers (partial list below).
1. Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck.
  "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph".
  ACM Transactions on Programming Languages and Systems (TOPLAS), 13(4):451-490, October 1991.
2. Preston Briggs, Keith D. Cooper, Timothy J. Harvey, and L. Taylor Simpson.
  "Practical improvements to the construction and destruction of static single assignment form".
  Software: Practice & Experience, 28(8):859-881, July 1998.
3. Mark N. Wegman and F. Kenneth Zadeck.
  "Constant Propagation with Conditional Branches".
  ACM Transactions on Programming Languages and Systems (TOPLAS), 13(2):181-210, April 1991.
4. Jens Knoop, Oliver Rüthing, and Bernhard Steffen.
  "Lazy Code Motion".
  Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 212-223, July 1992.
5. Karl-Heinz Drechsler and Manfred P. Stadel.
  "A Variation of Knoop, Rüthing, and Steffen's Lazy Code Motion".
  SIGPLAN Notices 28(5), pages 29-38, 1993.
6. Robert Kennedy, Sun Chan, Shin-Ming Liu, Raymond Lo, Peng Tu, and Fred Chow.
  "Partial redundancy elimination in SSA form".
  ACM Transactions on Programming Languages and Systems (TOPLAS), 21(3):627-676, May 1999.
7. Paul Wilson.
  "Uniprocessor Garbage Collection Techniques".
  (Read only Sections 1, 2, 3.1-3.3, 4.1-4.3, 4.5-4.7, 8, and 9.)
Slides (for most) of the lectures
- Foundations of Data-Flow Analysis (lectures 3 & 4).
- Static Single Assigment Form (lecture 6).
- SSA-based Optimizations (lecture 7).
- Partial Redundancy Elimination & Lazy Code Motion (lecture 8).
- Loop Optimizations (lecture 9).
- Global Register Allocation (lecture 10). Color slides are also available.
- Code Scheduling (lecture 11). Color slides are also available.
- Control-Flow and Low-Level Optimizations (lecture 12). Color slides are also available.
- Automatic Memory Management (lecture 13).
- Virtual Machines, Interpretation Techniques, and Just-In-Time Compilers (lecture 14).

Additional Information:

Last modified: Tue Mar 11 19:44:09 MET 2003

Advanced Compiler Techniques (Kompilatorteknik DV2)

Fourth Year (D-Level) Course Period 3, February-March 2003 (2AD518)