CSC4251_4252 — Compilation : du langage de haut niveau à l'assembleur

Nous utilisons l'outil MARS (MIPS Assembler and Runtime Simulator) pour éditer, compiler, et émuler du code assembleur MIPS. Pour installer MARS, créez un répertoire dédié et télécharger l'archive JAR de l'émulateur MARS (mars.jar), ainsi que le script d'exécution de l'émulateur (mars). Ajoutez les droits d'exécution sur le script mars, et complétez votre variable d'environnement PATH avec le répertoire contenant l'archive et le script d'exécution de MARS.

Téléchargez le premier programme MIPS (fichier skel.asm), puis renommez skel.asm en freq.asm.

Démarrez l'émulateur MARS (commande mars). Ensuite, chargez freq.asm (menu File > Open) et assemblez-le (menu Run > Assemble).

Vous devez voir une fenêtre qui contient :

• à gauche, le code assembleur en haut, l'état de la mémoire à l'adresse 0x10010000 au milieu et la console en dessous.
• à droite, l'état des registres (avec leur nom symbolique et leur numéro),

Exécutez le programme en appuyant sur la touche de lecture verte Run > Go. Vérifiez que vous voyez le caractère « a » s'afficher dans la console. Revenez au début du programme en appuyant sur la flèche verte de retour arrière Run > Reset et exécutez pas à pas votre programme avec la touche verte Run > Step. En vous aidant du cours, de la documentation donnée au début de ce TP, du code exécuté, des commentaires et de l'état des registres, comprenez ce que fait votre programme à chaque pas.

Revenez au début du programme. Avant de relancer votre programme, modifiez le contenu de l'adresse 0x10010000 en double cliquant sur le 0x00000061 dans la zone data segment. Remplacez cette valeur par 0x00000062 et exécutez votre nouveau programme. Que constatez-vous ?

Positionnez-vous sur le code source du programme (bouton edit). Supprimez la déclaration de la variable caractère (.byte 0x00000062) et remplacez-la par le code suivant :

Assemblez votre programme et exécutez-le. Vérifiez que le programme affiche bien maintenant le « A » du début du poème d'Apollinaire. Observez aussi le contenu de la mémoire : vous pouvez voir que la mémoire se trouvant en 0x10010000 contient bien tout le poème. Pensez que vous pouvez voir les caractères représentés par les codes hexadécimaux en appuyant sur la case à cocher ASCII dans le cadre Data Segment. Remarquez que notre déclaration se termine par la ligne .byte 0. Cette déclaration ajoute un 0 à la fin de la chaîne de caractères. Nous nous servirons de ce marqueur dans la suite de l'exercice pour identifier la fin de la chaîne de caractères.

Pour commencer, nous restructurons a minima notre programme pour extraire dans une fonction le code qui calcule la fréquence. Pour ce faire :

• Ajoutez un label compute_frequencies à la fin de votre programme (après le syscall qui quitte le programme).
• Déplacez tout le code qui calcule les fréquences après le label compute_frequencies, c'est-à-dire le code allant du label blcf jusqu'au label alcf.
• À la place du code déplacé, ajoutez un saut vers compute_frequencies avec l'instruction b. Puis, ajoutez derrière un label retour, et, à la fin du code qui calcule la fréquence, ajoutez un saut vers ce label retour.
• Vérifiez que votre programme affiche toujours le poème, calcule toujours les fréquences, et se termine toujours correctement.

Dans la suite, le code qui va de compute_frequencies: à b retour s'appelle la fonction compute_frequencies. Pour le moment, notre fonction ne permet que de revenir au label retour, ce qui est loin d'être idéal. En effet, à la fin d'un appel de fonction, on s'attend à ce que le flot d'exécution reprenne à l'instruction qui suit l'appel. Dans notre cas, si on appelait plusieurs fois compute_frequencies, les deux appels reviendraient au même point du programme, ce qui est incorrect.

Pour appeler une fonction, l'assembleur MIPS offre une instruction nommée jal label (Jump And Link). Tout comme l'instruction b label, jal label saute vers le label label. En revanche, contrairement à b label, jal label stocke l'adresse de l'instruction qui suit le jal dans le registre $ra (Return Address). À la fin de la fonction, au lieu de sauter directement sur un label comme on le fait avec l'instruction b retour, on peut sauter vers l'adresse stockée dans un registre avec l'instruction jr (Jump Register).

Modifiez votre programme de façon à utiliser jal pour appeler compute_frequencies et jr pour revenir vers l'appelante. Supprimez le label retour et vérifiez, en exécutant pas à pas votre programme, que votre programme est toujours correct (c'est-à-dire qu'il affiche toujours le poème, calcule les fréquences et se termine correctement).

