Compilation 2022/2023 – Journal du cours

En licence, vous avez acquis les bases de l'informatique : appris à programmer dans plusieurs langages, découvert l'algorithmique sous diverses formes, vous êtes familiarisés avec l'utilisation d'un système UNIX, etc.

En master, on ouvre les boîtes noires ! Par exemple, le cours d'architecture des ordinateurs vous initie au fonctionnement interne d'un processeur.

Dans ce cours, on ouvre la boîte noire des langages de programmation : comment fonctionne un compilateur ? Comment passer d'un fichier texte contenant du code source à un programme que votre processeur peut exécuter ?

Comprendre le fonctionnement des compilateurs est l'objectif affiché du cours. Il y en a un deuxième, un peu caché : vous faire programmer, et beaucoup ! Vous allez écrire un compilateur, en OCaml, tout au long du semestre, en binôme, de façon guidée. Vous allez pour ce faire utiliser des méthodes et outils de développement modernes : gestion de version, tests, intégration continue, etc.

Ce n'est pas une compétence directement mobilisable dans la plupart des emplois de développeur, même si la demande pour des experts en compilation est forte à l'international (exemple : compilation de JavaScript).

Mais comprendre comment fonctionne un compilateur vous transformera en des programmeurs plus mûrs, qui maîtrisent les fondements de leurs outils. C'est une aide concrète lorsqu'on programme, et notamment lorsqu'on débogue et qu'on a besoin de regarder ``sous le capot''.

De plus, la compilation est un sujet pluridisciplinaire :

• architecture des ordinateurs,
• théorie des graphes
• théorie des langages et automates,
• sémantique des langages de programmation,
• génie logiciel,
• méthodes formelles…

Vous allez donc mettre en pratique et revisiter certains concepts que vous avez vu dans d'autres cours, ce qui peut vous aider à les assimiler.

Il va sans dire que la réalisation du projet va aussi beaucoup augmenter votre expérience de la programmation. Ce sera pour la majorité d'entre vous l'occasion de vous confronter pour la première fois à une base de code réaliste !

• Venir avec son ordinateur portable, vendredi
• S'assurer que celui-ci dispose d'un environnement de développement OCaml fonctionnel (compilateur OCaml, OPAM, dune).

https://listes.u-paris.fr/wws/info/m1.2022.compilation.info

• Finir la gestion des commentaires dans marthe.ml.

• https://caml.inria.fr/pub/docs/manual-ocaml/lexyacc.html
• http://pauillac.inria.fr/~fpottier/menhir/manual.pdf

• Forker le dépôt Git du projet

https://gaufre.informatique.univ-paris-diderot.fr/aguatto/compilation-m1-2022

• Passer votre fork du dépôt en visibilité privée
• Ajouter l'accès à l'équipe enseignante
  • Adrien Guatto @aguatto
  • Peter Habermehl @habermeh
• Remplir le fichier AUTEURS du dépôt

Une partie du sucre syntaxique est éliminée lors de l'analyse syntaxique. C'est le cas du if <expr> then <expr> qui se désucre de la même façon que celui d'OCaml.

Menhir ne connaît pas le fichier source, uniquement le lexbuf. C'est donc à l'analyseur lexical de remplir ce dernier correctement pour que l'analyseur syntaxique puisse avoir accès à l'information de position. Voir le type Lexing.lexbuf pour cette information de position.

L'analyseur lexical doit essentiellement détecter les nouvelles lignes pour mettre à jour le lexbuf. Cf. Lexing.new_line, déjà utilisée dans le fichier l'analyseur lexical fourni.

Les règles de l'analyseur syntaxique peut ensuite utiliser les variables Menhir $startpos et $endpos. Dans le fichier fourni, leur utilisation passera par la règle paramétrique located(X).

On peut utiliser cette règle pour analyser une valeur de type 'a located. Par exemple, le non-terminal located(expression) produit une valeur de type 'a located.

J'apporte quelques précisions à l'énoncé du jalon 1.

Les erreurs doivent de syntaxe doivent être levées via la fonction Error.error, à laquelle il faut passer une position valide.

Les positions générées dans les messages d'erreur peuvent dépendre de détails de la structure de votre grammaire. Il n'est donc pas gênant que vous n'ayez pas exactement les mêmes messages que ceux présents dans les tests fournis avec le jalon.

