Le jeu d’instructions MIPS
Nous allons voir le langage de la machine :
Les opérations du matériel de l’ordinateur
Les opérandes du matériel de l’ordinateur
La représentation des instructions dans
l’ordinateur
Des instructions pour prendre des décisions
19/10/2012 12:39 [Link] 1
les instructions. 1
Les opérations du matériel de l’ordinateur
Tout ordinateur doit être capable d’effectuer des
opérations arithmétiques.
La notation MIPS
add a,b,c
chaque instruction arithmétique MIPS doit toujours
avoir trois variables.
19/10/2012 12:39 [Link] 2
les instructions. 2
Les opérandes du matériel de l’ordinateur
Les opérandes des instructions arithmétiques doivent
provenir d’un nombre limité d’emplacements particuliers
appelés registres.
La taille d’un registre dans l’architecture MIPS est de 32
bits
MIPS possède 32 registres, notés $0, $1, ...,$31
Les registres sont plus rapide que la mémoire
Les registres sont plus facile à utiliser pour le compilateur
Les registres peuvent contenir des variables
Réduction trafic mémoire
19/10/2012 12:39 [Link] 3
les instructions. 3
Les opérandes du matériel de l’ordinateur
230 octet mémoire
31 registres 32 bits + R0=0
HI, LO, CP
R0 0
R1
…
R31
CP
LO
HI
19/10/2012 12:39 [Link] 4
les instructions. 4
Les registres du MIPS
Le MIPS comporte 32 registres généraux interchangeables, sauf
:
le registre zéro qui vaut toujours 0, même après une écriture.
Le registre ra, utilisé implicitement par certaines instructions
pour sauver l'adresse de retour avant un saut.
Les autres registres ont des utilisations préférentielles, mais
cela n'est strict que pour communiquer avec d'autres
programmes(exemple: utiliser des programmes en librairies).
19/10/2012 12:39 [Link]
5
les instructions. 5
Les registres du MIPS
Nom Numéro Usage
zero 0 Zéro (toujours)
at 1 Réservé par l'assembleur
v0 .. v1 2 .. 3 Retour de valeurs
a0 .. a3 4 .. 7 Passage d'arguments
t0 .. t7 8 .. 15 Temporaires non sauvegardés
s0.. s7 16 .. 23 Temporaires sauvegardés
t8.. t9 24 .. 25 Temporaires non sauvegardés
k0.. k1 26 .. 27 Réservés par le système
gp 28 Global Pointer
sp 29 Stack Pointer
fp 30 Frame Pointeur
ra 31 Return Address
19/10/2012 12:39 [Link]
6
les instructions. 6
Exemple
f=(g+h)-(i+j);
Les variables f,g,h,i et j peuvent être
assignées aux registres $16, $17,… $20.
C’est au compilateur que revient cette
tâche délicate.
add $8,$17,$18 #Registre $8 contient g+h
add $9,$19,$20 #Registre $9 contient i+j
sub $16,$8,$9 # f reçoit $8-$9, ou (g+h)-(i+j)
19/10/2012 12:39 [Link] 7
les instructions. 7
Les opérandes du matériel de l’ordinateur
Beaucoup de programmes ont plus de variables que
les machines n’ont de registres. Par conséquent, le
compilateur cherche à conserver dans les registres les
variables les plus souvent utilisées et place le reste en
mémoire.
Les structures de données comme les tableaux sont
donc stockées en mémoire
19/10/2012 12:39 [Link] 8
les instructions. 8
Les opérandes du matériel de l’ordinateur
Les opérations arithmétiques n’ont lieu que dans
les registres. MIPS doit donc disposer
d’instructions qui transfèrent les données entre la
mémoire et les registres.
Load
Processeur Mémoire
Store
19/10/2012 12:39 [Link] 9
les instructions. 9
Les opérandes du matériel de l’ordinateur
Depuis 1980 toutes les machines utilisent des
adresses au niveau de l’octet (8 bits)
Adresse Donnée
0 10
4 45
Processeur 8 8456666
12 0
... ...
Puisque on peut lire un mot de 32 bits comme 4 octets
en un seul coup, comment ces octets sont ranger dans le
mot ?
19/10/2012 12:39 [Link] 10
les instructions. 10
Les opérandes du matériel de l’ordinateur
Big-endian: l’adresse de l’octet le plus significatif
est l’adresse du mot
Numéro d’octet
3 2 1 0 Motorolla, MIPS, SPARC
Little-endian: l’adresse l’octet le moins
significatif est l’adresse du mot
Numéro d’octet
Intel 8086, VAX, Alpha
0 1 2 3
19/10/2012 12:39 [Link] 11
les instructions. 11
Transfert de donnée
Chargement mot :
lw $1,100($2)
$1 = Mémoire[$2+100]
Rangement mot :
sw $1,100($2)
Mémoire[$2+100] = $1
19/10/2012 12:39 [Link] 12
les instructions. 12
Exemple
T[i]=h+T[i] ;
T est un tableau d’entiers.
On suppose que la variable h est dans
$18. $19 contient la valeur i, et que le
tableau débute à l’adresse Tstart
muli $19,$19,4 #i=i*4
lw $8,Tstart($19) #reg temporaire $8 reçoit T[i]
add $8,$18,$8 #reg temporaire $8 reçoit h+T[i]
sw $8,Tstart($19) #on recopie h+T[i]dans T[i]
19/10/2012 12:39 [Link] 13
les instructions. 13
Branchement conditionnel
branchement si égal
beq $1,$2,L
si ($1==$2) aller en L
branchement si non égal :
bne $1,$2,L
si ($1!=$2) aller en L
les instructions. 14
Exemple
if (i==j)
f=g+h;
else
f=g-h;
f,g,h,ietj correspondent aux registres $16 à $20
bne $19,$20,Else # aller en Else si i¹j
add $16,$17,$18 # f=g+h
j Exit # aller en Exit
Else:sub $16,$17,$18 # f=g-h
Exit:
les instructions. 15
Exemple
While (stock[i]==k)
i=i+j;
i,j et k correspondent aux registres $19 à $21,
le tableau stock débute à Sstart,
le registre $10 contient la valeur 4;
loop : mult $9,$19,$10 #reg temporaire $9=i*4
lw $8,Sstart($9) #reg temporaire $8=stock[i]
bne $8,$21,Exit #aller en Exit si stock[i]¹k
add $19,$19,$20 #i=i+j
j Loop #aller en Loop
Exit:
les instructions. 16
Le format des instructions
31-26 25-21 20-16 15-11 10-6 5-0
0p rs rt rd decval fonct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
Nous donnons des noms aux champs MIPS pour faciliter leur
description
• op : opération correspondant à l’instruction
• rs : le premier registre opérande source
• rt : le second registre opérande source
• rd : le registre opérande destination ; il reçoit le résultat de
l’opération
• decval : valeur du décalage
• fonct : fonction ; ce champ détermine la variante de
l’opération décrite dans le champ op
les instructions. 17
Le format des instructions
Instruction de type R
31-26 25-21 20-16 15-11 10-6 5-0
0 rs rt rd decval fonct
Exemples :
add $1,$2,$3 signification $1=$2+$3
0 2 3 1 0 32
Sub $1,$2,$3 signification $1=$2-$3
0 2 3 1 0 34
les instructions. 18
Le format des instructions
Instruction de type I
Instruction de chargement ou de rangement
31-26 25-21 20-16 15-0
35ou43 rs rt adresse
6 bits 5 bits 5 bits 16 bits
Exemples :
lw $1,100($2) signification : $1=Mémoire($2+100)
35 2 1 100
Sw $1,100($2) signification : Mémoire($2+100)=$1
43 2 1 100
les instructions. 19
Le format des instructions
Instruction de branchement
31-26 25-21 20-16 15-0
4 ou 5 rs rt adresse
Exemples :
beq $1,$2,100 signification : si ($1=$2) aller en 100
4 1 2 100
bne $1,$2,100 signification : si ($1¹$2) aller en 100
5 1 2 100
les instructions. 20
Le format des instructions
• Instruction type J
op adresse
6 bits 26 bits
Exemple : J 2000
2 2000
6 bits 26 bits
Différents formats d’instructions MIPS
31 26 21 16 11 6 0
R-type op rs rt rd decval funct add, sub
I-type op rs rt immediate ori, lw, sw, beq
J-type op Address destination j, jal
les instructions. 21
Modes d’adressage
1. Adressage par registre
31 26 21 16 11 6 0
op rs rt rd decval funct
registre
Opérande est un registre Add $4,$2,$3
2. Adressage indexé
op rs rt adresse
registre
+ Mémoire
lw $1,100($2)
Opérande se trouve à
l’emplacement mémoire
les instructions. 22
Modes d’adressage
3. Adressage immédiat
op rs rt immédiat
6 bits 5 bits 5 bits 16 bits
Opérande constante addi $1,$2,100
4. Adressage relatif à CP
op rs rt adresse
CP
bne $1,$2,100 + Mémoire
Nombre de mots qui séparent l ’instruction
de branchement de l ’instruction cible
les instructions. 23
L’utilisation de la mémoire
Conventions adoptées sur un système MIPS :
Segment de texte (détient les instructions du
programme)
Segment de données
Segment de pile
Il se situe au sommet de l’espace adressable.
Lorsque le programme dépose des valeurs sur la
pile, le système d’exploitation étend le segment
de pile vers le bas.
les instructions. 24
L’utilisation de la mémoire
7fffffff
Segment de pile
Segment de
données
10000000
Segment de texte
00400000 Réservé
les instructions. 25
Traitement des procédures
Procédure A
0: procédure A
Éditeur
Procédure B de 64: procédure B
liens
112:procédure C
Procédure C
Appel de procédure.
Retour à l’instruction qui suit l’appel.
Passage des paramètres
Imbrication des procédure
les instructions. 26
Traitement des procédures
Instruction jal (saut avec lien)
jal AdresseProcedure
Ä L’Adresse de retour est rangé dans $31.
Le retour est effectue par l’instruction : jr $31
$31 CP: compteur de programme
Cas plus compliqué lorsque une procédure appelle une
autre procédure
Ä Vidée les registre $31 dans la mémoire
les instructions. 27
Les appels de procédures
Void procB(){
procC();
}
Void procA(){
procB();
}
les instructions. 28
Appels et retours
procA procB procC
Retour
Retour
les instructions. 29
Les appels de procédures
Void procB(){
procC();
}
Void procA(){
procB();
}
jal AdresseProcedure :
Affecte un saut à une adresse donnée en
sauvegardant l’adresse de l’instruction suivante dans
le registre $31
jr $31
Instruction qui fait un saut de retour
les instructions. 30
Sauvegarde et restitution de l’adresse de retour
procA:...
... $31
Mémoire
jal procB
...
procB:... $29
...
addi $29,$29,-4
sw $31,0($29)
jal procC
lw $31,0($29)
addi$29,$29,4
...
jr $31
procC:...
...
jr $31
les instructions. 31
Après que procA ai appelé procB
procA:...
... $31
Mémoire
jal procB ad ret procB
...
procB:... $29
...
addi $29,$29,-4
sw $31,0($29)
jal procC
lw $31,0($29)
addi$29,$29,4
...
jr $31
procC:...
...
jr $31
les instructions. 32
Juste avant que procB n’appelle procC
procA:...
... $31
Mémoire
jal procB ad ret procB
...
procB:... $29
...
addi $29,$29,-4
sw $31,0($29)
jal procC
lw $31,0($29)
addi$29,$29,4
...
jr $31
procC:...
...
jr $31
les instructions. 33
Juste avant que procB n’appelle procC
procA:...
... $31
Mémoire
jal procB ad ret procB
...
procB:... $29
...
addi $29,$29,-4
sw $31,0($29) ad ret procB
jal procC
lw $31,0($29)
addi$29,$29,4
...
jr $31
procC:...
...
jr $31
les instructions. 34
Appel
procA:...
... $31
Mémoire
jal procB ad ret procC
...
procB:... $29
...
addi $29,$29,-4
sw $31,0($29) ad ret procB
jal procC
lw $31,0($29)
addi$29,$29,4
...
jr $31
procC:...
...
jr $31
les instructions. 35
Après que procB ait appelé procC
procA:...
... $31
Mémoire
jal procB ad ret procC
...
procB:... $29
...
addi $29,$29,-4
sw $31,0($29) ad ret procB
jal procC
lw $31,0($29)
addi$29,$29,4
...
jr $31
procC:...
...
jr $31
les instructions. 36
procA:...
... $31
Mémoire
jal procB ad ret procC
...
procB:... $29
...
addi $29,$29,-4
sw $31,0($29) ad ret procB
jal procC
lw $31,0($29)
addi$29,$29,4
...
jr $31
procC:...
...
jr $31
les instructions. 37
Juste avant que procB ne retourne
procA:...
... $31
Mémoire
jal procB ad ret procB
...
procB:... $29
...
addi $29,$29,-4
sw $31,0($29) ad ret procB
jal procC
lw $31,0($29)
addi$29,$29,4
...
jr $31
procC:...
...
jr $31
les instructions. 38
Juste avant que procB ne retourne
procA:...
... $31
Mémoire
jal procB ad ret procB
...
procB:... $29
...
addi $29,$29,-4
sw $31,0($29) ad ret procB
jal procC
lw $31,0($29)
addi$29,$29,4
...
jr $31
procC:...
...
jr $31
les instructions. 39
Retour à procA
procA:...
... $31
Mémoire
jal procB ad ret procB
...
procB:... $29
...
addi $29,$29,-4
sw $31,0($29) ad ret procB
jal procC
lw $31,0($29)
addi$29,$29,4
...
jr $31
procC:...
...
jr $31
les instructions. 40
instructions arithmétiques
Instruction Exemple signification
add add $1,$2,$3 $1 = $2 + $3 exception possible
sous sub $1,$2,$3 $1 = $2 – $3 exception possible
add immediate addi $1,$2,100 $1 = $2 + 100 exception possible
add non signé addu $1,$2,$3 $1 = $2 + $3 pas d’exception
sous non signé subu $1,$2,$3 $1 = $2 – $3 pas d’exception
add imm. non sig addiu $1,$2,100 $1 = $2 + 100 pas d’exception
mul mult $2,$3 Hi, Lo = $2 x $3
Mul non signé multu$2,$3 Hi, Lo = $2 x $3
div div $2,$3 Lo = $2 ÷ $3, Lo = quotient
Hi = $2 mod $3 Hi = reste
div non signé divu $2,$3 Lo = $2 ÷ $3,
Hi = $2 mod $3
Move from Hi mfhi $1 $1 = Hi
Move from Lo mflo $1 $1 = Lo les instructions. 41
instructions logiques
Instruction Exemple Signification
and and $1,$2,$3 $1 = $2 ET $3
or or $1,$2,$3 $1 = $2 OR $3
xor xor $1,$2,$3 $1 = $2 XOR $3
nor nor $1,$2,$3 $1 = $2 NOR $3
and immediat andi $1,$2,10 $1 = $2 ET 10
or immediat ori $1,$2,10 $1 = $2 OU 10
xor immediat xori $1, $2,10 $1 = $2 XOR 10
shift left logical sll $1,$2,10 $1 = $2 << 10
shift right logical srl $1,$2,10 $1 = $2 >> 10
shift right arithm. sra $1,$2,10 $1 = $2 >> 10
shift left logical sllv $1,$2,$3 $1 = $2 << $3
shift right logical srlv $1,$2, $3 $1 = $2 >> $3
shift right arithm. srav $1,$2, $3 $1 = $2 >> $3
les instructions. 42
instructions de transfert de données
Instruction Comment
sw $3, 500($4) enreg. D’un mot en mémoire
sh $3, 502($2) enreg. D’un demi-mot
sb $2, 41($3) enreg. D’un octet
lw $1, 30($2) chargement d’un mot
lh $1, 40($3) chargement d’un demi mot
lhu $1, 40($3) chargement d’un demi-mot non signé
lb $1, 40($3) chargement d’un octet
lbu $1, 40($3) chargement d’un octet non signé
lui $1, 40 Load Upper Immediate (16 bits shifted left par 16)
LUI $1 0040
$1 0040 0000 … 0000
les instructions. 43
Comparaison et branchement
Instruction Exemple Signification
branch on equal beq $1,$2,100 Si ($1 == $2) go to CP+4+100
branch on not eq. bne $1,$2,100 Si ($1!= $2) go to PC+4+100
set on less than slt $1,$2,$3 Si ($2 < $3) $1=1; else $1=0
set less than imm. slti $1,$2,100 Si ($2 < 100) $1=1; else $1=0
set less than uns. sltu $1,$2,$3 Si ($2 < $3) $1=1; else $1=0
set l. t. imm. uns. sltiu $1,$2,100 Si ($2 < 100) $1=1; else $1=0
jump j 10000 go to 10000 saut à une adresse
jump register jr $31 go to $31 retour de procédure
jump and link jal 10000 $31 = PC + 4; go to 10000
appel de procédure
les instructions. 44
Langage machine et langage assembleur
Le langage assembleur attribue des noms
symboliques aux instructions, aux registres, et aux
adresses constantes.
Le langage machine est une suite de mots, qui
peuvent représenter des données ou des
instructions.
L’assembleur (pour nous, SPIM) est un programme
qui traduit le langage assembleur en langage
machine.
les instructions. 45
C’est quoi le SPIM ?
SPIM n’est que le mot MIPS écrit à l’envers.
SPIM est un simulateur logiciel qui exécute des
programmes écrits pour les processeurs MIPS
R2000/R3000.
SPIM permet de déboguer plus facilement avec
les Breakpoints et l’exécution pas à pas .
Machine virtuelle = jeu d’instructions
plus riche que le matériel réel.
19/10/2012 12:39 [Link] 46
les instructions. 46
1-Instructions et pseudo-instructions
Les instructions (RISC) étant très élémentaires, on
ajoute des pseudo-instructions, qui n’existent pas
réellement pour le processeur, mais sont traduites
vers une suite d’instructions réelles par l’assembleur.
Par exemple,
blt $t0, $t1, address
est expansée en
slt $at, $t0, $t1
bne $at, $zero, address
les instructions. 47
[Link] et pseudo-instructions
Ou encore,
l i $t0,0xA400020
est expansée en
lui $at,0x0A40
ori $t0, $at,0x0020
les instructions. 48
[Link] commentaires :
Un commentaire sera toujours précédé par un ‘#’ .
# <commentaire>
Exemple :
#################
#-----Programme-----#
#################
19/10/2012 12:39 [Link] 49
les instructions. 49
[Link] chaines de caractères :
Une chaine de caractère sera déclarée entre “ “.
Exemple :
.asciiz “Hello world !\n”
On peut utiliser quelques caractères spéciaux
compatible avec le langage C :
newline(retour-chariot) \n
tabulation \t
19/10/2012 12:39 [Link] 50
les instructions. 50
[Link] directives de SPIM :
Définition : ce sont des instructions qui vont dire à
l’assembleur (SPIM) comment traduire un programme.
Les directives ne produisent pas des
instructions machine.
Format d’une directive : .directive
19/10/2012 12:39 [Link] 51
les instructions. 51
[Link] directives de SPIM :(Suite)
Exemples :
.data : déclaration du segment de données.
.text : déclaration du segment de code.
.ascii “ str“ :déclaration de chaines de caractères.
.asciiz “ str“ :déclaration de chaines de caractères se
terminant avec le caractère nul.
.space n : Alloue n octets d’espace mémoire dans le
segment de données.
19/10/2012 12:39 [Link] 52
les instructions. 52
[Link] directives de SPIM :(Suite)
.word w1, …, wn : Enregistre les n quantités 32 bits
dans des mots consécutive en mémoire
. half h1, ..., hn : Enregistre les n quantités 16 bits
dans des mots consécutive en mémoire
. byte b1, …, bn : Enregistre les n quantités d’octets
sucessivement en mémoire
.globl sym :déclare une étiquette ou variable globale
c.-à-d. pouvant être appelé depuis un autre fichier.
19/10/2012 12:39 [Link] 53
les instructions. 53
[Link] appels système :
$v0
$a0-$a3 syscall
$a0
$v0
•v0 (2) : Ce registre doit contenir le code de l’appel système .
•a0-a3 (4 -7) : pour les arguments en cas de manipulation de
print_int , print_string .
•v0 (2): résultat cas des services : read_int
19/10/2012 12:39 [Link] 54
les instructions. 54
[Link] appels système ( Suite ) :
Nom No Effet
print_int 1 imprime l'entier contenu dans a0
print_string 4 imprime la chaîne en a0 jusqu'à '\000'
read_int 5 lit un entier et le place dans v0
Lecture d’une chaîne
read_string 8 L’adresse du buffer en a0
La longeur de la chaîne en a1
exit 10 arrêt du programme en cours d'exécution
19/10/2012 12:39 [Link] 55
les instructions. 55
Un exemple complet 1: Factorielle (itératif)
.data
str1: .asciiz " Entrez un entier :"
str2: .asciiz "Sa factorielle est «
.text
main: li $v0 , 4 # system call code for print_str
la $a0 , str1 # address of string to print
syscall # print the string
li $v0 , 5 # system call code for read_int
syscall # read int , result in $v0
les instructions. 56
Un exemple complet 1: Factorielle (itératif)
li $3 , 1 # initialisation du resultat
loop: blt $v0,1,sortie # Si $v0 <1, on sort
mul $3,$v0,$3
sub $v0,$v0,1
b loop # sinon , $3=$3*$v0 , $v0 =$v0 -1
sortie:li $v0 , 4 # system call code for print_str
la $a0 , str2 # address of string to print
syscall # print the string
les instructions. 57
Un exemple complet 1: Factorielle (itératif)
li $v0,1 # system call code for print_int
move $a0,$3 # integer to print
syscall # print the integer
li $v0,10 # on sort proprement du programme
syscall
les instructions. 58
Fonctions récursives
voici une fonction C récursive.
int f (int n)
{
if (n<= 0)
return 1;
else
return n*f(n − 1);
}
les instructions. 59
Fonctions récursives
• Parce que fact est récursive, plusieurs appels imbriqués
peuvent être actifs simultanément :
a0 a0 – 1
a0 a0 – 1
fact fact
v0 a0 x v0
v0 a0 x v0
L’appel récursif modifie a0 . en fait, il en détruit le contenu.
Or, celui-ci est utilisé après l’appel.
Il faut donc sauvegarder le contenu de a0 avant l’appel, puis
le restaurer après l’appel. (Et de même pour $ra.)
les instructions. 60
La pile
• Par convention, la pile grandit dans le sens des adresses
décroissantes. Le registre $sp pointe vers le sommet de la
pile, c’est-`a-dire vers le dernier mot alloué.
On sauvegarde le contenu de a0 sur la pile comme ceci :
sub $sp, $sp, 4 # alloue un mot sur la pile
sw $a0, 0($sp) # copie $a0 vers le sommet de la pile
On restaure le contenu de a0 depuis la pile comme cela :
lw $a0, 0($sp) # copie le sommet de la pile vers $a0
add $sp, $sp, 4 # d´esalloue un mot sur la pile
les instructions. 61
Factorielle (récursive)
. data
str1 : . asciiz " Entrez un entier :"
str2 : . asciiz "Sa factorielle est "
. text
main : li $v0 , 4 # system call code for print_str
la $a0 , str1 # address of string to print
syscall # print the string
li $v0 , 5 # system call code for read_int
syscall # read int , result in $v0
move $a0,$v0
jal fact
sortie : move $16,$v0
li $v0 , 4 # system call code for print_str
la $a0 , str2 # address of string to print
syscall # print the string
li $v0 ,1 # system call code for print_int
move $a0 ,$16 # integer to print
syscall # print the integer
li $v0 ,10 # on sort proprement du programme
les instructions.
Syscall 62
Factorielle (récursive)
fact : blez $a0, fact 0 # si a0 <= 0 saut a fact 0
sub $sp, $sp, 8 # reserve deux mots en pile
sw $ra, 0( $sp) # sauve l'adresse de retour
sw $a0, 4($sp) # et la valeur de a0
sub $a0, $a0, 1 # decrement a0
jal fact # appel recursif (a0-1)
lw $a0, 4($sp) # recupere a0
mul $v0, $v0, $a0 # v0 a0 x v0
lw $ra, 0( $sp) # recupere l' adresse de retour
add $sp, $sp, 8 # libere la pile
j $ra # retour a l ' appelant
fact 0 : li $v0, 1 # v0 1
j $ra # retour a l ' appelant
les instructions. 63
