Sélection d’instructions |
Comme d’habitude, il faut commencer par télécharger l’archive td4-pp2upp.tar.gz puis la dépaqueter et construire l’exécutable avec make :
# tar xvfz td4-pp2upp.tar.gz # cd td4-pp2upp # make
On cherche à transformer l’AST (Arbre de Syntaxe Abstraite) obtenu par parsing du code Pseudo-Pascal sous une forme plus proche du langage compris par la machine. On passe du langage défini dans PP.mli au langage défini dans UPP.mli.
Ces transformations consistent à :
L’assembleur n’étant pas typé, les opérations générées n’ont plus besoin de connaître le type des expressions manipulées. On peut donc en parallèle abandonner le type des expressions.
Note : La correction du typage est une phase du compilateur codée dans le fichier typechecking.ml, qui opère sur le langage LPP de façon à pouvoir émettre des messages d’erreur donnant la localisation des erreurs dans le fichier source. On peut donc considérer qu’au moment de traduire PP en UPP, le typage est correct.
Les traductions plus complexes comme l’affectation de registres aux variables locales ou les appels de fonctions seront traitées plus tard.
Commencez par comparer attentivement les fichiers qui décrivent le langage source et le langage destination de la traduction qu’il va falloir implémenter. Le langage source est décrit par PP.mli et le langage destination par UPP.mli.
Note : Vous pouvez le faire en éditant les deux fichiers en parallèle (faire Ctrl-x 3 sous emacs), mais même un diff -w donne une bonne idée des différences ici.
Le fichier à modifier est pp2upp.ml décrit par l’interface pp2upp.mli. Traduisez les appels de procédure du langage PP vers le langage UPP. Il s’agit de traiter le motif PP.IProcCall (callee, es) de la fonction translate_instruction. Cela permet d’interpréter correctement le code UPP d’un code trivial qui appelle writeln :
# ./compilo -iupp test/trivial.p # 10
Il s’agit dans un premier temps de calculer l’espace mémoire à réserver pour les variables globales du programme. Comme tous les types (entier, booléen et tableau) ont la taille d’un mot mémoire (4 octets ici, taille définie par la constante MIPS.word), ce calcul est une simple multiplication.
Note : Dans le cas général, avec des types de tailles différentes, il faudrait se préoccuper de l’alignement des variables, qui contraint le compilateur à les placer à des adresses multiples de leur taille.
On veut également connaître l’adresse de chaque variable globale, qui consistera pour l’instant en un décalage ou offset entre l’adresse de début de la zone des variables globales (inconnue pour l’instant) et l’adresse de la variable considérée.
On vous demande d’implémenter la fonction allocate_globals qui fait tout ça. Elle renvoie un couple formé de :
Vous pouvez utiliser la fonction StringMap.fold appliquée aux variables globales p.PP.globals du programme p.
Ensuite, il faut traduire les lectures et écritures de variables globales en fonction de cette nouvelle représentation. Il s’agit donc de traiter les cas suivants :
On peut vérifier sur un exemple simple qui utilise une variable globale que ça marche :
# ./compilo -iupp test/echo.p # 98 # 98
Il faut traduire les lectures/écritures de tableaux en accès élémentaires à la mémoire, utilisant les opérations load et store. On vous demande d’implémenter les fonctions suivantes, en utilisant la fonction Upp2upp.mkbinop :
let w2b (e : UPP.expression) : UPP.expression = ... let element_address (base : UPP.expression) (index : UPP.expression) : UPP.expression = ... let mkload (addr : UPP.expression) : UPP.expression = ... let mkstore (addr : UPP.expression) (value : UPP.expression) : UPP.instruction = ...
Utilisez les fonctions précédemment implémentées pour traduire les lectures/écritures de tableaux :
Il ne reste plus qu’à traduire l’allocation de tableau en un appel à la fonction primitive Alloc, en traduisant également la taille du tableau en octets. Cela revient à traiter le motif PP.EArrayAlloc (_, e) de translate_expression.
Comme vous avez maintenant un traducteur complet (même si pas optimal) de PP vers UPP, vous pouvez vérifier à tout moment la correction de vos modifications avec make upp, qui doit rendre OK pour tous les tests.
On s’intéresse maintenant à la façon dont les opérations binaires sont traduites dans upp2upp.ml, en particulier les opérations les plus courantes, addition, soustraction et multiplication, qui doivent être les plus efficaces possibles.
La traduction courante manque assez d’imagination, il va falloir l’améliorer :
let mkadd e1 e2 = EBinOp (OpAdd, e1, e2) let mksub e1 e2 = EBinOp (OpSub, e1, e2) let rec mkmul e1 e2 = EBinOp (OpMul, e1, e2)
Une contrainte importante à prendre en compte est la possibilité d’effets de bord durant l’évaluation d’une expression, par exemple l’affectation d’une variable ou une impression sur la sortie standard. Un compilateur doit conserver le comportement observable du programme lors des phases d’optimisations. Dans notre cas, la seule possibilité d’effet de bord dans une expression est l’appel de fonction. Une expression expr est sans effets de bord (ne contient pas d’appel) lorsque pure expr renvoie true.
Une première optimisation évidente consiste à faire calculer au compilateur le résultat de l’opération quand les deux opérandes sont constantes. C’est ce qui est déjà fait pour la division de deux constantes, cf le code de mkdiv. Faites-le pour les opérations citées ci-dessus.
Note : Cette optimisation est parfois essentielle, par exemple pour le template metaprogramming en C++ qui consiste à faire sélectionner par le compilateur le code à compiler, en fonction du calcul d’expressions constantes.
Ensuite on peut regarder comment optimiser les cas ou une des opérandes est constante, dans le cas où la constante vaut 0 ou 1.
L’utilisation d’une opération unaire d’addition (avec une constante) étant moins coûteuse qu’une addition normale, on peut essayer de transformer ces dernières lorsque la valeur de la constante le permet (lorsqu’elle peut être codée sur 16 bits). La fonction Integer.fits16 donne cette information.
Par exemple, l’addition i + e entre une petite constante i et une expression e peut être traduite par une addition unaire (i+) e.
On peut également chercher dans quels cas ces constantes peuvent se combiner, par exemple lors d’une addition (i1+) e1 + (i2+) e2.
Enfin, pour favoriser ces combinaisons de constantes, il peut être intéressant de pousser ces additions unaires le plus possible à l’extérieur des expressions.
La multiplication est l’opération arithmétique la plus coûteuse (en temps d’exécution), il est donc intéressant de la transformer en décalage de bits quand une des opérandes est une puissance de 2.
Vous pouvez utiliser pour ceci l’opérateur UPP.UOpSlli.
Que faire lorsque l’opération englobante est elle-même une multiplication ?
La sélection d’instructions était relativement simple, puisque l’architecture MIPS est RISC (Reduced Instruction Set Computer). Pour les architectures CISC (Complex Instruction Set Computer), avec des modes d’adressage très variés et des dizaines d’instructions possibles, on utilise des algorithmes de minimisation de coût, cf le livre d’Andrew Appel, « Modern compiler implementation in ML ».
La sélection des opérations arithmétiques complète est codée dans le fichier upp2upp.ml. Lire notamment les commentaires sur les règles de réécriture.
La traduction de PP vers UPP est faite dans le fichier pp2upp.ml.
Enfin, allez regarder le code d’impression printUPP.ml (pour la gestion des priorités des opérateurs sous forme d’appels mutuellement récursifs) et de l’interprète interpretUPP.ml (pour l’utilisation de l’exception RuntimeError pour gérer les erreurs d’exécution).
Ce document a été traduit de LATEX par HEVEA