Dataflow Analysis
Dataflow Analysis
Il 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
programma
La 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)
Tino Cortesi
Tecniche di Analisi di Programmi
2
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)
Tino Cortesi
Tecniche di Analisi di Programmi
3
Control flow graph
Ogni istruzione del programma corrisponde ad un nodo del
grafo
Se 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
Tino Cortesi
Tecniche di Analisi di Programmi
4
Esempio
1
[ input n; ]1
input n;
[ m:= 1; ]2
[ while n>1 do
2
m:= 1;
]3
3
[ m:= m * n; ]4
[ n:= n - 1;
[ output m; ]6
n>1;
]5
4
m:= m*n;
5
6
n:= n-1;
output m;
Tino Cortesi
Tecniche di Analisi di Programmi
5
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” contemporaneamente
Il 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.
Tino Cortesi
Tecniche di Analisi di Programmi
7
1
Esempio
a:= 0;
2
b:= a+1;
a = 0;
do{
b= a+1;
c+=b;
a=b*2;
}
while (a<N);
return c;
3
c:= c+b;
4
a:= b*2;
5
a<N;
6
return c;
Tino Cortesi
Tecniche di Analisi di Programmi
8
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 4
Il comando 3 non assegna nulla a
b, quindi b è live anche nell’arco 2
3
Il comando 2 assegna un valore a
b. Questo significa che il valore di
b nell’arco 1 2 non è utilizzato
da nessuno in futuro
Quindi il “live range” di b è:
{2 3, 3 4}
Tino Cortesi
Tecniche di Analisi di Programmi
1
a:= 0;
2
b:= a+1;
3
c:= c+b;
4
a:= b*2;
5
a<N;
6
return c;
9
1
a:= 0;
a è live negli archi 4 5 e 5 2
La variabile a è live nell’arco 1 2
a non è live negli archi 2 3 4
2
b:= a+1;
3
c:= c+b;
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
4
a:= b*2;
5
a<N;
6
return c;
Tino Cortesi
Tecniche di Analisi di Programmi
10
1
a:= 0;
2
La variabile c è live sin dall’inizio
di questo programma: potrebbe
essere ad esempio un parametro
formale
c è 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)
Tino Cortesi
Tecniche di Analisi di Programmi
b:= a+1;
3
c:= c+b;
4
a:= b*2;
5
a<N;
6
return c;
11
1
1
a:= 0;
a:= 0;
2
2
b:= a+1;
b:= a+1;
3
3
c:= c+b;
c:= c+b;
4
4
a:= b*2;
a:= b*2;
5
5
a<N;
a<N;
6
6
return c;
return c;
Sono sufficienti 2 registri: le variabili a e b non sono mai vive
contemporaneamente
Tino Cortesi
Tecniche di Analisi di Programmi
12
Notazione
1
a:= 0;
Un grafo di flusso ha archi uscenti (outedges), 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.
2
b:= a+1;
3
c:= c+b;
4
a:= b*2;
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}
Tino Cortesi
Tecniche di Analisi di Programmi
5
a<N;
6
return c;
13
Notazione
1
Un assegnamento ad una variabile
definisce tale variabile
L’occorrenza di una variabile
nell’espressione a destra dell’operatore di
assegnamento usa tale variabile
def[n] è l’insieme di variabili che sono
definite nel nodo n
use[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}
Tino Cortesi
a:= 0;
2
b:= a+1;
3
c:= c+b;
4
a:= b*2;
5
a<N;
6
return c;
Tecniche di Analisi di Programmi
14
Formalizzazione
1
Una 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 2
a è live-in nel nodo 2, b non lo è.
c è live-out nel nodo 5
Tino Cortesi
Tecniche di Analisi di Programmi
a:= 0;
2
b:= a+1;
3
c:= c+b;
4
a:= b*2;
5
a<N;
6
return c;
15
Calcolare la Liveness
L’informazione di liveness (live-in e live-out) si può calcolare
nel modo seguente:
1.
2.
3.
Tino Cortesi
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
Se una variabile è live-in nel nodo n, allora è live-out per tutti i
nodi in pred[n]
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
Tecniche di Analisi di Programmi
16
Dataflow Equations
Se indichiamo con
in[n] l’insieme delle variabili che sono live-in nel nodo n
out[n] l’insieme delle variabili che sono live-out nel nodo n
possiamo esprimere le regole precedenti con due equazioni:
in[n] = use[n] U (out[n] - def[n])
2. out[n] = U { in[m] | m succ[n]}
1.
Tino Cortesi
Tecniche di Analisi di Programmi
17
Liveness Analysis
(una formalizzazione alternativa)
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)
Tino Cortesi
Tecniche di Analisi di Programmi
18
Algoritmo
Per ottenere una soluzione alle due equazioni precedenti si può
usare il seguente algoritmo:
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])
Tino Cortesi
Tecniche di Analisi di Programmi
19
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])
1
use def in
1
a
2 a
3 bc
4 b
5 a
6 c
Tino Cortesi
b
c
a
2
out in
a
bc
b
a
c
a
out
a
3
in
a:= 0;
2
b:= a+1;
3
c:= c+b;
out
a
a
bc
b
bc
b
a
ac
bc
b
bc
b
a
a
c
ac
ac
c
ac
Tecniche di Analisi di Programmi
1
4
a:= b*2;
5
a<N;
6
return c;
20
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])
3
use def in
1
a
4
out in
a
2 a
3 bc
4 b
ac
bc
b
bc
b
a
ac
c
ac
5 a
6 c
Tino Cortesi
b
c
a
a:= 0;
2
b:= a+1;
3
out
ac
5
in
c
out
ac
ac
bc
b
bc
b
ac
ac
bc
bc
bc
b
ac
ac
c
ac
ac
c
ac
Tecniche di Analisi di Programmi
1
c:= c+b;
4
a:= b*2;
5
a<N;
6
return c;
21
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])
5
use def in
1
a
c
6
out in
ac c
2 a
3 bc
4 b
ac
bc
bc
bc
b
ac
ac
c
ac
5 a
6 c
Tino Cortesi
b
c
a
a:= 0;
2
b:= a+1;
3
out
ac
7
in
c
out
ac
ac
bc
bc
bc
bc
ac
ac
bc
bc
bc
bc
ac
ac
c
ac
ac
c
ac
Tecniche di Analisi di Programmi
1
c:= c+b;
4
a:= b*2;
5
a<N;
6
return c;
22
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
use def in
6 c
Tino Cortesi
2
out in
c
3
out in
c
out
c
5 a
4 b
a
3 bc c
c
ac ac ac
ac bc ac bc
bc bc bc bc
ac ac
ac bc
bc bc
2 a
1
bc ac bc ac
ac c
ac c
bc ac
ac c
b
a
Tecniche di Analisi di Programmi
23
Backward Analysis
Dall’esempio è chiaro come la Liveness Analysis sia
un’analisi di tipo “backward”: l’informazione si
propaga dai nodi terminali del grafo al nodo iniziale.
Tino Cortesi
Tecniche di Analisi di Programmi
24
Rappresentare insiemi
Ci 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 bits
calcolare l’unione di due insiemi equivale alla “or” dei bits
corrispondenti ad ogni posizione
efficiente se gli insiemi sono densi
liste ordinate
un 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
duplicati
efficiente se gli insiemi sono sparsi
Tino Cortesi
Tecniche di Analisi di Programmi
25
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])
Time-Complexity
Diciamo 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 elementi
Ogni 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)
Tino Cortesi
Tecniche di Analisi di Programmi
26
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])
Time Complexity
Ogni 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 iterazioni
Quindi 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).
Tino Cortesi
Tecniche di Analisi di Programmi
27
Approssimazione Conservativa
in[n] = use[n] U (out[n] - def[n])
2.
out[n] = U { in[m] | m succ[n]}
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 è.
1.
X
use
1
Tino Cortesi
Y
Z
def
in
out
in
out
in
out
a
c
ac
cd
acd
c
ac
2
a
b
ac
bc
acd
bcd
ac
b
3
bc
c
bc
bc
bcd
bcd
b
b
4
b
a
bc
ac
bcd
acd
b
ac
5
a
ac
ac
acd
acd
ac
ac
6
c
c
c
Tecniche di Analisi di Programmi
c
28
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”.
Tino Cortesi
Tecniche di Analisi di Programmi
29
Soluzione Minima
Abbiamo visto che il sistema di equazioni
1.
in[n] = use[n] U (out[n] - def[n])
2.
out[n] = U { in[m] | m succ[n]}
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.
Tino Cortesi
Tecniche di Analisi di Programmi
30
Uso dell’analisi
L’informazione di liveness è utilizzata per diversi tipi
di ottimizzazioni nei compilatori
Dead code elimination
ad es. rimozione di un comando che assegna un valore ad
una variabile che non viene utilizzata prima di essere
riassegnata
Code motion
ad es. spostamento di un comando che assegna variabili che
non vengono utilizzate in una porzione di codice
Register Allocation
una 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
Tino Cortesi
Tecniche di Analisi di Programmi
31
Grafo di interferenza
Una 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 flusso
Ad 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
c
a
x
b
x
c
Tino Cortesi
b
x
b
a
c
x
Tecniche di Analisi di Programmi
32
Esercizio
Analizzare 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.
2.
3.
4.
5.
6.
7.
8.
Tino Cortesi
m:=0
v:=0
if (v>=n) goto 15
r:=v
s:=0
if (r<n) goto 9
v:= v+1
goto 3
9.
10.
11.
12.
13.
14.
15.
Tecniche di Analisi di Programmi
x:=M[r]
s:=s+x
if (s<=m) goto 13
m:= s
r:= r+1
goto 6
return m
33
Esercizio
Verificare, 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);
Tino Cortesi
y = 1;
repeat {
x = x + 1;
y = x;
} until (x > 10);
print(y);
Tecniche di Analisi di Programmi
34
Esercizio
Modificare 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
assegnamento
La variabile x è dead dopo il terzo ed il quinto
La variabile x è live dopo il primo assegnamento.
Tino Cortesi
Tecniche di Analisi di Programmi
35
Esempio
1
use
1
def LVin
LVout
DVin
DVout
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
abce ace
d
bd
7
c
c
abde abcde
d
FAin
FAout
a:= 0;
2
b:= a+1;
3
c:= c+b;
4
a:= b*2;
5
a<N;
6
7
return c;
Tino Cortesi
Tecniche di Analisi di Programmi
d:= b*e;
36
Esercizio
La 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
Tino Cortesi
Tecniche di Analisi di Programmi
37
Esercizio
La 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
Tino Cortesi
Tecniche di Analisi di Programmi
38