Analyse de durée de vie.

Cours (super, self)	Exercises
Définitions Algorithme Mise en oeuvre Graphe d'interference	Travaux dirigés

La chaîne de compilation

Sa place dans la chaîne de compilation

Calculer pour chaque instruction la liste des temporaires vivants à la fin de l'instruction:

Þ	Les temporaires vivant simultanément ne peuvent pas être identifiés. En particulier, ils ne peuvent pas utiliser le même registre.
Þ	Les autres peuvent partager le même registre.

L'analyse de la durée se retrouve sous d'autres formes (analyse de flow) en aval pour faire des optimisations plus poussées.

Le problème

Chaque instruction

·	utilise (lit) un ensemble de temporaires, calcule et
·	définit (écrit) un ensemble de temporaires.

Les deux ensembles ne sont pas nécessairement disjoints.

Un temporaire est vivant à la sortie d'une instruction i si sa valeur est utilisée dans une instruction suivante (au sens large) avant d'être redéfinie. La durée de vie d'un temporaire est l'ensemble des instructions où il est vivant.

Lorsqu'un temporaire est mort, sa valeur n'a pas d'importance. Deux temporaires qui ont des durées de vie disjointes peuvent être superposés et utiliser le même registre.

Le calcul de la durée de vie est un préliminaire à l'allocation de registres.

Exemples

z ¬ x + y utilise les variables x, y et définit z.

Analogie temporaire ¬¾® variable globale

Groupements On peut traiter un groupe d'instructions linéaires (sans saut ni entrée), en particulier un bloc élémentaire, comme une ``macro-instuction'':

z ¬ x + y

t ¬ z

utilise x, y

définit z, t

Important: la valeur locale de z est utilisée dans le bloc, mais pas sa valeur à l'entrée du bloc! Donc z n'est pas lu par le bloc.

L'instruction call se comporte comme une instruction qui

·	lit a0, a1, etc. (selon le nombre d'arguments).
·	écrit ra, les registres spéciaux, les registres t, v, et a.

Le graphe d'un programme

Un programme peut être vu comme un graphe dont les noeuds sont les instructions et les arcs décrivent la possibilité de passer d'une instruction à une autre et sont étiquetés par des conditions (mutuellement exclusives ---déterminées à l'évaluation).

L'exécution du programme évalue une instruction puis passe à l'instruction suivante autorisée (satisfaisant la condition de saut).

Les conditions de branchement sont des conditions dynamiques. Elles peuvent dépendent d'un calcul arbitrairement complexe. Elles ne sont donc pas décidables.

Approximation On ne peut calculer qu'une approximation de la durée de vie. (On la choisira par excès pour être correct.)

On majore grossièrement les conditions de saut en les supposant toujours vraies (elles ne sont plus disjointes).

Un (sous) programme

Définition de la durée de vie

Pour chaque instruction i, on définit

·	`Use` (i) l'ensemble des temporaires utilisés par i
·	`Def` (i) l'ensemble des temporaires définis par i
·	`Out` (i) l'ensemble des temporaires vivants à la sortie de i
·	`Succ` (i) l'ensemble des successeurs immédiats de i

Par définition, t Î Out (i) si et seulement si il existe un chemin à partir de i pour lequel t sera lu avant d'être écrit:

$ i₁ Î Succ (i), ... i_n+1 Î Succ (i_n), Ù

ì
í
î

t Î Use (i_n+1)

" k Î [1, n], t Ï Def (i_k)

Calcul de la durée de vie

On définit

·	`Succ` ^k (i) comme l'ensemble des séquences de k-instructions consécutives à i.
·	p^¬ la séquence p privée de la dernière instruction,
·	p la dernière instruction de p.

On peut réécrire Out (i) comme

n Î IN^*

p Î Succ ⁿ (i)

ì
ï
í
ï
î

t Î Use ( p)

" j Î

, t Ï Def (j)

(En fait on peut ajouter le cas n=0 en considérant que Succ ⁰(i) est vide.)

Temporaires vivant en entrée

Out

ⁿ(i) =^def

k = 1

p Î Succ ^k (i)

ì
ï
í
ï
î

t Î Use ( p)

" j Î

, t Ï Def (j)

peut s'écrire

i' Î Succ i

æ
ç
ç
ç
è

n-1

k = 0

