Compilation : De l'algorithme à la porte logique (2023-2024)

Pour commencer, téléchargez le fichier skel.asm qui se trouve ici et renommez le en freq.asm. Ensuite, lancez l'émulateur mars. Comme pour les autres outils utilisés dans le cours, vous le trouverez dans le répertoire $LIBCOMP/bin. Dans mars, chargez freq.asm (menu File->Open) et assemblez le (menu Run->Assemble). Vous devriez 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. 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 et exécutez pas à pas votre programme (touche de lecture avec un 1). En vous aidant du cours, de la documentation donné au début de ce TP, du code exécuté, des commentaires et de l'état des registres, essayez de comprendre 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 lancez votre programme. Que constatez-vous ?

Allez sur le code source du programme (bouton edit). Supprimez la déclaration de 'a' et remplacez là 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 ASCII dans data segment. Remarquez que notre déclaration se termine par un .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.

Nous allons maintenant afficher tous les caractères constituant la chaîne de caractères. Pour cela, nous aurons besoin de définir une étiquette (label), c'est-à-dire un emplacement dans le code auquel nous donnons un nom de façon à pouvoir sauter à cet emplacement. Pour définir une étiquette de nom name, il suffit d'ajouter une déclaration name: dans le code. Ajoutez une étiquette nommée _lcf (pour loop compute frequency) avant de lire la valeur se trouvant à l'adresse $s1, et une étiquette _alcf (after lcf) après le syscall qui affiche le caractère se trouvant dans $a0.

Assemblez votre programme et vérifiez que l'ajout des étiquettes ne change rien au code généré. C'est normal : une étiquette ne génère pas de code, elle ne définit qu'un point de saut.

Avant d'afficher le caractère courant, ajoutez le code permettant de sauter en _alcf quand on est à la fin de la chaîne. Comme votre programme ne boucle pas encore, cette modification ne devrait rien changer et votre programme devrait toujours afficher 'A'.

Après avoir lu le caractère se trouvant en $s1 dans $a0, il faut utiliser beq pour comparer $a0 à $zero (qui vaut toujours 0) avant de sauter sur _alcf.

Modifiez votre code de façon à sauter (instruction b) sur _lcf après avoir affiché le caractère. Avant d'effectuer ce saut, modifiez $s1 pour passer au caractère suivant.

Pour stocker les fréquences, nous aurons besoin d'un tableau d'octets (on considère qu'une lettre ne peut pas apparaître plus de 256 fois). Comme dans notre exercice, nous calculerons toutes les adresses des variables à la main, il vaut mieux déclarer ce tableau avant le poème. En effet, compter le nombre de lettres du poème pour trouver l'adresse qui se trouve après semble légèrement fastidieux, alors qu'en déclarant le tableau en premier, il est facile de voir que le poème se trouve à l'adresse 0x10010000 + 256. En effet, une lettre est encodée sur 1 octets et, ce qui fait qu'en informatique, l'alphabet possède 256 lettres (il faut compter les lettres accentuées ou les caractères spéciaux).

Pour déclarer un tableau, il faut utiliser .space N, où N est le nombre d'octets réservé pour le tableau. Dans notre cas, comme un caractère est encodé sur un octets, nous avons besoin d'un tableau de 256 octets pour stocker les fréquences : un octet par caractère possible. Assemblez votre programme et vérifiez que les 256 premiers octets du segment de données contiennent bien des zéros et que les octets suivants contiennent bien toujours le poème.

Actuellement, $s1, qui devrait contenir l'adresse de la première lettre du poème, contient l'adresse du premier élément du tableau de fréquences que vous venez de déclarer. Si vous lancez votre programme, vous devriez constater qu'il n'effectue plus aucun affichage puisque le tableau des fréquences est initialisé avec des zéros qui sont interprétés par votre code comme des caractères de fin de chaîne. Modifiez votre programme de façon à stocker l'adresse du début du poème dans $s1. Vérifiez que votre programme affiche de nouveau le poème.

Après avoir calculé l'adresse du poème, stockez dans $s2 l'adresse du tableau des fréquences.

Avant d'afficher la lettre courante, modifiez votre programme pour mettre à jour la fréquence de la lettre courante. À cette question, utilisez les registres $t0/$t9 pour stocker vos valeurs intermédiaires (vous comprendrez mieux comment on choisit quel registre utiliser dans l'exercice suivant).

