Analyse de durée de vie

Description

c3c%Y[Z"O"NP\]X^X^NWV_KQN-IK`y]yy]yyy]yy]yFl"B-!#$98acfhgi0!#=8A K!1?j$98$98-!2F{F:;:jB-!1?j$ Kk?:;8DFzY[Z"O"NJp'L^N-`^Vwvyy5y5y]y5y5y5y]yDNO"J\J`AN:dk"*l"BA:S8nmY[Z"O"NJp'L^N-`^Vwv2:rtD:aF 2t$K$ M698C:44c8A K!1?j$c?:A@"#BC ?:cD:;$E>F#!#$$K$u:;e:;$U!#8FKB; "!1?j$:G:;$98:H"IKJMLANPO"NQNSRUT:NWV=NX8W!Y[Z"O"NP\]X^X^NWV_KQN-IK`:S82NO"J\J`AN32224$$ 57698;:Y[Z"O"NP\]X^X^NWV_KQN-IK`?'&(%/ 0!6"8/!<"Sa place dans la cha^ ne de compilationCalculer pour chaque instruction la liste des temporaires vivantsSlide 2a la n de l’instruction :) Les temporaires vivant simultanement ne peuvent pas ^etreidenti es. En particulier, ils ne peuvent pas ...

Informations

• Publié par: Novug
• Nombre de lectures: 31
• Langue: Français

Extrait

F#!#$$K$u:;e:;$U!#8FKB; "!1?j$:G:;$98:H"IKJMLANPO"NQNSRUT:NWV=NX8W!Y[Z"O"NP\]X^X^NWV_KQN-IK`:S82NO"J\J`AN32224$$ 57698;:Y[Z"O"NP\]X^X^NWV_KQN-IK`?'&(%/ 0!6"8/!<"Sa place dans la cha^ ne de compilationCalculer pour chaque instruction la liste des temporaires vivantsSlide 2a la n de l’instruction :) Les temporaires vivant simultanement ne peuvent pas ^etreidenti es. En particulier, ils ne peuvent pas ..." />

Analyse de duree de vie.
Didier Remy
Octobre 2000
http://cristal.inria.fr/~remy/poly/compil/5/
http://w3.edu.polytechnique.fr/profs/informatique/Didier.Remy/compil/5/
Slide 1
KB; "!1?j$
:S
$
<
:S8
2

:
:
z
2
$98-!
:;$
%
$K$u:;e:;$U!#8
!
:
:-:
8W!
:S8
NO"J\J`AN
:;8-!1?j$
2
:S8s<t
c



4
"!#$
:

NO"J\J`AN
%
:;:jB-!1?j$
'&)(
l"B-!#$98
*
+-,".0/1
c
2
D
3
F
2
a
4
F
$ 57698;:=<>?:A@"#BC ?:

