Wikipedia

Compilatore con ottimizzatore

compilatore che effettua automaticamente l'ottimizzazione di un programma

Il compilatore con ottimizzatore o compilatore ottimizzante è un compilatore che effettua automaticamente l'ottimizzazione di un programma durante il processo di compilazione. Considerando un'architettura a tre stadi di un compilatore, come quella di LLVM, ciò implica che negli stadi middle-end e/o back-end vengono effettuati passaggi atti a migliorare il codice compilato prodotto. Nel caso di un'architettura a due stadi (solo front-end e back-end) le ottimizzazioni vengono considerate parte del back-end.[1]

Schema a tre stadi di un compilatore. Le ottimizzazioni target-independent vengono effettuate nel middle-end, quelle target-dependent nel back-end.

Effettuare ottimizzazioni durante la compilazione di un programma è importante al fine di sopperire alle inefficienze derivanti dalla traduzione di costrutti di alto livello in rappresentazione intermedia o in codice macchina (lowering). Queste inefficienze possono essere semplici ridondanze nel codice, oppure caratteristiche più profonde che riducono la parallelizzabilità del programma o altre caratteristiche di efficienza.[2]

Storia modifica

I primi compilatori capaci di effettuare ottimizzazioni risalgono alla seconda metà degli anni sessanta. Ad esempio, il compilatore IBM FORTRAN H, disponibile commercialmente nel 1969, e il compilatore Alpha, sviluppato nel 1966, vengono considerati i primi compilatori di questo genere. La struttura a passi e le analisi e le ottimizzazioni più semplici sono state introdotte in questo stesso periodo.[3]

Il compilatore GCC, introdotto nel 1987[4], e Clang, basato su LLVM e introdotto nel 2007[5] sono entrambi compilatori ottimizzanti.[6][7]

Architettura e classi di ottimizzazioni modifica

Le ottimizzazioni si classificano in ottimizzazioni target-independent (dipendenti dal target) o target-dependent (indipendenti dal target).[8] Le ottimizzazioni target-dependent operano su proprietà generali del codice, e quindi non richiedono conoscenza dell'architettura su cui verrà eseguito il codice compilato. Pertanto, possono essere effettuate direttamente sulla rappresentazione intermedia. Al contrario, le ottimizzazioni target-dependent sono efficaci solo su una o più piattaforme target specifiche; devono quindi essere effettuate durante lo stadio di generazione del codice target.[1]

Ogni ottimizzazione costituisce un sottoprogramma a sé stante, chiamato passo di compilazione.[9] Il compilatore decide in base alle flag di compilazione quali ottimizzazioni eseguire.[10] Questa decisione può essere presa anche in base a dati sull'esecuzione del programma; in tal caso si parla di profile-guided optimization.[11]

Gli algoritmi di trasformazione del programma implementati nelle ottimizzazioni talvolta necessitano di effettuare un'analisi preliminare del codice per individuare dove l'ottimizzazione può essere applicata. Queste analisi sono spesso comuni a più ottimizzazioni, quindi vengono separate dall'ottimizzazione stessa per evitare duplicazione di codice e operazioni di ricalcolo superflue. Di conseguenza si parla anche di passi di analisi.[12][13]

