Série corrigée MIPS
Exercice 1
On cherche à calculer la somme des nombres de p à q inclus.
long sum(long p, long q)
{
long s = 0;
while (p <= q)
s += p++;
return s;
}
Rappel
Cette fonction n’appelant pas d’autres fonctions, il est inutile de sauver $31 (adresse de retour
de fonction) et de modifier $29 (le pointeur de pile).
De plus, les registres arguments ont du être sauvés si l’appelant voulait les retrouver en l’état,
et on peut donc les utiliser à notre guise. La valeur de retour est dans $2.
Rappeler que :
– il n’y a pas d’instruction de manipulation de la pile dans le R3000
– la pile grandit vers les adresses décroissantes
– les 4 premiers arguments sont passés dans les registres 4 à 7
– après son déplacement, le pointeur de pile pointe sur la place du premier argument, mais
cette place est vide est n’est utilisée que si on a besoin de sauver le registre 4. Il en est de
même des cases suivantes. Les arguments supplémentaires sont empilés dans l’ordre 5, 6, etc.
Au dessus se trouve une zone pour les variables locales et les registres à sauver, qui se
terminent par le registre $31. Au dessus se trouve la place du 1er argument de la fonction
appelante, qui est une zone qui ne doit pas être modifiée par la fonction courante.
– le déplacement du pointeur de pile est calculé comme la somme des éléments à sauver, c.-à-
d. du nombre d’argument, des variables locales, puis des registres à sauver. Dès que
nécessaire (i.e lorsqu’une fonction devra être appelée), on déplace le pointeur, on sauve ce qui
doit l’être et on effectue l’appel. Avant de retourner à l’appelant, on récupère ce qui doit l’être
et on redéplace la pile de la même quantité, puis l’on retourne à l’appelant.
– une fonction terminale ne nécessite pas de déplacement de pile, sauf si elle a besoin de
variables locales ou utilise tellement de registres qu’il faut en sauver quelques-uns.
Solution
sum : li $2, 0 # s = 0
next: slt $3, $5, $4 # q < p
bnez $3, ret # c’est fini
addu $2, $2, $4 # ajoute p à s inconditionnelement
j next #continue
addiu $4, $4, 1 # après avoir incrémenté p
ret: jr $31 # retour à l’appelant
1
Exercice 2
La fonction sum vue précédemment peut s’écrire, sous forme récursive.
long sum(long p, long q)
{
return p < q ? q + sum(p, q - 1) : q;
}
Publicité
Solution
sum :
slt $3, $4, $5
beqz $3 ,retq
addiu $29, $29, -12 # place pour $31 et les paramètres
sw $5, 16($29) #sauve q, inutile pour p
sw $31, 8($29) # sauve l’adresse de retour
jal sum
addiu $5, $5, -1 # q - 1
lw $5, 16($29) # récupère q
lw $31, 8($29) # récupère l’adresse de retour
add $2, $2, $5 # q + sum
retq:
jr $31
addiu $29, $29, 12 # réajustement de la pile
Exercice 3
On définit la fonction moyenne, qui fait appel à sum, de la façon suivante :
long moyenne(long x, long y)
{
return sum(x, y) / (y - x + 1);
}
Solution
moyenne:
addiu $29, $29, -12 # place pour $31 et les 2 paramètres
sw $31, 8($29) #sauve l’adresse de l’appelant
sw $4, 12($29) # sauve x à sa place réservée
jal sum # appelle sum
sw $5, 16($29) # sauve y à sa place réservée
lw $4, 12($29) # récupère x de sa place réservée
lw $5, 16($29) # récupère y de sa place réservée
sub $5, $5, $4 # y - x
addiu $5, $5, 1 # + 1
div $2, $5 # divise
2
lw $31, 8($29) # récupère l’adresse de l’appelant
mflo $2 # récupère le résultat de la division
jr $31 # retour à l’appelant
addui $29, $29, 12 # restauration de la pile
Rappel
La récursivité est une nécessité pour bien des algorithmes. Si les problèmes que nous allons
étudier pourraient être écrits de façon plus simple, et surtout beaucoup plus efficace, de
manière itérative, ils n’en servent pas moins à illustrer ce principe un peu complexe. Cette
vision « matérielle » des choses permet par ailleurs de mieux comprendre le principe même de
la récursivité et de son exécution sur la machine.
Exercice 4
1) Traduire le code MIPS suivant en C
func:
Publicité
addi $t0, $zero, 1 # i = 1
addi $v0, $zero, 1 # v = 1
Loop: sle $t1, $t0, $a0 # set $t1 to 1 if (i <= arg)
beq $t1, $zero, Exit # exit loop if (i > arg)
mul $v0, $v0, $t0 # v *= i
addi $t0, $t0, 1 # i++
j Loop # loop
Exit:
jr $ra
2) De quelle fonction mathématique il s’agit ?
Solution
1)
int func (int arg){ / return type is int, one argument of type int /
int v = 1, i;
for (i = 1 ; i <= arg ; i++) {
v = v * i;
}
return v;
}
2) Factoriel (pour des arguments non-négatifs).
Exercice 5
Ecrire un code MIPS qui lit un entier entré au clavier et l’affiche à l’écran.
Solution
main:
li $v0, 5 # Le prochain appel système sera un read_int
3
syscall # Lecture de l’entier n au clavier
move $t2, $v0 # Place n dans le registre temporaire $t2
li $v0, 1 # Le prochain appel système sera un print_int
move $a0, $t2 # Place l’entier à afficher dans $a0
syscall # Affiche l’entier $a0
jr $31
Exercice 6
Traduire le code C suivant en MIPS :
int multiply(int x, int y) {
prod=0;
while (y>0) {
prod = prod + x;
y--;
}
return(prod);
}
Solution
multiply:
add $t0,$zero,$zero # prod=0
m_loop:
beq $a1,$zero,m_eol # while y>0
Publicité
add $t0,$t0,$a0 # prod = prod+x
subi $a1,$a1,1 # y--
j m_loop
m_eol:
add $v0,$t0,$zero # return(prod)
jr $ra
Exercice 7
Supposez le code assembleur MIPS suivant:
lw $t0,0($a0)
lw $t1,0($a1)
bne $t0,$t1,toto
add $v0,$t0,$zero
j titi
toto: add $v0,$t1,$zero
titi:
1) Quelle est la fonction réalisée, exprimée dans un langage de haut niveau ?
2) Supposez que $a0=0x1234 et $a1=0x3. Quelle est la valeur du registre $t0 après
l’exécution du programme MIPS suivant ?
add $t0,$0,$0
4
toto: add $t0,$t0,$a0
addi $a1,$a1,-1
bne $a1,$zero,toto
srl $t0,$t0,4
3) Supposez le code MIPS suivant, qui reçoit deux entrées dans les registres $10 et $11 et
produit une sortie dans le registre $20.
add $1,$0,$0
lo: beq $11,$0,fin
add $1,$1,$10
subi $11,$11,1
j lo
fin: addi $1,$1,100
add $20,$1,$0
a) Décrivez en une phrase la fonction du programme.
b) Quelle est la valeur de $20 à la fin du programme, si $10=4 et $11=6 au début du
programme?
Solution
1) if a<>b
then b
else a
2) 0x369
3)
a) Le programme produit une sortie $20 = ($10 * $11) + 100
b) $20 = 124
5