TECNICHE DI COMPILAZIONE AVANZATA
PROGRAMMA DEFINITIVO - A.A. 1999-00
Parte prima: Metodologie di analisi
- Analisi locali: definizione di basic block; partizionamento
del codice intermedio in basic blocks; definizione di ottimizzazioni a
livello di basic block; tecnica del value numbering [appunti del corso]
- Analisi data-flow globali: definizione di analisi data-flow:
il linguaggio while [NNH 1.1,1.2,1.3.1]; esempi: live variables, reaching
definitions, very busy expression, available expressions [NNH 2.1]
-
- Una metodologia per l'analsi data-flow: richiami di teoria
dei reticoli [NNH A1, A.3, A.4]; proprietà generali delle analisi:
monotonia, distributività [NNH 2.3]; risoluzione delle equazioni
data flow: la soluzione MFP [NNH 2.4.1]; qualità della soluzione;
la soluzione MOP [NNH 2.4.2]; operatori per accellerare la convergenza:
widening, narrowing [NNH 4.2]
-
- Impementazione di analisi data-flow: algoritmi work-list [NNH
6.1], criteri di scheduling dei nodi: reverse-postorder [NNH 6.2], round
robin [NNH 6.2.1], componenti connesse [NNH 6.3]; complessità della
analisi: analisi fast, rapide [NNH 6.2.1]
-
- PAG: uno strumento per la generazione automatica di analizzatori statici:
definizione dei domini, il linguaggio di specifica FULA
- Trasformazione di programmi in forma Static Single Assignment:
dominatori, frontiera dei dominatori, determinazione della forma SSA [A
19.1, 19.3]
Parte seconda: Tecniche di ottimizzazione
- Tecniche globali per la allocazione dei registri: tecniche
basate sulla colorazione di grafi. [A 11 escluso 11.5]
- Ottimizzazioni di costrutti iterativi basate su analisi
data flow: strength reduction, invariant code motion, loop unswitching
[BGS 6.1, A. 18]
- Ottimizzazioni di costrutti iterativi basate su analisi
delle dipendenze: esempi di trasformazioni per diverse classi di architetture:
aumento della località, parallelizzazione per architetture vettoriali,
architetture a memoria condivisa e distribuita [W 1]
- Analisi delle dipendenze: tipi di dipendenza, rappresentazione
delle dipendenze; vettori distanza e direzione; test di dipendenza: Il
GCD test, il test sui valori estremi [BGS5]
- Ottimizzazione dell'uso della gerarchia di memoria: allocazione
di registri a variabili indicizzate: scalar replacement [BGS 6.5.4]; ottimizzazione
dell'uso del cache istruzioni: prefetching, code colocation [BGS 6.5.5];
ottimizzazione del cache dati: loop interchange, [BGS 6.2.1]; loop tiling
[BGS6.2.6]; loop fusion [BGS 6.2.8] loop distribution [BGS 6.2.7]; tecniche
basate sulla modifica della allocazione dei dati in memoria : array padding
[BGS 6.5.1]
Modalità di esame Progetto + orale (l'orale comprende la
discussione del progetto + il programma del corso)
Materiale Didattico
Parte prima:
[NNH] Flemming Nielson, Hanne Riis Nielson, Chris Hankin "Principles
of program Analysis" Springer, Ottobre 1999.
[TMA] S. Thesing, F. Martin, M. Alt, PAG user's Manual, Version
1.0, Settembre 1998. Reperibile in /usr/local/PAG/DOCU (paperino.di.unipi.it)
Parte seconda:
[A] A.Appel "Modern compiler implementation in Java"
Cambridge University Press, 1998.
[BGS] D.Bacon, S. Graham, O. Sharp "Compiler Transformation
for High-Performance Computing" ACM Computing surveys, Vol. 26,
No. 4, Dicembre 1994.
[W] M. Wolfe "High performance Compilers for Parallel Computing",
1996, Addison-Wesley.
Testi di consultazione
Aho, Sethi, Ullman "Compilers: Principles, Techniques and Tools",
Addison-Wesley.
Robert Morgan "Building an Optimizing Compiler", 1998,
Digital Press.