Expressions et registres

Présentation

Les sources sont dans l’archive td5-upp2rtl.tar.gz, on construit l’exécutable avec la commande make.

On continue le travail de transformations sur l’AST (Arbre de Syntaxe Abstraite) représentant le programme. On a obtenu la dernière fois un programme dans un langage intermédiaire UPP qui utilise les opérateurs MIPS, mais sépare toujours les expressions des instructions. La transformation de UPP en RTL consiste justement à transformer chaque expression en une séquence d’instructions équivalentes, ce qui oblige à introduire des variables intermédiaire qu’on appelle pseudo-registres. En particulier, chaque variable locale est transformée en pseudo-registre.

Ces transformations du graphe de flot de contrôle sont l’occasion de passer des structures de contrôle de haut-niveau (if-then-else, while) à des structures équivalentes de bas-niveau (label et goto). Chaque instruction possède un label qui l’identifie de façon unique, et un ou plusieurs labels qui représentent la ou les instructions à exécuter juste après. Une instruction goto est un transfert de contrôle inconditionnel, qui servira à traduire la boucle while.

Commencez par comparer les définitions des langages source et cible de la transformation, dans UPP.mli et RTL.mli. Vous pouvez vous contenter pour ce TD d’examiner les instructions, vous n’aurez pas à traduire les procédures.

Pour commencer

Le code de la transformation se partage entre les fichiers upp2rtl.ml et upp2rtlI.ml (I comme Implémentation). Le premier est donné, le second est à compléter, c’est lui qui contient les éléments essentiels :

let translate_expression (destr : Register.t) (e : UPP.expression) (destl : Label.t) : Label.t = ...

let translate_condition (c : UPP.condition) (truel : Label.t) (falsel : Label.t) : Label.t = ...

let translate_instruction (i : UPP.instruction) (destl : Label.t) : Label.t = ...

• translate_expression prend en argument une expression e, construit une séquence d’instructions équivalentes, et retourne le label représentant la première instruction de la séquence. Cela nécessite de connaître à l’appel le label destl de l’instruction qui suit et le registre destr où stocker le résultat de l’évaluation de l’expression.
• translate_condition prend en argument une condition c, construit une séquence d’instructions équivalentes, et retourne le label représentant la première instruction de la séquence. Les paramètres supplémentaires sont les labels associés aux instructions à exécuter ensuite, truel si la condition est vraie et falsel si la condition est fausse.
• translate_instruction transforme une instruction UPP en instruction ou séquence d’instructions RTL équivalentes. Là-encore, il est nécessaire de donner à la fonction le label destl de l’instruction suivante.

La traduction de la plupart des instructions vous sont données dans la fonction translate_instruction. Relisez le code pour comprendre le fonctionnement à rebours de ces fonctions de transformation : on part du label de l’instruction suivante et on renvoie le label de l’instruction nouvellement créée.

Détail important : remarquez l’utilisation de la fonction allocate pour créer un nouveau pseudo-registre.

Pour vous échauffer, traitez le cas d’une constante dans translate_expression. Cela permet d’interpréter correctement le code RTL d’un programme trivial qui appelle writeln :

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

Un langage inexpressif (sans expressions ;0)

On va compléter progressivement la fonction translate_expression. Il faudra utiliser les sous-fonctions suivantes :

let lookup (var_name : string) : Register.t = ...

let allocate () : Register.t = ...

let generate (instr : RTL.instruction) : Label.t = ...

• lookup associe à un nom de variable locale le pseudo-registre représentant cette variable.
• allocate renvoie un nouveau pseudo-registre.
• generate associe à une instruction un nouveau label.

Variables globales et appels de fonctions

Le cas le plus simple est celui de la lecture d’une variable globale, pour lequel presque rien ne change. Idem pour un appel de fonction, avec l’utilisation de translate_call.

Variables locales

Le cas de la lecture d’une variable locale est à peine plus compliqué. Il n’y a pas d’opérateur de copie d’un registre dans un autre, il faut trouver une traduction équivalente en utilisant les opérations MIPS.

Note : Essayez d’utiliser l’opérateur UOpAddi avec des arguments bien choisis.

Vous complèterez aussi le cas de l’écriture d’une variable locale dans translate_instruction.

Opérations unaires/binaires

