Reaching Definitions
Reaching definitions
Dato un punto del programma, quali sono i comandi di
assegnamento (definizioni) che sono attuali quando la
computazione raggiunge quel punto?
Un punto del programma può “uccidere” una definizione: se il
comando associato è un assegnamento, vengono uccisi gli altri
assegnamenti alla stessa variabile
Un punto del programma può “generare” nuove definizioni.
Tino Cortesi
Tecniche di Analisi di Programmi
2
Formalizzazione
La proprietà di interesse può essere rappresentata da insiemi di
coppie
{(x,p) | x è una variabile del programma
p è un punto del programma}
Il significato della coppia (x,p) nell’insieme associato al punto q è
che l’assegnamento di x nel punto p “raggiunge” il punto q.
Tino Cortesi
Tecniche di Analisi di Programmi
3
Si tratta di un’analisi “in avanti” (forward analysis)
Il valore iniziale è
i = {(x,?) | x è una variabile del programma}
Percorrendo il grafo di flusso, ad ogni punto dovremo togliere le
definizioni “uccise” e aggiungere quelle “generate”.
Tino Cortesi
Tecniche di Analisi di Programmi
4
Specifica
L’analisi può essere specificata dalle seguenti equazioni:
Per ogni punto p del programma...
i se p è il punto iniziale
RDentry(p)=
U { RDexit(q) | q precede p}
RDexit(p)= (RDentry(p) \ killRD(p) ) U genRD(p)
Tino Cortesi
Tecniche di Analisi di Programmi
5
RDentry(1)= {(n,?),(m,?)}
RDexit(1) = {(n,?),(m,?)}
1
RDentry(2)= {(n,?),(m,?)}
RDexit(2)= {(n,?),(m,2)}
input n;
2
RDentry(3)= RDexit(2) U RDexit(5)
={(n,?),(n,5),(m,2),(m,4)}
RDexit(3)= {(n,?),(n,5),(m,2),(m,4)}
m:= 1;
3
n>1;
4
m:= m*n;
5
n:= n-1;
6
output m;
RDentry(4)= {(n,?),(n,5),(m,2),(m,4)}
RDexit(4)= {(n,?),(n,5),(m,4)}
RDentry(5)= {(n,?),(n,5),(m,4)}
RDexit(5)= {(n,5),(m,4)}
RDentry(6)= {(n,?),(n,5),(m,2),(m,4)}
RDexit(6)= {(n,?),(n,5),(m,2),(m,4)}
Tino Cortesi
Tecniche di Analisi di Programmi
6
Algoritmo
Input: grafo di controllo del programma
Output : RD
Strategia:
Passo 1 (inizializzazione):
assegna l’insieme vuoto a RDentry(p) per ogni p
RDentry(1) = i = {(x,?) | x è una variabile del programma}
Tino Cortesi
Tecniche di Analisi di Programmi
7
Passo 2 (iterazione)
novità=TRUE;
while novità
novità = FALSE;
per ogni punto p del programma
new= U{f(RD,q) | (q,p) è un arco del grafo}
if RDentry(p) != new
novità = TRUE;
RDentry(p) = new;
dove f(RD,q)= (RDentry(q) \ killRD(q) ) U genRD(q)
Tino Cortesi
Tecniche di Analisi di Programmi
8
Esempio
[ input n;
RDentry(1)= {(n,?), (m,?)}
]1
RDentry(2)= {(n,?), (m,?)}
[ m:= 1; ]2
[ while n>1 do ]3
[ m:= m * n; ]4
[ n:= n - 1; ]5
[ output m; ]6
Tino Cortesi
RDentry(3)= {(n,?), (n,5), (m,2), (m,4)}
RDentry(4)= {(n,?), (n,5), (m,4)}
RDentry(5)= {(n,5), (m,4)}
RDentry(6)= {(n,?), (n,5), (m,2), (m,4)}
Tecniche di Analisi di Programmi
9
Constant Folding
Constant Folding
Constant Folding è una tecnica di trasformazione source-to-source:
sulla base dell’informazione disponibile dall’analisi, il programma
viene modificato in un programma più efficiente.
Ci sono due ingredienti fondamentali:
Sostituire l’uso di una variabile in certe espressioni con una
costante se è noto che il valore di quella variabile assumerà
sempre quel valore costante
Semplificare le espressioni valutandole parzialmente: si
possono valutare (a tempo di compilazione) sottoespressioni
che non contengono variabili
Tino Cortesi
Tecniche di Analisi di Programmi
11
Trasformazioni
Trasformazioni di tipo Constant Folding possono essere
realizzate sulla base di una Reaching Definitions Analysis.
Dato un programma S*, consideriamo la minima soluzione RD
della Reaching Definition Analysis per S*.
Ogni comando S di S* può essere sostituito da un comando
“migliore” S’.
Esprimiamo questo con la notazione:
RD |- S w S’
Tino Cortesi
Tecniche di Analisi di Programmi
12
Regola 1
1.
RD |- [x := a]n w [x := a[y  n]]n
se y  FV(a) 
(y,?)  RDentry(n)

