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"

none

INR318

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.

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.
5. 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.
6. 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.
   
7. Global Register Allocation
   Slides as PDF 6/p or 1/p.
   Read: M: Ch 11 A: Ch 16. E: Ch 13.
8. Code Scheduling
   Slides as PDF 6/p or 1/p.
   Read: M: Ch 20 A: Ch 17. E: Ch 12.
9. 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.
10. Implementation of Concurrency

Slides as PDF 6/p or 1/p.

11. (Automatic) Memory Management
    Slides as PDF 6/p or 1/p.
    Read: M: Ch 13, (Ch 21) A: (Ch 20.) E: Ch 6.7.
12. Virtual Machines, Interpretation Techniques, and Just-In-Time Compilers.
    Slides as PDF 6/p or 1/p.
    
13. Bits and pieces, such as implementation of exceptions, linkers and loaders.
    Q&A.
    Summary.
    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").

• Due date: 230404
• Start date: 260304
• Credits: 15%
• Project details
• Framework

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.

• Due date: 180604
• Start date: 230404
• Credits: 25% (PRELIMINARY)
• Project details
• Framework
• Results

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

• Andrew W. Appel, Modern compiler implementation in Java (second edition). Cambridge University Press, 2002, ISBN 052182060X. Denoted as M.

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

Handouts

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.

• Erik Stenman, none, +46-702705615
• Michel Schinz, INR318, 34209

• VM Seminar the page is in Finish but the slides are in English.
• A Memory Managment glossary
• Catalog of Compiler Construction Tools
• Compilers newsgroup: comp.compilers
• Java Language Specification
• Java 2 platform
• Local Java resources