Architecture des Ordinateurs, MIPS, corrigé TP 2
Recommandations
— Etudier préalablement, et utiliser le MémoMIPS proposé en ligne.
— Commenter soigneusement chaque ligne écrite en assembleur...
Exercice 1. Compiler en MIPS le programme C++ suivant :
#include <iostream>
using namespace std;
int power(int x, int n)
{
int i; int result = 1;
for (i=1;i<=n;++i) result=result*x;
return result;
} // power()
int main(void)
{
int x; int n;
cin >> x;
cin >> n;
cout << power(x,n);
return 0;
} // main()
Correction. Les variables x et n sont des variables globales, donc statiques. Autrement dit, il faut
allouer dans le segment de données les deux mots mémoires correspondants (32 bits, puisqu’elles sont
int). Inversement les variables i et result de la fonction power sont locales : leur durée de vie dans
la mémoire ne doit pas excéder la durée du temps d’exécution de la fonction, et elles devraient donc
être rangées dans la pile. Mais on peut aussi remarquer que ces variables (un incrément de boucle et
un résultat) ont une portée très réduite (une boucle d’une instruction) et peuvent être immédiatement
et avantageusement associées à deux registres temporaires de façon à minimiser le traffic avec la
mémoire. On obtient alors :
1
.data
x: .word 0x00000000 # allocation memoire pour x
n: .word 0x00000000 # allocation memoire pour n
.text
main: la $t0, x # $t0 contient l’adresse de x
ori $v0, $zero, 5 # $v0 <- 5
syscall # lecture au clavier
sw $v0, 0($t0) # la valeur lue est rangee dans x
or $a0, $zero, $v0 # $a0 <- $v0
la $t0, n # $t0 contient l’adresse de n
ori $v0, $zero, 5 # $v0 <- 5
syscall # lecture au clavier
sw $v0, 0($t0) # la valeur lue est rangee dans n
or $a1, $zero, $v0 # $a1 <- $v0
jal power # appel de power
or $a0, $zero, $v0 # $a0 <- $v0
ori $v0, $zero, 1 # $v0 <- 1
syscall # affichage de l’entier $a0
ori $v0, $zero, 10 # $v0 <- 10 pour exit
syscall # appel systeme de terminaison
power: ori $t1, $zero, 1 # $t1:result=1
ori $t0, $zero, 1 # $t0:i=1
for: slt $t2, $a1, $t0 # $t2=(i>n?1:0)
bne $t2, $zero, exitfor # if (i=n) goto exitfor;
mul $t1, $t1, $a0 # result=result*x;
addi $t0, $t0, 1 # ++i;
j for # goto for
exitfor: or $v0, $zero, $t1 # $v0 <- $t1:result
jr $ra # return result
Exercice 2. Dans la fonction power(x,n) précédente, remplacer en MIPS la boucle :
for (i=1;i<=n;++i) result=result*x;
par :
for (i=0;i<n;++i) result=result*x;
Quel est le gain obtenu ?
2
Correction. Faire partir l’incrément i à 0 au lieu de 1 permet à l’autre extrémité d’inverser le test
sur n et rend ainsi inutile l’instruction slt :
power: ori $t1, $zero, 1 # $t1:result=1
or $t0, $zero, $zero # $t0:i=0
for: beq $t0, $a1, exitfor # if (i=n) goto exitfor;
mul $t1, $t1, $a0 # result=result*x;
addi $t0, $t0, 1 # ++i;
j for # goto for
exitfor: or $v0, $zero, $t1 # $v0 <- $t1:result
jr $ra # return result
Exercice 3. Le programme C++ suivant permet d’effectuer un tri naı̈f sur un tableau :
#include <iostream>
#include <iomanip>
using namespace std;
namespace
{
const unsigned TailleT = 9;
unsigned T[] = {1, 3, 5, 2, 9, 8, 6, 4, 7, 0};
void AfficherTableau (unsigned T[], const unsigned N)
{
cout << "T : ";
for (unsigned i = 0; (i < N); ++i)
cout << setw(3) << T[i];
cout << "\n";
} // AfficherTableau()
void Swap (unsigned T[], unsigned k)
{
unsigned Temp;
Temp = T[k];
T[k] = T[k+1];
T[k+1] = Temp;
} // Swap()
void Sort (unsigned T[], unsigned N)
{
for (unsigned i = 1; (i<N); ++i)
for (unsigned j = i-1; ((j>=0) && (T[j] > T[j+1])); --j)
Swap(T, j);
} // Sort()
3
} // namespace anonyme
int main ()
{
AfficherTableau(T, TailleT);
Sort(T, TailleT);
AfficherTableau(T,TailleT);
return 0;
} // main()
Traduire ce programme en assembleur MIPS, en en respectant strictement la structure et la sémantique
tout en optimisant au mieux les échanges entre mémoire et registres.
Correction.
— les variables de type int TailleT et T sont rangées dans le segment .data chacune sur un mot
de la mémoire ; on y ajoute les deux chaı̂nes de caractères (au format ntsc, autrement dit par
le biais de la macro .asciiz) permettant l’affichage "T : " et "\n" (retour à la ligne) et, pour
faire simple, une chaı̂ne de trois espaces simulant la fonction setw(3) ;
— la fonction AfficherTableau() requiert l’appel de la macro d’affichage MIPS syscall utilisant
le registre $a0 qu’il est donc commode de réserver à cet effet ;
— les fonctions Sort() et AfficherTableau() prennent TailleT et l’adresse T comme arguments,
auxquels il est raisonnable d’associer respectivement les registres $a1 et $a2 dédiés au passage
d’arguments dans les conventions MIPS ; la fonction Swap() prend pour argument l’indice k
(rang auquel effectuer la permutation dans le tableau T) auquel on associe le registre de passage
d’argument restant $a3 ;
— les fonctions AfficherTableau() et Swap() sont toutes deux terminales et ne modifient pas
les arguments reçus qu’il n’est donc pas nécessaire d’empiler ; la fonction Sort() est, elle, non-
terminale : si elle ne modifie pas non plus les arguments reçus, elle utilise les deux incréments
de boucles imbriquées i et j qu’il est donc nécessaire de sauvegarder dans la pile à partir des
deux registres associés $s0 (pour i) et $s1 (pour j).
Au final, le programme MIPS correspondant est le suivant :
.data
.word
TailleT: 0x00000009
T: 0x00000001,
0x00000003,
0x00000005,
0x00000002,
0x00000009,
0x00000008,
0x00000006,
0x00000004,
0x00000007,
0x00000000
4
.asciiz
Str: "T : "
Setw3: " "
CR: "\n"
# Association registres/variables ----------------------------------------------
# $a0, reserve a l’affichage
# $a1, associe a TailleT
# $a2, associe a @T
.text
main: la $t0, TailleT # $t0 <- @TailleT
lw $a1, 0($t0) # $a1 <- TailleT
la $a2, T # $a2 <- @T[]
jal AfficherTableau
jal Sort
jal AfficherTableau
ori $v0, $zero, 10 # $v0 <- 10
syscall # return 0;
# Sort() -----------------------------------------------------------------------
Sort: addi $sp, $sp, -16 # reserve 4 mots en sommet de pile
sw $ra, 12($sp) # push adresse de retour $ra
sw $a3, 8($sp) # push $a3, argument de Swap()
sw $s0, 4($sp) # push index de boucle i:$s0
sw $s1, 0($sp) # push index de boucle j:$s1
ori $s0, $zero, 1 # i:$s0 <- 1
for1_Sort: slt $t0, $s0, $a1 # $t0 = (i:$s0 < N:$a1)?1:0;
beq $t0, $zero, exitfor1_Sort # if (i>=0) goto exitfor_Sort1
addi $s1, $s0 -1 # j:$s1 <- i:$s0 -1
for2_Sort: slt $t0, $s1, $zero # $t0 = (j:$s1 < $zero)?1:0;
bne $t0, $zero, exitfor2_Sort # if (j<0) goto exitfor_Sort2
sll $t0, $s1, 2 # $t0 <- j:$s1 * 4
add $a3, $t0, $a2 # @T[j]:$a3 <- @T[]:$a2 + $t0
lw $t1, 0($a3) # $t1 <- T[j]
lw $t2, 4($a3) # $t2 <- T[j+1]
slt $t0, $t2, $t1 # $t0 = (T[j+1]<T[j])?1:0;
beq $t0, $zero, exitfor2_Sort # if (T[j]<=T[j+1]) goto exitfor2_Sort
jal Swap # appel de Swap(), modification de $ra
addi $s1, $s1, -1 # --j
j for2_Sort # goto for2_Sort
exitfor2_Sort: addi $s0, $s0, 1 # ++i
j for1_Sort # goto for1_Sort
5
exitfor1_Sort: lw $s1, 0($sp) # pop index de boucle j:$s1
lw $s0, 4($sp) # pop index de boucle i:$s0
lw $a3, 8($sp) # pop $a3, argument de Swap()
lw $ra, 12($sp) # pop adresse de retour $ra
addi $sp, $sp, 16 # rend 4 mots en sommet de pile
jr $ra # retour a la fonction appelante
# ------------------------------------------------------------------------------
# Swap() -----------------------------------------------------------------------
Swap: lw $t0, 0($a3) # Temp:$t0 <- T[k]
lw $t1, 4($a3) # $t1 <- T[k+1]
sw $t1, 0($a3) # T[k] = T[k+1];
sw $t0, 4($a3) # T[k+1] = Temp;
jr $ra # retour a la fonction appelante
# ------------------------------------------------------------------------------
# AfficherTableau() ------------------------------------------------------------
AfficherTableau: la $a0, Str # $a0 <-@Str
ori $v0, $zero, 4 # affichage d’une chaine
syscall # cout << "T : ";
or $t0, $zero, $zero # i:$t0 <- $zero
for_AfficherTableau: beq $t0, $a1, exitfor_AfficherTableau # if (i:$t0==N)
# goto exitfor_AfficherTableau
la $a0, Setw3 # $a0 <- @Setw3
ori $v0, $zero, 4 # affichage d’une chaine
syscall # cout << setw(3);
sll $t1, $t0, 2 # $t1 <- i:$t0 * 4
add $t1, $t1, $a2 # $t1 <- @T[i]
lw $a0, 0($t1) # $a0 <- T[i]
ori $v0, $zero, 1 # affichage d’un entier
syscall # cout << T[i];
addi $t0 , $t0, 1 # i:$t0 <- i:$t0 + 1
j for_AfficherTableau # goto for_AfficherTableau
exitfor_AfficherTableau: la $a0, CR # $a0 <- @Cr
ori $v0, $zero, 4 # affichage d’une chaine
syscall # cout << "\n";
jr $ra # retour a la fonction appelante
# ------------------------------------------------------------------------------
