Advanced Compiler Design


Advanced Compiler Design
(Kompilatorteknik DV2)

Fourth Year (D-Level) Course (1DL520)

News:

The schedule of the course (also available here), pointers to the lecture notes, and reading instructions for the topics covered in the lectures appear below.

Course Description:

The lecture part of the course will study the construction of optimizing compilers with a focus on uniprocessor architectures. Topics that we will examine include foundations of data-flow analysis, use of dataflow analysis for program optimization, and code generation across basic blocks, procedures, and complete programs. Classical topics such as interprocedural and intraprocedural analysis, intermediate representations such as control-flow graphs in static single assignment (SSA) form and algorithms for register allocation will be presented in the context of modern optimizing compilers. 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, dynamic (just-in-time) and adaptive compilers, and uniprocessor garbage collector techniques.
The course will also include some hands-on experience with various implementation aspects of modern programming languages. As examples of implementing languages via virtual machine interpreters, we will study in depth the implementation of the virtual machine for executing Erlang and we will overview the Java Virtual Machine (JVM). As examples of implementing high-level languages, we will study implementation aspects of functional and object-oriented programming languages. Two guest lectures on implementing features of object oriented languages and garbage collectors in the context of Java-like languages will also be given this year.

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. The programming project provides experience with implementation issues and allows students to evaluate the impact of many of the techniques covered in the course in the context of an actual ``real-world'' compiler.

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) and Adaptive Compilation, Runtime System Architectures and Automatic Memory Management Techniques.

Class Schedule:

Num	Date	Time	Place	Topics Covered	Read
1	Jan 17	15-17	1112	Introduction to Optimizing Compilers	Slides; Ch. 1; Ch. 8.1,8.2,8.4
2	Jan 18	15-17	1112	Introduction to Erlang	Slides; Extensive on-line documentation
3	Jan 20	10-12	1112	Using Dataflow Analysis for Global Optimization	Slides; Ch. 9.1,9.2
4	Jan 21	15-17	1112	Foundations of Dataflow Analysis	Slides; Ch. 7.1-7.5,8.1-8.5
5	Jan 31	15-17	1112	Introduction to Abstract Interpretation	same as above
6	Feb 1	13-15	1146	Control-Flow Optimizations	Slides; Ch. 8.11; Ch. 9.3
7	Feb 2	13-15	1112	Static Single Assignment Form	Slides; Ch. 8.11; Ch. 9.3
8	Feb 3	15-17	1112	Global Optimizations on SSA Form	Slides; Ch. 12.6; Ch. 10.3,10.4.1
9	Feb 4	13-15	1112	Global Register Allocation	Slides; Ch. 16; Ch. 13.1-13.5
10	Feb 7	8-10	1112	The HiPE Compiler: An Overview	Slides; Paper 1
11	Feb 18	13-15	2344	Virtual Machines and their Interpreters	Slides; Papers 3 & 4
12	Feb 22	13-15	1212	Automatic Memory Management: Basic Algorithms	Slides; Paper 2
13	Feb 22	15-17	1212	Automatic Memory Management: Incremental and Concurrent Algorithms	same as above
14	Feb 23	10-12	1213	Garbage Collection in Oracle's JVMs — lecture by Bengt Rutisson, Oracle	Slides
15	Feb 28	13-15	1113	Implementation of Object-Oriented Languages — lecture by Tobias Wrigstad	Slides
16	Mar 7	13-15	1146	Compilers for Embedded Systems — lecture by Johan Runeson, IAR	TBA

Course Materials:

The instructor strongly recommends at least one of the following two books that nicely describe in depth most of the topics covered in the course:

Steven Muchnick, Advanced Compiler Design & Implementation, Morgan Kaufmann, August 1997.
Keith Cooper and Linda Torczon, Engineering a Compiler, Morgan Kaufmann, October 2003.

In addition, we will use material from:

Various handouts and research papers (required reading).
1. K. Sagonas, M. Pettersson, R. Carlsson, P. Gustafsson, and T. Lindahl.
  "All you wanted to know about the HiPE compiler".
  In Proceedings of the ACM SIGPLAN Erlang workshop, pages 36-43, August 2003.
2. 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.)
3. Stephan Diehl, Pieter Hartel, and Peter Sestoft.
  "Abstract machines for programming language implementation".
  Future Generation Computer Systems, 16(7):739-751, May 2002.
4. John Aycock.
  "A brief history of Just-In-Time".
  ACM Computing Surveys, 35(2):97-113, May 2003.
Slides of the lectures (required reading).
Other research papers (recommended reading).
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.

Additional Information:

Last modified: Mon Feb 28 15:28:10 2011.