Compilatore con ottimizzatore

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]

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]

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]

Le ottimizzazioni si classificano in ottimizzazioni target-independent (dipendenti dal target) o target-dependent (indipendenti dal target).^[8] Le ottimizzazioni target-independent 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]

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]

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à.

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]

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]

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]

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]

• (EN) Andrew W. Appel e Jens Palsberg, Modern Compiler Implementation in Java, 2ª ed., Cambridge University Press, 2004, ISBN 0-521-82060-X.
• (EN) Alfred V. Aho, Monica S. Lam, Ravi Sethi e Jeffrey D. Ullman, Compilers: Principles, Techniques & Tools, 2ª ed., Pearson Education, 2007, ISBN 0-321-48681-1.

• Compilatore
• Ottimizzazione (informatica)
• Rappresentazione intermedia
• CFLAGS

• (EN) LLVM’s Analysis and Transform Passes, su llvm.org. (lista delle ottimizzazioni e delle analisi in LLVM)