Ecole Polytechnique Fédérale de Lausanne
Advanced Compiler Techniques (Compilation Avancée)
English only
Added results of project 2.
Lectures: Friday 10:15-12:00, room INN118
(Friday 13:15-14:00, room INN118)
Lab: Friday 13:15-14:00, room INF1

The student will learn about techniques used to implement high level languages, and compilation techniques used to obtain high performance on modern computer architectures. He or she will also get the opportunity to study one of these techniques in depth and gain experience with implementation issues through a project in the context of an actual compiler.

  • Optimization techniques
    • Data-flow analysis, program optimization, and code generation across basic blocks, procedures, and complete programs.
    • Interprocedural and intraprocedural analysis, intermediate representations, register allocation, and instruction scheduling.
    • Dependence analysis and loop transformations.
  • Implementation of high level languages
    • Implementation of higher order functions, coroutines, and processes.
    • Uniprocessor garbage collector techniques.
    • Virtual machines and the efficient implementation of their interpreters.

The course will include two practical projects.

Note: The examination form of the course has changed from "Branche à examen (oral) avec contrôle continu" to "Contrôle continu"

Lecturer: Dr. Erik Stenman, stairsnone, phone+46-702705615
Assistant: Michel Schinz, stairsINR318, phone34209
Course schedule
Date 10:15-12:00, room INN118 (Lecture) 13:15-14:00, room INF1 (Project)
12.03.04 Lecture 1   Lecture 2a (INN118)  
19.03.04 Lecture 2b & 3a   Lecture 3b (INN118)  
26.03.04 Lecture 4 Project 1
02.04.04 Lecture 5 Project 1
09.04.04 Good Friday  
16.04.04 Easter break  
23.04.04 Lecture 6 Project 2 (Dealine P1!)
30.04.04 Lecture 7 Project 2
07.05.04 Lecture 8 Project 2
14.05.04 Lecture 9 Project 2
21.05.04 Lecture 10 Project 2
28.05.04 Lecture 11 Project 2
04.06.04 Lecture 12 Project 2
11.06.04 Project 2,11:15-13:00 (INF1) Project 2
18.06.04 - INN 118 Summary (+Exam)
Exam schedule (paper chosen in brackets)
15.06.2004 16.06.2004 17.06.2004 18.06.2004
09:00-09:20 Martin Voelkle [7] Jonathan Maïm [8]
09:20-09:40 Xavier Perseguers [8] Pascal Jermini [2]
09:40-10:00 Peter Amrhyn [8] Christophe Dubach [8] Francesco Devittori [8]
10:00-10:20 Iulian Dragos [3] Renault John [8] Etienne Dysli [8]
10:20-10:40 Eric Winnington [8] Nicolas Blanc [2] Jérôme Maye [8]
14:00-14:20 Urs Keller [7] Olivier Crameri [8] Grégory Mermoud [8] not available
14:20-14:40 Jean-David Maillefer [1] Kaspar Schiess [7] not available
14:40-15:00 Martin Nyffenegger [7] Marius Kleiner [4] not available
15:00-15:20 Grégory Théoduloz [8] Gilles Dubochet [8] not available
  1. Introduction to Optimizing Compilers.
    Slides as PDFs 6/page, 1/page.
    Read: M: Ch 1, A: Ch 1, E: Ch 8.1,8.2,8.4
  2. Terminology, foundations of dataflow analysis (partial orders and lattices) & introduction to abstract interpretation.
    Slides as PDFs 6/page, 1/page.
    Read: M: Ch 8.2, 17.1, A: Ch 7.1-7.2, 8.1-8.2, E: Ch 9.1-9.2.
  3. Local (one basic block) optimizations: CSE, constant propagation, copy propagation, dead code elimination, (algebraic simplification, strength reduction). Using dataflow analysis (abstract interpretation) for global optimizations (one CFG): reaching definitions, available expressions, and liveness analysis.
    Slides as PDFs 6/page, 1/page.
    Read: M: Ch 17.2-17.5, A: Ch 7.3-7.5, 8.3-8.5.
  4. Static Single Assignment Form (SSA) & Dominators.

  5. Slides as PDFs 4/page, 1/page.
    Read: M: Ch 18.0-18.1, 19.0-19.2, A: Ch 8.11. E: Ch 9.3., Paper 1 & 2.
  6. PART 1: SSA-based Dead Code Elimination & Sparse Conditional Constant Propagation.
    Slides as PDF 6/p or 1/p.
    Read: M: Ch. 19.3, 19.5, A: Ch 12.6. E: Ch 10.3, 10.4.1., Paper 3.
    PART 2: Partial Redundancy Elimination.
    Slides as PDF 6/p or 1/p.
    Read: A: Ch 13.0-13.2.
  7. PART 1: Loop Optimizations.
    Slides as PDF 6/p or 1/p.
    Read: M: Ch. 18 A: Ch 13.2. .
    PART 2: Lazy Code Motion.
    Slides as PDF 6/p or 1/p.
    Read: A: Ch 13.3. E: Ch 10.3.2., Papers 4,5 & 6.
  8. Global Register Allocation
    Slides as PDF 6/p or 1/p.
    Read: M: Ch 11 A: Ch 16. E: Ch 13.
  9. Code Scheduling
    Slides as PDF 6/p or 1/p.
    Read: M: Ch 20 A: Ch 17. E: Ch 12.
  10. Summary of part 1 of the course: "Optimizations techniques".
    Slides as PDF 6/p or 1/p.
    Introduction to part 2: "Implementation of high level languages"
    Implementation of Objects and FPL (higher order functions, laziness).
    Slides as PDF 6/p or 1/p.
    Read: M: Ch 14, Ch 15 E: Ch 7.10.
  11. Implementation of Concurrency

  12. Slides as PDF 6/p or 1/p.
  13. (Automatic) Memory Management
    Slides as PDF 6/p or 1/p.
    Read: M: Ch 13, (Ch 21) A: (Ch 20.) E: Ch 6.7.
  14. Virtual Machines, Interpretation Techniques, and Just-In-Time Compilers.
    Slides as PDF 6/p or 1/p.
  15. Bits and pieces, such as implementation of exceptions, linkers and loaders.
    Slides as PDF 6/p or 1/p.