Il faut commencer par calculer l'adresse de la case qui contient le nombre d'occurrences de la lettre courante. La lettre courante se trouve dans $a0 et le début du tableau des fréquences dans $s2. Il suffit donc d'additionner ces deux registres pour trouver l'adresse de la case qui contient le nombre d'occurrences de la lettre courante. Ensuite, il faut charger incrémenter de 1 la valeur stockée à cette adresse. Il faut charger l'octet se trouvant à cette adresse dans un registre, incrémenter ce registres, puis écrire la valeur de ce registre à cette même adresse.

Pour commencer, nous allons juste restructurer notre programme de façon à commencer à transformer le code qui calcule la fréquence en une fonction. Pour cela, ajoutez un label compute_frequencies à la fin de votre programme (après le syscall qui quitte le programme). Ensuite, déplacez tout le code qui calcule les fréquences après le label compute_frequencies, c'est-à-dire le code allant du label _lcf jusqu'au label _alcf. Enfin, à la place de ce code, ajoutez un saut vers compute_frequencies avec l'instruction b, 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.

Votre code devrait respecter le schéma suivant :

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. 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'appelant. 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).

Il faut remplacer le b retour par un jr $ra puisque l'adresse de retour est placé dans $ra par le $jal.

Dans notre fonction, nous supposons que $s1 contient l'adresse de la chaîne de caractère et que $s2 contient l'adresse du tableau des fréquences. En effet, dans notre version sans fonction, ce sont ces registres que nous avons utilisés pour stocker ces adresses. 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 va donc adapter 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 va continuer à utiliser $s1 pour stocker l'adresse du poème et $s2 pour stocker l'adresse du tableau des fréquences. En revanche, maintenant, on va transmettre ses valeurs via $a0 et $a1 et, au début de la fonction, 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é. 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étruit 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 $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 ce $ra même quand c'est inutile est une bonne habitude.

Avant de préserver les valeurs de $s1, $s2 et $ra, on va d'abord créer 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. Pour cela, vous pouvez utiliser les formes évoluées des instructions lw et sw qui permette 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.

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 quitter en appelant syscall avec comme numéro d'appel 10 (on vous rappelle que le numéro d'appel système est transmis dans $v0).

Dans votre programme, définissez une fonction nommée fact. Comme notre programme respecte les conventions d'appels, fact s'attend à recevoir un paramètre entier dans le registre $a0. Appelez la fonction fact avec comme paramètre 10. Vérifiez que votre programme se termine correctement en l'exécutant pas à pas.

À terme, l'algorithme que nous allons mettre 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.

De façon à simplifier le travail, à cette question, nous simplifions le problème : dans le cas où $a0 est différent de 0, notre fonction va, pour le moment, renvoyer 2.

Pour construire la conditionnelle Il faut respecter le schéma suivant en assembleur :

Techniquement, si la condition est vraie, alors le code se poursuit dans "code_vrai" puis saute le "code_faux" pour se poursuivre en cas_commun. Si la condition est fausse, alors le beq saute le "code_vrai" pour sauter vers "cas_faux" et l'exécute avant de se poursuivre en cas_commun comme dans le cas où la condition est vraie.

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 une résultat via le registre $v0.

Modifiez le code de façon à afficher 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.

Maintenant que la conditionnelle est correcte, nous nous occupons de l'appel récursif. Comme fact appelle 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 la valeur de $ra à la fin de la fonction.

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

Commencez par écrire une fonction print_frequency prenant an argument deux paramètres $a0 et $a1. $a0 est un caractère et $a1 sa 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 (attention, vous allez déplacer la zone contenant le poème, pensez à mettre à jour votre appel à compute_frequencies). Il faut savoir que l'appel système 1 affiche l'entier se trouvant en $a0 et que l'appel système 4 affiche la chaîne de caractères terminée par un zéro se trouvant en $a0.

Écrivez la fonction print_frequencies permettant d'afficher toutes les fréquences non nulles.