Presentation
du cours Le processeur MIPS Programmation du MIPS
Compilation
(INF 564)
Introduction & architecture MIPS
Francois Pottier
10 decembre
2014
Francois Pottier
Compilation (INF 564)
Presentation
du cours Le processeur MIPS Programmation du MIPS
Presentation
du cours
Le processeur MIPS
Programmation du MIPS
Francois Pottier
Compilation (INF 564)
Presentation
du cours Le processeur MIPS Programmation du MIPS
Quest-ce quun compilateur ?
Un compilateur traduit un langage de haut niveau (adapte a` lesprit
humain) vers un langage de bas niveau (concu pour e tre execut
e
efficacement par une machine).
Francois Pottier
Compilation (INF 564)
Presentation
du cours Le processeur MIPS Programmation du MIPS
Apercu du cours
En 9 seances,
ecrivons
un compilateur dun langage source
modeste (sous-ensemble de Pascal et C) vers un langage
assembleur (MIPS).
Chaque cours expose une des phases du compilateur. Le TP qui
suit permet daborder la pratique devant la machine.
Francois Pottier
Compilation (INF 564)
Presentation
du cours Le processeur MIPS Programmation du MIPS
Pourquoi suivre ce cours ?
pour ecrire
un programme complexe et el
dans un langage
egant
de tr`es haut niveau (Objective Caml) ;
pour comprendre le fosse entre lintention humaine et le langage
de bas niveau execut
e par le microprocesseur ;
pour decouvrir
des techniques et algorithmes dusage gen
:
eral
analyse lexicale, analyse syntaxique, transformation darbres de
syntaxe abstraite, analyse de flot de donnees,
allocation de
registres par coloriage de graphe, etc.
Francois Pottier
Compilation (INF 564)
Presentation
du cours Le processeur MIPS Programmation du MIPS
Attention !
Un compilateur, ...
I
I
cest beau comme des maths, et en plus ca tourne !
ca demande du travail :
I
I
on demande de finir chez soi chaque TP ;
il ny a pas de poly : venez en cours !
Francois Pottier
Compilation (INF 564)
Presentation
du cours Le processeur MIPS Programmation du MIPS
Un compilateur de Pseudo-Pascal vers MIPS
Texte source
Texte cible
Analyse lexicale et syntaxique
Achage
Pseudo-Pascal
ASM
Slection d'instructions
Ralisation des trames de pile
UPP
LIN
Cration du graphe
de flot de contrle
Linarisation du graphe
de flot de contrle
RTL
ERTL
Explicitation des
conventions d'appel
Francois Pottier
LTL
Allocation des registres
Compilation (INF 564)
Presentation
du cours Le processeur MIPS Programmation du MIPS
Plan du cours
1. Architecture MIPS.
2. Syntaxe, semantique
et interpretation
de Pseudo-Pascal.
3. Analyse lexicale et syntaxique (du texte source vers PP).
4. Typage. Selection
dinstructions (de PP vers UPP).
5. Creation
du graphe de flot de controle (de UPP vers RTL).
6. Explicitation de la convention dappel (de RTL vers ERTL).
7. Analyse de duree
de vie (sur ERTL).
8. Coloriage de graphe et allocation des registres (de ERTL vers LTL).
9. Linearisation
du code (de LTL vers LIN) puis realisation
des trames de
pile (de LIN vers ASM).
Francois Pottier
Compilation (INF 564)
Presentation
du cours Le processeur MIPS Programmation du MIPS
Presentation
du cours
Le processeur MIPS
Programmation du MIPS
Francois Pottier
Compilation (INF 564)
Presentation
du cours Le processeur MIPS Programmation du MIPS
Architecture dun ordinateur
Du point de vue du programmeur ou du compilateur, un ordinateur
est constitue principalement dun processeur et dune memoire.
Francois Pottier
Compilation (INF 564)
10
Presentation
du cours Le processeur MIPS Programmation du MIPS
Le processeur
Le processeur est capable de lire et decrire
des informations en
memoire.
Il
dispose
egalement
dun
petit
nombre
demplacements
memoire
plus rapides, appeles
registres.
Les instructions que doit executer
le processeur sont elles-memes
stockees
en memoire.
Un registre special
nomme pc contient ladresse
de la prochaine instruction a` executer.
De facon rep
et
ee,
le processeur lit linstruction stockee
a` ladresse pc
(fetch), lanalyse (decode), puis linterpr`ete (execute), ce qui peut avoir
pour effet de modifier certains registres (dont pc) et/ou la memoire.
Francois Pottier
Compilation (INF 564)
11
Presentation
du cours Le processeur MIPS Programmation du MIPS
CISC et RISC
Les principales differences
entre processeurs concernent leur jeu
dinstructions.
I
Les processeurs CISC (Complex Instruction Set)
I
Leurs instructions, de taille variable, sont variees
et realisent
souvent des transferts avec la memoire.
Ces processeurs
poss`edent en gen
peu de registres, dont certains sont
eral
reserv
es
pour des usages specifiques.
Exemples : Intel 8086 et Motorola 68000 (pre-1985).
Les processeurs RISC (Reduced Instruction Set)
I
Leurs instructions, de taille fixe, sont reguli`
eres et peu dentre
elles lisent ou ecrivent
en memoire.
Ces processeurs poss`edent en
gen
de nombreux registres, lesquels sont uniformes.
eral
Exemples : Alpha, Sparc, Mips, PowerPC, ARM (post-1985).
Francois Pottier
Compilation (INF 564)
12
Presentation
du cours Le processeur MIPS Programmation du MIPS
La memoire
La memoire
est un grand tableau dont les indices sont les adresses.
Pour des raisons historiques, les adresses sont mesurees
en octets
(8 bits).
Cependant, les lectures et ecritures
en memoire
se font sur des
quantites
plus importantes que loctet. Le mot est la
de memoire
taille des donnees
que lon peut transferer
en une instruction :
typiquement 32 ou 64 bits, selon les processeurs. Le mot est
egalement
la taille des adresses et des registres.
Francois Pottier
Compilation (INF 564)
13
Presentation
du cours Le processeur MIPS Programmation du MIPS
La memoire
virtuelle
Tous les processeurs modernes contiennent une unite de gestion
memoire
(MMU) qui distingue adresses physiques et adresses
virtuelles.
La MMU est utilisee
par le syst`eme dexploitation pour donner a`
chaque processus lillusion quil dispose de toute la memoire.
Francois Pottier
Compilation (INF 564)
14
Presentation
du cours Le processeur MIPS Programmation du MIPS
15
La memoire
vue depuis un processus
Pile (stack)
Paramtres de fonctions
Variables locales
sp
Espace non allou
Tas (heap)
Objets allous dynamiquement
Donnes
Variables globales
Code
(en lecture seule)
gp
pc
Francois Pottier
Compilation (INF 564)
Presentation
du cours Le processeur MIPS Programmation du MIPS
Les registres du MIPS
Le MIPS comporte 32 registres gen
nommes
eraux,
r0 a` r31. Le
registre r0, appele zero, contient toujours la valeur 0, meme apr`es
une ecriture.
Les 31 autres registres sont interchangeables.
Neanmoins,
ces 31 registres peuvent e tre, par convention :
reserv
es
pour le passage darguments (a0-a3, ra) ou le renvoi
de resultats
(v0-v1) ;
consider
es
comme sauvegardes
par lappele (s0-s7) ou non
(t0-t9) lors des appels de fonctions ;
reserv
es
pour contenir des pointeurs vers la pile (sp, fp) ou vers
les donnees
(gp) ;
reserv
es
par le noyau (k0-k1) ;
reserv
es
par lassembleur (at).
Francois Pottier
Compilation (INF 564)
16
Presentation
du cours Le processeur MIPS Programmation du MIPS
Les instructions du MIPS
Le MIPS propose trois types principaux dinstructions :
I
les instructions de transfert entre registres et memoire
;
les instructions de calcul ;
les instructions de saut.
Seules les premi`eres permettent dacceder
a` la memoire
; les autres
op`erent uniquement sur les registres.
Francois Pottier
Compilation (INF 564)
17
Presentation
du cours Le processeur MIPS Programmation du MIPS
Les instructions de transfert
Lecture (load word) :
lw
dest , offset(base)
On ajoute la constante (de 16 bits) offset a` ladresse contenue
dans le registre base pour obtenir une nouvelle adresse ; le mot
stocke a` cette adresse est alors transfer
e vers le registre dest.
Francois Pottier
Compilation (INF 564)
18
Presentation
du cours Le processeur MIPS Programmation du MIPS
Les instructions de transfert
Ecriture
(store word) :
sw
source , offset(base)
On ajoute la constante (de 16 bits) offset a` ladresse contenue
dans le registre base pour obtenir une nouvelle adresse ; le mot
stocke dans le registre source est alors transfer
e vers cette
adresse.
Francois Pottier
Compilation (INF 564)
19
Presentation
du cours Le processeur MIPS Programmation du MIPS
Les instructions de calcul
Ces instructions lisent la valeur de 0, 1 ou 2 registres dits
arguments, effectuent un calcul, puis ecrivent
le resultat
dans un
registre dit destination.
Un meme registre peut figurer plusieurs fois parmi les arguments et
destination.
Francois Pottier
Compilation (INF 564)
20
Presentation
du cours Le processeur MIPS Programmation du MIPS
Les instructions de calcul nullaires
Ecriture
dune constante (Load Immediate) :
li
dest , constant
Produit la constante constant.
Francois Pottier
Compilation (INF 564)
21
Presentation
du cours Le processeur MIPS Programmation du MIPS
Les instructions de calcul unaires
I
Addition dune constante (Add Immediate) :
addi
Produit la somme de la constante (de 16 bits) constant et du
contenu du registre source.
Deplacement
(Move) :
move
dest , source , constant
dest , source
Produit le contenu du registre source. Cas particulier de addi !
Negation
(Negate) :
neg
dest , source
Produit loppose du contenu du registre source. Cas particulier
de sub !
Francois Pottier
Compilation (INF 564)
22
Presentation
du cours Le processeur MIPS Programmation du MIPS
Les instructions de calcul binaires
I
Addition (Add) :
add
dest , source1 , source2
Produit la somme des contenus des registres source1 et
source2.
I
On a egalement
sub, mul, div.
Comparaison (Set On Less Than) :
slt
dest , source1 , source2
Produit 1 si le contenu du registre source1 est inferieur
a` celui
du registre source2 ; produit 0 sinon.
I
On a egalement
sle, sgt, sge, seq, sne.
Francois Pottier
Compilation (INF 564)
23
Presentation
du cours Le processeur MIPS Programmation du MIPS
Les instructions de calcul variante
Les instructions de calcul prec
(add, addi, sub, etc.)
edentes
provoquent une exception du processeur (trap) en cas de
depassement
de capacite (overflow).
Une exception provoque un appel de procedure
a` un gestionnaire
(handler) prealablement
installe.
Il existe des variantes dites non signees
(unsigned) de ces
instructions (addu, addiu, subu, etc.), qui ne provoquent pas
dexception.
Nous utiliserons ces derni`eres, aussi bien pour les calculs dadresses
que pour les calculs sur les entiers de Pseudo-Pascal.
Francois Pottier
Compilation (INF 564)
24
Presentation
du cours Le processeur MIPS Programmation du MIPS
Les instructions de saut
On distingue les instructions de saut selon que :
I
leurs destinations possibles sont au nombre de 1 (saut
inconditionnel) ou bien 2 (saut conditionnel) ;
leur adresse de destination est constante ou bien lue dans un
registre ;
une adresse de retour est sauvegardee
ou non.
Francois Pottier
Compilation (INF 564)
25
Presentation
du cours Le processeur MIPS Programmation du MIPS
Saut inconditionnel
Saut (Jump) :
j
address
Saute a` ladresse constante address. Celle-ci est en gen
eral
donnee
que lassembleur
sous forme symbolique par une etiquette
traduira en une constante numerique.
Francois Pottier
Compilation (INF 564)
26
Presentation
du cours Le processeur MIPS Programmation du MIPS
Saut conditionnel
I
Saut conditionnel unaire (Branch on Greater Than Zero) :
bgtz
source , address
Si le contenu du registre source est superieur
a` zero,
saute a`
ladresse constante address.
I
On a egalement
bgez, blez, bltz.
Saut conditionnel binaire (Branch On Equal) :
beq
source1 , source2 , address
Si les contenus des registres source1 et source2 sont egaux,
saute a` ladresse constante address.
I
On a egalement
bne.
Francois Pottier
Compilation (INF 564)
27
Presentation
du cours Le processeur MIPS Programmation du MIPS
Saut avec retour
Saut avec retour (Jump And Link) :
jal
address
Sauvegarde ladresse de linstruction suivante dans le registre
ra, puis saute a` ladresse constante address.
Francois Pottier
Compilation (INF 564)
28
Presentation
du cours Le processeur MIPS Programmation du MIPS
Saut vers adresse variable
Saut vers adresse variable (Jump Register) :
jr
target
Saute a` ladresse contenue dans le registre target.
Linstruction jr $ra est typiquement employee
pour rendre la main a`
lappelant a` la fin dune fonction ou procedure.
Francois Pottier
Compilation (INF 564)
29
Presentation
du cours Le processeur MIPS Programmation du MIPS
Une instruction speciale
Appel syst`eme (System Call) :
syscall
Provoque un appel au noyau. Par convention, la nature du service
souhaite est specifi
ee
par un code entier stocke dans le registre
v0. Des arguments supplementaires
peuvent e tre passes
dans
les registres a0-a3. Un resultat
peut e tre renvoye dans le
registre v0.
spim propose un tr`es petit nombre dappels syst`eme : voir la page
A-44 de sa documentation.
Francois Pottier
Compilation (INF 564)
30
Presentation
du cours Le processeur MIPS Programmation du MIPS
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 representer
des donnees
ou des instructions.
Lassembleur (pour nous, spim ou mars) est un programme qui
traduit le langage assembleur en langage machine.
Francois Pottier
Compilation (INF 564)
31
Presentation
du cours Le processeur MIPS Programmation du MIPS
Instructions et pseudo-instructions
Certaines des instructions prec
ne sont en fait pas
edentes
implantees
par le processeur, mais traduites par lassembleur en
sequences
dinstructions plus simples.
Par exemple,
blt $t0, $t1, address
est expansee
en
slt $at, $t0, $t1
bne $at, $zero , address
Francois Pottier
Compilation (INF 564)
32
Presentation
du cours Le processeur MIPS Programmation du MIPS
Instructions et pseudo-instructions
Ou encore,
li
$t0, 400020
est expansee
en
lui $at, 6
ori $t0, $at, 6804
Pour nous, la distinction entre instructions et pseudo-instructions
naura pas dimportance.
Francois Pottier
Compilation (INF 564)
33
Presentation
du cours Le processeur MIPS Programmation du MIPS
Exemple de programme assembleur
.data
hello :
.asciiz hello world\n
.text
main :
l i $v0, 4
la $a0, hello
syscall
jr $ra
#
#
#
#
#
#
#
#
#
Des donnees
suivent.
L adresse de la donnee
qui suit.
Chane terminee
par un z ero.
Des instructions suivent.
Adresse de l instruction qui suit.
Code de l appel print string.
Adresse de la chane.
Appel au noyau.
Fin de la procedure
main.
Francois Pottier
Compilation (INF 564)
34
Presentation
du cours Le processeur MIPS Programmation du MIPS
Execution
dun programme par spim
Le programme est assemble puis execut
e a` laide de la commande :
spim f i l e hello . spi
Par convention, lexecution
debute
au label main et termine lorsque
cette procedure
rend la main.
spim est donc a` la fois un assembleur et un simulateur.
Francois Pottier
Compilation (INF 564)
35
Presentation
du cours Le processeur MIPS Programmation du MIPS
Execution
dun programme par spim
En realit
debute
au label start et termine lorsque le
e,
lexecution
programme effectue lappel syst`eme numero
10 (exit).
Cela ne se voit pas parce que spim charge aussi un morceau de
code qui ressemble a` ceci :
start :
jal main
l i $v0, 10
syscall
# Stoppe l ex ecution
du processus.
Si on donne a` spim loption -notrap, il ne charge pas ce code.
Francois Pottier
Compilation (INF 564)
36
Presentation
du cours Le processeur MIPS Programmation du MIPS
Execution
dun programme par mars
mars se comporte comme spim -notrap. On ecrit
donc :
mars hello . spi
et lexecution
debute
au label
start.
mars est aussi un editeur
intelligent. Tapez simplement mars et
ecrivez
votre programme. Vous pourrez lassembler et lexecuter
sans
quitter linterface graphique.
Francois Pottier
Compilation (INF 564)
37
Presentation
du cours Le processeur MIPS Programmation du MIPS
Presentation
du cours
Le processeur MIPS
Programmation du MIPS
Francois Pottier
Compilation (INF 564)
38
Presentation
du cours Le processeur MIPS Programmation du MIPS
Haut niveau et bas niveau
Des constructions qui peuvent sembler el
dans un langage
ementaires
tel que Pascal (tests, boucles, fonctions) seront traduites par de
nombreuses instructions assembleur.
Par ailleurs, des notions dapparence pourtant simple nont pas
dequivalent.
Par exemple, les variables de Pascal seront traduites en
termes demplacements memoire
et de registres une tache non
triviale.
Francois Pottier
Compilation (INF 564)
39
Presentation
du cours Le processeur MIPS Programmation du MIPS
Tests
Le fragment de Pascal suivant :
if t1 < t2 then t3 := t1 else t3 := t2
peut e tre traduit en assembleur MIPS comme ceci :
blt $t1, $t2, then
move $t3, $t2
j
done
then :
move $t3, $t1
done :
# si t1 < t2 saut vers l etiquette
then
# t3 := t2
# saut vers l etiquette
done
# t3 := t1
# suite du programme
Francois Pottier
Compilation (INF 564)
40
Presentation
du cours Le processeur MIPS Programmation du MIPS
Boucles
Le fragment de Pascal suivant :
t2 := 0;
while t1 > 0 do begin t2 := t2 + t1; t1 := t1 1 end
peut e tre traduit en assembleur MIPS comme ceci :
l i $t2, 0
while :
blez $t1, done
add $t2, $t2, $t1
sub $t1, $t1, 1
j
while
done :
#
#
#
#
#
#
#
t2 := 0
debut
de la boucle
si t1 <= 0 saut vers l etiquette
done
t2 := t2 + t1
t1 := t1 1
retour vers l etiquette
while
suite du programme
Francois Pottier
Compilation (INF 564)
41
Presentation
du cours Le processeur MIPS Programmation du MIPS
Fonctions
La fonction Pascal suivante :
function succ (x : integer) : integer ;
begin
succ := x + 1
end;
peut e tre traduite en assembleur MIPS comme ceci :
succ :
addi $v0, $a0, 1
jr $ra
# $a0 contient l argument x
# $v0 contient le r esultat
# retour a` l appelant
Le choix des registres est impose par la convention dappel.
Francois Pottier
Compilation (INF 564)
42
Presentation
du cours Le processeur MIPS Programmation du MIPS
Convention dappel
La convention dappel regit
la communication entre appelant et appele
lors de lappel de procedure
ou de fonction. Pour le MIPS, la
convention proposee
par le fabricant est :
I
les arguments sont passes
dans a0-a3 puis (sil y en a plus de
quatre) sur la pile ;
ladresse de retour est passee
dans ra ;
la valeur de retour est renvoyee
dans v0 ;
les registres mentionnes
ci-dessus, ainsi que t0-t9, peuvent e tre
modifies
par lappele ; lappelant doit donc les sauvegarder si
necessaire
; on les appelle caller-save ;
les registres s0-s7 doivent e tre preserv
es
par lappele ; on les
appelle callee-save.
Francois Pottier
Compilation (INF 564)
43
Presentation
du cours Le processeur MIPS Programmation du MIPS
Fonctions recursives
Plus difficile : voici une fonction Pascal recursive.
function f (n : integer) : integer ;
begin
if n <= 0 then
f := 1
else
f := n f (n 1)
end;
Francois Pottier
Compilation (INF 564)
44
Presentation
du cours Le processeur MIPS Programmation du MIPS
Fonctions recursives
Voici une traduction nave et incorrecte en assembleur MIPS :
fact :
blez $a0,
sub $a0,
jal fact
mul $v0,
jr $ra
fact0 :
l i $v0,
jr $ra
fact0
$a0, 1
$a0, $v0
# si a0 <= 0 saut vers l etiquette
fact0
# a0 := a0 1
# appel r ecursif
; l i t a0 et ecrit
dans v0
# v0 := a0 v0
# retour a` l appelant
# v0 := 1
# retour a` l appelant
Quelle est lerreur ?
Francois Pottier
Compilation (INF 564)
45
Presentation
du cours Le processeur MIPS Programmation du MIPS
Fonctions recursives
Parce que fact est recursive,
plusieurs appels imbriques
peuvent e tre
actifs simultanement
:
a0
a0 1
a0 a0 1
...
fact
fact
v0 a0 v0
v0 a0 v0
Lappel recursif
modifie a0 en fait, il en detruit
le contenu. Or,
celui-ci est utilise apr`es lappel.
Il faut donc sauvegarder le contenu de a0 avant lappel, puis le
restaurer apr`es lappel. (Et de meme pour ra.)
Francois Pottier
Compilation (INF 564)
46
Presentation
du cours Le processeur MIPS Programmation du MIPS
La pile
Par convention, la pile grandit dans le sens des adresses
decroissantes.
Le registre sp pointe vers le sommet de la pile,
cest-a-dire
vers le dernier mot alloue.
`
On sauvegarde le contenu de a0 sur la pile comme ceci :
subu $sp, $sp, 4
sw $a0, 0($sp)
# alloue un mot sur la pile
# copie $a0 vers le sommet de la pile
On restaure le contenu de a0 depuis la pile comme cela :
lw $a0, 0($sp)
addu $sp, $sp, 4
# copie le sommet de la pile vers $a0
# d esalloue
un mot sur la pile
Francois Pottier
Compilation (INF 564)
47
Presentation
du cours Le processeur MIPS Programmation du MIPS
48
La version assembleur
Voici le code produit par une version de notre compilateur :
f17 :
addiu
sw
sw
move
blez
addiu
jal
mul
$sp,
$ra ,
$s0,
$s0,
$s0,
$a0,
f17
$v0,
f28 :
lw
lw
addiu
jr
f4 :
li
j
$sp, 8
4($sp)
0($sp)
$a0
f4
$s0, 1
$ra , 4($sp)
$s0, 0($sp)
$sp, $sp, 8
$ra
$v0, 1
f28
$s0, $v0
Exercice recommande : expliquez chaque instruction.
Francois Pottier
Compilation (INF 564)
