Reaching Definitions. Tino CortesiTecniche di Analisi di Programmi 2 Reaching definitions Dato un...

Reaching Definitions

Tino Cortesi Tecniche di Analisi di Programmi 2

Reaching definitionsDato 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 variabileUn punto del programma può “generare” nuove definizioni.


FormalizzazioneLa 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.


Si tratta di un’analisi “in avanti” (forward analysis)

Il valore iniziale è = {(x,?) | x è una variabile del programma}

Percorrendo il grafo di flusso, ad ogni punto dovremo togliere le definizioni “uccise” e aggiungere quelle “generate”.


SpecificaL’analisi può essere specificata dalle seguenti equazioni:Per ogni punto p del programma...

se p è il punto iniziale

RDentry(p)=

U { RDexit(q) | q precede p}

RDexit(p)= (RDentry(p) \ killRD(p) ) U genRD(p)


RDentry(1)= {(n,?),(m,?)}RDexit(1) = {(n,?),(m,?)}

RDentry(2)= {(n,?),(m,?)}RDexit(2)= {(n,?),(m,2)}

RDentry(3)= RDexit(2) U RDexit(5) ={(n,?),(n,5),(m,2),

(m,4)}RDexit(3)= {(n,?),(n,5),(m,2),(m,4)}

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)}

input n;

m:= 1;

n>1;m:= m*n;

n:= n-1;

output m;

1

2

3

4

5

6


AlgoritmoInput: grafo di controllo del programmaOutput : RD

Strategia:Passo 1 (inizializzazione):

assegna l’insieme vuoto a RDentry(p) per ogni p

RDentry(1) = = {(x,?) | x è una variabile del programma}


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) != newnovità = TRUE;RDentry(p) = new;

dove f(RD,q)= (RDentry(q) \ killRD(q) ) U genRD(q)


EsempioRDentry(1)= {(n,?), (m,?)}

RDentry(2)= {(n,?), (m,?)}

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)}

[ input n; ]1

[ m:= 1; ]2

[ while n>1 do ]3

[ m:= m * n; ]4

[ n:= n -

1; ]5

[ output m; ]6

Constant Folding


Constant FoldingConstant 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 costanteSemplificare le espressioni valutandole parzialmente: si possono valutare (a tempo di compilazione) sottoespressioni che non contengono variabili


TrasformazioniTrasformazioni 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 |SS’


Regola 11. RD |[x := a][x := a[y Š n]]

se y FV(a) (y,?) RDentry() per ogni (z,) RDentry(): ( z=y [. . .] è [y:=n])

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.


Regola 22. RD |[x := a][x := 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


Regole di composizione3. RD |S

S’

RD |S; SS’ ; S

4. RD |SS’

RD |S; SS ; S’

Queste regole dicono come la trasformazione di un sottocomando (in questo caso di un comando sequenziale) può essere estesa all’intero comando


EsempioIl 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)}


Utilizzando RD così calcolato, possiamo applicare le regole di trasformazione ed ottenere:

RD |[x:=10]1; [y:=x+10]2; [z:=y+10]3

[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][y := a[x Š 10]]

se x FV(a) (x,?) RDentry() per ogni (z,) RDentry(): ( z=x [. . .]è [x:=10])


RD |[x:=10]1; [y:=x+10]2; [z:=y+10]3

[x:=10]1; [y:=10+10]2; [z:=y+10]3

[x:=10]1; [y:=20]2; [z:=y+10]3

qui si applica la regola 2, con a=(10+10)

RD |[y := a][y := n]



RD |[x:=10]1; [y:=x+10]2; [z:=y+10]3

[x:=10]1; [y:=10+10]2; [z:=y+10]3

[x:=10]1; [y:=20]2; [z:=y+10]3

[x:=10]1; [y:=20]2; [z:=20+10]3

qui si riapplica la regola 1, con a=(y+10)

RD |[z := a][z := a[y Š 20]]

se y FV(a) (y,?) RDentry() per ogni (w,) RDentry(): ( w=y [. . .]è [y:=20])


RD |[x:=10]1; [y:=x+10]2; [z:=y+10]3

[x:=10]1; [y:=10+10]2; [z:=y+10]3

[x:=10]1; [y:=20]2; [z:=y+10]3

[x:=10]1; [y:=20]2; [z:=20+10]3

[x:=10]1; [y:=20]2; [z:=30]3

qui si riapplica la regola 2 con a=(20+10)

RD |[z := a][z := n]



Questo esempio mostra che in realtà si è interessati a realizzare una serie di trasformazioni:

RD |SSS. . . Sk

In teoria, una volta calcolato S bisognerebbe rieseguire la Reaching Definition Analysis su S, e così via.

Ma siamo fortunati: se RD è una soluzione della Reaching Def. Analysis per Sie RD |SiSi+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.

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.


Espressioni uccise e generate

Diciamo che un’espressione è uccisa (killAE) in un punto del programma se una qualsiasi delle variabili che vi compaiono viene modificataDiciamo 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 killAE(n) genAE(n)

1 {a+b}

2 {a*b}

3 {a+b}

4 {a+b, a*b,a+1} 5 {a+b}




AEentry(p)=

{ AEexit(q) | (q,p) è un arco del grafo}

AEexit(p)= (AEentry(p) \ killAE(p)) U genAE(p)



AEentry(p)=

{ AEexit(q) | (q,p) arco }

AEexit(p)= (AEentry(p) \ killAE(p)) U genAE(p)

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)



AEexit(1)= AEentry(1) U {a+b}

AEexit(2)= AEentry(2) U {a*b}


AEexit(4)= AEentry(4) - {a+b, a*b, a+1}


Equazioni


Soluzione

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}

AEentry(1)=


AEentry(3)=AEexit(2) AEexit(5)




AEexit(2)= AEentry(2) U {a*b}


AEexit(4)= AEentry(4) - {a+b, a*b, a+1}



Risultato[x:=a+b]1 ; [y:=a*b]2 ; while [y>a+b]3 do ([a:=a+1]4 ; [x:=a+b]5)

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).

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}

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.


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.


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) n killVB(n) genVB(n)

1 2 {b-a}

3 {a-b}

4 {b-a}

5 {a-b}



se p è un punto finale

VBexit(p)=

{ VBentry(q) | (p,q) è un arco del grafo}

VBentry(p)= (VBexit(p) \ killVB(p)) U genVB(p)


se p è il punto finaleVBexit(p)=

{ VBentry(q) | (p,q) arco }

VBentry(p)= (VBexit(p) \ killVB(p)) U genVB(p)

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}

VBexit(1)= VBentry(2) VBentry(4)

VBexit(2)= VBentry(3)

VBexit(3)=

VBexit(4)= VBentry(5)

VBexit(5)=

Equazioni

n killVB(n) genVB(n)

1 2 {b-a}

3 {a-b}

4 {b-a}

5 {a-b}a>b

x:=b-a

y:=a-b

y:=b-a

x:=a-b

1

2 4

53


Risultatoif [a>b]1 then ([x:=b-a]2 ; [y:=a-b]3 ) else ([y:=b-a]4 ; [x:=a-

b]5)

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 successivoNessuna espressione è very busy all’uscita di un punto finale del grafo.

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}

a>b

x:=b-a

y:=a-b

y:=b-a

x:=a-b

1

2 4

53

Reaching Definitions. Tino CortesiTecniche di Analisi di Programmi 2 Reaching definitions Dato un...

Documents

Transcript of Reaching Definitions. Tino CortesiTecniche di Analisi di Programmi 2 Reaching definitions Dato un...