There will be two projects during the course. The performance on these projects will directly influence the grade. Students are allowed and encouraged to work in groups of two.

Like for the first compilation course, we will use Sygeco to manage the course. You are kindly asked to register yourself and your group on this system before the deadline for the first project.

The first project will be to implement a simple register allocator using Sethi-Ullman register allocation for trees. (See Chapter 11.5 in "Modern Compiler Implementation").

The second project will be to implement any number of optimizations in an existing compiler framework. To pass the performance on the benchmark-suite has to be improved by a certain percentage (TO BE ANNOUNCED).

Suggested optimizations: see the project detail page.


Note: The examination form of the course has changed from "Branche à examen (oral) avec contrôle continu" to "Contrôle continu"

There will be an oral exam during the last week of the course. This exam will cover the lecture notes (the slides) and the corresponding information that can be found in all three books. (I.e., the intersection of the information in the books. The lazy student can try to find the minimal set to read, while the highly motivated student can read all three books to get three different views on the material.) It will also cover one of the articles mentioned below (the handouts), which you will need to understand.

You will have to register for a 20 minute slot for the individual exam, by sending an email to Michel or Erik.

In order to encourage you all to come to the last lecture there will be one written question during that lecture that will also count towards your final grade.

Course book

Reference books (can also be used instead of the official course book)

  • Steven Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann, August 1997. Denoted as A.
  • Keith Cooper and Linda Torczon, Engineering a Compiler, Morgan Kaufmann, October 2003. Denoted as E.

The slides

The slides from all the lectures are available as one big (ca 5 MB) pdf file.


  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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.)
  8. Anton Ertl and David Gregg.
    Branch prediction and VM interpreters.
  9. Xavier Leroy.
    The ZINC experiment: an economical implementation of the ML language.

The Deadly Sins from P. J. Brown's Writing Interactive Compilers and Interpreters, Wiley 1979.

  • The first deadly sin is to code before you think.
  • The second deadly sin is to assume the user has all the knowledge the compiler writer has.
  • The third deadly sin is not to write proper documentation.
  • The fourth deadly sin is to ignore language standards.
  • The fifth deadly sin is to treat error diagnosis as an afterthought.
  • The sixth deadly sin is to equate the unlikely with the impossible.
  • The seventh deadly sin is to make the encoding of the compiler dependent on its data formats.
  • The eighth deadly sin is to use numbers for objects that are not numbers.
  • The ninth deadly sin is to pretend you are catering for everyone at the same time.
  • The tenth deadly sin is to have no strategy for processing break-ins.
  • The eleventh deadly sin is to rate the beauty of mathematics above the usability of your compiler.
  • The twelfth deadly sin is to let any error go undetected.
  • The thirteenth deadly sin is to leave users to find the errors in your compiler.