Analisi Interprocedurale
Chiamata di procedura
Le tecniche di analisi dataflow viste finora non consideravano
chiamate di funzioni o procedura: sono analisi intraprocedurali.
Si parla di analisi interprocedurale quando si tengono in
considerazione anche chiamate di procedure e funzioni
Consideriamo chiamate di procedura del tipo:
[call p(a,z)]lclr
dove:
a è un parametro di ingresso
z è un parametro di output
lc è l’etichetta che segna l’ingresso della procedura p
lr è l’etichetta che segna l’uscita dalla procedura p
Tino Cortesi
Tecniche di Analisi di Programmi
2
Flusso
Nell’analisi intraprocedurale abbiamo usato il termine “flusso” per
denotare insiemi di coppie di etichette (archi del grafo).
Consideriamo la chiamata
[call p(a,z)]lclr
dove la procedura p è definita da
proc p(val x, res y) islin S endlout;
Nel grafo di flusso interprocedurale bisognerà considerare due archi
particolari:
(lc; lin) è il flusso che corrisponde alla chiamata di una procedura in
lc, dove lin è il punto di entrata nel corpo della procedura chiamata
(lout; lr) è il flusso che corrisponde all’uscita dal corpo della
procedura in lout, ed al ritorno del controllo alla procedura
chiamante (nel punto lr).
Tino Cortesi
Tecniche di Analisi di Programmi
3
Esempio
La dichiarazione di una procedura è del tipo
proc p(val x, res y) islin S endlout;
proc fib(val: z,u; res: v) is1
if [z<3]2
then [v:=u+1]3
else
[call fib(z-1,u,v)]45 ; [call fib(z-2,v,v)]67
end8;
[call fib(x,0,y)]910
Tino Cortesi
Tecniche di Analisi di Programmi
4
Grafo di flusso (animazione)
is
[call fib(x,0,y)]910
1
[z<3]2
[call fib(z-1,u,v)]45
[v:=u+1]3
[call fib(z-2,v,v)]67
end8
Tino Cortesi
Tecniche di Analisi di Programmi
5
Grafo di flusso
is
[call fib(x,0,y)]910
1
[z<3]2
[call fib(z-1,u,v)]45
[v:=u+1]3
[call fib(z-2,v,v)]67
end8
Tino Cortesi
Tecniche di Analisi di Programmi
6
Equazioni dell’analisi (naif)
Una formulazione naif delle equazioni di analisi dataflow
potrebbe essere una semplice estensione di quella formulata per
l’analisi intraprocedurale:
i
se l E
GA(l)=
lub { GA(l’) | (l’, l)  F o (l’; l)  F} altrimenti
GA(l)= fl ( GA(l) )
Tino Cortesi
Tecniche di Analisi di Programmi
7
Cammini non percorribili
Poiché consideriamo tutti i possibili flussi (l’, l)  F o (l’; l)  F
l’analisi risulta essere corretta.
Ma niente ci impedisce nell’analisi di considerare il cammino
[9, 1, 2, 4, 1, 2, 3, 8, 10] che non corrisponde a nessuna
esecuzione del programma. L’analisi risulterebbe poco precisa!
Tino Cortesi
Tecniche di Analisi di Programmi
8
Cammini non percorribili
is
[call fib(x,0,y)]910
1
[z<3]2
[call fib(z-1,u,v)]45
[v:=u+1]3
[call fib(z-2,v,v)]67
end8
Il cammino [9, 1, 2, 4, 1, 2, 3, 8, 10] non corrisponde a
nessuna esecuzione del programma
Tino Cortesi
Tecniche di Analisi di Programmi
9
Inter-flusso
Definiamo il concetto di flusso interprocedurale:
inter-flusso = {(lc, lin ,lout ,lr) | il programma P contiene
sia [call p(a,z)]lclr
che proc p(val x, res y) islin S endlout
}
Tino Cortesi
Tecniche di Analisi di Programmi
10
Flusso e inter-flusso
is
[call fib(x,0,y)]910
1
[z<3]2
[call fib(z-1,u,v)]45
[v:=u+1]3
[call fib(z-2,v,v)]67
end8
flusso =
{(1,2), (2,3), (2,4), (3,8), (4;1), (5,6), (6;1), (7,8),
(8;5), (8;7), (8;10), (9;1)}
inter-flusso= {(9,1,8,10), (4,1,8,5), (6,1,8,7)}
Tino Cortesi
Tecniche di Analisi di Programmi
11
Rendere esplicito il contesto
Per estendere il Framework Generale all’analisi interprocedurale
dovremo:
codificare l’informazione sui cammini (contesto)
estendere lo spazio delle proprietà al contesto
estendere le funzioni di transfer introducendo in particolare
due funzioni di trasfer in corrispondenza di ogni flusso
interprocedurale (lc, lin ,lout ,lr)
Tino Cortesi
Tecniche di Analisi di Programmi
12
Rendere esplicito il contesto
Data un’istanza (L, F, F, E, i, f) del framework monotono,
costruiamo una istanza del framework monotono arricchito che
tiene in considerazione il contesto:
(L, F, F, E, i, f ), dove
L=DL
( ad es. D= codifica dei cammini)
le funzioni di transfer in F sono monotone
la funzione f mappa etichette in F e E in funzioni di transfer
in F :
per ogni l in E o F, d in L e ogni d in D, la funzione di trasfer fl è
definita da:
fl (d)(d) = fl (d(d))
Tino Cortesi
Tecniche di Analisi di Programmi
13
Il frammento intraprocedurale
EA(l)= fl ( EA(l) )
per tutte le etichette l che non sono etichette
di una chiamata di procedura, ovvero che non
compaiono come primo o quarto elemento di
una tupla
EA(l)=
{ EA(l’) | (l’, l)  F o (l’; l) F}
i lE
per tutte le etichette l, incluse quelle che sono
etichette di una chiamata di procedura
Tino Cortesi
Tecniche di Analisi di Programmi
14
Il frammento interprocedurale
Restano da formulare le equazioni relative alle chiamate di procedura.
In corrispondenza di ogni dichiarazione di procedura del tipo
proc p(val x, res y) islin S endlout
abbiamo due funzioni di transfer:
flin , flout: (D  L)  (D  L)
che possono essere ad es. l’identità: flin(d) = flout(d) = d
Tino Cortesi
Tecniche di Analisi di Programmi
15
Il frammento interprocedurale
In corrispondenza ad ogni chiamata di procedura (interflusso)
(lc, lin ,lout ,lr)
abbiamo due funzione di transfer:
flc(d): (D  L)  (D  L)
flc,lr(d,d’): (D  L)  (D  L)  (D  L)
E per ogni inter-flusso (lc, lin ,lout ,lr) avremo in più le equazioni
EA(lc)= flc( EA(lc) )
EA(lr)= flc,lr( EA(lc), EA(lr) )
Tino Cortesi
Tecniche di Analisi di Programmi
16
Chiamata di procedura
proc p(val x, res y)
flc(d)
d
islin
[call p(a,z)]lclr
d
d’
endlout
flc,lr(d,d’)
Tino Cortesi
Tecniche di Analisi di Programmi
17
Peephole Optimizations
guardando dallo spioncino...
Un modo relativamente semplice per migliorare la
qualità del codice nativo prodotto da un compilatore
semplice è quello di far girare un peephole optimizer.
Un peephole optimizer lavora considerando una
finestrella di alcune istruzioni alla ricerca di istruzioni
subottimali equivalenti.
L’insieme dei patterns da osservare sono in gran
parte frutto di euristiche
Tino Cortesi
Tecniche di Analisi di Programmi
19
Esercizio
ognuno dei seguenti frammenti di codice può essere ottimizzato.
in quale codice lo trasformereste?
che nome dareste a queste trasformazioni? (ce ne sono di 6 tipi!)
quali analisi dataflow potrebbero supportarle?
1.
2.
3.
4.
r2:= 3 * 2
r2:= 4
r3:= r1 + 2
r2:= 2 * r3
r2:= 4
r3:= r1 + r2
r3:= *r3
(assumendo r2 dead)
r1:=3
r2:= r1*2
Tino Cortesi
5.
6.
7.
8.
r2:= r1 * 5
r2:= r2 + r3
r3:= r1 * 5
r2:= r1
r3:= r1 + r2
r2:= 5
r1:= r2 * 2
r3:= r4 / 2
r1:= r1 + 0
r2 := r2 * 1
Tecniche di Analisi di Programmi
9.
r2:= r1 + 5
i := r2
r3:= i
r4:=r3 * 3
20
Constant Folding
il peephole optimizer può spesso accorgersi che alcuni calcoli
richiesti a tempo di esecuzione possono essere realizzati a
tempo di compilazione
r2:= 3 * 2
Tino Cortesi
diventa
Tecniche di Analisi di Programmi
r2:=6
21
Constant Propagation
A volte possiamo dire che una variabile in un certo punto del
programma avrà sempre un certo valore costante. Possiamo
quindi sostituire le occorrenze della variabile con occorrenze di
tale costante
r2:= 4
r3:= r1 + r2
r2:= 2 * r3
Tino Cortesi
diventa
r2:=4
r3:=r1+4
r2:= 2*r3
Tecniche di Analisi di Programmi
diventa r3:=r1+4
r2:= 2*r3
22
Constant Propagation
r2:= 4
r3:= r1 + 4
r3:= r1 + r2
diventa r3:= *r3
r3:= *r3
(assumendo che r2 sia dead)
r1:=3
r2:= r1*2
Tino Cortesi
diventa r1:= 3
r2:= 3*2
Tecniche di Analisi di Programmi
diventa r3:= *(r1+4)
diventa r1:= 3
r2:= 6
23
Common Subexpression Elimination
Quando la stessa espressione viene calcolata più di una volta
nello spioncino dell’ottimizzatore, si può spesso eliminare la
seconda computazione
r2:= r1 * 5
r2:= r2 + r3
r3:= r1 * 5
Tino Cortesi
diventa
Tecniche di Analisi di Programmi
r4:= r1*5
r2:= r4 + r3
r3:= r4
24
Copy Propagation
Anche quando non si può dire che il contenuto di una variabile
sarà costante, si può osservare talvolta che la variabile b
contiene sempre lo stesso valore della variabile a. In questo
caso si può rimpiazzare l’uso di b con la variabile a fino a che né
a né b vengono modificate
r2:= r1
r3:= r1 + r2
r2:= 5
Tino Cortesi
r2:= r1
diventa r3:= r1+r1 diventa r3:= r1+r1
r2:= 5
r2:= 5
Tecniche di Analisi di Programmi
25
Strenght Reduction
Alcune istruzioni aritmetiche sono più “costose” di altre (ad
esempio la moltiplicazione o la potenza rispetto all’addizione), e
possono essere sostituite da operazioni meno costose. In
particolare, la moltiplicazione e la divisione per potenze di 2
possono essere rimpiazzate, rispettivamente, con addizioni e
shifts:
r1:= r2 * 2
diventa
r1:= r2 + r2
r3:= r4 / 2
diventa
r3 >> 1
Tino Cortesi
Tecniche di Analisi di Programmi
26
Eliminazione di codice inutile
Istruzioni come le seguenti possono essere tout court
eliminate:
r1:= r1 + 0
r2 := r2 * 1
Tino Cortesi
diventa
Tecniche di Analisi di Programmi

