Fusion de tableaux
Squelette
# Fusion, boucle infinie
irmovl u, %ebx # pointeur pu
mrmovl (%ebx), %eax
irmovl v, %esi # pointeur pv
mrmovl (%esi), %ecx
irmovl f, %edi # pointeur pf
addl %eax, %ecx
rmmovl %ecx, (%edi) # taille f
irmovl 4, %edx
addl %edx, %ebx # pu++
addl %edx, %esi # pv++
mrmovl (%ebx), %eax # x
mrmovl (%esi), %ecx # y
boucle: # à compléter
# .......
# .......
.pos 0x200
u: .long 10
.long 1
.long 1
.long 2
.long 3
.long 5
.long 8
.long 13
.long 21
.long 34
.long 55
.pos 0x240
v: .long 7
.long 1
.long 2
.long 4
.long 8
.long 16
.long 32
.long 64
.pos 0x280
f:
Voici ci-contre le début d'un programme qui fusionne deux tableaux
triés u et v dans un tableau f ;
le premier élément de chaque tableau indique sa taille.
- Vu le choix des adresses pour u, v, f
combien d'entiers peut-on ranger dans les tableaux u
et v ?
- On considère d'abord le cas d'une boucle infinie,
c'est-à-dire sans test d'arrêt.
Combien d'accès à la mémoire sont-ils nécessaires
à chaque tour de boucle ?
Distinguer les accès mémoire en lecture
(instruction mrmovl)
et en écriture
(instruction rmmovl).
- Combien de pointeurs faut-il incrémenter à chaque
tour de boucle ?
- Ecrire le code de la boucle de la façon la plus courte
et efficace possible. Compter le nombre d'instructions
exécutées à chaque tour de boucle
— il existe une solution où la réponse est 9.
On souhaite maintenant transformer ce code en un code
de fonction, qu'on appellera avec l'instruction
call fusion.
- Quels sont les paramètres de la fonction
fusion ?
- Ecrire les instructions qui permettent d'appeler
la fonction avec les bons arguments.
- Ajouter au début et à la fin
du code ci-contre les instructions
qui permettent de gérer
le cadre (frame) associé à cette fonction
— on réservera de la place pour deux variables locales.
- Quelles sont les instructions à modifier ?
Compteurs
irmovl 0x400, %esp
irmovl f, %eax
pushl %eax
irmovl v, %eax
pushl %eax
irmovl u, %eax
pushl %eax
call fusion
halt
fusion: pushl %ebp
rrmovl %esp, %ebp
irmovl 8, %edx
subl %edx, %esp # 2 variables locales
mrmovl 8(%ebp), %ebx # pointeur pu
mrmovl (%ebx), %eax
mrmovl 12(%ebp), %esi # pointeur pv
mrmovl (%esi), %ecx
mrmovl 16(%ebp), %edi # pointeur pf
addl %eax, %ecx
rmmovl %ecx, (%edi) # taille f
irmovl 4, %edx
addl %edx, %ebx # pu++
addl %edx, %esi # pv++
mrmovl (%ebx), %eax # x
mrmovl (%esi), %ecx # y
boucle: addl %edx, %edi # pf++
rrmovl %eax, %edx
subl %ecx, %edx # x - y
irmovl 4, %edx
jg ymov
rmmovl %eax, (%edi) # x -> f
addl %edx, %ebx # pu++
mrmovl (%ebx), %eax # x suivant
jmp boucle
ymov: rmmovl %ecx, (%edi) # y -> f
addl %edx, %esi # pv++
mrmovl (%esi), %ecx # y suivant
jmp boucle
fin: rrmovl %ebp, %esp
popl %ebp
ret
Le programme ci-contre est un corrigé de la page précédente.
- Compléter ce code pour que la fonction
fusion se termine lorsqu'on a parcouru
entièrement l'un des deux tableaux.
Conseil : placer des compteurs dans les deux variables locales.
- En fait on peut se passer des compteurs de la question précédente :
expliquer comment utiliser plus efficacement les deux variables locales.
- Que reste-t-il à faire pour achever la fusion des deux tableaux ?
Remarque : on ne demande pas le code, ce serait lassant.
- Ecrire une fonction C fusion
avec les mêmes paramètres et les mêmes conventions
(le premier élément d'un tableau contient sa taille)
et comparer le code produit par gcc avec celui
fourni en réponse aux questions précédentes.
Note : lorsqu'un des tableaux est épuisé, appeler
une petite fonction de copie d'un tableau dans un autre
— le code optimisé produit par gcc est intéressant.
Corrigé
fusion: pushl %ebp
rrmovl %esp, %ebp
irmovl 8, %edx
subl %edx, %esp # 2 variables locales
mrmovl 8(%ebp), %ebx # pointeur pu
mrmovl (%ebx), %eax
rmmovl %eax, -4(%ebp) # compteur cu
mrmovl 12(%ebp), %esi # pointeur pv
mrmovl (%esi), %ecx
rmmovl %ecx, -8(%ebp) # compteur cv
mrmovl 16(%ebp), %edi # pointeur pf
addl %eax, %ecx
rmmovl %ecx, (%edi) # taille f
irmovl 4, %edx
addl %edx, %ebx # pu++
addl %edx, %esi # pv++
mrmovl (%ebx), %eax # x
mrmovl (%esi), %ecx # y
boucle: addl %edx, %edi # pf++
rrmovl %eax, %edx
subl %ecx, %edx # x - y
irmovl 4, %edx
jg ymov
rmmovl %eax, (%edi) # x -> f
addl %edx, %ebx # pu++
mrmovl -4(%ebp), %eax # compteur cu
irmovl 1, %edx
subl %edx, %eax # cu--
je fin
rmmovl %eax, -4(%ebp)
irmovl 4, %edx
mrmovl (%ebx), %eax # x suivant
jmp boucle
ymov: rmmovl %ecx, (%edi) # y -> f
addl %edx, %esi # pv++
mrmovl -8(%ebp), %ecx # compteur cv
irmovl 1, %edx
subl %edx, %ecx # cv--
je fin
rmmovl %ecx, -8(%ebp)
irmovl 4, %edx
mrmovl (%esi), %ecx # y suivant
jmp boucle
fin: rrmovl %ebp, %esp
popl %ebp
ret
Remarque :
les lignes
irmovl 1, %edx et
irmovl 4, %edx
sont des lignes parasites car dans un vrai processeur
on dispose d'instructions
inc et dec
pour incrémenter ou décrémenter un registre.
Utiliser les variables locales comme compteurs a pour inconvénient
de demander une écriture en mémoire chaque fois que le compteur est
décrémenté. Une autre solution est de calculer et d'enregistrer
une fois pour toutes dans ces variables locales
les adresses de fin des tableaux u et v :
chaque fois qu'on incrémente l'un des pointeurs
pu ou pv on le compare alors à l'une de ces variables
pour savoir si le tableau correspondant est épuisé.
Pour terminer le programme il faudrait remplacer les sauts
je fin
par deux sauts distincts vers des fragments de code
qui achèvent de copier
les éléments restants de l'autre tableau
(celui qui n'est pas épuisé)
dans le tableau f, ce n'est pas difficile.