Explicitation de la convention d’appel

Présentation

Le sujet est dans l’archive td6.tar.gz.

Il s’agit aujourd’hui de passer du language RTL, défini dans RTL.mli, au langage ERTL, défini dans ERTL.mli. Étudiez la différence entre ces deux langages, expliquée en particulier par les commentaires introductifs de ERTL.mli.

Pour passer de RTL à ERTL, il faut:

• d’une part, traduire de façon non triviale les instruction d’appel (ICall et ITailCall); c’est le point de vue de l’appelant;
• d’autre part, ajouter à chaque procédure un prologue et un épilogue; c’est le point de vue de l’appelé.

La convention d’appel et les registres du processeur MIPS sont décrits par le fichier MIPS.mli. Par ailleurs, quelques fonctions auxiliaires utiles sont regroupées dans misc.mli. Consultez ces deux interfaces...

Comme la semaine dernière, la traduction est séparée en deux modules. Le module rtl2ertl.ml définit quelques fonctions de base et les fournit au module paramétré rtl2ertlI.ml, que vous allez devoir implémenter.

Aujourd’hui, le fichier rtl2ertlI.ml vous est fourni vide! (C’est pourquoi, si vous avez fait make, la compilation a échoué.) À vous de compléter ce fichier pour satisfaire l’interface rtl2ertlI.mli. (Un peu d’aide?¹) Ceci doit vous permettre de compiler via make. Bien sûr, le petit compilateur ne fonctionne pas.

Ce qui vous est fourni

Vous disposez des informations et facilités offertes par le paramètre Env. Celles-ci sont décrites au début de rtl2ertlI.mli.

Notons que les labels et pseudo-registres de RTL restent valables en ERTL. On utilise si possible les mêmes, mais les fonctions allocate et generate permettent d’en engendrer de nouveaux si besoin.

Ce que vous devez écrire

Voici les éléments qu’il vous faut définir:

• la fonction translate_call construit une séquence d’instructions ERTL qui correspondent à une instruction RTL ICall;
• l’étiquette prologue est le point d’entrée d’une séquence d’instructions qui constitue le prologue; en d’autres termes, l’étiquette prologue deviendra le nouveau point d’entrée de la procédure, et cette séquence d’instructions devra transférer le contrôle à l’ancien point d’entrée de la procédure;
• l’étiquette epilogue est le point d’entrée d’une séquence d’instructions qui constitue l’épilogue; en d’autres termes, un saut sera installé de l’ancien point de sortie de la procédure vers epilogue, et cette séquence d’instructions devra se terminer par IReturn;
• la fonction translate_tail_call construit une séquence d’instructions ERTL qui correspondent à une instruction RTL ITailCall.

Dans un premier temps, vous pourrez d’une part faire l’hypothèse que les appels ont au plus quatre arguments, de sorte que les quatre registres de la liste MIPS.parameters suffisent et la pile n’est pas utilisée; d’autre part implémenter translate_tail_call à l’aide de translate_call, c’est-à-dire compiler les appels terminaux comme des appels ordinaires. Ceci devrait vous permettre d’obtenir plus facilement un compilateur qui fonctionne (presque).

Fonctions auxiliaires – pas à pas

On suggère d’implémenter les fonctions auxiliaires suivantes. Vous pouvez choisir de les écrire d’abord ou de passer tout de suite à la section suivante.

Pseudo-registres et registres physiques

Le language ERTL fournit deux instructions pour copier une valeur d’un pseudo-registre à un registre matériel et inversement: IGetHwReg et ISetHwReg.

On suggère d’implémenter les fonctions suivantes:

let sethwreg ((desthwr, sourcer) : MIPS.register * Register.t) (l : Label.t) : Label.t = ...

let sethwregs (moves : (MIPS.register * Register.t) list) (l : Label.t) : Label.t = ...

let osethwreg ((desthwr, osourcer) : MIPS.register * Register.t option) (l : Label.t) : Label.t = ...

let gethwreg ((destr, sourcehwr) : Register.t * MIPS.register) (l : Label.t) : Label.t = ...

let gethwregs (moves : (Register.t * MIPS.register) list) (l : Label.t) : Label.t = ...

let ogethwreg ((odestr, sourcehwr) : Register.t option * MIPS.register) (l : Label.t) : Label.t = ...

La spécification de ces fonctions est la suivante:

• sethwreg engendre une instruction qui copie le contenu d’un pseudo-registre sourcer vers un registre matériel desthwr et a pour successeur l’étiquette l; renvoie l’étiquette de l’instruction engendrée;
• sethwregs est analogue à sethwreg, mais accepte une liste de paires de registres et engendre une séquence d’instructions;
• osethwreg n’engendre aucune instruction si osourcer est None, et engendre une instruction à l’aide de sethwreg dans le cas contraire;
• gethwreg, gethwregs, ogethwreg sont symétriques aux précédentes.

Pseudo-registres et emplacements de pile

Le language ERTL fournit deux instructions pour transférer une valeur d’un pseudo-registre à un emplacement de pile et inversement: IGetStack et ISetStack.

On distingue pour le moment deux types d’emplacements de pile: les emplacements entrants (SlotIncoming), utilisés pour lire les paramètres en provenance de l’appelant, et les emplacements sortants (SlotOutgoing), utilisés pour écrire des paramètres à destination d’un appelé.

