Création du graphe de flot de contrôle

Voici le cours correspondant. La solution se trouve dans le fichier upp2rtlI.ml.

Présentation

Le sujet est constitué par l’archive td5.tar.gz. On construit l’exécutable avec la commande make.

On continue le travail de transformation du programme. On a obtenu la semaine dernière un programme exprimé dans le langage intermédiaire UPP, qui utilise les opérateurs du MIPS, mais repose toujours sur des arbres de syntaxe abstraite, et distingue expressions, conditions, et instructions. La transformation que nous étudions aujourd’hui, de UPP vers RTL, fait disparaître les arbres de syntaxe abstraite, et efface la distinction entre expressions, conditions et instructions: tout devient séquence d’instructions.

Les variables locales (nommées) du programme UPP sont transformées en pseudo-registres (numérotés). Il est facile de créer de nouveaux pseudo-registres. La transformation que nous implémentons en créera parfois pour stocker des résultats intermédiaires.

Les arbres de syntaxe abstraite, qui représentent des structures de contrôle de haut niveau (conditionnelle, boucle), sont remplacés par des structures équivalentes de bas niveau (étiquettes et sauts). Dans RTL, chaque instruction possède une étiquette (ou label) qui l’identifie de façon unique. Chaque instruction porte zéro, un ou deux labels qui représentent ses successeurs dans le graphe de flot de contrôle.

Commencez par comparer les définitions des langages source et cible de la transformation, données par UPP.mli et RTL.mli.

Ce que vous devez implémenter

Pour des raisons pédagogiques, le code de la transformation est partagé en deux fichiers. Le premier, upp2rtl.ml, est donné; il définit quelques fonctions administratives dont vous n’aurez pas à vous soucier. Le second, upp2rtlI.ml,est à compléter. (Le grand «I» peut signifier «intéressant»...) C’est ce second fichier qui contient les fonctions les plus importantes:

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 = ...

Voici les spécifications de ces trois fonctions:

Ces trois fonctions renvoient le label d’entrée des instructions RTL qu’elles ont engendrées.

Dans les trois cas, le graphe de flot de contrôle RTL en cours de construction reste implicite. Pour lui ajouter de nouveaux sommets et de nouvelles arêtes, vous disposez des fonctions generate et loop, décrites ci-dessous.

Ce qui vous est donné

Le module upp2rtlI définit un foncteur, Make. (Un «foncteur» est une fonction qui attend un module et renvoie un module. On peut voir cela comme une simple facilité pour écrire une fonction qui attend de nombreux arguments et renvoie de nombreux résultats.) Les trois fonctions que vous devez compléter, translate_expression, translate_condition et translate_instruction, font partie du résultat de ce foncteur. Pour les implémenter, vous aurez donc accès à l’argument de ce foncteur. Cet argument, nommé Env, vous offre une série de fonctions auxiliaires utiles:

Pour commencer

La traduction de la plupart des instructions est déjà effectuée 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.

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

Traduction des expressions

Vous pourrez ensuite ajouter à translate_expression les cas suivants:

Vous ajouterez également à translate_instruction le cas de l’écriture d’une variable locale (ISetVar).

# ./compilo -irtl test/calcul.p
# 1
# 50

Traduction des conditions

Complétez ensuite translate_condition.

Vous ajouterez également à translate_instruction le cas de la conditionnelle (IIf).

# ./compilo -irtl test/court-circuit.p

Traduction de la boucle

La seule instruction restant à traduire est la boucle (IWhile).

Nous ne pourrons pas engendrer les instructions nécessaires, comme nous l’avons fait jusqu’ici, uniquement à l’aide de la fonction auxiliaire fonction generate. (Pourquoi?) C’est ici que la fonction auxiliaire loop est utile.

Traitez le cas IWhile de la fonction translate_instruction.

Vous avez maintenant un traducteur complet de UPP vers RTL, que vous pouvez tester avec les commandes make rtl ou make test.

Identification des appels terminaux

Le langage RTL offre deux instructions d’appel de procédure: ICall et ITailCall. Examinez la différence entre les deux fonctions auxiliaires (fournies) translate_call et translate_tail_call. Un appel ordinaire rend la main à l’appelant lorsque la fonction ou procédure appelée termine son exécution, tandis qu’un appel terminal ne rend pas la main à l’appelant (il rend la main directement à l’appelant de l’appelant). De ce fait, l’instruction ITailCall demande moins de paramètres: pas besoin de registre destination où stocker le résultat de l’appel, ni de label destination où continuer l’exécution après l’appel.

La question est d’identifier correctement les «appels terminaux», qui peuvent être traduits par ITailCall, par opposition aux appels ordinaires, qui doivent être traduits par ICall.

Un exemple typique d’appel terminal est donné par test/fact3.p, qui implémente une fonction factorielle récursive avec un accumulateur. Le code que produit actuellement votre compilateur contient un appel ordinaire:

# ./compilo -drtl test/fact3.p
# ./compilo -dasm test/fact3.p

Le programme test/tail.p contient d’autres exemples, artificiels, d’appels terminaux.

Ajoutez à la fonction translate_instruction deux cas supplémentaires pour identifier les appels terminaux à une procédure ou à une fonction.

Pour identifier correctement ces situations, vous pourrez avoir besoin des informations auxiliaires is_exit et result. Vous pourrez employer la construction when d’Objective Caml pour indiquer qu’un cas ne s’applique que si une certaine condition est satisfaite. Enfin, une fois l’appel terminal identifié, employez la fonction auxiliaire translate_tail_call pour le traduire.

Vérifiez dans les cas de test/fact3.p et test/tail.p que la traduction est correcte. Au niveau du code assembleur, vous devez observer que le calcul de la factorielle est traduit par une simple boucle. Vérifiez via make test que vous n’avez rien cassé.

Optimisation de la traduction des conditions

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 le processeur MIPS dans les branchements? Consultez la définition des types MIPSOps.uncon et MIPSOps.bincon pour savoir quels tests sont permis.

Améliorez le cas CExpression de la fonction translate_condition pour engendrer des tests plus efficaces lorsque la forme de l’expression le permet. Vous pourrez utiliser à nouveau les fonctions auxiliaires mkunbranch et mkbinbranch.

Vérifiez dans le cas de test/gcdfunc.p que vos optimisations ont l’effet désiré, et vérifiez via make test que vous n’avez rien cassé.


Ce document a été traduit de LATEX par HEVEA