Les jeux d’instructions MIPS

Exercice 1 - Traduction d'expressions arithmétiques

Partie a/ - Addition et soustraction

Le code assembleur MIPS fourni effectue des opérations arithmétiques de base. En analysant les commentaires inclus dans le code source, nous pouvons reconstituer l'expression de haut niveau (en langage C) correspondante.

Code fourni :

addu $t0, $s1, $s2 # $t0 = g + h
addu $t1, $s3, $s4 # $t1 = i + j
subu $s0, $t0, $t1 # f = (g+h)–(i+j)

Explication : Les variables sont assignées aux registres de la manière suivante :

Variable C	Registre MIPS
f	$s0
g	$s1
h	$s2
i	$s3
j	$s4

L'expression mathématique finale correspond à : f = (g + h) - (i + j);

Parties b/ et c/ - Données manquantes

Le document source est endommagé ou incomplet ici : il n'y a aucune instruction ni question sous les étiquettes b/ et c/. Il est par conséquent impossible de formuler une réponse pour ces deux points.

Exercice 2 - Structures de contrôle et boucles

Cet exercice demande de mettre en correspondance des structures de contrôle en C avec leur traduction en assembleur MIPS.

Partie a/ - Structure conditionnelle If-Else

Code C : if (a == b) c = d + e; else c = d - e;

Code MIPS corrigé : Le code source utilise else comme étiquette, ce qui est valide mais requiert les deux points : lors de sa définition.

      bne   $s0, $s1, label_else  # Si a != b, on saute à la branche else
      addu  $s2, $s3, $s4         # Branche if : c = d + e
      j     exit                  # Fin de la condition, on saute la branche else
label_else: 
      subu  $s2, $s3, $s4         # Branche else : c = d - e
exit: 
      # Suite du programme

Partie b/ - Condition logique ET (&&)

Code C : if (($s1 > 0) && ($s2 < 0)) {$s3++;};

Le source propose deux solutions. La deuxième est plus optimisée car elle utilise des conditions inverses pour sauter le bloc dès qu'une condition est fausse (évaluation de type court-circuit).

Solution optimisée :

      blez  $s1, next       # Si $s1 <= 0, la condition globale est fausse, on saute
      bgez  $s2, next       # Si $s2 >= 0, la condition globale est fausse, on saute
      addiu $s3, $s3, 1     # Si on arrive ici, les deux conditions sont vraies : $s3++
next:

Partie c/ - Condition logique OU (||)

Code C : if (($s1 > $s2) || ($s2 > $s3)) {$s4 = 1;};

Ici, si la première condition est vraie, on doit exécuter le code sans vérifier la seconde.

      bgt   $s1, $s2, L1    # Si $s1 > $s2, la condition globale est vraie, on saute à L1
      ble   $s2, $s3, next  # Si $s2 <= $s3, la condition globale est fausse, on saute à next
L1:   li    $s4, 1          # Le bloc "if" est exécuté
next:

Partie d/ - Comparaison non signée

Code C : if ($s1 <= $s2) {$s3 = $s4;}; (non signés)

Pour les entiers non signés, MIPS utilise les instructions terminant par u (comme bgtu pour Branch if Greater Than Unsigned).

      bgtu  $s1, $s2, next  # Condition inverse : on saute si $s1 > $s2
      move  $s3, $s4        # $s3 = $s4
next:

Partie e/ - Condition multiple signée

Code C : if (($s3 <= $s4) && ($s4 > $s5)) {$s3 = $s4 + $s5;}; (signés)

      bgt   $s3, $s4, next  # Si $s3 > $s4, échec de la 1ère condition, on saute
      ble   $s4, $s5, next  # Si $s4 <= $s5, échec de la 2ème condition, on saute
      addu  $s3, $s4, $s5   # Exécution du bloc
next:

Partie f/ - Boucle Do-While (Copie de chaîne)

Code C : i = 0; do {target[i]=source[i]; i++;} while (source[i]!=0);

Code MIPS :

      move  $t0, $s0        # $t0 = pointeur source
      move  $t1, $s1        # $t1 = pointeur cible
L1:   lb    $t2, 0($t0)     # Charge un octet depuis la source
      sb    $t2, 0($t1)     # Stocke l'octet dans la cible
      addiu $t0, $t0, 1     # Incrémente le pointeur source
      addiu $t1, $t1, 1     # Incrémente le pointeur cible
      bne   $t2, $zero, L1  # Continue tant que le caractère copié n'est pas '\0'