Dans notre fonction, nous supposons que $s1 contient l'adresse de la chaîne de caractères et que $s2 contient l'adresse du tableau des fréquences. Ce choix de registres est relativement aléatoire et incompatible avec ce qu'un compilateur d'un langage de haut niveau pour MIPS générerait. En effet, par convention, les quatre paramètres doivent être transmis via les registres $a0 à $a3.

On adapte donc le code de notre fonction pour respecter cette convention. De façon à minimiser l'impact de cette modification qui pourrait nécessiter de renommer tous les registres dans notre code, on continue à utiliser $s1 pour stocker l'adresse du poème et $s2 pour stocker l'adresse du tableau des fréquences. En revanche, maintenant, on transmet ses valeurs via $a0 et $a1, et au début de la fonction, on les recopier de façon adéquate dans les registres $s1 et $s2. Effectuez cette modification.

Notre fonction utilise des registres. Il faut savoir que, par convention, une fonction a le droit d'écraser la plupart des registres, mais pas les registres $s0 à $s7 qui doivent être préservés par l'appelée. Dans notre cas, notre fonction doit donc préserver les registres $s1 et $s2.

Pour respecter cette convention, nous pourrions, par exemple, utiliser les registres $t6 et $t7 à la place des registres $s1 et $s2. Toutefois, cette solution n'est pas satisfaisante car ces registres peuvent être détruits par le syscall qui affiche les caractères.

Pour préserver ces registres, nous vous proposons donc d'utiliser des variables locales. Une variable locale est une variable en mémoire qui n'existe que le temps d'un appel de fonction. Les variables locales sont stockées dans une zone pré-allouée au démarrage du processus et qui s'appelle la pile. À chaque instant, le registre $sp indique où se trouve le bas de la pile, c'est-à-dire l'adresse de la dernière variable locale créée. Pour créer une nouvelle variable locale, il suffit donc de soustraire 4 à $sp : notre nouvelle variable locale se trouve à l'adresse $sp. Pour supprimer la variable locale, il suffit alors d'ajouter 4 à $sp.

Dans notre fonction, nous aurons besoin de 3 variables locales : une pour préserver $s1, une pour préserver $s2, et une dernière pour stocker le $ra à l'entrée de la fonction. Cette dernière variable locale n'est pas nécessaire dans notre cas, mais si compute_frequencies appelait une sous-fonction, celle-ci écraserait $ra. Il faudrait donc préserver le registre $ra à l'entrée de la fonction afin de le restaurer à la fin. Comme appeler des sous-fonctions est extrêmement fréquent, préserver $ra même quand c'est inutile est une bonne habitude.

Avant de préserver les valeurs de $s1, $s2, et $ra, on crée l'espace pour accueillir ces variables locales sur la pile. Au début de compute_frequencies, ajoutez -12 (3 variables de 4 octets) à $sp et, à la fin de la fonction, ajoutez 12 à $sp. Vérifiez que $sp reprend bien sa valeur initiale à la fin de la fonction.

Sauvegardez les registres $s1, $s2, et $ra au début de votre fonction, et restaurez-les à la fin de la fonction. Pour cela, vous pouvez utiliser les formes évoluées des instructions lw et sw qui permettent d'ajouter une constante à une adresse avant d'effectuer un accès mémoire :

De façon symétrique, vous pouvez utiliser la forme lw $t1, n($sp) pour restaurer les valeurs des registres.

Vérifiez que les registres $s1, $s2 et $sp ne sont pas modifiés par l'appel à compute_frequencies.

Reprenez le programme que vous avez réalisé dans la question 4.d (calcul des fréquences), et ajoutez dans ce programme une fonction permettant d'afficher les fréquences lorsqu'elles sont différentes de 0. Nous proposons de procéder en deux temps : (1) une fonction print_frequency pour l'affichage de la fréquence d'un des 256 caractères, et (2) une fonction print_frequencies pour la boucle d'appel de la fonction print_frequency pour les 256 caractères.

Commencez par écrire la fonction print_frequencies permettant de préparer l'appel à la fonction print_frequency pour toutes les fréquences non nulles. L'adresse du tableau des fréquences est passée en paramètre via le registre $a0.

Continuez avec l'écriture de la fonction print_frequency prenant en argument deux paramètres $a0 et $a1, $a0 contenant le caractère et $a1 la valeur de la fréquence. Votre fonction doit afficher $a0 => $a1\n. Pour cela, ajoutez les chaînes de caractères «  =>  » et « \n » dans votre segment de données :

