Analisi Interprocedurale. Tino CortesiTecniche di Analisi di Programmi 2 Chiamata di procedura Le...

Analisi Interprocedurale

Tino Cortesi Tecniche di Analisi di Programmi 2

Chiamata di proceduraLe 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 outputlc è l’etichetta che segna l’ingresso della procedura p

lr è l’etichetta che segna l’uscita dalla procedura p


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


EsempioLa 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)]4

5 ; [call fib(z-2,v,v)]67

end8;[call fib(x,0,y)]9

10


Grafo di flusso (animazione)

[call fib(x,0,y)]9

10

[call fib(z-2,v,v)]6

7

[call fib(z-1,u,v)]4

5

end8

[v:=u+1]3

[z<3]2

is 1


Grafo di flusso

[call fib(x,0,y)]9

10


7


5

end8

[v:=u+1]3

[z<3]2

is 1


Equazioni dell’analisi (naif)Una formulazione naif delle equazioni di analisi dataflow potrebbe essere una semplice estensione di quella formulata per l’analisi intraprocedurale:

se l E GA(l)=

lub { GAœ(l’) | (l’, l) F o (l’; l) F} altrimenti

GAœ(l)= fl ( GA(l) )


Cammini non percorribiliPoiché 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!


Cammini non percorribili

[call fib(x,0,y)]9

10


7


5

end8

[v:=u+1]3

[z<3]2

is 1

Il cammino [9, 1, 2, 4, 1, 2, 3, 8, 10] non corrisponde a nessuna esecuzione del programma


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

}


Flusso e inter-flusso

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

[call fib(x,0,y)]9

10



end8

[v:=u+1]3

[z<3]2

is 1


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 contestoestendere le funzioni di transfer introducendo in particolare due funzioni di trasfer in corrispondenza di ogni flusso interprocedurale (lc, lin ,lout ,lr)


Rendere esplicito il contesto

Data un’istanza (L, F, F, E, , f) del framework monotono, costruiamo una istanza del framework monotono

arricchito che tiene in considerazione il contesto: (L, F, F, E, , f ), dove

L = L ( ad es. = 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 in , la funzione di trasfer fl è definita da: fl (d)() = fl (d())


Il frammento intraprocedurale

EAœ(l)= fl ( EA(l) )per tutte le etichette l che non sono

etichettedi una chiamata di procedura, ovvero che

non compaiono come primo o quarto

elemento diuna tupla

EA(l)= { EAœ(l’) | (l’, l) F o (l’; l) F} lE

per tutte le etichette l, incluse quelle che sono etichette di una chiamata di procedura


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: ( L) ( L)

che possono essere ad es. l’identità: flin(d) = flout(d) = d


Il frammento interprocedurale

In corrispondenza ad ogni chiamata di procedura (interflusso)(lc, lin ,lout ,lr)

abbiamo due funzione di transfer:

flc(d): ( L) ( L)

flc,lr(d,d’): ( L) ( L) ( 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) )


Chiamata di procedura

[call p(a,z)]lclr

proc p(val x, res y)

islin

endlout

flc,lr(d,d’)

d

d

d’

flc(d)

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


Esercizio

1. r2:= 3 * 2

2. r2:= 4r3:= r1 + 2r2:= 2 * r3

3. r2:= 4r3:= r1 + r2r3:= *r3(assumendo r2 dead)

4. r1:=3r2:= r1*2

5. r2:= r1 * 5r2:= r2 + r3r3:= r1 * 5

6. r2:= r1r3:= r1 + r2r2:= 5

7. r1:= r2 * 2 r3:= r4 / 2

8. r1:= r1 + 0r2 := r2 * 1

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?9. r2:= r1 + 5

i := r2r3:= ir4:=r3 * 3


Constant Foldingil peephole optimizer può spesso accorgersi che alcuni calcoli richiesti a tempo di esecuzione possono essere realizzati a tempo di compilazione

r2:= 3 * 2 diventa r2:=6


Constant PropagationA 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 r2:=4r3:= r1 + r2 diventa r3:=r1+4 diventa r3:=r1+4 r2:= 2 * r3 r2:= 2*r3 r2:= 2*r3


Constant Propagationr2:= 4 r3:= r1 + 4r3:= r1 + r2 diventa r3:= *r3 diventa r3:=

*(r1+4)r3:= *r3(assumendo che r2 sia dead)

r1:=3 diventa r1:= 3 diventa r1:= 3

r2:= r1*2 r2:= 3*2 r2:= 6


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 r4:= r1*5r2:= r2 + r3 diventa r2:= r4 + r3r3:= r1 * 5 r3:= r4


Copy PropagationAnche 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 r2:= r1r3:= r1 + r2 diventa r3:= r1+r1 diventa r3:= r1+r1r2:= 5 r2:= 5 r2:= 5


Strenght ReductionAlcune 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


Eliminazione di codice inutile

Istruzioni come le seguenti possono essere tout court eliminate:

r1:= r1 + 0 diventa r2 := r2 * 1


Loads e stores ridondantiil peephole optimizer può spesso accorgersi che il valore prodotto da una istruzione di load è già disponibile in un registro

r2:= r1 + 5 r2:=r1+5i := r2 diventa i:= r2r3:= i r4:= r2 * 3r4:=r3 * 3


= Stringhe di chiamata Per completare l’analisi di un programma rimane da specificare l’insieme che contiene l’informazione di contesto, ed il valore iniziale .Ad esempio, possiamo prendere = Lab* i cui valori sono sequenze di etichette.Per ogni tupla di inter-flusso (lc, lin ,lout ,lr)

flc(d)([, lc])= flc(d())

dove [,lc] denota il cammino ottenuto appendendo lc a e flc : L L specifica come la proprietà viene modificata.

flc,lr(d,d’)()= flc,lr(d(), d’([lc]))

e flc,lr : LL L permette di combinare l’informazione d di contesto con d’ .


Analisi dei segniConsideriamo 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 che mappano variabili nei loro segni possibili

Ad esempio, se Var={x,y}, un elemento di L può essere= { {x+, y+}, {x-, y-}}

che dice “le variabili x e y sono entrambe positive oppure entrambe negative”


Funzioni di transferLa funzione di transfer fl quando l è un comando di assegnamento del tipo [x:= a]l può essere scritta come:

fl (Y) = { l () | Y} dove

Y (Var Sign)l () = {[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)


EsercizioSpecificare 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

Analisi Interprocedurale. Tino CortesiTecniche di Analisi di Programmi 2 Chiamata di procedura Le...

Documents

Transcript of Analisi Interprocedurale. Tino CortesiTecniche di Analisi di Programmi 2 Chiamata di procedura Le...