per ogni (z,m)  RDentry(n): ( z=y a [. . .]m è [y:=n]m)
Questa regola dice che una variabile può essere sostituita da una
costante se si sa che la variabile avrà sempre quel valore.
a[y  n] significa che nell’espressione a la variabile y è sostituita
con il valore n
FV(a) sono le variabili libere nell’espressione a.
Tino Cortesi
Tecniche di Analisi di Programmi
13
Regola 2
2.
RD |- [x := a]n w [x := n]n
se FV(a)=  a  Num  il valore di a è n
Questa regola dice che una espressione può essere valutata
parzialmente se non contiene nessuna variabile libera, in
quanto in questo caso assumerà sempre lo stesso valore
Tino Cortesi
Tecniche di Analisi di Programmi
14
Regole di composizione
3.
4.
RD |- S 1 w S’1 a
RD |- S 1 ; S2 w
S’1 ; S2
RD |- S 2 w S’2 a
RD |- S 1 ; S2 w
S1 ; S’2
Queste regole dicono come la trasformazione di un
sottocomando (in questo caso di un comando sequenziale)
può essere estesa all’intero comando
Tino Cortesi
Tecniche di Analisi di Programmi
15
Regole di composizione
RD |- S1 w S’1 a
RD |- if [b]n then S1 else S2 w
if [b]n then S’1 else S2
6. RD |- S2 w S’2 a
RD |- if [b]n then S1 else S2 w
if [b]n then S1 else S’2
7. RD |- S w S’ a
RD |- while [b]n do S w
while [b]n do S’
5.
Tino Cortesi
Tecniche di Analisi di Programmi
16
Esempio
Il programma
[x:=10]1; [y:=x+10]2; [z:=y+10]3;
La minima soluzione della Reaching Definition Analysis di questo
programma è:
RDentry(1) = {(x,?),(y,?),(z,?)}
RDexit(1) = {(x,1),(y,?),(z,?)}
RDentry(2) = {(x,1),(y,?),(z,?)}
RDexit(2) = {(x,1),(y,2),(z,?)}
RDentry(3) = {(x,1),(y,2),(z,?)}
RDexit(3) = {(x,1),(y,2),(z,3)}
Tino Cortesi
Tecniche di Analisi di Programmi
17
Utilizzando RD così calcolato, possiamo applicare le regole di
trasformazione ed ottenere:
RD |- [x:=10]1; [y:=x+10]2; [z:=y+10]3
w[x:=10]1; [y:=10+10]2; [z:=y+10]3
qui si applica la regola 1, con a=(x+10)
RDentry(2) = {(x,1),(y,?),(z,?)}
RDexit(2) = {(x,1),(y,2),(z,?)}
RD |- [y := a]2 w
[y := a[x  10]]2
se x  FV(a)

(x,?)  RDentry(2)

per ogni (z,m)  RDentry(2): ( z=x a [. . .]m è [x:=10]m)
Tino Cortesi
Tecniche di Analisi di Programmi
18
RD |- [x:=10]1; [y:=x+10]2; [z:=y+10]3
w[x:=10]1; [y:=10+10]2; [z:=y+10]3
w[x:=10]1; [y:=20]2; [z:=y+10]3
qui si applica la regola 2, con a=(10+10)
RD |- [y := a]2 w [y := n]2
se FV(a)=  a  Num  il valore di a è n
Tino Cortesi
Tecniche di Analisi di Programmi
19
RD |- [x:=10]1; [y:=x+10]2; [z:=y+10]3
w[x:=10]1; [y:=10+10]2; [z:=y+10]3
w[x:=10]1; [y:=20]2; [z:=y+10]3
w[x:=10]1; [y:=20]2; [z:=20+10]3
qui si riapplica la regola 1, con a=(y+10)
RD |- [z := a]3 w [z := a[y  20]]3
se y  FV(a)

(y,?)  RDentry(3)

