Sélection d’instructions

Voici le cours correspondant. La solution se trouve dans les fichiers pp2upp.ml et upp2upp.ml.

Présentation

Comme d’habitude, il faut commencer par télécharger l’archive td4.tar.gz puis la dépaqueter et construire l’exécutable:

# tar xvfz td4.tar.gz
# cd td4
# make

L’objectif de ce TD est de passer du langage PP au langage UPP. En d’autres termes, on cherche à transformer un arbre de syntaxe abstraite Pseudo-Pascal, obtenu par analyse syntaxique du code, en un arbre de syntaxe abstraite UPP. Les syntaxes abstraites de ces langages sont définies respectivement dans PP.mli et UPP.mli.

Les principales transformations sont les suivantes:

Au passage, on effectue quelques autres transformations, qui ne nous intéresseront pas dans ce TD:

Pour commencer

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.

Vous pouvez le faire en éditant les deux fichiers en parallèle (faire Ctrl-x 3 sous emacs), ou bien (pourquoi pas) en utilisant la commande diff -w PP.mli UPP.mli.

Le fichier à modifier est pp2upp.ml. Son interface est donnée par pp2upp.mli.

Traduisez d’abord 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 programme trivial qui appelle writeln:

# ./compilo -iupp test/trivial.p
# 10

À tout moment, vous pouvez lancer make test pour apprécier vos progrès.

Adressage des variables globales

Les variables globales sont stockées dans une zone de taille fixe. Il faut calculer la taille que l’on souhaite attribuer à cette zone, et l’adresse de chaque variable, exprimée comme un décalage (offset) relatif à l’adresse du début de cette zone. L’adresse absolue du début de cette zone n’est pas connue pour le moment, mais nous ferons en sorte qu’elle soit stockée dans le registre $gp.

Quel que soit leur type (entier, booléen ou tableau), les valeurs que nous manipulons occupent un mot en mémoire. (Pourquoi? Réfléchissez-y.) Pour nous, un mot égale 32 bits ou 4 octets.

Si les variables sont par exemple nommées x, y, z, etc., alors nous souhaitons leur attribuer respectivement les offsets 0, 4, 8, etc.

Cependant, plutôt que de faire apparaître partout la constante 4, nous utiliserons la constante MIPS.word. Ainsi, il nous suffirait en théorie de modifier la définition de cette constante pour produire du code MIPS 64 bits.

Implémentez la fonction allocate_globals. Celle-ci doit produire un couple formé de:

Pour itérer sur la table des variables globales, p.PP.globals, vous pourrez utiliser la fonction StringMap.fold.

Ensuite, traduisez les accès (en lecture et en écriture) aux variables globales. Il vous faut traiter les cas suivants:

Vous pouvez vérifier que votre code est correct à l’aide d’un exemple simple. Par exemple, le programme Pseudo-Pascal echo.p attend un entier sur l’entrée standard et le répète sur la sortie standard:

# ./compilo -iupp test/echo.p
# 98
# 98

Accès au tas

En Pseudo-Pascal, les tableaux sont alloués dynamiquement et stockés dans le tas. Un accès (en lecture ou en écriture) à un tableau se traduit donc par un accès à la mémoire (à l’aide d’une opération load ou store), à une adresse que l’on doit calculer.

Implémentez successivement les fonctions suivantes:

Utilisez ensuite les fonctions ci-dessus pour traduire les accès, en lecture ou en écriture, aux tableaux:

Enfin, traitez le motif PP.EArrayAlloc (_, e) de translate_expression. Vous traduirez l’opération d’allocation d’un nouveau tableau en un appel à la fonction primitive Alloc. Cette fonction primitive attend un entier, qui représente une taille exprimée en octets. Elle alloue dans le tas un bloc de mémoire de la taille souhaitée, et en renvoie l’adresse. (Elle correspond à la fonction malloc du langage C.) Cette fonction n’existe pas en Pseudo-Pascal, mais nous est utile pour la compilation, donc est introduite dans UPP.

Vous avez maintenant un traducteur complet (quoique pas optimal) de PP vers UPP. Vous pouvez vérifier à tout moment la correction de vos modifications à l’aide de la commande make test (qui utilise spim) ou bien make upp (qui utilise l’interprète UPP). Vous devez obtenir OK pour tous les tests.

Une solution au TD, pour ce qui concerne la traduction de PP vers UPP, est donnée dans pp2upp.ml.

Opérations arithmétiques

