Réponses intégrées ou à la demande

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 riqi par un multi-move (mmv (qk)k Î I, k ¹ i riqi).

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 = {qi, 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 pj 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 ri 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 LATEX by HEVEA and HACHA.