Les opérations unaires (UPP.EUnOp) et binaires (UPP.EBinOp) produisent des valeurs intermédiaires qui doivent être sauvées dans des pseudo-registres. Attention à l’ordre des instructions générées !

La lecture dans un tableau (UPP.Load) se traite de manière similaire.

Un langage inconditionnel (sans conditions ;0)

En première approche

On cherche maintenant à compléter le code de translate_condition. On remplace les conditions par des instructions de branchement conditionnel. On se contente pour l’instant de tester la non-nullité de la condition (fonction mkunbranch).

On finit par les opérateurs logiques UPP.CNot, UPP.CAnd et UPP.COr, en n’oubliant pas le caractère paresseux des deux derniers.

Pour pouvoir tester vos traductions, vous aurez aussi besoin de traiter le cas du if dans translate_instruction.

Note : Une seule expression Pseudo-Pascal peut avoir des effets-de-bord, laquelle ? Est-ce vrai dans d’autres langages que vous connaissez (C, Java, OCaml) ?

En y réfléchissant mieux

Considérez le test test/gcdfunc.p, qui contient de nombreuses conditions, et imprimez votre traduction :

# ./compilo -drtl test/gcdfunc.p

Que pensez-vous de la traduction des conditions ? Pourrait-on l’améliorer en tenant compte des tests autorisés par MIPS dans les branchements ? (consultez les types MIPSOps.uncon et MIPSOps.bincon pour le détail des tests en RTL)

En effet, MIPS autorise certains tests binaires comme condition de branchement. Quand c’est possible, on essaiera donc de traduire la condition binaire par un test binaire (fonction mkbinbranch).

On cherchera ensuite à profiter des tests unaires de comparaison à zéro (UConGez, UConGtz, UConLez, UConLtz), quand les opérateurs correspondants apparaissent dans la condition en UPP.

Vérifiez sur test/gcdfunc.p que vos optimisations ont l’effet désiré.

Boucler la boucle

La seule instruction qui n’est pas déjà traduite est la seule qui pose problème, la boucle UPP.IWhile. Est-ce que vous voyez pourquoi ?

Le problème est que la fonction generate qui associe une instruction à un label crée un nouveau label après que l’instruction ait été créée. Il est donc impossible d’utiliser ce nouveau label pendant la traduction de l’instruction, et donc de créer une boucle.

Que faire ?

On a besoin d’une nouvelle fonction pour associer un label à une instruction. Cette fonction devrait :

• générer un nouveau label nouvl,
• utiliser ce nouveau label comme destination de l’instruction,
• traiter l’instruction et récupérer le label associé instrl,
• boucler la boucle, c’est-à-dire créer une instruction associée au label nouvl qui transfère le contrôle à instrl.

Appelons loop cette fonction, avec la signature :

let loop (f : Label.t -> Label.t) : Label.t = ...

Traduisez le cas UPP.IWhile de la fonction translate_instruction, en utilisant la fonction loop.

Vous avez un traducteur complet de UPP vers RTL, que vous pouvez tester avec la commande make rtl.

Suivant le temps qui vous reste, vous pouvez soit implémenter la fonction loop vous-même, en remplaçant l’implémentation existante, ou bien lire le code de la fonction loop existante dans upp2rtl.ml, qui fait exactement ce qui est décrit ci-dessus.

La traduction complète de UPP vers RTL est faite dans le fichier upp2rtlI.ml. Vous pouvez remarquer l’utilisation d’une fonction pick_destination, qui permet d’éviter de générer un pseudo-registre quand ce n’est pas nécessaire (pour une variable locale déjà représentée par un pseudo-registre).

Comme l’implémentation dans upp2rtlI.ml dépend de fonctions définies dans upp2rtl.ml (justement pour ne pas faire dépendre l’implémentation de la structure de graphe de flot de contrôle choisie), on utilise un foncteur, qui est en OCaml un module paramétré, et on prend comme paramètres les fonctions de manipulation du graphe de flot de contrôle.

Enfin, il est intéressant de revenir sur le langage RTL défini dans RTL.mli, pour regarder la description des procédures en RTL. Le fichier upp2rtl.ml détaille comment elles sont traduites.

Ce document a été traduit de L^AT_EX par H^EV^EA