Dataflow Analysis. Tino CortesiTecniche di Analisi di Programmi 2 Dataflow Analysis Il punto di...

Dataflow Analysis

Tino Cortesi Tecniche di Analisi di Programmi 2

Dataflow AnalysisIl punto di partenza per una dataflow analysis è una rappresentazione del grafo di controllo del programma I nodi di questo grafo possono rappresentare uno o più comandi del programma, e sono in corrispondenza a punti del programmaLa specifica dell’analisi è data mediante un insieme di equazioni che legano l’informazione che si sta analizzando ai punti del programma (ovvero ai nodi del grafo)


Quando non è disponibile il grafo di controllo del programma, è necessario premettere alla dataflow analysis una control flow analysis.L’informazione può essere propagata in avanti (forward analysis), come nel caso della parity analysis, oppure all’indietro (backward analysis)


Control flow graphOgni istruzione del programma corrisponde ad un nodo del grafoSe il comando a può essere seguito dal comando b, allora nel Control Flow Graph deve esserci un arco dal parte dal nodo che corrisponde ad a ed arriva al nodo che corrisponde a b


Esempio

[ input n; ]1

[ m:= 1; ]2

[ while n>1 do ]3

[ m:= m * n; ]4

[ n:= n -

1; ]5

[ output m; ]6

input n;

m:= 1;

n>1;m:= m*n;

n:= n-1;

output m;

1

2

3

4

5

6

Liveness Analysis


Liveness Analysis

Una delle fasi principali della compilazione è la traduzione del programma in un linguaggio intermedio (IR) con un numero illimitato di temporanei.Questo programma dovrà girare su una macchina con un numero limitato di registri.Due temporanei a e b potranno utilizzare lo stesso registro se a e b non sono mai “in uso” contemporaneamenteIl compilatore ha bisogno di analizzare il programma IR per determinare quali temporanei sono in uso contemporaneamente

Diciamo che una variabile è viva (live) se contiene un valore che sarà utilizzato in futuro.


a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6

a = 0;do{ b= a+1; c+=b; a=b*2;}while (a<N);return c;

Esempio


Una variabile è live se contiene un valore che sarà utilizzato in futuro. L’analisi è quindi “dal futuro al passato” (backward).La variabile b è usata nel comando 4: è live nell’arco 3 4Il comando 3 non assegna nulla a b, quindi b è live anche nell’arco 2 3Il comando 2 assegna un valore a b. Questo significa che il valore di b nell’arco 1 2 non è utilizzato da nessuno in futuroQuindi il “live range” di b è:{2 3, 3 4}

a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6


a è live negli archi 4 5 e 5 2La variabile a è live nell’arco 1 2a non è live negli archi 2 3 4

Anche se nel nodo 3 la variabile a ha un valore ben definito, questo non sarà più utilizzato finché ad a non sarà assegnato un nuovo valore

a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6


La variabile c è live sin dall’inizio di questo programma: potrebbe essere ad esempio un parametro formalec è live in tutti gli archi l’analisi di liveness ci dice anche che se c è una variabile locale, c viene usata senza essere inizializzata (questo può essere utilizzato per generare un messagio di warning)

a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6


Sono sufficienti 2 registri: le variabili a e b non sono mai vive contemporaneamente

a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6 6

a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;


NotazioneUn grafo di flusso ha archi uscenti (out-edges), che portano a nodi successori, ed archi entranti (in-edges) che provengono da nodi predecessori. pred[n] e succ[n] denotano, rispettivamente, i nodi predecessori e successori del nodo n.

Ad esempio, in questo grafo di flusso:gli out-edges del nodo 5 sono 5 6 e 5 2.gli in-edges del nodo 2 sono 5 2 e 1 2.pred[2]={1,5}

a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6


NotazioneUn assegnamento ad una variabile definisce tale variabileL’occorrenza di una variabile nell’espressione a destra dell’operatore di assegnamento usa tale variabiledef[n] è l’insieme di variabili che sono definite nel nodo nuse[n] è l’insieme delle variabili che sono usate nel nodo n

Ad esempio, in questo grafo di flusso:def[3]={c}use[3]={b, c}

a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6


FormalizzazioneUna variabile è live su un arco se esiste un cammino orientato da tale arco ad un use di quella variabile che non attraversa nessun altro def di quella stessa variabile.Una variabile è live-in in un nodo se è live su ognuno dei suoi in-edges.Una variabile è live-out in un nodo se è live su almeno uno dei suoi out-edges.

Ad esempio, in questo grafo di flusso:a è live negli archi 1 2, 4 5 e 5 2a è live-in nel nodo 2, b non lo è.c è live-out nel nodo 5

a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6


Calcolare la LivenessL’informazione di liveness (live-in e live-out) si può calcolare nel modo seguente:

1. Se una variabile è in use[n], allora è live-in nel nodo n. Ovvero, se un comando usa una variabile, tale variabile è viva all’entrata di quel comando

2. Se una variabile è live-in nel nodo n, allora è live-out per tutti i nodi in pred[n]

