IFT 3065/6232 -- Compilation


Professeur: Stefan Monnier

Page Moodle du cours pour H2017.

Description

La connaissance intime des langages de programmation est cruciale pour pouvoir écrire des programmes fiables, portables, et efficaces.

La compréhension des techniques d'implantation des langages de programmation, autant d'interprétation, que de compilation, et donc non seulement indispensable à la réalisation de nouveaux compilateurs et la conception de nouveaux langages, mais est beaucoup plus généralement nécessaire pour écrire du code de qualité.

C'est dans cette optique que ce cours traitera des sujets qui touchent à la définition, l'interprétation, et la compilation des langages de programmation.

Les sujets suivants sont au menu, quoiqu'il n'y aura pas le temps de tous les couvrir:

Horaire

Jour Heure Lieu Type
Lundi 15h30-17h30 AA-1177 Cours
Mercredi 10h30-12h30 AA-1177 Cours
13 fév 15h30-17h30 AA-1177 Intra
19 avr 10h30-13h30 AA-1177 Final

¡¡ Premier cours lundi 9 janvier !!

Le choix des salles n'est pas sous mon contrôle et est parfois changé sans préavis, donc dans le doute, faites plutôt confiance au formulaire insupportable de Synchro

Évaluation

L'évaluation du cours se divisera en trois parties: travaux pratiques, à faire par groupe de deux (ou seul), présentations en classe, et examens

La pondération pour IFT-3065 est comme suit:

La pondération pour IFT-6232 est comme suit:

Manuels

Il n'y a pas de manuel officiel pour ce cours. Si vous voulez un livre pour accompagner ce cours, je recommande un mélange de Advanced Compiler Design & Implementation de Steven Muchnick, Building an Optimizing Compiler de Bob Morgan, Modern Compiler Implementation in ML de Andrew Appel, ainsi que Types and Programming Languages de Benjamin C. Pierce.

Notes de cours:

Ancien matériel: notes de cours, Exemple d'interpréteur

Exemple d'examen intra


Travaux Pratiques

TP #1

La donnée du travail, avec ses fichiers de soutient.

TP #2

La donnée du travail.

TP #3

La donnée du travail.

Présentations

Horaires

JourOrateurThème
27 marsÉtudiants 3065TP2
29 mars Constantin Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO
3 avril Samuel Efficient Program Compilation through Machine Learning Techniques
3 avril Vincent Optimization of range checking
5 avril Frédéric Higher-Order Distributed Objects
5 avril Constantin Improving locality of reference in a garbage-collecting memory management system
10 avril Samuel Meta Optimization: Improving Compiler Heuristics with Machine Learning
10 avril Vincent Optimisations en C++
12 avril Frédéric BIT: A Very Compact Scheme System for Microcontrollers

Pour étudiants de ift-3065

Il faut faire une présentation de 15-20 minutes qui montre le travail que vous avez fait dans le TP2: quelles optimisations vous avez choisies, et pourquoi, quels tests vous avez utilisés (et pourquoi), quels sont les résultats, un bref aperçu de quels seraient vos plans futurs si vous aviez le privilège de pouvoir continuer à travailler sur ce projet, ...

Comme mentionné, vous avez un maximum de 20 minutes pour votre présentation. Il y a une présentation par groupe de TP2.

Les présentations se feront pendant le cours du 27 mars. Je m'attends à ce que vous ayez un document à projeter pour accompagner cette présentation. Vous devez me l'envoyer par courriel en PDF avant le cours, au plus tard le 27 à midi! Je veux voir de plus une version préliminaire au plus tard le 24 mars (là encore, par courriel).

La note se divisera comme suit:

Pour étudiants de ift-6232

Il faut faire 2 présentations de 45 minutes chacune. Le sujet de chaque présentation est libre, mais doit être tiré d'un article académique, et vous devez me les soumettre pour approbation au plus tard le 21 mars, par courriel (voir liste ci-dessous si vous êtes à court d'idée). Les dates disponibles sont les cours du 29 mars, 3 avril, 5 avril, 10 avril et 12 avril. Inclure vos 3 dates préférées dans votre courriel.

Pour chaque présentation, je m'attends à ce que vous ayez un document à projeter pour accompagner cette présentation. Vous devez me l'envoyer par courriel en PDF 3h avant le cours! Je veux voir de plus (là encore, en PDF, par courriel) une version préliminaire soit le vendredi avant (pour les présentations du lundi) ou le lundi avant (pour les présentations du mercredi).

Une présentation d'article devrait:

