Série corrigée MIPS
Série corrigée MIPS
Programming, Math, etc. · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Le but de cet exercice est de traduire une fonction C calculant la somme des entiers de p à q vers l'assembleur MIPS.
Le code source d'origine présente des anomalies classiques liées à une mauvaise gestion des « branch delay slots » (instructions exécutées pendant le délai de branchement) qui faussent la logique, ainsi qu'un entrelacement déroutant des instructions. Pour garantir un code qui s'exécute correctement sur un simulateur standard (comme SPIM ou MARS), voici le code réparé et remis en ordre séquentiel.
Conformément à la convention MIPS rappelée dans l'énoncé :
$4 contient le premier argument (p).$5 contient le second argument (q).$2 (v0) contient la valeur de retour (s).$3 est utilisé comme registre temporaire pour les comparaisons.sum:
li $2, 0 # Initialise la somme : s = 0
next:
slt $3, $5, $4 # $3 = 1 si q < p
bnez $3, ret # Si q < p (donc $3 != 0), on a terminé, saut vers ret
addu $2, $2, $4 # Ajoute p à s : s += p
addiu $4, $4, 1 # Incrémente p : p++
j next # Recommence la boucle
ret:
jr $31 # Retour à la fonction appelante
Dans cette version corrigée, l'addition conditionnelle est bien protégée par l'instruction de branchement, empêchant ainsi d'ajouter p à la somme si p est déjà supérieur à q dès le premier tour.
Cette fois, on traduit la même fonction sum(p, q) mais sous forme récursive.
Le code extrait de l'énoncé omettait de retourner la valeur q dans le cas de base (lorsque p >= q), altérait le pointeur de pile sans l'avoir initialisé lors d'un retour précoce, et plaçait la sauvegarde des arguments dans des zones décalées. Voici le code MIPS corrigé et fonctionnel.
On applique scrupuleusement la convention O32 décrite dans le rappel : l'appelant fournit un espace de 16 octets minimum au-dessus de sa pile pour que la fonction appelée puisse y sauvegarder ses 4 premiers arguments (registres $4 à $7).
sum:
slt $3, $4, $5 # $3 = 1 si p < q
beqz $3, cas_de_base # Si p >= q, on saute au cas de base
# --- Cas récursif : p < q ---
addiu $29, $29, -12 # Alloue l'espace sur la pile pour 3 mots (12 octets)
sw $31, 8($29) # Sauvegarde l'adresse de retour ($31) sur la pile
sw $5, 16($29) # Sauvegarde q dans l'espace réservé par l'appelant
addiu $5, $5, -1 # Calcule q - 1 et le place dans $5 pour l'appel
jal sum # Appel récursif : sum(p, q - 1)
lw $5, 16($29) # Récupère la valeur d'origine de q
lw $31, 8($29) # Récupère l'adresse de retour d'origine
add $2, $2, $5 # Ajoute q au résultat de sum(p, q-1) : $2 = q + sum
addiu $29, $29, 12 # Réajuste la pile (libère les 12 octets)
jr $31 # Retour à l'appelant
cas_de_base:
# --- Cas de base : p >= q ---
move $2, $5 # La valeur de retour est q (copie $5 dans $2)
jr $31 # Retour direct sans toucher à la pile
La fonction moyenne appelle sum(x, y) puis divise le résultat par y - x + 1.
L'énoncé d'origine contenait une instruction inexistante (addui) et un ordre de sauvegarde des arguments qui supposait l'usage de délais de branchement. De plus, il faut veiller à sauvegarder x et y avant l'appel à sum, car cette dernière modifiera obligatoirement les registres $4 et $5. Voici la logique assainie :
moyenne:
addiu $29, $29, -12 # Alloue l'espace sur la pile (12 octets)
sw $31, 8($29) # Sauvegarde de l'adresse de retour $31
sw $4, 12($29) # Sauvegarde de x dans sa place réservée
sw $5, 16($29) # Sauvegarde de y dans sa place réservée
jal sum # Appelle sum(x, y). Le résultat sera dans $2.
lw $4, 12($29) # Restaure x depuis la pile
lw $5, 16($29) # Restaure y depuis la pile
lw $31, 8($29) # Restaure l'adresse de retour
sub $5, $5, $4 # $5 = y - x
addiu $5, $5, 1 # $5 = (y - x) + 1
div $2, $5 # Effectue la division entière : $2 / $5
mflo $2 # Récupère le quotient depuis le registre LO vers $2
addiu $29, $29, 12 # Restaure la pile (correction de "addui")
jr $31 # Retour à l'appelant
Analysons pas à pas le code fourni :
$t0 est initialisé à 1 (variable i).$v0 est initialisé à 1 (variable v).$t0 à $a0 (l'argument de la fonction). Si i > arg, la boucle se termine.v par i, puis on incrémente i.Cela correspond à une boucle for (ou while) classique. Le code C correspondant est bien celui proposé dans le corrigé source :
int func (int arg) {
int v = 1, i;
for (i = 1 ; i <= arg ; i++) {
v = v * i;
}
return v;
}
Le programme calcule le produit des nombres entiers de 1 jusqu'à l'argument arg (soit 1 × 2 × 3 × ... × arg). Il s'agit donc de la factorielle. Comme précisé dans la source, cette logique fonctionne pour les entiers non-négatifs.
Cet exercice montre l'utilisation des appels système (syscalls) gérés par le système d'exploitation ou le simulateur (comme MARS).
La solution donnée dans la source est parfaitement valide :
main:
li $v0, 5 # Charge 5 dans $v0 (code de l'appel système read_int)
syscall # Interruption : lit un entier au clavier et le place dans $v0
move $t2, $v0 # Sauvegarde l'entier lu dans un registre temporaire $t2
li $v0, 1 # Charge 1 dans $v0 (code de l'appel système print_int)
move $a0, $t2 # Place l'entier à afficher dans $a0 (argument requis pour print_int)
syscall # Interruption : affiche l'entier à l'écran
jr $31 # Fin de la fonction main
L'objectif est de traduire le code C d'une fonction de multiplication itérative vers MIPS.
Le code source proposé contient l'instruction subi $a1, $a1, 1. Or, subi n'est pas une instruction valide dans le jeu d'instructions standard MIPS (il n'existe que addi). Pour soustraire une valeur immédiate, il faut utiliser addi avec une valeur négative. Le code ci-dessous corrige cette erreur :
multiply:
add $t0, $zero, $zero # prod = 0
m_loop:
beq $a1, $zero, m_eol # Tant que y > 0 (si y == 0, on sort de la boucle)
add $t0, $t0, $a0 # prod = prod + x
addi $a1, $a1, -1 # y-- (correction : subi n'existe pas, on additionne -1)
j m_loop # Retour au début de la boucle
m_eol:
add $v0, $t0, $zero # Place le résultat prod dans $v0 (valeur de retour)
jr $ra # Retour à l'appelant ($ra est un alias pour $31)
Le code charge les valeurs pointées par les adresses contenues dans $a0 et $a1 (soit *a0 et *a1).
Il compare ces deux valeurs.
toto et place la valeur de *a1 dans la valeur de retour ($v0).*a0 dans $v0, puis saute à titi (la fin).La fonction réalisée est donc :
Si la valeur pointée par a0 est différente de celle pointée par a1, on retourne la valeur pointée par a1, sinon on retourne celle pointée par a0.
(Note : l'énoncé source résume cela par if a<>b then b else a, en assimilant "a" et "b" aux valeurs pointées).
On initialise $a0 = 0x1234 et $a1 = 3 (0x3).
Détaillons l'exécution :
$t0 est initialisé à 0.toto) :
$t0 = 0 + 0x1234 = 0x1234. $a1 devient 2. $a1 n'est pas nul, on boucle.$t0 = 0x1234 + 0x1234 = 0x2468. $a1 devient 1. On boucle.$t0 = 0x2468 + 0x1234 = 0x369C. $a1 devient 0. On sort de la boucle.srl $t0, $t0, 4 décale logiquement le contenu de $t0 vers la droite de 4 bits. En hexadécimal, décaler de 4 bits vers la droite revient à supprimer le dernier chiffre à droite (division par 16).
0x369C >> 4 = 0x0369.La valeur finale du registre $t0 est donc 0x369.
Le programme boucle tant que $11 n'est pas égal à 0. À chaque itération, il ajoute la valeur de $10 au registre temporaire $1, et décrémente $11. Cela équivaut à réaliser la multiplication de $10 par $11.
Une fois la boucle terminée, le programme ajoute 100 au résultat, et place le tout dans $20.
En une phrase : Le programme calcule le produit des registres $10 et $11, ajoute 100 à ce produit, et place le résultat final dans le registre $20 (soit $20 = $10 × $11 + 100).
(Note: L'instruction subi présente dans le code source est ici aussi fictive et devrait s'écrire addi $11, $11, -1).
Si $10 = 4 et $11 = 6 au début du programme :
On applique la formule trouvée à la question précédente :
$20 = (4 × 6) + 100
$20 = 24 + 100
La valeur de $20 à la fin du programme sera donc 124.
Face à une épreuve d'architecture et de programmation assembleur, voici les points cruciaux à surveiller :
jal) ou modifie des registres sauvegardés doit impérativement allouer de l'espace sur la pile en abaissant $29 (stack pointer). Elle doit y stocker $31 (return address) sous peine de boucler à l'infini lors du retour.subi) n'existe pas en matériel ; on lui préfère toujours une addition avec un immédiat négatif (addi -1).srl).