• la zone contenant le poème étant déplacée, pensez à mettre à jour votre appel à compute_frequencies, c'est-à-dire à la valeur mise dans le registre $a0 avant l'appel de fonction ;
• la nouvelle valeur est calculée comme suit : chaîne de caractères «  =>  » (ne pas oublier l'octet de fin de chaîne de caractères 0) + « \n » (idem pour l'octet 0 à la fin de la chaîne de caractères), soit $s0 + 256 + 4 + 1 + 1 + 1 = $s0 + 263.

Commencez par écrire un programme nommé fact.asm. Dans ce programme, vous n'avez pas besoin de définir de variable. Le programme doit simplement appeler la fonction fact et quitter en appelante syscall avec comme numéro d'appel 10 (transmis via le registre $v0).

La fonction fact s'attend à recevoir un paramètre entier dans le registre $a0. Appelez la fonction fact avec comme paramètre 10.

Nous aurons un appel récursif de la fonction fact, l'appel imbriqué détruit $ra (l'adresse de retour) et $a0 (le paramètre de fact) qui va être nécessaire pour effectuer la multiplication finale. Pour cette raison, vous avez besoin de deux variables locales pour stocker temporairement $ra et $a0. Avec $sp, créez 2 variables locales à l'entrée de fact et détruisez-les à la sortie de fact. Sauvegardez $ra et $a0 dans ces variables locales à l'entrée de fact, et restaurez les valeurs de $ra et $a0 à la fin de la fonction.

Vérifiez que votre programme se termine correctement en l'exécutant pas à pas.

À terme, l'algorithme que nous mettons en œuvre est le suivant :

• si $a0 est égal à 0 ($zero), fact renvoie 1,
• sinon, fact renvoie le résultat de l'appel à fact avec comme paramètre $0 - 1 multiplié par $a0.

Dans cette question, nous considérons que, dans le cas où $a0 est différent de 0, la fonction renvoie pour le moment 2.

Voici le schéma en assembleur pour construire la conditionnelle if("cond") { "code-vrai" } else { "code-faux" } :

Mettez en œuvre l'algorithme simplifié qui consiste à renvoyer 1 dans le cas où $a0 est égal à 0, et 2 sinon. Par convention, une fonction renvoie un résultat via le registre $v0.

Affichez la valeur de $v0 après l'appel à fact (appel système 1 qui affiche $a0 sur le terminal).

Vérifiez qu'un appel à fact(0) entraîne l'affichage 1 et qu'un appel à fact(10) entraîne l'affichage 2.

Dans fact, utilisez l'instruction mult pour multiplier le résultat de l'appel récursif à fact par le contenu de la variable locale utilisée pour préserver $a0. Ensuite, placez le résultat de l'instruction mult dans $v0 de façon à ce que ce soit la valeur renvoyée par fact (pensez à supprimez l'affectation de $v0 à 2).

Nous utilisons l'exemple de la fonction factorielle. L'algorithme écrit en JAVA de la fonction factorielle est le suivant :

Décomposons le code JAVA de factorielle pour faire apparaître les variables temporaires. Cette décomposition est faite par le compilateur, c'est-à-dire que c'est l'une des questions à résoudre avant la phase de génération du code MIPS : ce sera l'un des rôles de la phase qui précède la génération du code MIPS, nommément la génération de la forme intermédiaire. Voici la décomposition que nous proposons d'écrire dans le compilateur MiniJAVA :

NB : la traduction en assembleur de la fonction ne correspond pas exactement à ce que le compilateur MiniJAVA proposera, mais le principe est maintenu.

Voici le code assembleur respectant la convention d'appel MIPS : exo6a.mips

Dessinez l'évolution du contenu de la pile pour l'exécution de la fonction factorielle avec l'argument 2, soit pour la séquence d'appel factorielle(2)[factorielle(1)[factorielle(0)]]. Dans un premier temps, on pourra s'arrêter à l'appel factorielle(2).

Voici un exemple de fonction avec plus de 4 paramètres ; cette fonction requiert le passage des quatre premiers paramètres par les registres $a0—3 et le passage des paramètres au delà du quatrième via la pile :

La décomposition pour faire apparaître les variables locales est la suivante :

Voici pour étude le code assembleur MIPS avec respect de la même convention d'appel. Votre attention doit être tout spécialement portée sur la gestion du passage des paramètres  les 4 premiers via les registres $a0—4 et les suivants sur la pile. Notez que l'appel écrit dans le « main » du programme assembleur est permut(6, 0, 1, 2, 3, 4, 5) : exo6b.mips.

Dessinez l'évolution du contenu de la pile pour l'exécution de la fonction permut avec les arguments 6, 0, 1, 2, 3, 4, 5.