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:
- Définition d'un langage.
- Techniques d'interprétation de langages.
- Structure d'un compilateur.
- Génération semi-automatique de compilateur: lex, yacc, burg, évaluation partielle, génération de code C et autres backends génériques.
- Analyse et optimisation: SSA, analyse de flot de donnée et de contrôle, interprétation abstraite, inlining, élimination de code mort, élimination des sous-expressions communes, analyse des pointeurs alias.
- Génération de code pour architectures modernes: allocation de registres, software pipelining, ordonnancement de code, prefetching, blocking, placement du code et des données.
- Compilation JIT: fast compilation, trace compilation, dynamic recompilation, basic bloc versioning.
- Implantation des langages modernes: inférence de types, représentations intermédiaires typées, gestion mémoire, dispatch, fermetures, polymorphisme, compilation dynamique, représentation des types à l'exécution.
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:
- 3 × 15% pour les TP
- 10% pour les présentations
- 15% pour l'intra
- 30% pour le final
La pondération pour IFT-6232 est comme suit:
- 3 × 15% pour les TP
- 25% pour les présentations
- 10% pour l'intra
- 20% pour le final
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
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
Jour | Orateur | Thème |
---|---|---|
27 mars | Étudiants 3065 | TP2 |
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:
- Version préliminaire (structure): 4 points
- Contenu technique: 4 points
- Gestion du temps: 2 points
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:
- Décrire le problème que l'article entend résoudre.
- Décrire comment le problème est résolu.
- Discuter de la qualité de cette solution (avantages, inconvénients, limites, comparaisons avec d'autres solutions).
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
- Version préliminaire (structure): 4 points
- Contenu technique: 4 points
- Motivation et background: 2½ points
- Gestion du temps: 2 points
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, 1993How 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, 1977ORBIT: 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, 1996Efficient and safe-for-space closure conversion, 2000
Inférence de types
Type Inference with Polymorphic Recursion, 1991Type 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