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 1615–17 1245 Introduction to Optimizing Compilers Slides; Ch. 1 or Ch. 8.1,8.2,8.4
2 Jan 1810–12 1145 Using Program Analysis for Optimization Slides; Ch. 9.1,9.2 or Ch. 9.1,9.2
3 Jan 1813–15 1145 Foundations of Dataflow Analysis Slides; Ch. 9.3 or Ch. 7.1-7.5,8.1-8.5
4 Jan 1910–12 1112 Introduction to Abstract Interpretation same as above
5 Jan 2010–12 1112 Control-Flow Optimizations Slides; Ch. 8.11 or Ch. 9.3
6 Jan 2713–15 1245 Static Single Assignment Form Slides; Ch. 8.11 or Ch. 9.3
7 Jan 3013–15 1146 Global Register Allocation Slides; Ch. 16 or Ch. 13.1–13.5
8 Feb 113–15 1146 Instruction Scheduling Slides
9 Feb 215–17 1245 The HiPE Compiler: An Overview Slides and Paper 1
10 Feb 613–15 1146 Lab with HiPE internals
11 Feb 813–15 1146 Virtual Machines and their Interpreters Slides and Papers 3 & 4
12 Feb 915–17 1245 Automatic Memory Management: Basic Algorithms Slides and Paper 2
13 Feb 1010–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:
  1. Steven Muchnick, Advanced Compiler Design & Implementation, Morgan Kaufmann, August 1997.
  2. Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd Edition, Addison-Wesley, 2006
  3. Keith Cooper and Linda Torczon, Engineering a Compiler, 2nd Edition, Morgan Kaufmann, 2011.
In addition, we will use material from:

Additional Information:


Valid HTML 4.01!

Last modified: Thu Feb 9 20:27:08 2012.