per ogni (w,m)  RDentry(3): ( w=y a [. . .]m è [y:=20]m)
Tino Cortesi
Tecniche di Analisi di Programmi
20
RD |- [x:=10]1; [y:=x+10]2; [z:=y+10]3
w[x:=10]1; [y:=10+10]2; [z:=y+10]3
w[x:=10]1; [y:=20]2; [z:=y+10]3
w[x:=10]1; [y:=20]2; [z:=20+10]3
w[x:=10]1; [y:=20]2; [z:=30]3
qui si riapplica la regola 2 con a=(20+10)
RD |- [z := a]3 w [z := n]3
se FV(a)=  a  Num  il valore di a è n
Tino Cortesi
Tecniche di Analisi di Programmi
21
Questo esempio mostra che in realtà si è interessati a realizzare
una serie di trasformazioni:
RD |- S1 w S2 w S3 w . . . w Sk
In teoria, una volta calcolato S2 bisognerebbe rieseguire la
Reaching Definition Analysis su S2, e così via.
Ma siamo fortunati: se RD è una soluzione della Reaching Def.
Analysis per Si e RD |- Si w Si+1, allora RD è anche una
soluzione della Reaching Def. Analysis per Si+1.
Infatti, la trasformazione si applica a elementi che non sono
osservati dalla Reaching Def. Analysis.
Tino Cortesi
Tecniche di Analisi di Programmi
22
Available Expressions
Avaliable Expressions Analysis
Vogliamo determinare, per ogni punto del programma, quali
espressioni sono sicuramente già state valutate, e non sono state
successivamente modificate.
Ad esempio
[x:=a+b]1 ; [y:=a*b]2 ; while [y>a+b]3 do ([a:=a+1]4 ; [x:=a+b]5)
Quando la computazione raggiunge il punto 3, l’espressione a+b è
già available, in quanto è già stata valutata precedentemente (in 1
prima della prima chiamata di while, ed in 5 per le chiamate
successive) e non ha bisogno di essere valutata di nuovo.
Tino Cortesi
Tecniche di Analisi di Programmi
24
Espressioni uccise e generate
Diciamo che un’espressione è uccisa (killAE) in un punto del
programma se una qualsiasi delle variabili che vi compaiono viene
modificata
Diciamo che una espressione è generata (genAE) in un punto del
programma se viene valutata in quel punto e nessuna delle variabili
che vi compaiono viene modificata nello stesso punto.
[x:=a+b]1 ; [y:=a*b]2 ; while [y>a+b]3 do ([a:=a+1]4 ;
[x:=a+b]5)n
kill (n)
gen (n)
AE
Tino Cortesi
AE
1

{a+b}
2

{a*b}
3

{a+b}
4
{a+b, a*b,a+1}

5

{a+b}
Tecniche di Analisi di Programmi
25
Specifica
L’analisi può essere specificata dalle seguenti equazioni:
Per ogni punto p del programma...
 se p è il punto iniziale
AEentry(p)=
 { AEexit(q) | (q,p) è un arco del grafo}
AEexit(p)= (AEentry(p) \ killAE(p)) U genAE(p)
Tino Cortesi
Tecniche di Analisi di Programmi
26
Equazioni
n
killAE(n)
genAE(n)
1

{a+b}
2

{a*b}
3

{a+b}
4
{a+b, a*b,a+1}

5

{a+b}
AEentry(1)= 
AEentry(2)=AEexit(1)
AEentry(3)=AEexit(2)  AEexit(5)
AEentry(4)=AEexit(3)
AEentry(5)=AEexit(4)
 se p è il punto iniziale
AEentry(p)=
 { AEexit(q) | (q,p) arco }
AEexit(p)= (AEentry(p) \ killAE(p)) U genAE(p)
Tino Cortesi
AEexit(1)=
AEexit(2)=
AEexit(3)=
AEexit(4)=
AEexit(5)=
Tecniche di Analisi di Programmi
AEentry(1)
AEentry(2)
AEentry(3)
AEentry(4)
AEentry(5)
U {a+b}
U {a*b}
U {a+b}
- {a+b, a*b, a+1}
U {a+b}
27
Soluzione
AEentry(1)= 
AEentry(2)=AEexit(1)
AEentry(3)=AEexit(2)  AEexit(5)
AEentry(4)=AEexit(3)
AEentry(5)=AEexit(4)
AEexit(1)=
AEexit(2)=
AEexit(3)=
AEexit(4)=
AEexit(5)=
Tino Cortesi
AEentry(1)
AEentry(2)
AEentry(3)
AEentry(4)
AEentry(5)
U {a+b}
U {a*b}
U {a+b}
- {a+b, a*b, a+1}
U {a+b}
n
AEentry(n)
AEexit(n)
1

{a+b}
2
{a+b}
{a+b, a*b}
3
{a+b}
{a+b}
4
{a+b}

5

{a+b}
Tecniche di Analisi di Programmi
28
Risultato
[x:=a+b]1 ; [y:=a*b]2 ; while [y>a+b]3 do ([a:=a+1]4 ; [x:=a+b]5)
n
AEentry(n)
AEexit(n)
1