27
Loads e stores ridondanti
il peephole optimizer può spesso accorgersi che il valore
prodotto da una istruzione di load è già disponibile in un registro
r2:= r1 + 5
i := r2
r3:= i
r4:=r3 * 3
Tino Cortesi
diventa
Tecniche di Analisi di Programmi
r2:=r1+5
i:= r2
r4:= r2 * 3
28
D = Stringhe di chiamata
Per completare l’analisi di un programma rimane da specificare
l’insieme D che contiene l’informazione di contesto, ed il valore
iniziale i.
Ad esempio, possiamo prendere D = Lab* i cui valori sono
sequenze di etichette.
Per ogni tupla di inter-flusso (lc, lin ,lout ,lr)
flc(d)([d, lc])= flc(d(d))
dove [d,lc] denota il cammino ottenuto appendendo lc a d
e flc : L L specifica come la proprietà viene modificata.
flc,lr(d,d’)(d)= flc,lr(d(d), d’([d,lc]))
e flc,lr : LL L permette di combinare l’informazione d di
contesto con d’ .
Tino Cortesi
Tecniche di Analisi di Programmi
29
Analisi dei segni
Consideriamo un’analisi volta a determinare il segno delle
variabili intere.
Possiamo considerare il seguente dominio Sign:{-,0,+}
Possiamo considerare il reticolo
L = (Var  Sign)
che descrive insiemi di stati astratti s che mappano variabili nei
loro segni possibili
Ad esempio, se Var={x,y}, un elemento di L può essere
s= { {x+, y+}, {x-, y-}}
che dice “le variabili x e y sono entrambe positive oppure
entrambe negative”
Tino Cortesi
Tecniche di Analisi di Programmi
30
Funzioni di transfer
La funzione di transfer fl quando l è un comando di
assegnamento del tipo [x:= a]l può essere scritta come:
fl (Y) = { fl (s) | s Y}
dove
Y (Var  Sign)
fl (s) = {s[x/s] | s A[a](s)}
A: AExp  (Var  Sign)  (Sign)
A specifica l’analisi di espressioni aritmetiche
Per esercizio, specificare completamente l’analisi dei segni
(intraprocedurale e interprocedurale)
Tino Cortesi
Tecniche di Analisi di Programmi
31
Esercizio
Specificare nei dettagli l’analisi dei segni, a partire dagli esempi
2.36 e 2.38 del libro Nielson - Nielson - Hankin (pag. 89-95),
modificando in modo opportuno le equazioni della Constant
Propagation Analysis
Analizzare l’esempio di analisi interprocedurale di Constant
Propagation dell’analizzatore PAG/WWW
Tino Cortesi
Tecniche di Analisi di Programmi
32