Compilation (INF564)

J'ai assuré ce cours pendant onze ans, de 2005-2006 jusqu'à 2015-2016. Le matériel ci-dessous est celui de l'année 2015-2016. Il peut être librement utilisé par les étudiants. Si vous êtes enseignant et si vous désirez en utiliser tout ou partie, merci de bien vouloir me contacter pour en demander la permission.

Aperçu

Le cours consiste à étudier et à écrire un compilateur d'un langage impératif simple, baptisé Pseudo-Pascal, vers l'assembleur MIPS. Il permet de comprendre l'étendue et le franchissement du fossé qui sépare langages de haut niveau et langages machine. Il permet également de découvrir des techniques et algorithmes non triviaux et de les exprimer dans un langage de très haut niveau, à savoir OCaml. Pour en savoir plus, consultez ces quelques transparents de présentation.

Matériau

• architecture MIPS (2 décembre 2015) (transparents, TD);
• syntaxe, sémantique et interprétation de Pseudo-Pascal (9 décembre 2015) (transparents, TD);
• analyse lexicale et syntaxique (16 décembre 2015) (transparents, TD);
• sélection d'instructions (6 janvier 2016) (transparents, TD);
• création du graphe de flot de contrôle (13 janvier 2016) (transparents, TD);
• explicitation de la convention d'appel (20 janvier 2016) (transparents, TD);
• analyse de durée de vie et construction du graphe d'interférences (27 janvier 2016) (transparents, TD);
• coloriage du graphe d'interférences (3 février 2016) (transparents, TD);
• arrière du petit compilateur; ramassage de miettes (10 février 2016) (transparents, TD);
• Une fiche rappelant la syntaxe abstraite de Pseudo-Pascal.
• Une fiche définissant la sémantique de Pseudo-Pascal.
• Téléchargez le code source complet du petit compilateur (version du ...).
• Consultez le code source en ligne. Les modules sont groupés de façon logique et accompagnés d'une courte explication de façon à vous donner une vision d'ensemble de l'architecture du compilateur. Le code est coloré pour en augmenter la lisibilité. De plus, lorsque vous passez votre souris au-dessus d'une variable, son type apparaît!

Outils

• Pour compiler le petit compilateur, il vous faut GNU make, ocaml et menhir. Pour le tester, il vous faut spim. Ces logiciels sont disponibles en salles machines.
• Plus récent, l'outil mars est préférable à spim pour écrire manuellement et exécuter pas-à-pas du code assembleur. Il est installé en salles machines sous le nom ~francois.pottier/bin/mars. Si vous ajoutez la ligne export PATH=~francois.pottier/bin:$PATH à la fin de votre fichier ~/.bash_profile, alors vous pourrez taper simplement mars.
• Pour éditer du code, je vous conseille d'utiliser un éditeur doté d'un mode OCaml, comme emacs ou vim. Voici un tutoriel pour emacs et un tutoriel pour vim. Sous emacs, trois commandes particulièrement utiles:
  • Ctrl-C Ctrl-C (contrôle-C-deux-fois) compile votre code (sans quitter emacs).
  • Ctrl-X ` (contrôle-X-backquote) vous amène au point de votre code où le compilateur signale une erreur.
  • Ctrl-C Ctrl-A vous fait passer du fichier toto.ml au fichier toto.mli, et vice-versa.
  Voici une liste plus complète, en une page, des principales commandes disponible sous emacs en mode tuareg. En salle info, si le mode Tuareg ne s'active pas automatiquement lorsque vous ouvrez un fichier .ml ou .mli dans emacs, recopiez cette incantation dans votre fichier ~/.emacs.

Références

• Cet excellent manuel, dû à Jim Larus, décrit l'architecture MIPS et son simulateur spim. Les sections A.1 à A.6 se lisent comme un roman: lisez-les donc dès le premier cours! Attention, les définitions des termes caller-saved et callee-saved en marge de la page A.23 ont été interchangées par erreur. Les sections A.9 et A.10 expliquent le simulateur spim et le jeu d'instructions du processeur MIPS.
• Deux très courts documents vous aideront à utiliser spim et xspim.
• Voici un court tutorial pour mars.
• Le manuel de référence d'OCaml et en particulier la description de sa librairie standard seront utiles. Voici en particulier deux liens directs vers la documentation des foncteurs Set.Make et Map.Make.
• quelques antisèches à propos d'OCaml permettent de se remémorer les points les plus importants: le langage, les outils, la librairie standard, emacs et le mode tuareg.
• Le manuel de référence de Menhir pourra également être utile.
• Le livre Apprendre à programmer avec OCaml constitue une excellente introduction à OCaml (ainsi qu'à l'algorithmique et à de nombreuses structures de données fondamentales). Dans sa deuxième partie, il illustre l'emploi des modules, signatures, foncteurs, etc.
• Des mêmes auteurs, cette introduction à OCaml est disponible en ligne.
• Le cours de Jean-Christophe Filliâtre, programmation en OCaml.
• Le livre Real World OCaml décrit le langage OCaml ainsi que son utilisation pratique.
• Le livre Modern Compiler Implementation in ML, d'Andrew Appel, est une excellente introduction à la compilation. Le livre aborde de nombreux sujets que je ne peux traiter en cours, et vous conduit également à écrire votre propre compilateur en ML. Il existe deux versions du livre dans lesquelles le langage d'implantation du compilateur est Java ou C.
• Pour en savoir (beaucoup) plus sur l'analyse syntaxique, le livre Parsing Techniques - Second Edition, de Dick Grune et Ceriel J. H. Jacobs, est excellent. Sa première édition est disponible en ligne.
• Arnaud Bonnet a écrit pasclang, un compilateur de Pseudo-Pascal vers LLVM, implémenté en C++.

Remerciements

Merci à Luc Maranget, qui assurait précédemment ce cours, pour son aide. Merci également à Xavier Leroy, dont le compilateur certifié a fortement inspiré l'architecture du petit compilateur que je présenterai en cours.

Contact

Envoyez vos questions ou commentaires à François Pottier.