Partie g/ - Boucle For (Somme d'un tableau)

Code C : sum = 0; for (i=0; i<n; i++) sum = sum + A[i];

L'instruction xor $t1, $t1, $t1 est une méthode classique et rapide pour mettre un registre à 0.

      move  $t0, $s0        # $t0 pointe sur A[i] (base du tableau)
      xor   $t1, $t1, $t1   # i = 0 ($t1)
      xor   $s2, $s2, $s2   # sum = 0 ($s2)
L1:   lw    $t2, 0($t0)     # $t2 = A[i]
      addu  $s2, $s2, $t2   # sum = sum + A[i]
      addiu $t0, $t0, 4     # Avance au mot suivant dans le tableau (4 octets)
      addiu $t1, $t1, 1     # i++
      bne   $t1, $s1, L1    # Boucle tant que i != n

Exercice 3 - Copie inversée et somme d'un tableau

Ce programme parcourt un tableau de 5 mots (20 octets au total). Il lit le tableau source du début vers la fin, et écrit dans le tableau de destination de la fin vers le début. En même temps, il calcule la somme des éléments.

Analyse et explications :

• Le pointeur source $t0 est initialisé au début de tab1.
• Le pointeur cible $t1 est initialisé à tab2 + 16 (le 5ème et dernier élément, car 4 mots précédents × 4 octets = 16 octets d'offset).
• Le registre $v1 accumule la somme.

Code MIPS avec indentations standard :

.data
tab1:   .word 10, 20, 30, 40, 50
tab2:   .word 0, 0, 0, 0, 0
somme:  .word 0

.text
main:   
      li    $v1, 0          # Initialise la somme à 0
      li    $s1, 5          # Compteur de boucle = 5
      li    $s2, 4          # Valeur de décalage mémoire (4 octets par mot)
      la    $t0, tab1       # Pointeur sur le 1er élément de tab1
      la    $t1, tab2+16    # Pointeur sur le dernier élément de tab2
      la    $t2, somme      # Pointeur pour stocker la somme à la fin

boucle: 
      lw    $s0, 0($t0)     # Lecture de tab1[i]
      sw    $s0, 0($t1)     # Écriture dans tab2[5-1-i]
      add   $t0, $s2, $t0   # $t0 = $t0 + 4 (avance dans tab1)
      sub   $t1, $t1, 4     # Recule dans tab2
      sub   $s1, $s1, 1     # Décrémente le compteur de boucle
      add   $v1, $s0, $v1   # Ajoute la valeur lue à la somme globale
      sw    $v1, 0($t2)     # Mise à jour de la mémoire pour 'somme'
      bne   $s1, $zero, boucle # Reboucle si le compteur n'est pas nul

      # Affichage du résultat
      li    $v0, 1          # Code syscall pour print_int
      move  $a0, $v1        # Place la somme dans l'argument $a0
      syscall

      # Fin du programme
      li    $v0, 10         # Code syscall pour exit
      syscall

Exercice 4 - Séparation des nombres pairs et impairs

Le principe mathématique utilisé ici pour déterminer la parité est le "ET binaire" (andi) avec la valeur 1.

• Si nombre AND 1 == 0, le nombre est pair (le bit de poids faible est à 0).
• Si nombre AND 1 == 1, le nombre est impair (le bit de poids faible est à 1).

Code MIPS expliqué :

.data
tab1:       .word 1, 2, 3, 4, 5, 6
tabpaire:   .word 0, 0, 0, 0, 0
tabimpaire: .word 0, 0, 0, 0, 0

.text
main:   
      li    $s2, 6          # Longueur du tableau initial
      la    $t0, tab1       # Pointeur de lecture
      la    $t1, tabpaire   # Pointeur d'écriture pour les pairs
      la    $t2, tabimpaire # Pointeur d'écriture pour les impairs

boucle: 
      lw    $s0, 0($t0)     # Charge un nombre depuis tab1
      andi  $s1, $s0, 1     # Masque binaire pour isoler le dernier bit
      beq   $s1, $zero, paire # Si le bit est 0, c'est pair, saut vers 'paire'
      
      # Bloc impair :
      sw    $s0, 0($t2)     # Stocke dans tabimpaire
      add   $t2, $t2, 4     # Avance le pointeur impair
      j     next            # Saute le bloc pair

paire:  
      sw    $s0, 0($t1)     # Stocke dans tabpaire
      add   $t1, $t1, 4     # Avance le pointeur pair

next:   
      add   $t0, $t0, 4     # Avance le pointeur source
      sub   $s2, $s2, 1     # Décrémente le compteur d'éléments restants
      bne   $s2, $zero, boucle

      li    $v0, 10         # Fin de programme
      syscall

Exercice 5 - Recherche de caractère dans une chaîne

L'objectif est de trouver la lettre 'b' dans la chaîne ch1. Si elle est trouvée, la fonction renvoie son index ; sinon, elle renvoie la longueur totale.

Corrections appliquées au code source :

1. L'instruction lw $a2,'b' est syntaxiquement incorrecte, on ne charge pas une constante littérale avec lw (Load Word) mais avec li (Load Immediate).
2. L'adresse de départ de la chaîne (ch1) n'était pas passée en paramètre ($a0) dans le programme principal, empêchant la fonction de lire la chaîne. L'instruction la $a0, ch1 a été ajoutée.
3. À la fin du main, le source contenait move $a0, $v1 pour l'affichage, ce qui affichait 0 puisque le résultat de la fonction est dans $v0. Cela a été corrigé en move $a0, $s0.

Code corrigé et opérationnel :

.data
lch1: .word 7               # Correction de l'espace manquant
ch1:  .asciiz "acgfvbh"

.text
main:   
      lw    $a1, lch1       # Paramètre 2 : Longueur = 7
      li    $a2, 'b'        # Paramètre 3 : Caractère à chercher (CORRIGÉ : li au lieu de lw)
      la    $a0, ch1        # Paramètre 1 : Adresse de la chaîne (CORRIGÉ : ajouté)
      jal   trouve_b        # Appel de la procédure
      
      move  $s0, $v0        # Sauvegarde le résultat
      li    $v0, 1          # Syscall pour afficher un entier
      move  $a0, $s0        # Prépare l'entier pour l'affichage (CORRIGÉ : $s0 au lieu de $v1)
      syscall
      
      li    $v0, 10         # Syscall pour exit
      syscall

trouve_b: 
      li    $v0, 0          
      li    $t0, 0          # $t0 = index courant i = 0

loop:   
      bge   $t0, $a1, exit  # Si i >= longueur, on sort (retourne la longueur)
      add   $t1, $a0, $t0   # $t1 = adresse de base + offset i
      lb    $t2, 0($t1)     # Charge le caractère courant
      bne   $t2, $a2, num   # Si différent de 'b', passe au suivant
      
      # Si trouvé : 
      move  $v0, $t0        # Résultat = i
      jr    $ra             # Retour prématuré au main

num:    
      add   $t0, $t0, 1     # Incrémente l'index
      j     loop            # Reboucle

exit:   
      move  $v0, $t0        # Place la longueur totale en valeur de retour
      jr    $ra             # Retour au main

Exercice 6 - Calcul de la factorielle (Récursif)

Ce code lit un entier depuis l'utilisateur et calcule sa factorielle en appelant de manière récursive la fonction fact. Remarque de convention : Habituellement en MIPS, la valeur de retour est placée dans le registre $v0. Ce code source utilise de manière explicite le registre $3 (qui correspond à $v1) pour renvoyer le résultat. Nous conservons cette convention puisqu'elle est définie par la source.

Code MIPS :

.data
str1: .asciiz "Entrez un entier :"
str2: .asciiz "La factorielle est "

.text
main:   
      li    $v0, 4          # Syscall pour print_string
      la    $a0, str1       
      syscall 
      
      li    $v0, 5          # Syscall pour read_int
      syscall               # L'entier lu est dans $v0
      move  $a0, $v0        # Place l'entier lu dans $a0 (argument pour fact)
      jal   fact            # Appel de la fonction fact (résultat retourné dans $3)
      
sortie: 
      li    $v0, 4          # Syscall pour print_string
      la    $a0, str2       
      syscall 
      
      li    $v0, 1          # Syscall pour print_int
      move  $a0, $3         # Place le résultat depuis $3 vers $a0
      syscall 
      
      li    $v0, 10         # Exit
      syscall 

fact:   
      bgt   $a0, 1, recur   # Si n > 1, on effectue l'appel récursif
      li    $3, 1           # Cas de base : fact(0) ou fact(1) = 1
      jr    $ra             # Retourne au parent

recur:  
      sub   $sp, $sp, 8     # Alloue 8 octets dans la pile
      sw    $ra, 0($sp)     # Sauvegarde l'adresse de retour
      sw    $a0, 4($sp)     # Sauvegarde le paramètre n courant
      
      sub   $a0, $a0, 1     # n = n - 1
      jal   fact            # Appel récursif (résultat partiel placé dans $3)
      
      lw    $a0, 4($sp)     # Restaure le n courant
      mul   $3, $a0, $3     # Multiplie le n courant par le résultat récursif : n * fact(n-1)
      
      lw    $ra, 0($sp)     # Restaure l'adresse de retour
      add   $sp, $sp, 8     # Libère la pile
      jr    $ra             # Retourne au parent

Exercice 7 - Suite de Fibonacci (Récursif)

Cette procédure fib calcule le n-ième terme de la suite de Fibonacci. Contrairement à la factorielle, elle requiert deux appels récursifs pour chaque étape (n-1 et n-2), ce qui nécessite de sauvegarder un registre supplémentaire ($s0) dans la pile pour conserver le résultat partiel du premier appel.

Note sur les instructions pseudo-MIPS : Le code utilise subi qui n'est pas une instruction MIPS matérielle native (MIPS n'a que addi), mais l'assembleur SPIM la traduit automatiquement en addi avec un nombre négatif.

Code MIPS :

fib:    
      subi  $sp, $sp, 12    # Alloue 12 octets sur la pile
      sw    $a0, 0($sp)     # Sauvegarde de n
      sw    $s0, 4($sp)     # Sauvegarde de $s0 (va stocker fib(n-1))
      sw    $ra, 8($sp)     # Sauvegarde de l'adresse de retour
      
      bgt   $a0, 1, gen     # Si n > 1, cas récursif
      move  $v0, $a0        # Cas de base : si n=0 ou n=1, fib(n)=n
      j     rreg            # Saute à la restauration des registres

gen:    
      subi  $a0, $a0, 1     # Paramètre = n - 1
      jal   fib             # Appel récursif pour fib(n-1)
      move  $s0, $v0        # Sauvegarde fib(n-1) dans $s0
      
      subi  $a0, $a0, 1     # Paramètre = n - 2 (puisque $a0 a déjà été décrémenté de 1)
      jal   fib             # Appel récursif pour fib(n-2)
      
      add   $v0, $v0, $s0   # Résultat total = fib(n-2) (dans $v0) + fib(n-1) (dans $s0)

rreg:   
      lw    $a0, 0($sp)     # Restaure les paramètres originaux
      lw    $s0, 4($sp)     
      lw    $ra, 8($sp)     
      addi  $sp, $sp, 12    # Libère la pile
      jr    $ra             # Retourne au parent

Méthode

Pour réussir ce type d'examen sur l'architecture et les instructions MIPS, il est crucial d'adopter une méthode de lecture et d'analyse pas-à-pas :

1. Identifier les traductions classiques : Comprenez les motifs récurrents qui lient le langage de haut niveau à l'assembleur. Un bloc if-else implique une condition de saut inversée (par exemple, si la condition C est a == b, on utilise bne pour sauter au code du "sinon"). Les boucles (for, while) nécessitent une phase d'initialisation avant une étiquette, un test de sortie, un incrément d'adresse et un saut inconditionnel ou conditionnel à la fin.
2. Gérer la mémoire (Tableaux et Adresses) : Chaque accès mémoire (avec lw ou sw) nécessite un pointeur calculé. N'oubliez pas que dans une architecture 32 bits, un entier occupe un "mot" (Word), soit 4 octets. L'incrément de l'index dans un tableau (le i++ du C) doit toujours se traduire par un incrément de 4 octets de l'adresse en MIPS.
3. Respecter l'usage des registres : Lors de l'appel de procédures, respectez les conventions d'appel. Les registres $a0-$a3 servent aux arguments, $v0-$v1 à la valeur de retour.
4. Tracer la pile d'exécution : Pour les fonctions récursives (Exercices 6 et 7), la clé est la préservation du contexte ($ra et les variables locales). Assurez-vous d'allouer suffisamment d'espace avec $sp (sub $sp, $sp, espace), de sauvegarder les registres avant de faire un appel jal, puis de les restaurer exactement dans l'ordre inverse des adresses avant de désallouer la pile et de retourner (jr $ra).