===== Assembleur y86 =====
y86 est un langage assembleur simplifié basé sur l'architecture des processeurs x86 (IA-32). Les mots mémoires sont alignés sur 32 bits et utilise la convention //little endian// (stockage des octets dans l'ordre inverse, c'est-à-dire en commençant par l'octet de poids faible).
Le y86 utilise 8 registres généraux de 32 bits, dont certains ont des rôles historiques.
* %eax : le registre d'accummulation
* %ecx : le registre de compteur utilisé dans les boucles
* %edx : un registre auxiliaire
* %ebx : le registre //base index// utilisé comme pointeur sur la base d'un tableau
* %esp : le registre //stack pointer// qui pointe sur le sommet du cadre d'appel de la fonction courante, c'est-à-dire le sommet de la pile
* %ebp : le registre //frame base pointer// qui pointe la base du cadre d'appel de la fonction courante
* %esi : le registre //source index// utilisé lors des copies de suite d'octets
* %edi : le registre //destination index// utilisé lors des copies de suite d'octets
En outre, le registre %eip (//instruction pointer//) pointe sur l'adresse de la prochaîne instruction à exécuter. On ne manipule pas ce registre directement. En revanche, il est modifié automatiquement lors de l'exécution ou par des instructions du type jmp, call, ret.
y86 propose un jeu d'instructions réduit :
* instructions arithmétiques : addl, subl, andl, xorl
* moves : irmovl, rrmovl, rmmovl, mrmovl
* sauts conditionnels (ou pas) : jmp, je, jne, jg, jge, jl, jle
* gestion pile : pushl, popl
* appel/retour de fonction : call, ret
* divers : nop, halt
Plus de détails : [[http://dept-info.labri.fr/ENSEIGNEMENT/archi/CSAPP/class1b-ISA.pdf|ici]]
==== Compilation & Simulation ====
Voici le code source du simulateur y86 : http://dept-info.labri.fr/ENSEIGNEMENT/archi/sim.tgz
Etant donné un code source //code.ys//, nous utilisons le compilateur //yas// et le simulateur séquentiel //ssim// de la façon suivante :
yas code.ys # generate code.yo
ssim code.yo # simulation
ssim -g code.yo # simulation (avec mode graphique)
L'interface graphique dispose d'un mode //instruction par instruction// très pratique pour suivre le déroulement de son programme.
==== Simulateur web y86 en JS ====
Voici un simulateur y86 écrit en JavaScript et disponible en ligne :
[[http://dept-info.labri.fr/ENSEIGNEMENT/archi/js-y86/ | Simulateur y86]]
Attention, cette version disponible sur https://github.com/orel33/js-y86/ a été modifiée par rapport à la version originale pour respecter la syntaxe étudiée dans ce cours.
A vous de jouer ;-)
==== If then ====
Pour effectuer un branchement conditionnel qui dépend d'un test entre deux registres %eax et %ebx, on commence typiquement à comparer ces deux registres par soustraction, ce qui a pour effet de modifier les //codes de condition// (Z pour zéro, O pour overflow et S pour strictement négatif). Il suffit alors d'effectuer le branchement approprié //jle, jl, je, jne, jge, jg// (l = lower, g = greater, e = equal). Par ailleurs, les instructions arithmétiques comme la soustraction "subl rA,rB" stockent le résultat dans le second registre, c'est-à-dire rB -= rA. Attention donc à l'ordre des arguments !
long a = 2, b = 3, c;
if (a < b) c = 1;
Afin de se rapprocher du code assembleur à écrire, il peut être utile de réécrire le code C de la façon suivante en utilisant //une condition d'évitement// :
long a = 2, b = 3, c;
// (a < b) <=> (a-b < 0) <=> ! (a-b >= 0)
long tmp = a-b; // calcul de la condition d'évitement
if (tmp >= 0) goto _endif; // test de la condition d'évitement
c = 1;
_endif:
.pos 0
mrmovl a,%eax
mrmovl b,%ebx
subl %ebx,%eax # on calcule a-b (dans ce sens)
jge endif # on teste la condition de sortie : a-b >= 0 ?
then: irmovl 1,%ecx
rmmovl %ecx,c # c = 1
endif: halt
.pos 0x100
a: .long 2
b: .long 3
c: .long 0
Ici, le branchement conditionnel doit éviter le bloc //then// pour se brancher directement sur //endif// : c'est pourquoi on choisit le test //jge//.
__Astuce__ : L'instruction //subl// modifie la registre cible, ce qui présente un inconvénient. Dans le cas où l'on souhaite tester si un registre %eax est égal à zéro (ou non) avec //je// (ou //jne//), une astuce consiste à effectuer l'opération //andl %eax,%eax// ;-)
==== If then Else ====
long a = 2, b = 3, c;
if (b <= a) c = 1; else c = 2;
Un peu de réécriture du code C :
long a = 2, b = 3, c;
long tmp = b - a;
if (tmp > 0) goto _else;
c = 1; // tmp <= 0, donc la condition b <= a est vraie
goto _endif;
_else:
c = 2; // tmp > 0, donc la condition b <= a est fausse
_endif:
Avant de traduire cela en assembleur :
.pos 0
mrmovl a,%eax
mrmovl b,%ebx
subl %eax,%ebx # on calcule b-a (dans ce sens)
jg else # on teste la condition du else : b-a > 0 ?
then: irmovl 1,%ecx
rmmovl %ecx,c # c = 1
jmp endif
else: irmovl 2,%ecx
rmmovl %ecx,c # c = 2
endif: halt
.pos 0x100
a: .long 2
b: .long 3
c: .long 0
Ici, c'est pareil que dans l'exemple précédent le branchement conditionnel doit éviter le bloc //then// pour se brancher sur le //else// : c'est pourquoi on choisit le test //jg//.
==== Boucle For ====
long sum = 0;
for(i = 1 ; i <= 10 ; i++) sum += i;
.pos 0
mrmovl sum,%edx # %edx: sum
irmovl 1,%eax # %eax: i = 1
loop: rrmovl %eax,%ebx
isubl 10,%ebx # on calcule i-10
jg end # condition arrêt si i-10 > 0
addl %eax,%edx # sum += i
iaddl 1,%eax # i++
jmp loop
end: rmmovl %edx,sum
halt
.pos 0x100
sum: .long 0
__Note Bene__ : On peut un peu simplifier ce code en parcourant la boucle à l'envers... la comparaison à zéro est toujours plus facile à écrire ;-)
.pos 0
mrmovl sum,%edx # %edx: sum
irmovl 10,%eax # %eax: i = 10
loop: isubl 1,%eax # on calcule i--
je end # condition arrêt si i == 0
addl %eax,%edx # sum += i
jmp loop
end: rmmovl %edx,sum
halt
.pos 0x100
sum: .long 0
==== Pointeurs ====
long a = 1, b = 0;
long * p = &a;
b = *p; /* b = 1 */
*p = 2; /* a = 2 */
Dans le code suivant, on utilisera le registre %esi pour désigner le pointeur p.
irmovl a,%esi # p = &a
mrmovl (%esi),%eax # b = *p
rmmovl %eax,b
irmovl 2,%eax # *p = 2
rmmovl %eax,(%esi)
.pos 0x100
a: .long 1
b: .long 0
==== Les tableaux ====
On rappelle que l'étiquette //t// représente une //adresse immédiate//. La notation //(%ebx)// désigne //l'adresse indirecte// en mémoire pointée par le registre //%ebx//. La notation //4(%ebx)// correspond à l'adresse //(%ebx)+4//. Notons qu'un //long// compte pour 4 octets.
irmovl t,%ebx # l'adresse t est mis dans %ebx, qui joue le rôle de pointeur
mrmovl (%ebx),%eax # load: %eax = t[0]
...
rmmovl %ecx,(%ebx) # t[0] <- %ecx
rmmovl %ecx,4(%ebx) # t[1] <- %ecx
.pos 0x100
t: .long 1 # tableau t d'adresse 0x100 et de taille 4 long
.long 2
.long 3
.long 4
//expliquer la variante d'adressage indexé : t(%eax)//
==== Décalage des valeurs dans un tableau ====
for(i = 0 ; i < n-1; i++)
t[i] = t[i+1];
.pos 0
mrmovl n,%ecx
irmovl t,%ebx
loop: isubl 1,%ecx # n--
je end
mrmovl 4(%ebx),%eax # t[0] <- t[1]
rmmovl %eax,(%ebx)
iaddl 4,%ebx # t += 4
jmp loop
end: halt
.pos 0x100
n: .long 5
t: .long 1
.long 2
.long 3
.long 4
.long 5
==== Appel de fonction et Pile ====
long f(long i, long j) { return (i+j); }
long a = f(1,2);
.pos 0
irmovl stack,%esp # initialisation du pointeur de pile (stack pointer)
jmp main
f: mrmovl 4(%esp),%eax # on récupère le premier paramètre (a)
mrmovl 8(%esp),%ecx # on récupère le second paramètre (b)
addl %ecx,%eax # variable de retour dans %eax
ret
main: mrmovl b,%eax # on empile les paramètres en sens inverse
pushl %eax
mrmovl a,%eax
pushl %eax
call f # appel de la fonction f()
aret: popl %ecx # on dépile les 2 paramètres avec popl
popl %ecx # ou iaddl 8,%esp
rmmovl %eax,res
halt
.pos 0x100
a: .long 1
b: .long 2
res: .long 0
.pos 0x200 # adresse de base de la pile
stack:
Tout d'abord, il faut noter que la pile stocke les données dans l'ordre décroissant des adresses mémoire, à partir de l'adresse //stack// (0x200) vers la zone des variables (0x100) ! Le registre //%esp// est le pointeur de pile (ou //stack pointer//) qui désigne le sommet de la pile à l'adresse //(%esp)//.
Avant l'appel de fonction //f()//, on commençe par empiler ces paramètres avec //pushl// dans l'ordre inverse ! Au moment de l'appel de fonction avec l'instruction //call//, l'adresse de retour de la fonction (notée //aret// pour illustrer notre propos) est automatiquement empilée et se trouve donc au sommet de la pile.
(...)
0x1F0-0x1F3:
0x1F4-0x1F7: adresse de retour (aret) <-- sommet de la pile après call (%esp = 0x1F4)
0x1F8-0x1FB: premier argument long (1) <-- sommet de la pile après second pushl (%esp = 0x1F8)
0x1FC-0x1FF: deuxième argument long (2) <-- sommet de la pile après premier pushl (%esp = 0x1FC)
0x200-0x203: <-- sommet initial de la pile (%esp = 0x200)
0x204-0x207:
(...)
Le retour de fonction avec l'instruction //ret// dépile automatiquement cette adresse et fait sauter le programme sur //aret//. Il faut encore dépiler les paramètres avec //popl// ou en ajoutant explicitement à //%esp// la taille nécessaire (2 long ici, soit 8 octets).
Par convention, on place la valeur de retour de la fonction dans le registre //%eax//.
__Nota Bene__ : Il ne faut pas oublier d'initialiser la pile au départ du programme ! A la fin du programme, on peut vérifier que %esp est revenu à sa valeur initiale //stack//.
==== Sauvegarde des registres lors d'un appel de fonction =====
Lors d'un appel de fonction, certains registres utilisés par l'appelant peuvent être modifié par l'appelé ! Il convient donc de les sauvegarder sur la pile. En principe, on distingue deux types de registres :
* les registres //caller-saved// (%eax, %ecx, %edx) qui doivent être sauvegardés/restaurés par l'appellant si nécessaire, et peuvent donc être utilisés librement par l'appelé ;
* les registres //callee-saved// (%ebx, %esi, %edi, %ebp), qui doivent être sauvegardés/restaurés par l'appelé s'il décide de les utiliser.
En pratique, la fonction appelée doit utiliser les registres %eax, %ecx et %edx en priorité. Les choses se compliquent évidemment lors des appels imbriqués de deux fonctions ;-)
g: # sauvegarde des registres caller
pushl %eax
pushl %ecx
pushl %edx
# empilement des paramètres de f
...
call f
# dépilement des paramètres de f
...
# restauration des registres caller
popl %edx
popl %ecx
popl %eax
halt
f: # récupération des paramètres
...
# sauvegarde des registres callee
pushl %ebp
pushl %esi
pushl %edi
pushl %ebx
...
...
...
# restauration des registres callee
popl %ebx
popl %edi
popl %esi
popl %ebp
ret
__Nota Bene__ : En pratique, on sauvegardera uniquement les registres utiles pour éviter d'allourdir le code. Attention à la modification de %esp !
==== Appel de fonction avec des variables locales ====
Les variables locales sont définies dans la pile après l'adresse de retour. On accède donc aux variables à partir de (%esp), mais du coup les paramètres sont décalés ! Le code de la fonction précédente est modifié pour utiliser une variable locale !
.pos 0
main: irmovl stack,%esp # initialisation du pointeur de pile (stack pointer)
mrmovl b,%eax # on empile le second param b
pushl %eax
mrmovl a,%eax # on empile le premier param a
pushl %eax
call f # appel de la fonction f()
aret: popl %ecx # on depile le premier param
popl %ecx # on depile le second param
rmmovl %eax,res # recup resultat
halt
f: isubl 4,%esp # alloc variable locale x sur la pile
mrmovl 8(%esp),%eax # recup premier param a
mrmovl 12(%esp),%edx # recup second param b
... # compute x
mrmovl (%esp),%ecx # load x
pushl %ecx # save x
... # do something else
mrmovl (%esp),%eax # restore x (variable de retour dans %eax)
iaddl 4,%esp # liberation variable locale x
ret
.pos 0x100
a: .long 1
b: .long 1
res: .long 0
.pos 0x200 # adresse de base de la pile
stack:
__Nota Bene__ : Dans un soucis de simplification, il est choisi ici (et plus tard) de ne pas utiliser le registre %ebp !
==== Utilisation du registre %ebp ====
Voici la recette magique pour l'utilisation de %ebp dans une fonction.
f:
pushl %ebp
rrmovl %esp,%ebp
pushl %ebx
pushl %esi
pushl %edi
... faire ce que vous voulez en utilisant %ebp
popl %edi
popl %esi
popl %ebx
popl %ebp
ret
Nota Bene : Dans un soucis de simplification, il est choisi de ne pas utiliser le registre %ebp... On travaillera uniquement avec %esp.
====Passage par référence dans les fonctions ====
Dans les exemples précédent de fonction, nous avons utiliser le //passage de paramètres par valleur//.
Ici, nous donnons l'exemple d'une fonction //swap(&a,&b)// qui utilise le //passage par référence//. Il s'agit d'échanger les valeurs de deux entiers.
.pos 0
main: irmovl stack,%esp # init de la pile
irmovl b,%eax
pushl %eax # empiler &b
irmovl a,%eax
pushl %eax # empiler &a
call swap
iaddl 8,%esp # depiler
halt
swap: mrmovl 4(%esp),%eax # param pa=&a
mrmovl 8(%esp),%ebx # param pb=&b
mrmovl (%eax),%ecx # valeur a=*pa
mrmovl (%ebx),%edx # valeur b=*pb
rmmovl %ecx,(%ebx) # swap *pb = a
rmmovl %edx,(%eax) # swap *pa = b
ret
.pos 0x100
a: .long 1
b: .long 2
.pos 0x200
stack:
Attention, cette fonction ne respecte pas la convention //callee-saved// car elle utilise %ebx ! Deux solutions sont possibles :
1) sauvegarder / restaurer le registre %ebx dans la fonction pour respecter la convention (attention au décalage de la pile) :
swap: pushl %ebx
mrmovl 8(%esp),%eax # param pa=&a
mrmovl 12(%esp),%ebx # param pb=&b
mrmovl (%eax),%ecx # valeur a=*pa
mrmovl (%ebx),%edx # valeur b=*pb
rmmovl %ecx,(%ebx) # swap *pb = a
rmmovl %edx,(%eax) # swap *pa = b
popl %ebx
ret
2) essayer si possible de se limiter aux seuls registres %eax, %ecx et %edx en essayant de se passer de %ebx (ce qui impose de faire des va-et-vient avec la mémoire) :
swap: mrmovl 4(%esp),%eax # &a
mrmovl (%eax),%ecx # a (sauvegarde)
mrmovl 8(%esp),%edx # &b
mrmovl (%edx),%edx # b
rmmovl %edx,(%eax) # maj a
mrmovl 8(%esp),%edx # &b
rmmovl %ecx,(%edx) # maj b à partir sauvgarde
ret
==== Exercice sur les registres caller/callee save ====
Etant donné la fonction //square(x)// qui calcule le carré de //x// et en vous inspirant de la fonction //sum(n,t)// qui calcule la somme des //n// éléments d'un tableau //t//, il faut écrire une fonction //sum2(n,t)// qui calcule la somme du carré des éléments du tableau. Attention à bien respecter les conventions de registres //caller/callee-save// !
.pos 0
irmovl stack,%esp # initialisation pile
jmp main # appel main()
square: mrmovl 4(%esp),%edx # param x
rrmovl %edx,%ecx # compteur n = x
xorl %eax,%eax # res = 0
loopsq: isubl 1,%ecx # n--
jl endsq # repeter n fois
addl %edx,%eax # res += x
jmp loopsq
endsq: ret # retour dans %eax
sum: mrmovl 4(%esp),%ecx # param n
mrmovl 8(%esp),%edx # param t
irmovl 0,%eax # res = 0
loop: isubl 1,%ecx # n--
jl end # fin si n < 0
mrmovl (%edx),%ebx # x=*t
addl %ebx,%eax # res += x
iaddl 4,%edx # t += 4
jmp loop
end: ret # retour dans %eax
main: xorl %eax,%eax # %eax = 0
rmmovl %eax,res # init de res
irmovl t,%eax # empiler n et t
pushl %eax
mrmovl n,%eax
pushl %eax
call sum # appel sum(n,t)
iaddl 8,%esp # depiler n et t
rmmovl %eax,res # mise à jour de res
halt
.pos 0x200
res: .long 0
t: .long 1
.long 2
.long 3
.long 4
n: .long 4
.pos 0x300
stack:
Dans le code ci-dessus, il faut noter que la fonction //square()// respecte la convention en utilisant que les registres //caller-save//, c'est-à-dire %eax, %ecx et %edx. Pas de problème donc !
Voici une première solution pour la fonction //sum2()//. Le resultat attendu dans la variable //res// est 0x1E.
sum2: mrmovl 4(%esp),%ecx # param n
mrmovl 8(%esp),%edx # param t
pushl %ebx # registre callee-save
irmovl 0,%eax # res = 0
loop2: isubl 1,%ecx # n--
jl end2 # fin si n < 0
mrmovl (%edx),%ebx # x=*t
pushl %eax # registre caller-save
pushl %ecx # registre caller-save
pushl %edx # registre caller-save
pushl %ebx # empiler x
call square # square(x)
iaddl 4,%esp # depiler x
rrmovl %eax,%ebx # recuperation retour x^2
popl %edx # registre caller-save
popl %ecx # registre caller-save
popl %eax # registre caller-save
addl %ebx,%eax # res += x^2
iaddl 4,%edx # t += 4
jmp loop2
end2: popl %ebx # registre callee-save
ret # retour dans %eax
Ici, la fonction //sum2()// qui est l'appelant de //square()// doit préalablement sauvegarder/restaurer les registres //caller-save// (%eax, %ecd, %edx) qui sont effectivement utilisés dans //square()// ! Notez par ailleurs que la fonction //sum2()// en tant que fonction appelé par //main()// se doit de sauvegarder/restaurer le registre %ebx qui est //callee-save//.
Une autre stratégie pour coder la fonction //sum2()// consiste à utiliser des registres //callee-save// (%esi, %edi, %ebx) : on sauvegarde ces registres en entrant dans la fonction, puis on les restaure en sortant. Attention néanmoins à la récupération des paramètres qui sont décalés sur la pile !
sum2: pushl %esi # registre callee-save
pushl %edi # registre callee-save
pushl %ebx # registre callee-save
mrmovl 16(%esp),%esi # param n
mrmovl 20(%esp),%edi # param t
irmovl 0,%ebx # res = 0
loop2: isubl 1,%esi # n--
jl end2 # fin si n < 0
mrmovl (%edi),%eax # x=*t
pushl %eax # empiler x
call square # square(x)
iaddl 4,%esp # depiler x
addl %eax,%ebx # res += x^2
iaddl 4,%edi # t += 4
jmp loop2
end2: rrmovl %ebx,%eax
popl %ebx # registre callee-save
popl %edi # registre callee-save
popl %esi # registre callee-save
ret # retour dans %eax
Cette dernière solution est plus efficace, car il n'y a pas d'instructions //pushl// dans la boucle //loop2//.
==== Appel récursif de fonction ====
f(n) { if(n == 0) return 0 ; else return (f(n-1)+n) ; }
main() { res = f(10); }
.pos 0
main: irmovl stack,%esp
mrmovl n,%eax
pushl %eax # empiler param n
call f
iaddl 4,%esp # depiler param
rmmovl %eax,res # resultat dans %eax
halt
f: mrmovl 4(%esp),%ecx # param n
andl %ecx,%ecx # eval condition code
je f0 # si n = 0 ?
fn: isubl 1,%ecx # n-1
pushl %ecx # empiler param n-1
call f # retour dans %eax
iaddl 4,%esp # depiler param
mrmovl 4(%esp),%ecx # restore param n
addl %ecx,%eax # retour dans %eax = n + f(n-1)
ret
f0: irmovl 0,%eax
ret # valeur de retour dans %eax
end: halt
.pos 0x100
n: .long 10
res: .long 0 # res = 55 = 0x37
.pos 0x200
stack:
==== Structure Liste Chaînée ====
struct list {
long x;
struct list * next;
};
long length(struct list * l) {
long n = 0;
while(l) { n++; l = l->next; }
return n;
}
main: .pos 0
irmovl stack,%esp
irmovl l1,%eax
pushl %eax
call length # retour dans %eax
iaddl 4,%esp
halt
length: mrmovl 4(%esp),%esi # param l
xorl %eax,%eax # n = 0
loop: andl %esi,%esi # test si l est NULL ?
je end
iaddl 1,%eax # n++
mrmovl 4(%esi),%esi # l = l->next
jmp loop
end: ret # retour n dans eax
.pos 0x100 # linked list
l1: .long 1
.long l2 # next = l2
l2: .long 2
.long l3 # next = l1
l3: .long 3
.long 0 # next = NULL
.pos 0x200
stack:
==== En vrac ====
.pos 0
irmovl stack, %esp
jmp main
# f(long *x, long y)
f:
mrmovl 4(%esp),%eax # x
mrmovl 8(%esp),%ecx # y
rmmovl %ecx,(%eax) # *x = y
ret
# main
main:
mrmovl u, %eax
pushl %eax # empiler 2eme arg (u)
irmovl t, %eax
pushl %eax # empiler 1er arg (&t)
call f
iaddl 8,%esp # depiler les args
halt
.pos 0x100
t: .long 0
u: .long 2
.pos 0x200
stack:
.pos 0
irmovl stack, %esp
jmp main
# f(long n, long * t)
f:
mrmovl 4(%esp),%ecx # n
mrmovl 8(%esp),%eax # t
loop:
isubl 1, %ecx
jl end
mrmovl (%eax),%edx # load *t
iaddl 1, %edx # inc
rmmovl %edx, (%eax) # store *t
iaddl 4,%eax # t++
jmp loop
end:
ret
# main
main:
irmovl t, %eax
pushl %eax # empiler 2eme arg (adresse t)
mrmovl n, %eax
pushl %eax # empiler 1er arg (valeur n)
call f
iaddl 8,%esp # depiler les args
halt
.pos 0x100
n: .long 4
t:
.long 1
.long 2
.long 3
.long 4
.pos 0x200
stack:
.pos 0
irmovl stack, %esp
jmp main
# sommme(long n, long v[0], long v[1], ...)
f:
pushl %ebx # save callee-saved registry
xorl %eax,%eax # sum = 0
mrmovl 8(%esp),%ecx # n
rrmovl %esp,%ebx
iaddl 12, %ebx # v
loop:
isubl 1, %ecx
jl end
mrmovl (%ebx),%edx # load *v
addl %edx,%eax # sum += *v
rmmovl %edx, (%ebx) # store *v
iaddl 4,%ebx # v++
jmp loop
end:
popl %ebx # restore callee-saved registry
ret # %eax
# main
main:
irmovl 3, %eax
pushl %eax # empiler v2
irmovl 2, %eax
pushl %eax # empiler v1
irmovl 1, %eax
pushl %eax # empiler v0
irmovl 3, %eax
pushl %eax # empiler n
call f
iaddl 16,%esp # depiler les args
halt
.pos 0x100
n: .long 4
.pos 0x200
stack: