Examen de majeure 2
Compilation
(Durée 2h)

20 mars 2000

On attachera une importance particulière à la clarté, à la précision, mais aussi à la concision de la rédaction. Les questions 1 et 4 sont indépendantes, ainsi que certaines sous-questions d'autres parties.

Mise en pile

Dans le cours, nous avons apporté un soin particulier à l'allocation de registres de façon à éviter au maximum les mises en pile et à éliminer le plus possible d'instructions move. Cependant, dans le cas d'une mise en pile, nous avons fait le choix délibéré de la simplicité, parfois au détriment de la qualité (rapidité d'exécution) du code produit. On cherche ici à améliorer le résultat de la mise en pile.

1	De bons exemples

On considère la fonction suivante d'un programme Pseudo-Pascal:

function sum (var n : integer) : integer; begin if n > 0 then sum := n + sum (n-1) else sum := 0 end;

1.1   Donner un code Spim possible, tel que pourrait le retourner le compilateur du cours (en particulier, on n'effectuera pas de transformation de programme avancée, telle que l'élimination de la récursion).

Réponse

1.2   Donner un argument prouvant que la mise en pile est inévitable dans la compilation du programme ci-dessus (on s'interdit toujours des transformations de programme avancées), quelque soit la qualité de l'allocateur de registres et le nombre de registres disponibles.

Réponse

1.3   La mise en pile est-elle satisfaisante dans l'exemple ci-dessus?

Réponse

1.4   En induire un cas, assez fréquent, de mise en pile bien traité par la solution simple du cours.

Réponse

2	Des insuffisances

Dans toute la suite du problème, on utilise les notations et restrictions suivantes. On suppose qu'il n'existe que trois registres machine $a0, $v0 et $t0 qui sont aussi des temporaires particuliers, pré-coloriés (on réserve le préfixe $ aux registres machine). Pour simplifier, on traite les registres spéciaux ($sp, $ra et $zero) à part: on ne les considérera pas comme des temporaires et on les exclut de toutes les phases d'analyse (durée de vie, interférence, allocation de registres).

On note G(A) le graphe d'interférence associé au code assembleur A et j(A) le code produit par la mise en pile d'un seul temporaire t dans le code A en utilisant la procédure du cours (le temporaire t est toujours le même et laissé implicite).

2.1 On considère comme exemple le code C suivant:

1: add t, $a0, 1 2: add t, t, $a0 3: add $a0, t, t 4: jal foo 5: add $v0, t, $v0

où la fonction foo lit $a0, écrase les trois registres machines et retourne son résultat dans v0. On suppose que le registre $v0 est vivant à la fin du code C. Donner le code j(C).

Réponse

2.2   Donner au moins une raison pour laquelle le code j(C) n'est pas bon.

Réponse

2.3   Donner un code de mise en pile meilleure que j(C), obtenu manuellement, en utilisant au mieux les registres disponibles (on donnera le code final, après allocation des registres).

Réponse

3	Approche mécanique

On note j⁺(A) le programme A transformé par la procédure suivante:

On donne un numéro i Î I à chaque instruction qui lit le temporaire t et un numéro j Î J à chaque instruction qui écrit le temporaire t (une instruction peut avoir à la fois un numéro i Î I et un numéro j Î J si t y est utilisé à la fois en lecture et en écriture.)
On se donne des nouveaux temporaires q_i^{i Î I} et p_j^{j Î J}.
On remplace dans chaque instruction i Î I toutes les occurrences de t en lecture par q_i.
On remplace chaque instruction j Î J par la séquence d'instructions composée, dans l'ordre:
1. de l'instruction j dans laquelle toutes les occurrences en écriture de t sont remplacées par p_j,
2. des instructions (move q_i, p_j)^{i Î I} (on rappelle que move u, v copie v dans u).

3.1   Donner, très soigneusement, le code j⁺(C).

Réponse

3.2   Montrer, dans le cas général, que la transformation de A en j⁺(A) est correcte, c'est-à-dire que les deux codes assembleurs sont équivalents (pour une machine qui préserverait la valeur des temporaires à chaque appel de fonction).

Réponse

3.3   Donner, soigneusement, pour chaque instruction de j⁺(C) la liste des temporaires vivants en sortie (on ne demande pas le détail du calcul, mais seulement le résultat).

Réponse

3.4   En déduire immédiatement (donc sans faire d'allocation de registres) que l'on peut supprimer certaines instructions move.

Réponse

3.5   Donner le code résultant que l'on notera C'.

Réponse

4	Interférences parasites

On s'intéresse maintenant au bloc de code B suivant:

add p2, q1, $a0 move q2, p2 move q3, p2

On suppose que les registres q2 et q3 sont les seuls vivants en sortie du bloc. Donner pour chaque instruction les registres vivants en sortie. Donner le graphe d'interférence (sans justification).

Réponse

4.1   Exhiber un arc superflu. En quoi est-ce gênant?

Réponse

4.2

On regroupe les deux instructions move q2, p2 et move q3, p2 ensemble en une macro-instruction mmv q2 q3, p2 (lire ``multi-move'') qui lit p1 et écrit q2 et q3.

Que devient le graphe d'interférence si le multi-move est traité comme une instruction de calcul ordinaire (noeud Oper dans le cours)?

Réponse

4.3   On traite le multi-move comme une forme généralisée de move: l'instruction mmv d₁ ... d_n, s copie le temporaire s dans les temporaires (d_k)^{k Î 1..n}.

Décrire les interférences minimales crées par une instruction mmv d₁ ... d_n, s en fonction de l'ensemble dest des temporaires (d_k)^{k
Î 1..n}, de s et de l'ensemble out des temporaires vivants en sortie de cette instruction.

Réponse

4.4   Donner le graphe d'interférence G(B) en considérant les deux moves successifs comme un multi-move.

Réponse

5	Exemple à suivre

Dans la suite, on note j⁺⁺(A) le code assembleur obtenu à partir de j⁺(A) en remplaçant les séquences de move introduites par des instructions mmv, puis en simplifiant ces instructions après l'analyse de durée de vie (en retirant certaines destinations, donc certains move) comme indiqué à la question 3.4.

5.1   Retrouver les temporaires vivants à la sortie de chaque instruction du code j⁺⁺(C) (en réutilisant simplement les réponses aux questions 3.3 et 3.5). En déduire G(j⁺⁺(C)).

Réponse

5.2   Donner un résultat possible pour l'allocateur de registres, en tenant compte des contraintes d'interférence, et si possible des préférences (arcs ``move''): on indiquera dans une table pour chaque temporaire le registre-machine associé ou bien le temporaire lui-même s'il doit être mis en pile.

Réponse

5.3   Donner le code résultant après expansion des instructions mmv et simplification des instructions move devenues inutiles par la fusion de leur source et de leur destination.

Réponse

6	Retour au cas général

On reprend le cas général d'un code A, coloriable à l'exception d'un seul temporaire t qu'il faut placer en pile.

6.1   Montrer que le graph G(j⁺⁺(A)) est coloriable à l'exception peut-être de certains noeuds parmi q_i^{i Î I} et p_j^{j Î J}.

Réponse

6.2   Peut-on être plus précis si l'on sait que G(j(A)) est coloriable (on ne fera pas de preuve)?

Réponse

6.3   On définit j ^#(A) à partir de j⁺⁺(A) en remplaçant chaque instruction i par l'instruction move r_i, q_i suivie de l'instruction i dans laquelle q_i est remplacé par r_i où r_i est un nouveau temporaire. Quel est l'intérêt de colorier G(j ^#(A)) plutôt que G(j⁺⁺(A)) ? En déduire, dans certains cas, une forme définitive, j ^¥(A), du code.

Réponse

6.4   (facultative) Quand le graphe n'est pas coloriable, il existe, en général plusieurs coloriages partiels possibles. Comment peut-on guider l'algorithme de coloriage du cours pour qu'il aboutisse, autant que possible, vers une forme permettant d'obtenir le code définitif j ^¥(A) à partir du coloriage de G(j ^#(A))?

Réponse

Pour en savoir plus

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