{a+b}
2
{a+b}
{a+b, a*b}
3
{a+b}
{a+b}
4
{a+b}

5

{a+b}
Anche se l’espressione a è ridefinita all’interno del ciclo (in 4),
l’espressione a+b è sempre disponibile all’entrata del ciclo (in 3).
Viceversa, l’espressione a*b è disponibile alla prima entrata nel
ciclo, ma viene uccisa prima della successiva iterazione (in 4).
Tino Cortesi
Tecniche di Analisi di Programmi
29
Very Busy Expressions
Very Busy Expressions Analysis
Diciamo che una espressione è very busy all’uscita da un certo
punto del grafo di flusso di un programma se in qualsiasi cammino
che parte da quel punto l’espressione viene usata prima che una
qualsiasi variabile che occorra in essa sia stata ridefinita
Ad esempio
if [a>b]1 then ([x:=b-a]2 ; [y:=a-b]3 ) else ([y:=b-a]4 ; [x:=a-b]5)
Le espressioni a-b e b-a sono entrambe very busy nel punto 1.
Tino Cortesi
Tecniche di Analisi di Programmi
31
A cosa serve?
L’informazione derivata da una very busy expression analysis può
essere utilizzata per valutare l’espressione ad un certo punto del
grafo e memorizzarne il valore per un uso successivo.
Questa ottimizzazione è anche chiamata “hoisting” di una
espressione
Ad esempio
if [a>b]1 then ([x:=b-a]2 ; [y:=a-b]3 ) else ([y:=b-a]4 ; [x:=a-b]5)
Le espressioni a-b e b-a possono essere “hoisted” prima del
comando condizionale: a questo punto il test non è più necessario e
il programma può essere trasformato in uno più efficiente.
Tino Cortesi
Tecniche di Analisi di Programmi
32
Espressioni uccise e generate
Diciamo che un’espressione è uccisa (killVB) in un punto del
programma se una qualsiasi delle variabili che vi compaiono viene
modificata (killVB=killAE)
Diciamo che una espressione è generata (genVB) in un punto del
programma se appare in quel punto (genVB!=genAE).
if [a>b]1 then ([x:=b-a]2 ; [y:=a-b]3 ) else ([y:=b-a]4 ; [x:=a-b]5)
Tino Cortesi
n
killVB(n)
genVB(n)
1


2

{b-a}
3

{a-b}
4

{b-a}
5

{a-b}
Tecniche di Analisi di Programmi
33
Specifica
L’analisi può essere specificata dalle seguenti equazioni:
Per ogni punto p del programma...
 se p è un punto finale
VBexit(p)=
 { VBentry(q) | (p,q) è un arco del grafo}
VBentry(p)= (VBexit(p) \ killVB(p)) U genVB(p)
Tino Cortesi
Tecniche di Analisi di Programmi
34
n
killVB(n)
genVB(n)
1


2

{b-a}
3

{a-b}
1
4
{b-a}
a>b

5

{a-b}
Equazioni
2
4
x:=b-a
VBentry(1)=VBexit(1)
VBentry(2)=VBexit(2) U {b-a}
VBentry(3)={a-b}
VBentry(4)=VBexit(4) U {b-a}
VBentry(5)={a-b}
y:=b-a
5
3
y:=a-b
x:=a-b
 se p è il punto finale
VBexit(p)=
 { VBentry(q) | (p,q) arco }
VBentry(p)= (VBexit(p) \ killVB(p)) U genVB(p)
Tino Cortesi
VBexit(1)=
VBexit(2)=
VBexit(3)=
VBexit(4)=
VBexit(5)=
Tecniche di Analisi di Programmi
VBentry(2)  VBentry(4)
VBentry(3)

VBentry(5)

35
Risultato
if [a>b]1 then ([x:=b-a]2 ; [y:=a-b]3 ) else ([y:=b-a]4 ; [x:=a-b]5)
1
a>b
2
x:=b-a
3
y:=a-b
4
y:=b-a
5
x:=a-b
n
VBentry(n)
VBexit(n)
1
{a-b, b-a}
{a-b, b-a}
2
{a-b, b-a}
{a-b}
3
{a-b}

4
{a-b, b-a}
{a-b}
5
{a-b}

L’analisi è “backward”: segue il grafo di flusso dalle foglie alla
radice: una espressione è very busy all’uscita di un punto del grafo
se è very busy all’entrata di ogni punto immediatamente successivo
Nessuna espressione è very busy all’uscita di un punto finale del
grafo.
Tino Cortesi
Tecniche di Analisi di Programmi
36