D
Kk?:;8
E>F
t
#!#$
c
F
4
:G:;$98
F
H"IKJMLANPO"NQNSRUT
c
NWV=NX
a
Y[Z"O"NP\]X^X^NWV_KQN-IK`
c
2
Y[Z"O"NJp'L^N-`^Vwv
3
Y[Z"O"NP\]X^X^NWV_KQN-IK`
2
3
4
x
$ 57698;:
D
<ba'c
c
5de K!1#BC ?:
2
fhgi0!#=8A K!1?j$98
8A K!1?j$
F
$K$ M698C:
:dk"*l"BA:S8nm
F
H*o*p'LA\5R"N)\_9XqL^`C\5JL^N
t
Y[Z"O"NP\]X^X^NWV_KQN-IK`
Y[Z"O"NJp'L^N-`^Vwv
2
yy5y5y]y5y5y5y]y
2
D
3
F{
2
c
2
y]yy]yyy]yy]y
r
Y[Z"O"NP\]X^X^NWV_KQN-IK`
Sa place dans la cha^ ne de compilation
Calculer pour chaque instruction la liste des temporaires vivantsSlide 2
a la n de l’instruction :
) Les temporaires vivant simultanement ne peuvent pas ^etre
identi es. En particulier, ils ne peuvent pas utiliser le m^eme
registre.
) Les autres peuvent partager le m^eme registre.
L’analyse de la duree se retrouve sous d’autres formes (analyse
de ow) en aval pour faire des optimisations plus poussees.
Le probleme
Chaque instruction
{ utilise (lit) un ensemble de temporaires, calcule et
{ de nit (ecrit) un de temporaires.
Les deux ensembles ne sont pas necessairement disjoints.
Un temporaire est vivant a la sortie d’une instruction i si sa
valeur est utilisee dans une instruction suivante (au sens large)
Slide 3
avant d’^etre rede nie. La duree de vie d’un temporaire est
l’ensemble des instructions o u il est vivant.
Lorsqu’un temporaire est mort, sa valeur n’a pas d’importance.
Deux temporaires qui ont des durees de vie disjointes peuvent
^etre superposes et utiliser le m^eme registre.
Le calcul de la duree de vie est un preliminaire a l’allocation de
registres.
2

/

%$
/ 0

)*+,.-*(

%

7




4

8

7
)*)=+.-*(
!6"
:5?-*13.51
-*213.542+
/
:9;-*

!<"

7



)=.->?

!<"
!#"

'&(Exemples
z x +y utilise les variables x;y et de nit z.
Analogie temporaire ! variable globale
Groupements On peut traiter un groupe d’instructions lineaires
(sans saut ni entree), en particulier un bloc elementaire, comme
une \macro-instuction" :
Slide 4
Important : la valeur locale de z
z x +y utilise x;y
est utilisee dans le bloc, mais pas
t z de nit z;t
sa valeur a l’entree 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).
{ ecrit ra, les registres speciaux, les registres t, v, et a.
Le graphe d’un programme
Un programme peut ^etre vu comme un graphe dont les n uds
sont les instructions et les arcs decrivent la possibilite de passer
d’une instruction a une autre et sont etiquetes par des conditions
(mutuellement exclusives |determinees a l’evaluation).
L’execution du programme evalue une instruction puis passe a
l’instruction suivante autorisee (satisfaisant la condition de saut).
Slide 5
Les conditions de branchement sont des conditions dynamiques.
Elles peuvent dependent d’un calcul arbitrairement complexe.
Elles ne sont donc pas decidables.
Approximation On ne peut calculer qu’une approximation de la
duree de vie. (On la choisira par exces pour ^etre correct.)
On majore grossierement les conditions de saut en les supposant
toujours vraies (elles ne sont plus disjointes).
3Un (sous) programme
Slide 6
De nition de la duree de vie
Pour chaque instruction i, on de nit
{ Use (i) l’ensemble des temporaires utilises par i
{ Def (i) des temporaires de nis par i
{ Out (i) l’ensemble des temporaires vivants a la sortie de i
{ Succ (i) des successeurs immediats de i
Slide 7 Par de nition, t2 Out (i) si et seulement si il existe un chemin a
partir de i pour lequel t sera lu avant d’^etre ecrit :
8
<^ t2 Use (i )n+1
9i 2 Succ (i);:::i 2 Succ (i );1 n+1 n
:8k2 [1;n];t2= Def (i )k
4












/





































'&)(+*

















































"!$#

,-.

23

































































































!$%

,



(211





































































































































































































"!$#

,



,-.



0

Calcul de la duree de vie
On de nit
k{ Succ (i) comme l’ensemble des sequences de k-instructions
consecutives a i.

p{ la sequence p privee de la derniere instruction,
{ p^ la derniere instruction de p.
Slide 8 On peut reecrire Out (i) comme
8
<[ [ ^ t2 Use (p^)

: p n 8j2 ;t2= Def (j)n2IN p2Succ (i)
0(En fait on peut ajouter le cas n = 0 en considerant que Succ (i)
est vide.)
Temporaires vivant en entree
8
n <[ [ ^ t2 Use (p^)4nOut (i) =
: p8j2 ;t2= Def (j)kk=1p2Succ (i)
peut s’ecrire
80 1
n 1 <[ [ [ ^ t2 Use (p^)
@ A
: 0
k 8j2ip;t2= Def (j)0 k=0 0i2Succ i p2Succ (i )Slide 9
| {z }
4 n 1 0= In (i )
Soit
8
> t2 Use (p^)n <[ [ ^ n pIn (i) = Use (i)[ 8j2 ;t2= Def (j)
| {z } >>kk=1 :p2Succ (i) t2= Def (i)k = 0
| {z }
nOut (i)nDef (i)
5