On s’intéresse maintenant à la façon dont les opérations binaires sont construites et réécrites dans upp2upp.ml. En particulier les opérations les plus courantes: addition, soustraction et multiplication doivent être aussi efficaces que possible.

Consultez le fichier upp2upp.ml qui vous est fourni. Il est correct, mais totalement trivial. Nous allons devoir l’améliorer...

Une contrainte à prendre en compte est la possibilité d’effets de bord durant l’évaluation d’une expression. On appelle effet de bord tout effet observable que peut avoir l’exécution d’une expression, en dehors du fait qu’elle produit un résultat: en particulier, le fait de modifier le contenu de la mémoire (qu’il s’agisse d’une variable globale ou d’un tableau alloué dans le tas), de lire sur l’entrée standard, ou d’écrire sur la sortie standard. Le compilateur doit préserver le comportement observable du programme, et ne doit donc pas changer la nature des effets de bord ni l’ordre dans lequel ils ont lieu. Par exemple, supprimer le calcul d’une expression sous prétexte que son résultat n’est pas utilisé n’est correct que si cette expression n’a pas d’effets de bord. On dit alors que l’expression est pure.

Dans notre cas, la seule possibilité pour une expression d’effectuer un effet de bord est via un appel à une fonction. La fonction pure, qui vous est fournie, attend une expression expr et renvoie true si cette expression est pure. Il s’agit d’une approximation: certaines expressions effectuent des appels de fonction et pourtant n’ont pas d’effets de bord.

Optimisations liées aux constantes

Une première optimisation aisée consiste à calculer dès la compilation le résultat d’une opération si tous les opérandes sont connus (sont des constantes). Faites-le pour les quatre opérations arithmétiques: addition, soustraction, multiplication, division. Vérifiez avec make test que vous n’avez pas introduit d’erreurs. Vérifiez que le code produit s’est amélioré, par exemple en examinant le fichier test/arith.spi. (Tous les fichiers test/*.spi sont mis à jour à chaque fois que make test est exécuté.)

Ensuite, vous pourrez optimiser les cas où l’un des opérandes est constant et vaut 0 ou 1.

Optimisations liées à UOpAddi

On souhaite transformer l’addition binaire en addition unaire lorsque l’un des opérandes est une constante et lorsque cette constante 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 ensuite chercher dans quels cas ces constantes peuvent se combiner, par exemple lors d’une addition binaire de la forme ((i1+) e1) + ((i2+) e2). C’est de là que peut provenir un certain gain d’efficacité.

Enfin, pour favoriser ces combinaisons de constantes, il peut être intéressant d’extraire ces additions unaires, autant que possible, vers l’extérieur des expressions.

Optimisation des multiplications

Comme dans le cas de l’addition, on pourra tenter d’extraire et de combiner les constantes: par exemple, l’expression 3 * (y * 8) devrait être traduite à l’aide d’une seule multiplication.

La multiplication est une opération arithmétique relativement coûteuse en termes de temps d’exécution. Il est donc intéressant de la transformer en décalage de bits lorsque l’un des opérandes est une puissance de 2.

Vous pouvez utiliser pour ceci l’opérateur unaire UPP.UOpSlli, qui représente le décalage à gauche (shift left logical).

Les fonctions is_power_of_two, log2 et exp2, définies dans le module Integer, pourront vous être utiles.

On fera en sorte que même une expression complexe comme 2 * (y * 8) soit traduite à l’aide d’une seule instruction de décalage à gauche...

On pourra ensuite faire de même pour la division par une puissance de deux.

Pour finir

Dans notre cas, la sélection d’instructions est relativement simple, parce que l’architecture MIPS est particulièrement simple et régulière. Pourtant, nous avons déjà dû formuler manuellement de nombreuses règles de réécriture. Pour des architectures plus complexes, avec des instructions et des modes d’adressage très variés, on ne peut plus formuler manuellement toutes les règles nécessaires. On utilise un algorithme dédié pour choisir, parmi les différentes traductions possibles, laquelle minimise une certaine fonction de coût. On consultera par exemple le livre d’Andrew Appel, « Modern compiler implementation in ML », chapitre 9, « Instruction Selection ». Le sujet donne encore lieu à des recherches; voir par exemple les articles de Dias et Ramsey (CC 2006, POPL 2010).

Une solution au TD, pour ce qui concerne l’optimisation des opérations binaires, est donnée dans upp2upp.ml. On lira notamment les commentaires à propos des règles de réécriture. Cette solution n’est pas complète: on pourrait imaginer encore plus de règles.


Ce document a été traduit de LATEX par HEVEA