The student will learn about techniques used to implement high level languages and interpreters, 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 severel projects in the context of an actual compiler and virtual machine.

• 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.
• 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.

The course will include several practical projects.

The projects count towards 70% of the final grade. The rest of 30% is given by the exam. The 70% are distributed unevenly between the 5 projects. Check each project for its assigned weight.

none

INR321

1. General course introduction.
Slides as PDFs 6/page b&w, 1/page color.
2. Project introduction.
Slides as PDFs 6/page b&w, 1/page color.
3. Interpreters and virtual machines.
Slides as PDFs 6/page b&w, 1/page color.
4. Memory management (part I).
Slides as PDFs 6/page b&w, 1/page color, 1/page color with animations.
5. Memory management (part II).
Slides as PDFs 6/page b&w, 1/page color, 1/page color with animations.
6. Object-oriented languages.
Slides as PDFs 6/page b&w, 1/page color, 1/page color with animations.
7. Functional languages (part I: functions).
Slides as PDFs 6/page b&w, 1/page color.
8. Functional languages (part II: tail calls).
Slides as PDFs 6/page b&w, 1/page color.
9. Functional languages (part III: continuations).
Slides as PDFs 6/page b&w, 1/page color.
10. Introduction to program optimisation.
Slides as PDFs 6/page b&w, 1/page color.
11. Data-flow analysis.
Slides as PDFs 6/page b&w, 1/page color.
12. Data-flow analysis (part II).
Slides as PDFs 6/page b&w, 1/page color.
13. Register allocation.
Slides as PDFs 6/page b&w, 1/page color, 1/page color with animations.
14. SSA form.
Slides as PDFs 6/page b&w, 1/page color.
15. Instruction scheduling.
Slides as PDFs 6/page b&w, 1/page color.

This first session will familiarize you with the framework you will be working for the rest of this course. You will not be graded, but you absolutely need to complete this part in order to work on the more advanced projects.

• Description: Part 0
• Start Date: March 17, 2006
• End Date: March 24, 2006
• Framework: project.zip

In this project you will implement threaded mode interpretation in minivm.

• Description: Part 1
• Start Date: March 24, 2006
• End Date: April 7, 2006
• Weight: 6%
• Framework: project.zip

In this project you will implement mark & sweep garbage collection.

• Description: Part 2
• Start Date: April 7, 2006
• End Date: May 5, 2006
• Weight: 14%
• Framework: project.zip (same as before)

In this project you will implement closure conversion.

• Description: Part 3
• Start Date: May 5, 2006
• End Date: May 19, 2006
• Weight: 14%
• Framework: project.zip (same as before)

In this project you will implement tail call elimination.

• Description: Part 4
• Start Date: May 19, 2006
• End Date: May 26, 2006
• Weight: 6%
• Framework: project.zip (same as before)

For this part you should choose an advanced project.

• Description: Part 5
• Start Date: June 2nd, 2006
• End Date: June 23, 2006
• Weight: 30%
• Framework: project.zip (same as before)

• Michel Schinz, none, none
• Iulian Dragos, INR321, 36864

• 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
• Scala homepage
• Scheme homepage