È possibile classificare le ottimizzazioni in base alla loro funzione, in base alle analisi su cui sono basate, oppure in base alla località dell'ottimizzazione. In particolare, rispetto alla località dell'ottimizzazione si parla di:[14]

  • Ottimizzazioni peep-hole (ottimizzazioni che operano su una quantità limitata di istruzioni adiacenti)
  • Ottimizzazioni locali (ottimizzazioni che operano all'interno di un singolo basic-block)
  • Ottimizzazioni intra-procedurali[15] (ottimizzazioni che operano all'interno della stessa procedura)
  • Ottimizzazioni inter-procedurali[15] (ottimizzazioni che influenzano più di una procedura)
  • Whole-program optimization[16] (ottimizzazioni che influenzano l'intero programma)

Nei linguaggi di programmazione dove il programma è diviso in multiple compilation unit (unità di compilazione) come C e C++ le ottimizzazioni inter-procedurali e whole-program possono essere effettuate dal linker. In questo caso di parla di link-time optimization.[17]

Ottimizzazioni SSA e non-SSA modifica

Le rappresentazioni intermedie single static assignment (o SSA) sono rappresentazioni intermedie dove ogni variabile temporanea viene definita una volta sola all'interno del listato della rappresentazione intermedia. Hanno il vantaggio di essere più semplici da analizzare, ma mantenere la proprietà che le definisce rende necessario l'uso di algoritmi di trasformazione del codice più complessi.[18]

Ai fini dell'ottimizzazione dei programmi, le rappresentazioni SSA rendono alcune analisi e ottimizzazioni ridondanti, perché la proprietà SSA è sufficiente per effettuarle implicitamente.[18]

Ottimizzazioni target-independent modifica

Nel seguito vengono elencate alcune ottimizzazioni di importanza generale indipendenti dal target, in base a una classificazione che prioritizza la funzione rispetto all'analisi utilizzata e alla località.

Ottimizzazioni di ciclo modifica

Le ottimizzazioni di ciclo sono quelle ottimizzazioni che operano sui cicli. In generale sono basate sull'analisi del data flow e sul dominator tree per individuare quali basic block costituiscono il ciclo.[19]

Queste ottimizzazioni spesso operano sulle variabili di induzione, o induction variables. Una variabile è di induzione se e solo se rispetta una delle seguenti proprietà:[20]

  1. All'interno del ciclo viene definita come somma algebrica di se stessa con una variabile invariante di ciclo, cioè costante durante l'esecuzione del ciclo (variabile di induzione di base)
  2. All'interno del ciclo viene definita a partire da un'altra variabile di induzione tramite moltiplicazione o somma algebrica con una variabile invariante di ciclo (variabile di induzione derivata)

I contatori di un ciclo sono variabili di induzione, quindi questa definizione permette di effettuare analisi e ottimizzazioni su di essi.[20]

Loop hoisting o Loop invariant code motion
Sposta delle istruzioni che definiscono delle variabili invarianti nel corso del ciclo al di fuori del ciclo stesso.[21]
Strength reduction
Semplifica le variabili calcolate a partire dalla variabile di induzione del ciclo moltiplicandola per un fattore costante, modificandole in addizioni.[22]
Loop unrolling
"Srotola" un ciclo, duplicandone il corpo tante volte quante viene eseguito il ciclo. Riduce l'overhead di calcolo della variabile di induzione del ciclo stesso.[23]
Loop interchange
Nel caso di due o più cicli innestati, inverte un ciclo interno con un ciclo esterno. Permette di migliorare la località degli accessi alla memoria, ad esempio quando il ciclo esegue accessi a matrici.[24]

Ottimizzazioni sul data-flow modifica

Queste ottimizzazioni operano modificando il data flow (flusso dei dati) di un programma, cioè la sequenza di istruzioni nella rappresentazione intermedia necessaria a calcolare una o più variabili.[25][26]

Common subexpression elimination
Se due espressioni condividono una stessa sotto-espressione, questa viene condivisa tra le due.[27][26]
Constant propagation o Constant folding
Se un'espressione è composta solamente da operandi costanti, il suo valore viene calcolato durante la compilazione.[28][26]
Copy propagation
Se una variabile viene assegnata a un'altra nella rappresentazione intermedia, tutti gli usi successivi della seconda variabile vengono sostituiti con usi della prima. In una rappresentazione non-SSA, questa operazione deve essere limitata fino a che la prima o la seconda variabile non vengono definite di nuovo. In una rappresentazione SSA questo non è necessario.[26]
Dead code elimination
Questa ottimizzazione elimina quelle istruzioni che effettuano calcoli che non vengono mai utilizzati.[29] È possibile rendere questa ottimizzazione più aggressiva sfruttando le informazioni derivate dal control flow graph.[30][31]

Ottimizzazioni target-dependent modifica

Mentre le ottimizzazioni target-independent vengono effettuate nel middle-end per migliorare proprietà di importanza generale, le ottimizzazioni target-dependent sono effettuate nel back-end per permettere al programma di sfruttare caratteristiche specifiche dell'architettura target. Queste caratteristiche possono essere ad esempio l'utilizzo di istruzioni per il parallelismo Single instruction multiple data (SIMD).[1]

Instruction scheduling
Le istruzioni del codice macchina vengono riordinate per migliorarne la parallelizzabilità in un'architettura con pipeline, superscalare o di tipo Very long instruction word.[32]
Register allocation
Le variabili temporanee nella trasformazione intermedia vengono associate a uno o più registri della architettura target, se possibile, invece di allocarle nella memoria centrale.[33]

Passi di analisi modifica

Alcune delle ottimizzazioni sopra menzionate necessitano di analizzare il codice per raccogliere le informazioni necessarie per poterlo modificare. Nel seguito elenchiamo alcune di queste analisi.[12]

Liveness analysis
Questa analisi calcola in quali intervalli di codice ogni variabile (anche detto registro virtuale) della rappresentazione intermedia è in uso. Una variabile è in uso se è stata definita (cioè se le è stato assegnato un valore) e se è possibile che verrà utilizzata in futuro.[34]
Reaching definitions
Calcola quale istruzione nella rappresentazione intermedia ha definito il valore di un certo registro virtuale utilizzato da un'altra istruzione. Questa analisi è fondamentale nei compilatori che non utilizzano la rappresentazione SSA.[35]
Costruzione del Dominator tree
Questa analisi consente di distinguere se una istruzione della rappresentazione intermedia è dominata da un'altra. Un'istruzione è dominata da un'altra se in qualsiasi traccia di esecuzione del programma per raggiungere la prima istruzione è necessario prima eseguire la seconda.[36]
Pointer-alias analysis
Individua se un puntatore può costituire riferimento alla stessa area di memoria di un altro puntatore. Non è possibile effettuare questa analisi con precisione in alcuni linguaggi di programmazione (ad esempio C) perché consentono calcoli arbitrari sui puntatori.[37]

Note modifica

  1. ^ a b c Aho, Lam, Sethi, Ullman, p. 5.
  2. ^ (EN) Monica S. Lam, "Advanced Compilers Course Introduction" (PDF), su suif.stanford.edu. URL consultato il 25 giugno 2020 (archiviato dall'url originale il 12 febbraio 2020).
  3. ^ Aho, Lam, Sethi, Ullman, pp. 703-704.
  4. ^ (EN) A Brief History of GCC, su gcc.gnu.org. URL consultato il 26 giugno 2020.
  5. ^ (EN) LLVM 2.1 Release Notes, su releases.llvm.org. URL consultato il 26 giugno 2020.
  6. ^ (EN) GCC Development Mission Statement (1999-04-22), su gcc.gnu.org. URL consultato il 26 giugno 2020.
  7. ^ (EN) Clang - Features and Goals, su clang.llvm.org. URL consultato il 26 giugno 2020.
  8. ^ Aho, Lam, Sethi, Ullman, p. 10.
  9. ^ Aho, Lam, Sethi, Ullman, p. 11.
  10. ^ (EN) Amy Brown e Greg Wilson (a cura di), LLVM, in The Architecture of Open Source Applications, 2011, p. 158, ISBN 978-1-257-63801-7.
  11. ^ (EN) Profile-Guided Optimization (PGO), su software.intel.com. URL consultato il 25 giugno 2020.
  12. ^ a b (EN) Monica Lam, Overview of the SUIF System (ps), su suif.stanford.edu. URL consultato il 25 giugno 2020.
  13. ^ (EN) LLVM’s Analysis and Transform Passes, su llvm.org. URL consultato il 25 giugno 2020.
  14. ^ (EN) Craig Chambers, Optimizations (PDF), su courses.cs.washington.edu. URL consultato il 25 giugno 2020.
  15. ^ a b Aho, Lam, Sethi, Ullman, p. 903.
  16. ^ (EN) /GL (Whole Program Optimization), su docs.microsoft.com. URL consultato il 25 giugno 2020.
  17. ^ (EN) LLVM Link Time Optimization Design and Implementation, su llvm.org. URL consultato il 5 giugno 2020.
  18. ^ a b Appel, pp. 399-402.
  19. ^ Appel, pp. 376-396.
  20. ^ a b Appel, p. 387.
  21. ^ Appel, p. 384.
  22. ^ Appel, p. 388.
  23. ^ Appel, p. 395.
  24. ^ Appel, p. 476.
  25. ^ Aho, Lam, Sethi, Ullman, p. 597.
  26. ^ a b c d Appel, p. 359.
  27. ^ Aho, Lam, Sethi, Ullman, p. 639.
  28. ^ Aho, Lam, Sethi, Ullman, p. 632.
  29. ^ Appel, p. 360.
  30. ^ Appel, p. 426.
  31. ^ Aho, Lam, Sethi, Ullman, p. 535.
  32. ^ (EN) Monica S. Lam, Instruction Scheduling (PDF), su suif.stanford.edu. URL consultato il 25 giugno 2020 (archiviato dall'url originale il 13 aprile 2021).
  33. ^ (EN) Monica S. Lam, Register Allocation (PDF), su suif.stanford.edu. URL consultato il 25 giugno 2020 (archiviato dall'url originale il 12 febbraio 2020).
  34. ^ Appel, pp. 203-214.
  35. ^ Appel, p. 354.
  36. ^ Appel, pp. 379-381.
  37. ^ Appel, pp. 369-374.

Bibliografia modifica

Voci correlate modifica

Collegamenti esterni modifica

Estratto da "https://it.wikipedia.org/w/index.php?title=Compilatore_con_ottimizzatore&oldid=137334057"