Série corrigée MIPS

Exercice 1 - Calcul itératif d'une somme

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.

Exercice 2 - Calcul récursif d'une somme

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

Exercice 3 - Fonction moyenne

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

Exercice 4 - Rétro-ingénierie de code MIPS vers C

Question 1 - Traduction du code MIPS en C

Analysons pas à pas le code fourni :

• $t0 est initialisé à 1 (variable i).
• $v0 est initialisé à 1 (variable v).
• La boucle compare $t0 à $a0 (l'argument de la fonction). Si i > arg, la boucle se termine.
• Dans la boucle, on multiplie 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;
}

Question 2 - Identification de la fonction mathématique

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.

Exercice 5 - Entrées / Sorties au clavier

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

Exercice 6 - Multiplication par additions successives

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)

Exercice 7 - Analyse et exécution pas-à-pas de code

Question 1 - Fonction haut niveau

Le code charge les valeurs pointées par les adresses contenues dans $a0 et $a1 (soit *a0 et *a1). Il compare ces deux valeurs.

• Si elles sont différentes, il saute à toto et place la valeur de *a1 dans la valeur de retour ($v0).
• Si elles sont égales, il ne saute pas, place *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).

Question 2 - Valeur finale d'un registre

On initialise $a0 = 0x1234 et $a1 = 3 (0x3). Détaillons l'exécution :

1. $t0 est initialisé à 0.
2. Début de la boucle (toto) :
   • Tour 1 : $t0 = 0 + 0x1234 = 0x1234. $a1 devient 2. $a1 n'est pas nul, on boucle.
   • Tour 2 : $t0 = 0x1234 + 0x1234 = 0x2468. $a1 devient 1. On boucle.
   • Tour 3 : $t0 = 0x2468 + 0x1234 = 0x369C. $a1 devient 0. On sort de la boucle.
3. L'instruction 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.

Question 3 - Analyse du troisième programme

Sous-question a) - Description de la fonction

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

Sous-question b) - Calcul d'une valeur précise

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.

Méthode

Face à une épreuve d'architecture et de programmation assembleur, voici les points cruciaux à surveiller :

1. Les conventions d'appel (ABI) : La gestion de la pile (stack) est souvent le point le plus fragile. N'oubliez pas qu'une fonction appelée qui fait elle-même un appel (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.
2. Le jeu d'instructions réel vs virtuel : Dans vos copies ou vos exercices, assurez-vous de connaître les limites de votre processeur (ici le MIPS R3000). Comme nous l'avons vu, la soustraction avec une valeur immédiate (subi) n'existe pas en matériel ; on lui préfère toujours une addition avec un immédiat négatif (addi -1).
3. Traçage de code : Pour les questions d'exécution (comme l'exercice 7), n'essayez pas de tout deviner de tête. Dressez un petit tableau avec l'état de chaque registre à la fin de chaque itération. C'est la méthode la plus sûre pour ne pas se tromper lors d'opérations bit-à-bit (comme les décalages srl).