Table of Contents
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 : 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 :
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:
- ifthen.ys
.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 :
- ifthenelse.ys
.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;
- sum.ys
.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
- sum2.ys
.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];
- decalage.ys
.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);
- function.ys
.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 !
- funcloc.ys
.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.
- swap.ys
.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) :
- swap1.ys
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) :
- swap2.ys
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 !
- sumsquare-exo.ys
.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.
- sumsquare.ys
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 !
- sumsquare-v2.ys
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); }
- recursif.ys
.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; }
- linkedlist.ys
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
- td04_exo1.ys
.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:
- td04_exo2.ys
.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:
- td04_exo3.ys
.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: