L'assembleur MIPS
Ce TP a pour objectif de vous faire comprendre l'assembleur MIPS
et le fonctionnement d'un processeur.
Ces connaissances vous seront nécessaires pour générer le code
lorsque vous allez compiler du Java et pour comprendre comment
est construit un ordinateur à partir de transistors.
Le mémento MIPS donne une documentation de base du langage assembleur MIPS. Pour une information plus complète, vous devez consulter le menu Help intégré dans l'application MARS.
Dans ce TP, nous n'utiliserons pas l'ensemble des instructions MIPS.
En effet, certaines instructions sont en fait des pseudo-instructions,
ce qui fait que, quand on utilise ces instructions,
le code généré n'est pas exactement celui que vous avez écrit.
Voici la liste des instructions que vous devez utiliser dans ce TP.
Dans cette liste, imm16 est une valeur immédiate sur 16 bits,
et $t1, $t2 et $t3 sont des registres quelconques.
lui $t1, imm16 | $t1 = (imm16 << 16) (décale de 16 bits imm16 avant de le stocker dans $t1). |
lbu $t1, ($t2) | Charge l'octet se trouvant à l'adresse mémoire $t2 dans les 8 premiers bits de $t1, et complète le reste avec des zéros. |
lw $t1, ($t2) | Charge les 4 octets se trouvant à l'adresse mémoire $t2 dans $t1. |
sb $t1, ($t2) | Écrit les 8 premiers bits de $t1 à l'adresse $t2. |
sw $t1, ($t2) | Écrit les 4 octets de $t1 à l'adresse $t2. |
b label | Saute vers le label. |
beq $t1, $t2, label | Saute vers le label si $t1 == $t2. |
addu $t1, $t2, $t3 | $t1 = $t2 + $t3. |
addiu $t1, $t2, imm16 | $t1 = $t2 + imm16. |
jal label | Appelle la fonction label. Stocke l'adresse de retour dans le registre $ra. |
jr $t1 | Saute vers l'adresse stockée dans le registre $t1. |
syscall | Appelle système ($v0 = 10 exit, $v0 = 11 affiche le caractère se trouvant dans $a0, $v0 = 1 affiche l'entier se trouvant dans $a0). |
- $zero reste toujours à 0,
- $v0 à $v1 sont utilisés pour les valeurs de retours des fonctions et en entrée des syscall,
- $a0 à $a3 sont les 4 premiers paramètres lors d'un appel de fonction et peuvent être écrasés par l'appelé,
- $t0 à $t9 sont des registres libres qui peuvent être écrasés par l'appelé lors d'un appel de fonction,
- $s0 à $s7 sont des registres libres qui ne doivent pas être écrasés par l'appelé (attention, lorsque vous écrivez une fonction, c'est à vous de les préserver),
- $ra est un registre utilisé lors d'un appel de fonction.
- $fp est un registre utilisé pour gérer le cadre d'appel (frame) d'une fonction.
Prise en main (∼ 20mn)
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.
Notez que la case mémoire 0x10010000 contient le caractère 'a'
puisque, dans le code source, on a imposé le chargement des données à l'adresse
0x10010000 et que nous avons déclaré une variable d'un octet
avec .byte.
Vérifiez que cette case mémoire contient bien la valeur 0x61 qui est le code du caractère 'a'.
Ce code s'appelle le code ASCII du caractère.
À venir
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 ?
À venir
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.
.ascii "Avec ses quatre dromadaires\n"
.ascii "Don Pedro d'Alfaroubeira\n"
.ascii "Courut le monde et l'admira.\n"
.ascii "Il fit ce que je voudrais faire\n"
.ascii "Si j'avais quatre dromadaires.\n"
.byte 0 # zero de fin de chaîne de caractères
Affichage d'une chaîne de caractères (∼ 30mn)
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.
Félicitations, vous savez maintenant écrire une boucle et manipuler des tableaux en assembleur !
Pour construire une boucle d'un langage de haut niveau comme :
il suffit de respecter ce schéma :
for(initialisation; test-de-continuation; iteration-suivante) {
corps-de-boucle
}
initialisation
_label_saut:
si test-de-continuation répond faux, saute en _label_apres
corps-de-boucle
iteration-suivante
saute en _label_saut
_label_apres:
Calcul des fréquences (∼ 20mn)
Cet exercice a pour but de calculer la fréquence d'apparition des lettres
dans le poème.
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.
À venir
Après avoir calculé l'adresse du poème, stockez dans $s2
l'adresse du tableau des fréquences.
À venir
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.
À venir
Fonctions (∼ 30mn)
Dans cet exercice, nous concevons des fonctions.
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 :
.text # .text = code
lui $s0, 0x1001 # upper immediate of data segment
addiu $s1, $s0, 256 # $s1 <- poeme
addiu $s2, $s0, 0 # $s2 <- frequences
b compute_frequencies
retour:
addiu $v0, $zero, 10
syscall
compute_frequencies:
_lcf:
...
_alcf:
b retour
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.
addiu $sp, $sp, -12 # reserve 12 octets dans la pile
sw $ra, 0($sp) # sauvegarde $ra en $sp + 0
sw $s1, 4($sp) # sauvegarde $s1 en $sp + 4
sw $s2, 8($sp) # sauvegarde $s2 en $sp + 8
À venir
Variables locales (∼ 50mn)
Cet exercice a pour but de vous faire manipuler des variables locales en
écrivant une fonction récursive classique permettant de calculer la factorielle d'un nombre.
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 :
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.
- 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.
if("cond") {
"code-vrai"
} else {
"code-faux"
}
beq cond est faux, saute vers cas_faux
"code_vrai"
saute vers cas_commun
cas_faux:
"code_faux"
cas_commun:
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.
Il n'est pas nécessaire de restaurer $a0 à la fin de fact
puisque l'appelant s'attend à ce que ce regsitre soit détruit. Dans notre fonction,
nous sauvegardons $a0 de façon à pouvoir le réutiliser
lorsque nous effectuerons la multiplication à la question suivante.
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).
L'instruction mult $t0, $t1 multiplie les deux registres
et stocke le résultat dans deux registres cachés nommés $hi (partie haute du résultat)
et $lo (partie basse du résultat).
Vous pouvez copier la valeur de $lo dans un autre registre avec
mflo $t0 (move from low).
À venir
Affichage des fréquences (∼ 50mn, optionnel)
Reprenez le programme que vous avez réalisé dans l'exercice 5 (calcul des fréquences),
et ajoutez dans ce programme une fonction permettant d'afficher les fréquences lorsqu'elles sont différentes de 0.
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.
À venir