On doit faire attention à distinguer architecture et micro-architecture.

L'architecture, ou Instruction Set Architecture est une abstraction permettant la programmation système ou applicative. Exemple : architecture x86-64, architecture ARMv8, architecture RISC-V, etc.

La micro-architecture est une implémentation (ou famille d'implémentations) d'une architecture. Par exemple, la micro-architecture Zen 3 d'AMD pour x86-64, la micro-architecture Vortex/Tempest d'Apple pour ARMv8, la micro-architecture U8 de SiFive pour RISC-V.

Par extension, le terme "micro-architecture" désigne également l'étude des techniques d'implémentation efficaces des processeurs.

Dans ce cours, en tant que spécialistes du logiciel, on s'intéressera à l'architecture plutôt qu'à la micro-architecture.

Deux types d'architectures s'affrontent depuis ~1980 : RISC et CISC.

RISC = Reduced Instruction Set Computer. Offre un petit nombre d'instructions simples et orthogonales, ce qui permet de simplifier la micro-architecture. Exemple : RISC-V, ARM (historiquement).

CISC = Complex Instruction Set Computer. Beaucoup d'instructions baroques et complexes, micro-architecture complexe (décodage). Exemple paradigmatique : x86 (32 bits) et x86-64. Les ARM modernes s'en rapprochent.

On va s'intéresser à x86-64, une architecture à la longue évolution.

           8086 (16bits)    x86 (32bits)    AMD64 (64bits)
 |—————————————|——————————————|———————————————|—————————————|—————————>
1970          1980           1990           2000          2010

Pourquoi générer du code x86-64 ?

Inconvénients : complexe, baroque, laid.

Avantages : réaliste. Vous permet d'exécuter du code sur votre PC, sans passer par une couche d'émulation (sauf si vous avez un Mac récent). On ne fait pas semblant !

La documentation à laquelle nous pouvons nous référer :

• Les notes d'Andrew Tolmach sur un tout petit sous-ensemble du jeu d'instructions que nous allons utiliser. Leur lecture est obligatoire.
• La documentation combinée d'Intel (5000+ pages), disponible sur la page du constructeur.

Les instructions x86-64 servent à modifier l'état du processeur qui, en ce qui nous concerne, est formé des données suivantes.

Attention : deux syntaxes pour le code assembleur x86-64 existent : Intel et GNU/AT&T. Nous utiliserons la syntaxe GNU/AT&T, comme Andrew Tolmach, mais beaucoup de documenation utilise la syntaxe Intel.

• je foo : saute vers foo si le flag ZF de rflags est à 1.
• call foo : saute vers foo en empilant rip.
• ret : dépile une valeur et la stocke dans rip.

Attention : à l'exécution d'une instruction de saut, %rsp+8 doit toujours être aligné sur 16 octets. Donc, %rsp doit être aligné sur 16 octets avant toute instruction call, puisque celle-ci va pousser l'adresse de retour.

Pour comprendre les deux dernières instructions, il faut discuter de la pile, ce qu'on va faire tout de suite. Pour les autres, je vous renvoie aux notes d'Andrew Tolmach.

Une architecture doit spécifier une convention d'appel, qui dicte le fonctionnement des appels de fonction dans le but de permettre l'interopérabilité entre différents compilateurs, voire entre différents langages.

Nous allons utiliser la convention d'appel dictée par l'interface binaire (application binary interface, ou ABI) POSIX System V pour x86-64.

Celle-ci spécifie l'usage d'une pile pour stocker certains arguments de fonction, ainsi que les variables locales. Le sommet courant de la pile (son adresse) est, par convention, stocké dans le registre %rsp (register stack pointer, logique !). Cette adresse doit toujours être alignée sur huit octets (multiple de huit). La pile croît vers les adresses basses.

Un appel de fonction stocke ses données dans son cadre de pile. Le cadre de pile courant est stocké dans le registre %rbp (register base pointer). Elle ne doit pas accéder au reste de la pile (à l'exception de ses arguments, voire plus bas).

Pour travailler sur la pile, on peut utiliser les instructions push et pop. L'instruction pushq SRC correspond à la séquence d'instructions subq $8, %rsp; movq SRC, (%rsp), l'instruction popq DST correspond à la séquence d'instructions movq -8(%rsp), DST; addq $8, %rsp.

La valeur de retour de la fonction est stockée dans %rax. Les six premiers arguments sont stockés dans %rdi, %rsi, %rdx, %rcx, %r8, %r9. Tous les autres arguments (au delà du sixième) sont empilés de droite à gauche.

Les registres %rbx, %rbp %r12, %r13, %r14 et %r15 doivent être préservé par l'appelé. Donc, si votre fonction les modifie, elle doit faire en sorte de les restaurer avant de. Les autres registres sont susceptibles d'être modifiés par les appelés arbitrairement, gare donc si vous les utilisez autour d'un appel de fonction !

Enfin, l'invariant suivant doit toujours être vérifié : lors d'un call, %rsp doit être aligné sur 16 octets (autrement dit, sa valeur doit être une adresse multiple de 16). Donc, comme call empile %rip, on sait que la valeur %rsp+8 est alignée sur 16 octets au point d'entrée de toute fonction.

Pour les curieux et curieuses qui voudraient connaître le pourquoi du comment, vous pouvez lire les réponses à cette question sur StackOverflow.

On a étudié des rudiments de programmation x86-64 lors de la dernière séance, et lors de la séance de TP. Essayons de mettre en pratique aujourd'hui ensemble.

Le code relatif à Retrolix est contenu dans src/retrolix/. Commencer par lire l'AST présent dans retrolixAST.ml, puis en cas de question, regarder la sémantique de référence dictée par l'interprète dans retrolixInterpreter.ml.

Il s'agit d'un langage presque aussi bas niveau que l'assembleur, mais pas tout à fait. Quelques caractéristiques :

• des registres (x86-64) et des variables (locales, globales, paramètres),
• le registre matériel %r15 est réservé (jamais utilisé),
• respecte la convention d'appel en ce qui concerne les registres (registres caller-save vs. callee-save, registre stockant la valeur de retour),
• un jeu d'instruction bas niveau.

Attention : les six premiers arguments sont passés par %rdi, %rsi, %rdx, %rcx, %r8, %r9. Donc les arguments déclarés et passés explicitement en Retrolix sont ceux qui viennent des fonctions sources (Fopix) qui avaient plus de six arguments au départ !

Le code est contenu dans src/x86-64/, et l'AST qui nous intéresse est dans x86_64_AST.ml. Pas d'interprète ou parser.

On a vu les points saillants de l'assembleur x86-64 la dernière fois.

Remarque : comme on utilise GCC pour l'assemblage et l'édition de liens, nos programmes assembleurs doivent disposer d'une fonction main().

Attention : l'AST est trop permissif ! Il permet d'écrire du code qui n'assemble pas, par exemple movq (%rsp), (%rsp). Éviter de générer ce genre de code fait partie de votre travail.

• des chaînes litérales en Retrolix,
• en Retrolix, pas de fonction main(), le point d'entrée du programme est la séquence des blocs d'initialisation de ses variables globales,
• pas de variables en x86-64,
• jeu d'instructions assez différent : Retrolix est plutôt RISC mais x86-64 est très CISC ; par exemple :
  • trois adresses vs. deux adresses,
  • modes d'adressage et opérandes mémoires limités en x86-64,
  • bizarreries en x86-64, par exemple la division.

Certaines des différences que nous venons de décrire ne sont pas essentielles, et sont donc déjà traitées pour vous (chaînes litérales, génération d'un main, …). On va se concentrer sur deux points :

• la traduction des constructions Retrolix en assembleur x86-64,
• la gestion des variables et de la pile.

La passe de traduction est dans retrolixToX86_64.ml. Vous devez remplacer les failwith "Students!" avec le code approprié.

Il s'agit essentiellement d'implémenter deux modules, InstructionSelector et FrameManager. Le premier se charge de la traduction de construction atomiques de Retrolix en x86-64, le second de la gestion de la pile et des variables. Le second va naturellement faire appel au premier.

Attention : dans ce jalon, on se concentrera sur la correction du code généré. Produire du code optimisé est un objectif secondaire.

Lecture de l'AST Fopix présent dans le fichier fopixAST.ml.

Voir hobixAST.ml.

Quelles similarités et différences distinguez-vous entre Hobix et Fopix ?

Les langages sont identiques à quelques exceptions près :

• Fopix ne dispose pas de read/write/allocate_block() ad-hoc ;
• En Hobix, les fonctions sont des valeurs, et on a une construction apply générique (la fonction est une expression quelconque), et surtout une construction de fonction anonyme dans les expressions ;
• Les littéraux de Fopix comprennent, en plus de ceux de Hobix, un nom de fonction LFun f (qui doit être compris comme un pointeur vers f).

En d'autres termes, en Hobix les fonctions sont de première classe, comme en OCaml, tandis que Fopix ne dispose que de pointeurs de code, comme en C.

Pour traduire Hobix vers Fopix, il faut donc ramener les constructions de bloc à des appels de fonctions génériques, mais surtout éliminer les fonctions de première classe. On va suivre l'approche vue durant le cours d'introduction à la sémantique, avec une passe dite d'explicitation des fermetures (ou closure conversion en anglais).

Comment traduire les programmes OCaml suivants en C ? Comme d'habitude, on cherche une traduction mécanique et locale (expression par expression), comme le ferait un compilateur !

On choisit le format suivant pour les fermetures.

À votre avis, vers quelle construction Hobix est-il naturel de traduire les boucles for de Hopix ?

La boucle while, bien sûr !

Proposons une traduction générale. Comme précédemment, on écrira C(-) pour la fonction de traduction, i.e., C(e) sera le traduit de e.

C(for x in (lo to hi) { body }) =
  << let cpt = allocate_block(1);
     let h = C(hi);
     cpt[0] := C(lo);
     while (cpt[0] <= h) {
       let x = cpt[0];
       C(body);
       cpt[0] := cpt[0] + 1;
     } >> où cpt et h sont fraîches.

C(e₁ ; e₂ ; ... ; eₖ) = << val _ = C(e₁); val _ = C(e₂); ...; C(eₖ) >>

Première question : quelle représentation sous forme d'un bloc ? On peut se contenter d'un bloc de taille 1, qui stocke le contenu de la référence.

Pourquoi ?

Parce que toutes les données qu'on va manipuler occupent exactement un mot. Cela provient du fait qu'on manipule soit des entiers machines, soit des booléens manipulés comme des entiers (c'est une perte de place qui nous simplifie néanmoins la vie), soit des pointeurs (y compris des adresses de bloc). Par exemple, une référence qui contient un n-uplet va être implémentée par un bloc de taille 1 dont l'unique cellule contient l'adresse du bloc qui lui même stocke le contenu du N-uplet.

C(ref e) = << let x = allocate_block(1); x[0] := C(e); x >> où x est frais

C(!e) = << C(e)[0] >>

C(e₁ := e₂) = << C(e₁)[0] := C(e₂) >>

Quelle représentation ? Un bloc de taille N, où N est le nombre de champs de l'enregistrement.

La traduction suppose qu'on a fixé un ordre d'énumération quelconque des champs : f1, f2, … jusqu'à fN. En pratique, on peut prendre l'ordre de déclaration, mais cet ordre n'a pas d'importance.

On va supposer qu'on a une fonction IDX(f) qui associe au champ f un indice. Il peut être calculé lors de la définition du type correspondant.

(Pourquoi ? Parce le code source Hopix n'est pas capable de l'observer.)

C({ f1 = e1; ...; fN = eN; }) = << let x = allocate_block(N) in
				   x[IDX(f1)] := C(e1);
				   ...;
				   x[IDX(fN)] := C(eN);
				   x >> où x est frais

Attention : si l'ordre n'importe pas, dans la traduction ci-dessus, il est important qu'on fasse le calcul de eᵢ avant eᵢ₊₁ pour respecter la sémantique de Hopix !

C(e.f) = C(e)[IDX(f)]

Une simple variation sur les enregistrements, à la différence que l'ordre des champs est fixé.

Supposons qu'on ait le type Hopix suivant (syntaxe OCaml).

type t =
  | Empty
  | Leaf of int
  | Node of t * t

Quelle représentation sous forme de bloc adopter pour ses constructeurs ?

On doit toujours avoir au moins une cellule dans le bloc, pour distinguer le constructeur dont il s'agit. Celle-ci contient une étiquette (tag), qui associe un entier unique à chaque constructeur (comme pour la fonction IDX() des enregistrements, elle peut être calculée à la définition du type). En plus du tag, on a besoin d'autant d'espace que le constructeur a de paramètres : 0 pour Empty, 1 pour Leaf et 2 pour Node.

Plus généralement, si le constructeur Kᵢ a kᵢ paramètres, on a besoin d'un bloc de taille 1 + kᵢ pour le représenter.

C(K (e_1, ..., e_kᵢ)) = << let x = allocate_block (1 + kᵢ);
			   x[0] := TAG(K);
			   x[1] := C(e_1);
			   ...
			   x[1 + kᵢ] := C(e_kᵢ);
			   x >> où x est frais

La traduction du filtrage de motif est plus subtile que celle des constructions précédentes, puisque le filtrage est une construction très expressive qui permet simultanément de déstructurer une valeur, lier des variables, discriminer entre plusieurs cas, etc. Comment traduire l'exemple suivant ?

def len (l) =
  case l {
  | Nil => 0
  | Cons (_, xs) => 1 + len (xs)
  }

def len (l) =
   if l[0] = 0 then
     0
   else
     let xs = l[2] in
     1 + len (xs)

On rappelle que le filtrage est de la forme match e { b1 | ... | bN } où chaque bᵢ est une branche, c'est à dire de la forme p ⇒ e, où p est un motif. Pouvez-vous rappeler les formes de motifs possibles ?

Il s'agit des :

• variables,
• attrape-tout (wildcard en anglais),
• annotations de types,
• constantes littérales,
• constructeur de types sommes,
• n-uplets,
• enregistrement,
• motif ET,
• motif OU.

L'approche la plus simple est de traduire le filtrage vers une séquence de conditionnelles et déclarations locales imbriquées.

On peut commencer par éliminer les motifs OU, en les ramenant à des branches supplémentaires dans la construction de filtrage initiale. (Pouvez-vous expliciter cette traduction ?)

Comment formuleriez-vous la traduction d'un motif ? On traduit vers :

1. une expression booléenne qui dit si la valeur discriminée est filtrée,
2. une liste de liaisons identifiant → expression qui indique, le cas échéant, quelles variables ont été liées.

La fonction de traduction des motifs prend en paramètre le motif p mais également l'expression d dont on veut filtrer le résultat.

			C(d, x) = (~true~, [ ~x = d~ ])
			C(d, _) = (~true~, [ ])
		  C(d, p : ann) = C(d, p)
			C(d, l) = (~d = l~, [ ])
	    C(d, K(p₁, ..., pₖ) = (~c₁ && ... && cₖ && d[0] = TAG(K)~,
				   b₁ @ ... @ bₖ) où (cᵢ, bᵢ) = C(~d[i]~, pᵢ)
	  C(d, ⟨ p₁, ... , pₖ ⟩) = (~c₁ && ... && cₖ~, b₁ @ ... @ bₖ)
				  où (cᵢ, bᵢ) = C(~d[i-1]~, pᵢ)
C(d, { l₁ = p₁; ... ; lₖ = pₖ }) = (~c₁ && ... && cₖ~, b₁ @ ... @ bₖ)
				  où (cᵢ, bᵢ) = C(~d[IDX(lᵢ)]~, pᵢ)
				  en supposant l₁, ..., lₖ dans le bon ordre !
	       C(d, (p₁ && p₂)) = (~c₁ && c₂~, b₁ @ b₂)
				  où (cᵢ, bᵢ) = C(~d~, pᵢ)

La traduction du filtrage lui même est ensuite facile à formuler.

C(match e { p₁ ⇒ e₁ | ... | pₖ ⇒ eₖ }) =
  << let x = C(e);
     if c₁ then (let b₁; C(e₁))
     else if c₂ then (let b₂; C(e₂))
     ...
     else if cₖ then (let bₖ; C(eₖ))
     else error (* impossible si le filtrage est exhaustif *)
  >> où (cᵢ, bᵢ) = C(x, pᵢ)

À quoi ressemblent les fermetures allouées pour le code suivant ?

let f x y u w =
  let g () =
    let h n =
      let k m =
        x + y + n
      in
      k u + n
    in
    h w
  in g

Avec la représentation "plate" adoptée dans notre traduction :

(Pourquoi avoir besoin de x et y dans h ?)

On constate qu'il y a beaucoup de redondance. Comment faire mieux ?

Avec du partage ! On appelle ça des fermetures chaînées.

On peut ainsi économiser potentiellement beaucoup d'espace, au prix d'un accès un peu plus coûteux aux valeurs dans l'environnement. On économise aussi sur le temps de création de la fermeture.

Cette technique pose cependant un problème grave, qui est déclenché par exemple dans le code ci-dessous. Pouvez-vous voir lequel ?

let f a b =
  let g c =
    let h n = b + c + n in
    h (List.hd a)
  in
  g

let rec loop' k n =
  if n <= 0
  then k 0
  else
    let a = some_list_of_size n  in
    let k' = f a in
    loop' (fun r -> k (k' n r)) (n - 1)

let loop = loop' (fun r -> r)

Quelle est la complexité en espace de loop' n ? A priori, linéaire : dans le corps de loop' on fabrique une chaîne de n fermetures. Mais ici, les listes a de taille n ne peuvent pas être libérées avant que loop' termine, puisqu'elles sont atteignables depuis les fermetures pour h. La complexité en espace est donc quadratique !

Shao et Appel ont proposé une solution à ce problème. Elle consiste à introduire des environnements partagés de taille minimale pour factoriser uniquement les variables qui sont vraiment partagées entre fermetures. Lire leur article (URL ci-dessous) si la question vous intéresse.

https://flint.cs.yale.edu/flint/publications/escc.pdf

(Le compilateur OCaml utilise des fermetures à plat.)

Comment va être traduit le code suivant ?

let f x y z =
  x + y + z

let g =
  fun x ->
  print_string "hello";
  fun y ->
  print_string " world!\n";
  fun z ->
  x + y + z

let h =
  let r = ref 0 in
  fun x y z ->
    let n = !r + y + z in
    r := x;
    n

let test () =
  print_int (f 1 2 3);
  print_int (g 1 2 3);
  print_int (h 1 2 3)

Si on traduit tous les appels et fonctions anonymes uniformément, on va faire payer le même coût aux trois appels. En particulier, il va falloir allouer trois fermetures intermédiaires pour f et h. Ce n'est pas raisonnable dans un compilateur réaliste ; on voudrait réussir à compiler les appels à f et h vers l'instruction call x86-64, en passant les quatre arguments (1, 2 et 3 plus la fermeture) dans les registres.

On peut tout d'abord réaliser que f est une fonction top-level close, sans environnement. On pourrait donc éviter de créer une fermeture et l'appeler directement comme fonction connue. Attention : cette optimisation n'est possible que parce qu'on a accès au corps de f, ce qui nous permet de vérifier que celui-ci est directement de la forme fun x y z -> .... Cette optimisation n'est pas possible pour h.

Une autre solution serait d'inliner f dans son appelant. L'inlining est simplement le fait de remplacer un appel de fonction dont le corps est connu par le corps lui-même. Cela a l'avantage d'éviter un appel intermédiaire, et surtout d'exposer plus de code aux optimiseurs du compilateur.

Pour optimiser h, une solution employée par exemple dans le compilateur OCaml est d'augmenter chaque fermeture avec l'arité de la fonction, et de considérer une construction d'application n-aire (représentée dans l'AST par un constructeur comme Eapply of exp * exp list). Lors de l'exécution de l'application N-aire e e1 e2 ... eN, on commence par calculer la fermeture c associée à l'expression e, et par nommer x1 x2 ... N les résultats de l'évaluation de e1 e2 ... eN. Ensuite, on regarde le champ c.arity :

• si N = c.arity : on peut faire un appel à c.fun en passant tous les arguments, sans créer de fermeture intermédiaire;
• si N < c.arity : on doit créer une fermeture qui attend c.arity - N arguments y1, … yM, etc. et dont le corps appelle c.fun(c, v1, ..., vN, y1, y2, ..., yM);
• si N > c.arity (on parle parfois de surapplication) : faire les applications successives en créant les fermetures intermédiaires.

Un point important : on peut distinguer statiquement les applications partielles, à partir de l'information de typage. C'est à dire qu'on sait toujours si on est dans un cas ou N <= c.arity (application partielle potentielle) ou N >= c.arity (surapplication potentielle). On a donc besoin d'un seul test et pas deux.