Advanced Compiler Design
(Kompilatorteknik DV2)
Fourth Year (D-Level) Course (1DL520)


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.


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 1715-17 1112 Introduction to Optimizing Compilers Slides; Ch. 1; Ch. 8.1,8.2,8.4
2 Jan 1815-17 1112 Introduction to Erlang Slides; Extensive on-line documentation
3 Jan 2010-12 1112 Using Dataflow Analysis for Global Optimization Slides; Ch. 9.1,9.2
4 Jan 2115-17 1112 Foundations of Dataflow Analysis Slides; Ch. 7.1-7.5,8.1-8.5
5 Jan 3115-17 1112 Introduction to Abstract Interpretation same as above
6 Feb 113-15 1146 Control-Flow Optimizations Slides; Ch. 8.11; Ch. 9.3
7 Feb 213-15 1112 Static Single Assignment Form Slides; Ch. 8.11; Ch. 9.3
8 Feb 315-17 1112 Global Optimizations on SSA Form Slides; Ch. 12.6; Ch. 10.3,10.4.1
9 Feb 413-15 1112 Global Register Allocation Slides; Ch. 16; Ch. 13.1-13.5
10 Feb 78-10 1112 The HiPE Compiler: An Overview Slides; Paper 1
11 Feb 1813-15 2344 Virtual Machines and their Interpreters Slides; Papers 3 & 4
12 Feb 2213-15 1212 Automatic Memory Management: Basic Algorithms Slides; Paper 2
13 Feb 2215-17 1212 Automatic Memory Management: Incremental and Concurrent Algorithms same as above
14 Feb 2310-12 1213 Garbage Collection in Oracle's JVMs — lecture by Bengt Rutisson, Oracle Slides
15 Feb 2813-15 1113 Implementation of Object-Oriented Languages — lecture by Tobias Wrigstad Slides
16 Mar 713-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:
  1. Steven Muchnick, Advanced Compiler Design & Implementation, Morgan Kaufmann, August 1997.
  2. Keith Cooper and Linda Torczon, Engineering a Compiler, Morgan Kaufmann, October 2003.
In addition, we will use material from:

Additional Information:

Valid HTML 4.01!

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