p Î Succ ^k (i')

ì
ï
í
ï
î

t Î Use ( p)

" j Î

i'p

, t Ï Def (j)

ö
÷
÷
÷
ø

=^def In ^n-1(i')

Soit

In

ⁿ(i) =

Use (i)

k = 0

k = 1

p Î Succ ^k (i)

ì
ï
ï
í
ï
ï
î

t Î Use ( p)

" j Î

, t Ï Def (j)

t Ï Def (i)

_{Out ⁿ (i) \ Def (i)}

Algorithme

On a Out (i) = È_{n Î IN} Out ⁿ (i) où

ì
ï
í
ï
î

Out

ⁿ (i) =

i' Î Succ (i)

In ^n-1(i)

In ⁿ (i) = Use (i) È (Out ⁿ(i) \ Def (i))

ì
í
î

In ⁰ (i) = Ø

Out ⁰ (i) = Ø

Les suites In ^k et Out ^k sont croissantes et bornées (par l'ensemble de tous les temporaires), donc elles convergent. Ainsi, elles sont constantes à partir d'un certain rang.

Algorithme On calcule les fonctions (Out ⁿ, In ⁿ) pour n croissant tant que Out ⁿ est différent de Out ^n-1 (ie. tant qu'il existe i tel que Out ⁿ(i) est différent de Out ^n-1(i))

Complexité en O(n⁴): au plus n² itérations sur O(n) instructions coûtant O(n) par instruction.

Équations au point fixe

Lorsque le point fixe est atteint:

ì
ï
í
ï
î

Out

(i) =

i' Î Succ i

In (i')

In (i) = Use (i) È (Out (i) \ Def (i))

Résultat: Un temporaire est vivant à l'entrée de i s'il est lu par i ou s'il est vivant en sortie de i et n'est pas écrit par i.

L'algorithme précédent calcule le plus petit point fixe de ces équations.

Il existe aussi un plus grand point fixe, que l'on peut calculer en partant des ensembles pleins. Plus grand et plus petit point fixes ne sont pas égaux (considérer un temporaire jamais utilisé).

Le plus petit point fixe est bien celui que nous cherchions...

Accélération de la convergence

On peut remplacer In ^n-1 par In ⁿ dans le calcul Out ⁿ, lorsque que In ⁿ est déjà connu.

On a donc intérêt à calculer l'instruction Succ i avant l'instruction i.

Un tri topologique permettrait de traiter les composantes connexes les plus profondes en premier.

Comme la plupart des instructions sont simplement des sauts à l'instruction suivante, i.e. Succ (i) = { i+1 }, on obtient un bon comportement par un parcours du code en sens inverse.

En pratique, quelques itérations suffisent, et on obtient un comportement entre linéaire et quadratique en la taille du code.

On peut représenter les ensembles de temporaires par des listes ordonnées (union et différence en temps linéaire) ou par des vecteurs de bits.

Calcul sur les blocs de base

On peut faire une analyse en deux étapes:

On calcule Def (b) et Use (b) pour les blocs de base:

ì
ï
ï
í
ï
ï
î

Def (b) =

È

i Î b
Def (i)

Use (b) =

È

i Î b
æ
è Use (i) \ È

i' Î

*

Pred

(i) Ç b

Def (i') ö
ø

Puis les variables vivantes Out (b) à la sortie du bloc b comme précédemment.
On retrouve alors les Out (i) pour les instructions du bloc b par une simple passe linéaire en sens inverse sur le bloc.

La convergence est aussi rapide (même nombre d'itérations) à condition de faire un parcours arrière dans les deux cas, mais à chaque fois on considère un plus petit nombre de noeuds (donc d'opérations).

Calcul sur l'exemple

Données Calcul normal -accéléré

i

Def

Use

Succ

in₀

out₀

in₁

out₁

in₂

out₂

in₃

out₃

in₄

out₄

in₅

out₅

in'₀

out'₀

in'₁

out'₁

x,z

x,z,t

x,z

x,z,t

z,t

,z,t

4,1

x,z

x,z,t

x,z

x,z,t

x,z

x,z,t

x,z

,z,t

Out

(i) =

i' Î Succ i

In (i') et In (i) = Use (i) È (Out (i) \ Def (i))

Mise en oeuvre

Un noeud est une instruction annotée par les informations Def , Use et Succ ainsi que les champs mutables In et Out .

type flowinfo = { instr : Ass.instr; def : temp set; use : temp set; mutable live_in : temp set; mutable live_out : temp set; mutable succ : flowinfo list; }

On construit le graphe:

flowgraph : code -> flowinfo list;;

On itère le calcul jusqu'à ce que plus rien n'ai changé:

fixpoint : flowinfo list -> flowinfo list;;

(On peut facilement afficher la liste des temporaires vivants dans le code, en commentaire de chaque instruction.)

L'exemple du cours

[ Label ("L1", l1); Oper ("add___^d0,_^s0,_^s1", [x;z], [z], None); Move ("move__^d0,_^s0", z, t); Oper ("beq___^s0,_$zero", [t], [], Some [l1; l4]); Label ("L4", l4); Oper ("add___^d0,_^s0,_1", [z], [z], None); Oper ("jal___$ra", [], [], Some []); ] ;;

Résultat:

# Def <= Use # Out L1: add $z, $x, $z # z <= z x # z x move $t, $z # t <= z # z x t beq $t, $zero, L1 # <= t # z x L4: add $z, $z, 1 # z <= z # . jump Exit

fact: sub $sp, $sp, fact_f # sp <= sp # a0 s0 ra move $112, $ra # 112 <= ra # a0 s0 112 move $113, $s0 # 113 <= s0 # a0 112 113 move $108, $a0 # 108 <= a0 # 108 112 113 li $114, 1 # 114 <= # 108 112 113 114 bgt $108, $114, L9 # <= 108 114 # 108 112 113 li $115, 1 # 115 <= # 112 113 115 move $107, $115 # 107 <= 115 # 107 112 113L10: move $v0, $107 # v0 <= 107 # v0 112 113 move $s0, $113 # s0 <= 113 # v0 s0 112 move $ra, $112 # ra <= 112 # v0 s0 ra add $sp, $sp, fact_f # sp <= sp # v0 s0 ra j $ra # <= v0 s0 ra # L9: sub $116, $108, 1 # 116 <= 108 # 108 112 113 116 move $a0, $116 # a0 <= 116 # a0 108 112 113 jal fact # v0 a0 ra <= a0 # v0 108 112 113 move $109, $v0 # 109 <= v0 # 108 109 112 113 mul $117, $108, $109 # 117 <= 108 109 # 112 113 117 move $107, $117 # 107 <= 117 # 107 112 113 j L10 # <= # 107 112 113

Importance des annotations Use et Def

Noter l'effet des Use et Def dans

·	un appel de primitive,
·	un appel de fonction/procédure
·	au retour d'un programme.

En particulier, en rendant les registres spéciaux vivants à la fin d'une procédure, ils resteront vivants pendant toute la procédure puisqu'ils ne sont jamais écrits.

(Pour simplifier, les registres spéciaux n'ont pas été affichés dans l'exemple ci-dessus.)

Corriger, si nécessaire, ces annotations dans la génération de code

Autres analyses de flux

L'analyse de durée de vie est une analyse arrière: on a intérêt à aller en arrière (dans le sens du calcul) pour accélérer la convergence, parce que l'inforation se propage vers l'arrière.

La plupart des analyses de flux sont à l'inverse des analyses avant.

Analyse d'atteignabilité

On veut calculer l'ensemble des définitions qui sont vivantes à chaque point du programme (instruction ou bloc).

Application à la propagation de constantes

En amont (sur le code source) ou en aval (sur le code machine):

Si l'affectation d'une constante c à une variable globale (amont) ou à un temporaire t (aval) atteint un point p, alors on sait qu'à ce point on peut remplacer t par la constante c.

Analyse avant

L'information est en général déterminée comme le plus petit point fixe d'une équation de la forme:

ì
ï
í
ï
î

In

(i) =

i' Î Pred i

Out (i')

Out (i) = Gen (i) È (In (i) \ Kill (i))

Les fonctions Gen et Kill sont analogues à Use et Def :

·	`Gen` (i): l'ensemble des défintions générées par l'instruction i
·	`Kill` (i): l'ensemble des définitions détruites par i

Noter aussi l'inversion des ensembles In (i) et Out (i) dans les équations.

Graphe d'interférence

Les noeuds sont les temporaires et les arcs non orientés relient deux temporaires qui ne peuvent pas être superposés.

Cas général: Lorsqu'une instruction écrit dans un temporaire t, il n'est pas possible d'identifier t avec un autre temporaire qui survit après l'instruction.

Formellememt, on ajoute, pour chaque instruction i les arcs Def (i) × (Out (i) \ Def (i)).

Cas particulier des instructions Move: Comme à la sortie, la source et la destination ont le même contenu, il n'y a pas jamais interférence entre la source et la destination, même si la source survit à l'instruction. Au contraire, il est possible (et souhaitable) de pouvoir les identifier.

Formellement, on ajoute, pour chaque instruction move les arcs Def (i) × ((Out (i) \ Def (i)) \ Use (i)).

Élimination des instructions Move

Ces instructions ne calculent pas, et pourront être éliminées, si les temporaires source et destination sont superposés, ce que l'on cherche à faire. Donc, ces deux temporaires n'interfèrent pas! au contraire ils s'attirent. On les représente dans le graphe d'interférence par des arcs d'attraction.

Formellement, on ajoute pour chaque instruction move d s un arc d'attraction entre s et d.

Exemple

Les arcs d'interférence sont en rouge.

Les arcs qui s'attirent (liés par une instruction move) en blue pointillés). Ce seront des candidats privilégiés pour la superposition de noeuds.

Mise en oeuvre

Un noeud du graphe est un temporaire annoté par la liste des noeuds adjacents.

type interference = { temp : temp; mutable color : temp option; mutable adj : interference list; }type move = { move : Ass.instr; left : interference; right : interference; }

Le graphe d'interférence est créé en parcourant le code annoté par l'ensemble des registres vivants après chaque instruction.

interference : temp list (* précoloriés *) -> flowinfo list -> interference list * move list

Allocation de registres triviale

Le graphe d'interférence permet d'effectuer l'allocation de registres. Nous proposons ici une méthode triviale (une méthode plus performante sera présentée dans le cours suivant).

Les temporaires représentant des registres machines sont pré-coloriés, tous de couleur différente (on pourrait identifier les couleurs avec les registres.) Le but est de colorier les temporaires de telle façon que deux temporaires qui interfèrent aient deux couleurs différentes.

On choisit un temporaire t non colorié au hasard.
Les couleurs interdites sont l'ensemble des couleurs des temporaires déjà coloriés qui interfèrent avec t.
On choisit une couleur non interdite au hasard.
En cas d'échec, on choisit de placer t en pile.

Allocation en pile

Lorsqu'un temporaire t doit être alloué en pile, il faut

lui attribuer un emplacement en pile (position dans le bloc d'activation) à une distance n du sommet de pile.

pour chaque utilisation de t

·	charger la valeur à la position n du sommet de pile dans un nouveau temporaire t' (ajouter une instruction load)
·	remplacer le temporaire t par t' dans l'instruction.

pour chaque définition de t

·	remplacer le temporaire t par un nouveau temporaire t' dans l'instruction.
·	sauver la valeur de t' à la position n du sommet pile. (ajouter une instruction store)

Note d'implémentation: pour allouer un emplacement en pile, on utilise module frame (voir frame.mli).

Exemple d'allocation en pile de s0 et ra

fact: sub $sp, $sp, fact_f move $117, $s0 move $141, $s0 sw $141, 0($sp) move $125, $ra move $142, $ra sw $142, 4($sp) move $112, $a0 li $126, 1 bgt $112, $126, L10 li $127, 1 move $111, $127 L11: move $v0, $111 lw $143, 0($sp) move $s0, $117 move $s0, $143 lw $144, 4($sp) move $ra, $125 move $ra, $144 add $sp, $sp, fact_f j $ra

Élimination triviale des moves inutiles

Après coup, on élimine les moves inutiles.

En fait, une amélioration triviale consiste à choisir parmi les couleurs possibles d'un temporaire t la couleur d'un temporaire t' attiré par t (directement ou indirectement).

Cela permet d'éliminer de nombreux moves. Une approche plus systématique sera vue dans le chapitre suivant.

Allocation de registres minimale

Au minimum, il s'agit de produire du code qui tourne... Si on sauve systématiquement les registres s0, s1, ... en pile dans chaque procédure, on peut éviter le spilling dans les petits exemples. On peut donc se contenter d'un coloriage le plus simple possible.

Amélioration facile

Si le coloriage tire une couleur au hasard parmi les couleurs possibles, on trouvera peu de move inutiles.

Coloriage biaisé: on choisit, parmi les couleurs possibles, par ordre de préférence:

une couleur désirable:

celle d'un temporaire déjà colorié relié par un move;
qui n'est pas déconseillée:

celle qui est désirable pour un temporaire relié par un move;

Cela permet d'éliminer de nombreux moves, malgré une allocation des couleurs triviale (donc malgré un nombre de placements en pile relativement important).

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