Pour cela, il sera généralement nécessaire d'introduire divers concepts et techniques sans lesquels l'article serait incompréhensible. Aussi il sera souvent utile de remettre l'article dans son contexte: expliquer quels étaient les problèmes importants de l'époque et quels problèmes actuels ne les affectaient pas encore. Une discussion de l'impact/influence de l'article est aussi une bonne idée.

La contrainte principale est généralement le temps. Donc il vous faudra bien planifier votre présentation, en pensant à quels sont les éléments que l'audience doit vraiment comprendre. En général vous devrez pour cela éliminer toutes sortes de "détails" intéressants. Ne vous étonnez pas si vous finissez par passer 2/3 du temps d'introduction et seulement 1/3 sur l'article en soi (mais assurez-vous que vous aurez le temps d'arriver à ce tiers). Aussi pour pouvoir aller plus vite, il vous faudra utiliser des slides, ce qui vous aidera aussi à mieux structurer la présentation.

La note se divisera comme suit

Optimisations "classiques"

Optimizing indirect branch prediction accuracy in virtual machine interpreters , Kevin Casey, Anton Ertl, and David Gregg, 2007.
Optimization of range checking, Victoria Markstein, John Cocke, and Peter Markstein, 1982.
Engineering a simple, efficient code-generator generator, C. W. Fraser and D. R. Hanson and T. A. Proebsting, 1992.
Shrinking lambda expressions in linear time, Andrew Appel and Trevor Jim, JFP 1997.
Compiler-directed thermal management for VLIW functional units, M. Mutyam and F. Li and V. Narayanan and M. Kandemir, and M. J. Irwin, LCTES'2006.
Iterated register coalescing, Lal George and Andrew W. Appel, 1996.
Global optimization by suppression of partial redundancies, E. Morel and C. Renvoise, 1979.

JIT

A Third-Generation Self Implementation: Reconciling Responsiveness with Performance, Urs Hölzle and David Ungar, 1994.
Trace-based just-in-time type specialization for dynamic languages, Andreas Gal et al., 2009.
Simple and Effective Type Check Removal through Lazy Basic Block Versioning , Maxime Chevalier-Boisvert and Marc Feeley, 2015.

Analyses

Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Patrick Cousot and Radhia Cousot, 1997.
Analysis of pointers and structures, D. R. Chase and M. Wegman and F. K. Zadeck, 1990.
Control Flow Analysis in Scheme, Olin Shivers, 1988.

Représentation des types à l'exécution

Representing Type Information in Dynamically Typed Languages, David Gudeman, 1993
How to make ad-hoc polymorphism less ad hoc, P. Wadler and S. Blott, 1988
Unboxed objects and polymorphic typing, Xavier Leroy, 1992
Compiling Polymorphism Using Intensional Type Analysis, Bob Harper and Greg Morrisett, 1995
Flexible Representation Analysis, Zhong Shao, 1997
Message Dispatch on Modern Computer Architectures, Karel Driesen and Urs Hölzle and Jan Vitek, 1994

Filtrage

Compiling pattern matching, Lennart Augustsson, 1985.
Optimizing pattern matching

CPS

Debunking the "expensive procedure call" myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, 1977
ORBIT: an optimizing compiler for scheme, 1986

SSA

Global value numbers and redundant computations, B. K. Rosen and M. N. Wegman and F. K. Zadeck, 1988.
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, R. Cytron and J. Ferrante and B. K. Rosen and M. N. Wegman, 1991
A Correspondence between Continuation Passing Style and Static Single Assignment Form, 1995
SSA is Functional Programming, 1998
Simple Generation of Static Single-Assignment Form, 1998?

Conversion de fermetures

Selective and Lightweight Closure Conversion, 1996
Efficient and safe-for-space closure conversion, 2000

Inférence de types

Type Inference with Polymorphic Recursion, 1991
Type Inference with Constrained Types, 1999
MLF: Raising ML to the Power of System F, 2003
Discriminative sum types locate the source of type errors, 2003

Gestion mémoire

Improving locality of reference in a garbage-collecting memory management system, Robert Courts, 1988.
Implementation of the typed call-by-value λ-calculus using a stack of regions, Mads Tofte et Jean-Pierre Talpin, 1994
Region-Based Memory Management, Mads Tofte et Jean-Pierre Talpin, 1997

Compilation certifiée

From System F to Typed Assembly Language, Greg Morrisett, David Walker, Karl Crary, and Neal Glew, 1999

Outils

OCaml

Voici des manuels (dérivés de ceux de flex et bison) pour implémenter un front-end en Ocaml: ocamllex ocamlyacc