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.

  1. Vu le choix des adresses pour u, v, f combien d'entiers peut-on ranger dans les tableaux u et v ?
  2. 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).
  3. Combien de pointeurs faut-il incrémenter à chaque tour de boucle ?
  4. 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.

  1. Quels sont les paramètres de la fonction fusion ?
  2. Ecrire les instructions qui permettent d'appeler la fonction avec les bons arguments.
  3. 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.
  4. 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.

  1. 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.
  2. En fait on peut se passer des compteurs de la question précédente : expliquer comment utiliser plus efficacement les deux variables locales.
  3. Que reste-t-il à faire pour achever la fusion des deux tableaux ? Remarque : on ne demande pas le code, ce serait lassant.
  4. 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.