Mise en pile
(suite de l'examen de compilation)

20 mars 2000

Si vous êtes curieux

Ces questions ne faisaient pas partie de l'examen, mais en sont une suite naturelle. On reprend les notations et les définitions du sujet de l'examen.

7	Lectures superflues

On considère le code D suivant:

add t, $a0, 1 jal foo add $v0, t, $v0 add $v0, t, $v0

où le registre v0 est vivant en sortie.

7.1 Donner le code après mise en pile j ^¥(D) (i.e., déduit du coloriage de j ^#(D)) : on donnera d'abord le code avant application du coloriage puis le code final colorié.

Réponse La transformation automatique introduit ici deux temporaire q1 et q2 écrit avant l'appel à la fonction foo et lus tous deux après: ils devront donc être mise en pile. On obtient, après mise en pile:

add p1, $a0, 1 add $t0, $a0, 1 sw p1, 0($sp) sw $t0, 0($sp) jal foo jal foo lw r1, 0($sp) lw $t0, 0($sp) add $v0, r1, $v0 add $v0, $t0, $v0 lw r2, 0($sp) lw $t0, 0($sp) add $v0, r2, $v0 add $v0, $t0, $v0

7.2 Peut-on, manuellement, obtenir un code meilleur ? (On décrira seulement le code final après mise en pile et application du coloriage).

Réponse Il suffit de retirer la dernière instruction sur dans le code précédent.

add $t0, $a0, 1 sw $t0, 0($sp) jal foo lw $t0, 0($sp) add $v0, $t0, $v0 add $v0, $t0, $v0

Évidemment, le move résultant sera à son tour éliminé par l'allocateur de registres.

7.3 On définit la transformation j ^*(A) comme la transformation j ^#(A) suivie du remplacement de chaque instruction move r_i, q_i par un multi-move (mmv (q_k)k Î I, k ¹ i r_i, q_i).

Décrire l'effet général de cette transformation. Vérifiez qu'elle traite correctement le cas ci-dessus.

Réponse Cette transformation met à jour à chaque lecture de q_i tous les autres q_k avec la dernière valeur lue. L'effet est de recourcir les durées de vie des temporaores q_i: la lecture de q_i ne dépend plus de la dernière écriture de t, mais de la dernière lecture ou écriture de t.

Dans l'exemple précédent, on obtient avant allocation de registres (à droite après élimination des move inutiles):

1: add p1, $a0, 1 add p1, $a0, 1 2: mmv q1 q2, p1 mmv q1, p1 3: jal foo jal foo 4: mmv q2 r1, q1 mmv q2 r1, q1 5: add $v0, r1, $v0 add $v0, r1, $v0 6: mmv q1 r2, q2 mmv r2, q2 7: add $v0, r2, $v0 add $v0, r2, $v0

Ainsi, il n'y a plus besoin de placer q2 en pile car sa durée de vie ne contient plus l'appel à foo. En appliquant le coloriage sur la partie droite, on retrouve le code obtenu manuellement ci-dessus.

8	Effet pervers

La transformation précédente permet de réduire le nombre de sites mis en pile, en raccourcissant la longueur des interférences. Cependant, en retardant la mise en pile le plus tard possible, elle a aussi des effets secondaires.

8.1 Donner un exemple où la transformation entraîne une sauvegarde en pile alors que l'instruction correspondante du code d'origine ne faisait que lire t. (On donnera le code d'origine et le code final après la mise en pile et application du coloriage).

Réponse

1: add t, $a0, 1 add $t0, $a0, 1 2: add $s0, t, 1 add $s0, $t0, 1 sw $t0, 0($sp) 3: jal foo jal foo lw $t0, 0($sp) 4: add $v0, t, $v0 add $v0, $t0, $v0

8.2 En déduire (en utilisant une boucle) un cas, où la transformation conduit finalement à un résultat moins bon que j ^#(A).

Réponse Il suffit d'ajouter une itération du bloc de code 2-4. On donner, de gauche à droite, le code d'origine, le code j ^*(A) et le code j ^#(A), ces deux derniers après mise en pile.

1: add t, $a0, 1 add $t0, $a0, 1 add $t0, $a0, 1 sw $t0, 0($sp) 2: add $s0, t, 1 add $s0, $t0, 1 add $s0, $t0, 1 sw $t0, 0($sp) 3: jal foo jal foo jal foo lw $t0, 0($sp) lw $t0, 0($sp) 4: add $v0, t, $v0 add $v0, $t0, $v0 add $v0, $t0, $v0 5: bltz $v0, 3 bltz $v0, 3 bltz $v0, 3

La sauvegarde est effectuée à chaque boucle dans le code j ^*(A), alors qu'elle n'est effectuée qu'une seule fois en dehors de la boucle dans j⁺⁺(A).

9	Une solution conservatrice

On effectue toujours l'allocation de registres pour le code j ^*(A), ce qui fournit un coloriage q et une partition des temporaires Q = {q_i, i Î I} en deux ensembles R et S, les premiers étant coloriables alors que les seconds ne le sont pas et devront être mis en pile. Afin de corriger l'effet pervers précédent, on change la procédure de mise en pile: on décide de sauvegarder p_j en pile après change instruction j, maintenant ainsi la pile à la valeur de t avant tansformation, ce qui permet de ne plus jamais sauver r_i en pile.

Donner un exemple où cette transformation est moins bonne que j ^#(A).

Réponse C'est l'exemple C de l'examen. La nouvelle transformation va effectuer deux sauvergardes en pile (comme la procédure de mise en pile du cours), autant que d'instruction j Î J. Ici, le code j ^#(A) permettait de ne faire qu'une seule sauvegarde en pile.

10	La solution, enfin

10.1   Montrer que les sauvegardes en pile superflues peuvent facilement être éliminées par une analyse de durée de vie...sur l'emplacement en pile.

Réponse   On peut trace les lectures et les écritures en pile (dans l'emplacement réservé pour t) on le fait pour un temporaire. Une écriture en pile est inutile si dans toute trace d'exécution elle n'est jamais suivie directement d'une lecture en pile. Cela revient à l'élimination des moves superflues.

10.2   Comment la mettre en oeuvre simplement?

Réponse   Dans un premier temps on remplace les opérations en pile par des moves de ou vers un temporaire s représentant l'emplacement en pile. On fait l'analyse de durée de vie, puis on élimine parmi ces moves, ceux qui sont inutiles, ie. les moves vers s lorsque s n'est pas vivant en sortie.

10.3   Décrire comment à partir de j ^*(A), du coloriage q et de la partition R S de Q obtenu par l'allocation de registres de j ^*(A), on obtient le code final (que l'on note j ^¥(A)).

Réponse   Si S est non vide, on introduit un temporaire s pour représenter l'emplacement en pile et on appelle A₁ le code obtenu en remplaçant dans j ^*(A):

chaque multimove move K_j, p_j issu d'une lecture par move s, p_i suivi de move K_j Ç R, p_i
chaque multimove move r_i K_i, q_i issu d'une écriture par
- move r_i, s suivi de move K_i Ç R, r_i si q_i Î S et
- move r_i K_i Ç R, q_i sinon.
On effectue l'analyse de durée de vie (du registre s) sur le code A₁. On appelle A₂ le code obtenu en éliminant dans A₁ les moves superflus (de ou vers s).
On appelle A₃ le code obtenu en remplaçant dans A₂ les move de ou vers s restant par des lecture ou des écriture en pile.

On applique le coloriage et la coalescence définis par le coloriage q (sans refaire de calcul) au code A₃, ou à j ^*(A) si S est vide. On obtient le code final j ^¥(A).

This document was translated from L^AT_EX by H^EV^EA.