TD4 - Optimisation 1 Optimisation : expressions communes

Master Info - 2014-2015
Compilation
TD4 - Optimisation
Dans la suite nous regardons les optimisations ind´ependantes de machine cible. Elles sont
en g´en´eral r´ealis´ees sur le graphe de flot de contrˆole. Compilateurs (dragon book) Aho,
Sethi, Ullman
1
Optimisation : expressions communes
On rappelle :
(
∅
AEentry (`) = T
if ` = init
{AEexit
(`0 )|(`0 , `)
∈ f low(G)}
AEexit (`) = AEentry (`)\killAE (`) ∪ genAE (`)
Exercice 1 Optimisation expressions communes
Soit le code `
a trois adresses suivant :
(1)
(2)
(8)
(10)
a=b+c
b=a+c
d=c+e
si d>7 aller a (8)
t=a+c
v=c+e
aller a (10)
t=b+c
v=a+c
b=a+c
a=b+c
1. Construire le graphe de flot de contrˆole.
2. On cherche a
` r´ealiser l’optimisation des sous expressions communes. Pour chaque bloc,
calculer les ensembles d’expressions produites et supprim´ees : Prod et Sup.
3. Calculer les ensembles des expressions disponibles en entr´ee et en sortie de chaque bloc.
4. Avec ce r´esultat, optimiser le code.
Exercice 2 Avec une boucle
Mˆemes questions avec ce programme :
x:=a+b;
y:=a*b;
while(y>a+b) do
a:=a+a;
x:=a+b;
done
TD4 MIF12, Master Info - 2014-2015, L. Gonnord & E. Guillou
1/2
2
Autre analyse : variables actives
Une variable de gauche d’une affectation est tu´ee par le bloc. Une variable apparaissant dans
un bloc est dite g´ener´ee.
(
∅
if ` = f inal
LVexit (`) = S
0
0
{LVentry (` )|(` , `) ∈ f low(G)}
LVentry (`) = LVexit (`)\killLV (`) ∪ genLV (`)
Exercice 3 Variables actives
G´en´erer le graphe de flot de contrˆ
ole pour le code suivant :
while d>0 do{
a:=b+c;
d:=d-b;
e:=a+f;
if e>0
{f:=a-d;b:=d+f}
else
{e:=a-c}
b:=a+c}
Sur ce graphe de flot :
´
1. Ecrire
et r´esoudre le syst`eme d’´equations relatif aux ensembles Gen, Kill, In et Out pour
les variables actives, en prenant bien soin d’initialiser les ensembles correctement.
2. Supprimer les instructions inutiles (“code mort”).
Exercice 4 Variables actives
Apr`es g´en´eration de code, on obtient le programme suivant :
B1
d1 : i := m − 1
d2 : J := n
d3 : a := u1
B2
d4 : i := i + 1
d5 : j := j − 1
B3
d6 : a := u2
B4
d7 : i := u3
Supprimer le code mort.
TD4 MIF12, Master Info - 2014-2015, L. Gonnord & E. Guillou
2/2

Download Report