Advanced Compiler Techniques


Advanced Compiler Techniques
(Kompilatorteknik DV2)

Fourth Year (D-Level) Course
Period 3, January-February 2004 (2AD518)

Instructor: Kostis Sagonas <kostis AT it.uu.se>

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

Registration list

News:

The schedule of the course appears below. First lecture and registration is on Tuesday January 20th, 15-17, in Polacksbacken, Hus 1, 245. If interested in registering for the course, please show up in the first lecture (or mail the instructor about it, if you cannot attend).

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, dynamic (just-in-time) and adaptive compilers, and uniprocessor garbage collector techniques. As examples of implementing languages via virtual machine interpreters, we will study the virtual machines for executing Erlang and Prolog. As examples of implementing high-level languages, we will study implementation aspects of functional and logic programming languages.

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 many of the techniques covered in the course in the context of an actual compiler used for developing big ``real-world'' applications in the telecom and internet domain.

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	Tue 20/1	15-17	1245	Introduction to Optimizing Compilers	Ch. 1; Ch. 8.1,8.2,8.4
2	Wed 21/1	15-17	1245	The HiPE Compiler: An Overview	Slides; Paper 1
3	Thu 22/1	15-17	1245	Foundations of Data-Flow Analysis Introduction to Abstract Interpretation	Slides; Ch. 7.1-7.5,8.1-8.5
4	Tue 27/1	15-17	1245	Using Dataflow Analysis for Global Optimization	Slides; Ch. 9.1,9.2
5	Wed 27/1	15-17	1245	Static Single Assignment Form	Slides; Papers 2, 3; Ch. 8.11; Ch. 9.3
6	Thu 29/1	15-17	1245	SSA-based Dead Code Elimination & Sparse Conditional Constant Propagation	Slides; Paper 4; Ch. 12.6; Ch. 10.3,10.4.1
7	Mon 2/2	15-17	1245	Partial Redundancy Elimination & Lazy Code Motion	Slides; Papers 5, 6, and 7; Ch. 13.1, 13.3; Ch. 10.3.2
8	Tue 3/2	15-17	1146	Loop Optimizations	Slides; Ch. 13.2, 14.1
9	Thu 5/2	15-17	1245	Global Register Allocation	Slides; Ch. 16; Ch. 13.1-13.5
10	Mon 9/2	15-17	1245	Code Scheduling	Slides; Ch. 17.1-17.5; Ch. 12
11	Wed 11/2	15-17	1245	Automatic Memory Management	Slides; Paper 8
12	Tue 17/2	15-17	1245	Functional Programming Implementation: Some Issues	Slides
13	Wed 18/2	15-17	1245	Virtual Machines, Interpreters, and Just-In-Time Compilers	Slides; Papers 9 and 10
14	Tue 24/2	15-17	1211	Logic Programming Implementation: The WAM
15	Wed 25/2	15-17	1211	Logic Programming Implementation: Optimizations	Slides
16	Thu 25/3	13-15	1245	Project Progress Presentations

Course Materials:

The instructor strongly recommends one (or preferably both) 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 (partial list below).
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. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.)
9. Stephan Diehl, Pieter Hartel, and Peter Sestoft.
  "Abstract machines for programming language implementation".
  In Future Generation Computer Systems, 16(7):739-751, May 2002.
10. John Aycock.
  "A brief history of Just-In-Time".
  In ACM Computing Surveys, 35(2):97-113, May 2003.
Slides (for most) of the lectures

Additional Information:

Last modified: Tue Jan 20 22:18:10 MET 2004