Loading AI tools
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-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
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à.
Ottimizzazioni di ciclo
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]
- 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)
- 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]
Ottimizzazioni sul data-flow
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]
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]
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