3. Se una variabile è live-out nel nodo n, e non appartiene a def[n], allora la variabile è anche live-in nel nodo n.Ovvero, se un comando ha bisogno del valore di a alla fine del comando n, e n non fornisce quel valore, allora il valore di a è necessario anche all’entrata di n


Dataflow EquationsSe indichiamo con

in[n] l’insieme delle variabili che sono live-in nel nodo nout[n] l’insieme delle variabili che sono live-out nel nodo n

possiamo esprimere le regole precedenti con due equazioni:

1. in[n] = use[n] U (out[n] - def[n])2. out[n] = U { in[m] | m succ[n]}


genLV(p)= use[p]

killLV(p) = def[n]

se p è un punto finale

LVexit(p)=

U { LVentry(q) | q segue p}

LVentry(p)= ( LVexit(p) \ killLV(p) ) U genLV(p)

Liveness Analysis(una formalizzazione alternativa)


AlgoritmoPer ottenere una soluzione alle due equazioni precedenti si può usare il seguente algoritmo:

for each nin[n]:={}; out[n]:={}

repeatfor each n

in’[n]:=in[n]; out’[n]:=out[n]in[n] := use[n] U (out[n] - def[n])out[n]:= U { in[m] | m succ[n]}

until ( per ogni n: in’[n]=in[n] && out’[n]=out[n])


1 2 3

use

def in out in out in out

1 a a a

2 a b a a b c a c b c

3 b c c b c b c b b c b

4 b a b b a b a

5 a a a a a c a c a c

6 c c c c

for each n

in[n]:={}; out[n]:={}

repeat

for each n

in’[n]:=in[n]; out’[n]:=out[n]

in[n] := use[n] U (out[n] - def[n])

out[n]:= U { in[m] | m succ[n]}until ( per ogni n: in’[n]=in[n] && out’[n]=out[n])

a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6


3 4 5

use


1 a a a c c a c

2 a b a c b c a c b c a c b c

3 b c c b c b b c b b c b

4 b a b a b a c b c a c

5 a a c a c a c a c a c a c

6 c c c c

for each n

in[n]:={}; out[n]:={}

repeat

for each n




a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6


5 6 7

use


1 a c a c c a c c a c

2 a b a c b c a c b c a c b c

3 b c c b c b b c b c b c b c

4 b a b c a c b c a c b c a c

5 a a c a c a c a c a c a c

6 c c c c

for each n

in[n]:={}; out[n]:={}

repeat

for each n




a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;6


Nell’esecuzione precedente, bisogna aspettare la prossima iterazione per utilizzare la nuova informazione calcolata sugli in e out.Riordinando in modo opportuno i nodi si ottiene...

1 2 3

use

def

in out

in out in out

6 c c c c

5 a c a c a c a c a c a c

4 b a a c b c a c b c a c b c

3 b c c b c b c b c b c b c b c

2 a b b c a c b c a c b c a c

1 a ac c ac c ac c


Backward AnalysisDall’esempio è chiaro come la Liveness Analysis sia un’analisi di tipo “backward”: l’informazione si propaga dai nodi terminali del grafo al nodo iniziale.


Rappresentare insiemiCi sono due modi per rappresentare efficientemente insiemi di variabili:array di bits

se ci sono N variabili nel programma, ogni insieme può essere rappresentato con N bitscalcolare l’unione di due insiemi equivale alla “or” dei bits corrispondenti ad ogni posizioneefficiente se gli insiemi sono densi

liste ordinateun insieme può essere rappresentato come la lista dei suoi elementi, ordinati utilizzando una qualsiasi chiave totalmente ordinata (ad es. il nome della variabile)l’unione di due insiemi è il “merge” delle due liste, eliminando i duplicatiefficiente se gli insiemi sono sparsi


Time-ComplexityDiciamo che un programma ha dimensione N se ha al più N nodi nel grafo di flusso ed ha al più N variabili.Ogni insieme live-in (o live-out) ha al più N elementiOgni operazione di unione per calcolare live-in e live-out ha complessità O(N)Il ciclo for calcola un numero costante di operazioni di unione per ogni nodo del grafo. Ci sono O(N) nodi. Quindi il ciclo for ha complessità O(N2)

for each n

in[n]:={}; out[n]:={}

repeat

for each n





Time ComplexityOgni iterazione del ciclo repeat può solo accrescere gli insiemi live-in e live-out (c’è monotonia), e gli insiemi non possono crescere indefinitamente: al più ogni insieme contiene tutte le variabili. Quindi ci possono essere al più 2N2 iterazioniQuindi la complessità dell’algoritmo è al peggio O(N4).Ordinando opportunamente i nodi del grafo, si riduce il numero di iterazioni del ciclo repeat a 2 o 3. Inoltre gli insiemi live-in e live-out sono solitamente sparsi. In pratica, la complessità media varia da O(N) a O(N2).

for each n

in[n]:={}; out[n]:={}

repeat

for each n





Approssimazione Conservativa


Se d è un’altra variabile non usata in questo frammento di codice, sia X che Y della seguente tabella sono soluzioni delle due equazioni, mentre Z non lo è.