Les emplacements sont représentés par un décalage entier positif ou nul. Ceci nous amène naturellement à écrire les fonctions suivantes:

let offsets (rs : Register.t list) : ((Register.t * int32) list) = ...

let setstackslots (sourcers : Register.t list) (l : Label.t) : Label.t = ...

let getstackslots (destrs : Register.t list) (l : Label.t) : Label.t = ...

La spécification de ces fonctions est la suivante:

• la fonction offsets associe à chaque pseudo-registre de la liste rs un décalage correspondant à l’emplacement qui lui sera alloué (0, 4, etc.) et produit une liste d’association entre pseudo-registres et décalages;
• la fonction setstackslots engendre une séquence d’instructions qui copie chacun des pseudo-registres de la liste sourcers vers un emplacement de pile sortant approprié;
• la fonction getstackslots engendre une séquence d’instructions qui copie un emplacement de pile entrant approprié vers chacun des pseudo-registres de la liste destrs.

Les fonctions setstackslots et getstackslots implémentent respectivement le point de vue de l’appelant et de l’appelé. Elles doivent être d’accord sur l’emplacement attribué à chaque paramètre; ce sera naturellement le cas si elles s’appuient toutes deux sur la fonction offsets.

Explicitation de la convention d’appel

On rappelle brièvement la convention d’appel.

• Du côté de l’appelant – traduction d’un appel:
  • les premiers paramètres sont passés dans les registres de la liste MIPS.parameters, c’est-à-dire en fait $a0, $a1, $a2, $a3;
  • les paramètres suivants sont passés sur la pile, dans la zone des paramètres sortants;
  • l’adresse de retour est placée dans $ra par l’instruction ERTL.ICall – pas besoin pour nous de le faire explicitement, donc;
  • si l’appelé est une fonction, son résultat est transmis dans le registre MIPS.result, c’est-à-dire en fait $v0;
• Du côté de l’appelé – prologue:
  • une trame de pile est installée;
  • les registres callee-save, ainsi que le registre $ra, sont sauvegardés dans des pseudo-registres frais;
  • les premiers paramètres sont lus dans les registres de la liste MIPS.parameters et placés dans des pseudo-registres appropriés;
  • les paramètres suivants sont lus sur la pile, dans la zone des paramètres entrants, et placés dans des pseudo-registres appropriés;
• Du côté de l’appelé – épilogue:
  • si la procédure courante doit renvoyer un résultat, ce résultat est placé dans le registre MIPS.result;
  • les registres callee-save, ainsi que le registre $ra, retrouvent leur valeur initiale;
  • la trame de pile est désinstallée;
  • on rend la main à l’appelant via une instruction IReturn, qui par convention trouve l’adresse de retour dans le registre $ra.

À vous d’implémenter translate_call, prologue et epilogue suivant la description ci-dessus, et à l’aide des fonctions auxiliaires suggérées plus haut.

Pour commencer, implémentez translate_tail_call de façon triviale, à l’aide d’un simple appel à translate_call. Ce sera inefficace – les appels terminaux seront compilés comme des appels ordinaires – mais correct.

Vous pouvez tester le compilateur à l’aide des commandes make ertl et make test.

Compilation efficace des appels terminaux

Il reste à améliorer la fonction translate_tail_call pour compiler efficacement les appels terminaux.

On distingue deux cas, que l’on pourra traiter successivement.

• Si la procédure appelée coïncide avec la procédure courante, alors il est inutile de désinstaller la trame de pile pour la réinstaller aussitôt. On souhaite donc compiler l’appel par un simple saut vers le point d’entrée de la procédure, précédé d’un transfert des paramètres effectifs vers les pseudo-registres censés contenir les paramètres formels.
• Dans le cas général, on souhaite que l’appelant désalloue sa trame de pile avant d’effectuer l’appel. On doit donc transférer les paramètres effectifs vers les registres physiques appropriés, puis exécuter une séquence d’instructions analogue à l’épilogue, à la différence qu’elle se termine non pas par une instruction ERTL.IReturn, mais par une instruction de saut ERTL.ITailCall. On n’implémentera ceci que dans le cas où tous les paramètres sont passés dans des registres physiques, car le cas où certains paramètres sont passés sur la pile serait un véritable casse-tête. Dans ce dernier cas, on se contentera d’un appel à translate_call.

Pour le premier point ci-dessus, on aura besoin d’une fonction:

let parallel_move (destrs : Register.t list) (sourcers : Register.t list) (l : Label.t) : Label.t = ...

Cette fonction engendre une séquence d’instructions dont l’effet est de transférer le contenu des pseudo-registres sourcers vers les pseudo-registres destrs. Les listes sourcers et destrs sont supposées de même longueur. On prendra garde au fait que certains pseudo-registres peuvent apparaître à la fois dans sourcers et destrs!

1

Exécutez d’abord la commande cp -f rtl2ertlI.mli rtl2ertlI.ml, afin de recopier la signature du module Env. Ouvrez ensuite le fichier rtl2ertlI.ml. Remplacez « : sig » par « = struct », puis remplacez les déclarations val par des définitions let. Vous pouvez pour le moment donner des définitions vides à l’aide de la construction assert false.

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