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

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

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

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

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

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

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

10.2   Comment la mettre en oeuvre simplement?

Réponse

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

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