X Y Z

use def in out in out in out

1 a c a c cd acd c a c

2 a b a c b c acd

bcd a c b

3 b c c b c b c bcd

bcd b b

4 b a b c a c bcd

acd b a c

5 a a c a c acd

acd a c a c

6 c c c c


Approssimazione Conservativa

Come si legge allora la risposta dell’analisi? d è live oppure no?Se la variabile a sarà effettivamente utilizzata in qualche esecuzione del programma quando questa raggiunge il nodo n, allora siamo sicuri che a è nell’insieme live-out del nodo n in tutte le soluzioni del sistema di equazioni.Ma il viceversa non è vero: possiamo calcolare che d è nell’insieme live-out del nodo n, ma ciò non significa che necessariamente il suo valore sarà usato in qualche esecuzione del programma.“Approssimazione conservativa” nel caso di liveness significa che si può erroneamente derivare che una variabile sia live, ma non si deve mai derivare erroneamente che una variabile sia “morta”.


Soluzione MinimaAbbiamo visto che il sistema di equazioni


può avere più di una soluzione (X e Y, ad esempio).

Nel nostro caso, X è la soluzione minima, ovvero, ogni soluzione Y è tale che per ogni n:

inX[n] inY[n]

Si può dimostrare che l’algoritmo che abbiamo utilizzato calcola sempre la soluzione minima di questo sistema di equazioni.


Uso dell’analisiL’informazione di liveness è utilizzata per diversi tipi di ottimizzazioni nei compilatori

Dead code eliminationad es. rimozione di un comando che assegna un valore ad una variabile che non viene utilizzata prima di essere riassegnata Code motionad es. spostamento di un comando che assegna variabili che non vengono utilizzate in una porzione di codiceRegister Allocationuna condizione necessaria perché due variabili a e b possano essere allocate sullo stesso registro è che in nessun punto del programma a e b siano entrambe live


Grafo di interferenzaUna condizione che impedisce a due variabili a e b di essere allocate sullo stesso registro viene chiamata anche interferenza

Ad esempio, se le due variabili sono entrambe live nello stesso nodo del grafo di flussoAd esempio, se a viene generata da un’istruzione che non può accedere al registro r, a ed r interferiscono.

L’informazione sull’interferenza di variabili può essere espressa con una matrice, o con un grafo non orientato.Nel nostro esempio:a b c

a x

b x

c x x

a

c

b


EsercizioAnalizzare il flusso del seguente programma:

disegnare il grafo di controllo

calcolare live-in e live-out di ogni comando

costruire il grafo di interferenza

1. m:=0

2. v:=0

3. if (v>=n) goto 15

4. r:=v

5. s:=0

6. if (r<n) goto 9

7. v:= v+1

8. goto 3

9. x:=M[r]

10. s:=s+x

11. if (s<=m) goto 13

12. m:= s

13. r:= r+1

14. goto 6

15. return m


EsercizioVerificare, usando la liveness analysis, che è corretto rimuovere il comando y:=1 dal secondo dei seguenti programmi, ma non dal primo

y = 1;

while (x <= 10) { x = x + 1; y = x;

}

print(y);

y = 1;

repeat { x = x + 1; y = x;

} until (x > 10);

print(y);


EsercizioModificare la live variables analysis per realizzare la faint variables analysis. Una variable è faint (pallida) se è dead o se è solo utilizzata per calcolare variabili che sono faint; in caso contrario è fortemente live.Ad esempio, si consideri il frammento di codice x:=1; y:=3; x:= x-1; y:=2*y; x:= 2; con l’assunzione che poi x sia dead.

La variabile x è faint dopo il primo, il terzo ed il quinto assegnamentoLa variabile x è dead dopo il terzo ed il quinto La variabile x è live dopo il primo assegnamento.


Esempio

a:= 0;

b:= a+1;

1

2

c:= c+b;3

a:= b*2;4

a<N;5

return c;7

d:= b*e;6

use def

LVin LVout DVin DVout FAin FAout

1 a ce ace abd bd

2 a b ace bce bd ad

3 bc c bce bce ad ad

4 b a bce abce ad d

5 a abce

abce d d

6 be d abce

ace d bd

7 c c abde

abcde


EsercizioLa copy-propagation analysis determina per ogni punto del programma n se esiste un cammino da un comando di “copia”, ovvero da un assegnamento del tipo x := y, fino al nodo n, nel quale non ci siano altri assegnamenti alla variabile y.

Dare una specifica formale a tale analisi dataflow


EsercizioLa dominator analysis determina per ogni comando di assegnamento da quali altri assegnamenti esso è dominato.Un assegnamento è dominato da un’altro assegnamento se ogni possibile esecuzione del primo è sempre preceduta da un’esecuzione del secondo.

Dare una specifica formale a tale analisi dataflow

Dataflow Analysis. Tino CortesiTecniche di Analisi di Programmi 2 Dataflow Analysis Il punto di...

Documents

Transcript of Dataflow Analysis. Tino CortesiTecniche di Analisi di Programmi 2 Dataflow Analysis Il punto di...