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 16	15–17	1245	Introduction to Optimizing Compilers	Slides; Ch. 1 or Ch. 8.1,8.2,8.4
2	Jan 18	10–12	1145	Using Program Analysis for Optimization	Slides; Ch. 9.1,9.2 or Ch. 9.1,9.2
3	Jan 18	13–15	1145	Foundations of Dataflow Analysis	Slides; Ch. 9.3 or Ch. 7.1-7.5,8.1-8.5
4	Jan 19	10–12	1112	Introduction to Abstract Interpretation	same as above
5	Jan 20	10–12	1112	Control-Flow Optimizations	Slides; Ch. 8.11 or Ch. 9.3
6	Jan 27	13–15	1245	Static Single Assignment Form	Slides; Ch. 8.11 or Ch. 9.3
7	Jan 30	13–15	1146	Global Register Allocation	Slides; Ch. 16 or Ch. 13.1–13.5
8	Feb 1	13–15	1146	Instruction Scheduling	Slides
9	Feb 2	15–17	1245	The HiPE Compiler: An Overview	Slides and Paper 1
10	Feb 6	13–15	1146	Lab with HiPE internals
11	Feb 8	13–15	1146	Virtual Machines and their Interpreters	Slides and Papers 3 & 4
12	Feb 9	15–17	1245	Automatic Memory Management: Basic Algorithms	Slides and Paper 2
13	Feb 10	10–12	1145	Automatic Memory Management: Incremental and Concurrent Algorithms	same as above

Course Materials:

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

Steven Muchnick, Advanced Compiler Design & Implementation, Morgan Kaufmann, August 1997.
Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd Edition, Addison-Wesley, 2006
Keith Cooper and Linda Torczon, Engineering a Compiler, 2nd Edition, Morgan Kaufmann, 2011.

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: Thu Feb 9 20:27:08 2012.