Compilatore di ottimizzazione - Optimizing compiler

In informatica , un compilatore di ottimizzazione è un compilatore che cerca di minimizzare o massimizzare alcuni attributi di un programma eseguibile per computer. I requisiti comuni sono ridurre al minimo il tempo di esecuzione di un programma , l' ingombro della memoria , la dimensione di archiviazione e il consumo energetico (gli ultimi tre sono popolari per i computer portatili ).

L'ottimizzazione del compilatore viene generalmente implementata utilizzando una sequenza di trasformazioni di ottimizzazione , algoritmi che prendono un programma e lo trasformano per produrre un programma di output semanticamente equivalente che utilizza meno risorse o viene eseguito più velocemente. È stato dimostrato che alcuni problemi di ottimizzazione del codice sono NP-completi o addirittura indecidibili . In pratica, fattori come la disponibilità del programmatore ad attendere che il compilatore completi il proprio compito pongono limiti superiori alle ottimizzazioni che un compilatore potrebbe fornire. L'ottimizzazione è generalmente un processo che richiede molta CPU e memoria. In passato, anche le limitazioni della memoria del computer erano un fattore importante nel limitare le ottimizzazioni che potevano essere eseguite.

A causa di questi fattori, l'ottimizzazione raramente produce un output "ottimale" in alcun senso e, in effetti, in alcuni casi un'"ottimizzazione" può impedire le prestazioni. Piuttosto, sono metodi euristici per migliorare l'utilizzo delle risorse nei programmi tipici.

Tipi di ottimizzazione

Le tecniche utilizzate nell'ottimizzazione possono essere suddivise in vari ambiti che possono influenzare qualsiasi cosa, da una singola istruzione all'intero programma. In generale, le tecniche con ambito locale sono più facili da implementare rispetto a quelle globali, ma comportano guadagni minori. Alcuni esempi di ambiti includono:

Ottimizzazioni spioncino: Questi vengono solitamente eseguiti in ritardo nel processo di compilazione dopo che il codice macchina è stato generato. Questa forma di ottimizzazione esamina alcune istruzioni adiacenti (come "guardare attraverso uno spioncino" il codice) per vedere se possono essere sostituite da una singola istruzione o da una sequenza più breve di istruzioni. Ad esempio, una moltiplicazione di un valore per 2 potrebbe essere eseguita in modo più efficiente spostando il valore a sinistra o aggiungendo il valore a se stesso (questo esempio è anche un esempio di riduzione della forza ).
Ottimizzazioni locali: Questi considerano solo le informazioni locali a un blocco di base . Poiché i blocchi di base non hanno un flusso di controllo, queste ottimizzazioni richiedono pochissime analisi, risparmiando tempo e riducendo i requisiti di archiviazione, ma ciò significa anche che nessuna informazione viene conservata tra i salti.
Ottimizzazioni globali: Questi sono anche chiamati "metodi intraprocedurali" e agiscono su intere funzioni. Ciò fornisce loro più informazioni con cui lavorare, ma spesso rende necessari calcoli costosi. Le ipotesi peggiori devono essere fatte quando si verificano chiamate di funzione o si accede a variabili globali perché sono disponibili poche informazioni su di esse.
Ottimizzazioni del ciclo: Questi agiscono sul bilancio che costituiscono un ciclo, come ad esempio una per ciclo, per esempio il movimento di codice loop-invariante . Le ottimizzazioni dei loop possono avere un impatto significativo perché molti programmi trascorrono una grande percentuale del loro tempo all'interno dei loop.
Ottimizzazioni anticipate del negozio: Questi consentono di eseguire le operazioni di archiviazione prima di quanto sarebbe altrimenti consentito nel contesto di thread e blocchi. Il processo necessita di un modo per sapere in anticipo quale valore verrà memorizzato dall'assegnazione che avrebbe dovuto seguire. Lo scopo di questo rilassamento è consentire all'ottimizzazione del compilatore di eseguire determinati tipi di riarrangiamento del codice che preservano la semantica dei programmi correttamente sincronizzati.
Ottimizzazione interprocedurale, dell'intero programma o del tempo di collegamento: Questi analizzano tutto il codice sorgente di un programma. La maggiore quantità di informazioni estratte significa che le ottimizzazioni possono essere più efficaci rispetto a quando si ha accesso solo alle informazioni locali, cioè all'interno di una singola funzione. Questo tipo di ottimizzazione può anche consentire l'esecuzione di nuove tecniche. Ad esempio, function inlining , in cui una chiamata a una funzione viene sostituita da una copia del corpo della funzione.
Ottimizzazione del codice macchina e ottimizzatore del codice oggetto: Questi analizzano l'immagine dell'attività eseguibile del programma dopo che tutto il codice macchina eseguibile è stato collegato . Alcune delle tecniche che possono essere applicate in un ambito più limitato, come la compressione macro che consente di risparmiare spazio comprimendo sequenze comuni di istruzioni, sono più efficaci quando l'intera immagine dell'attività eseguibile è disponibile per l'analisi.

Oltre alle ottimizzazioni con ambito, esistono altre due categorie generali di ottimizzazione:

Linguaggio di programmazione –indipendente vs. dipendente dal linguaggio: La maggior parte dei linguaggi di alto livello condivide costrutti e astrazioni di programmazione comuni: decisione (if, switch, case), loop (for, while, repeat... fino a, do... while) e incapsulamento (strutture, oggetti). Pertanto, tecniche di ottimizzazione simili possono essere utilizzate tra le lingue. Tuttavia, alcune funzionalità del linguaggio rendono difficili alcuni tipi di ottimizzazione. Ad esempio, l'esistenza di puntatori in C e C++ rende difficile ottimizzare gli accessi agli array (vedi analisi degli alias ). Tuttavia, linguaggi come PL/1 (che supporta anche i puntatori) hanno comunque a disposizione compilatori di ottimizzazione sofisticati per ottenere prestazioni migliori in vari altri modi. Al contrario, alcune funzionalità linguistiche facilitano determinate ottimizzazioni. Ad esempio, in alcune lingue non è consentito che le funzioni abbiano effetti collaterali . Pertanto, se un programma effettua più chiamate alla stessa funzione con gli stessi argomenti, il compilatore può immediatamente dedurre che il risultato della funzione deve essere calcolato una sola volta. Nelle lingue in cui le funzioni possono avere effetti collaterali, è possibile un'altra strategia. L'ottimizzatore può determinare quale funzione non ha effetti collaterali e limitare tali ottimizzazioni alle funzioni prive di effetti collaterali. Questa ottimizzazione è possibile solo quando l'ottimizzatore ha accesso alla funzione richiamata.
Indipendente dalla macchina vs. dipendente dalla macchina: Molte ottimizzazioni che operano su concetti di programmazione astratti (loop, oggetti, strutture) sono indipendenti dalla macchina presa di mira dal compilatore, ma molte delle ottimizzazioni più efficaci sono quelle che sfruttano al meglio le caratteristiche speciali della piattaforma di destinazione. Gli esempi sono istruzioni che fanno più cose contemporaneamente, come decrementa registro e ramifica se non zero.

Quella che segue è un'istanza di un'ottimizzazione dipendente dalla macchina locale. Per impostare un registro su 0, il modo più ovvio è usare la costante '0' in un'istruzione che imposta un valore di registro su una costante. Un modo meno ovvio è XOR un registro con se stesso. Sta al compilatore sapere quale variante dell'istruzione usare. Su molte macchine RISC , entrambe le istruzioni sarebbero ugualmente appropriate, poiché avrebbero entrambe la stessa lunghezza e richiederebbero lo stesso tempo. Su molti altri microprocessori come la famiglia Intel x86 , risulta che la variante XOR è più corta e probabilmente più veloce, poiché non sarà necessario decodificare un operando immediato, né utilizzare il "registro operando immediato" interno. Un potenziale problema con questo è che XOR può introdurre una dipendenza dei dati dal valore precedente del registro, causando uno stallo della pipeline . Tuttavia, i processori hanno spesso XOR di un registro con se stesso come un caso speciale che non causa stalli.

Fattori che influenzano l'ottimizzazione

La macchina stessa: Molte delle scelte su quali ottimizzazioni possono e dovrebbero essere fatte dipendono dalle caratteristiche della macchina di destinazione. A volte è possibile parametrizzare alcuni di questi fattori dipendenti dalla macchina, in modo che un singolo pezzo di codice del compilatore possa essere utilizzato per ottimizzare macchine diverse semplicemente modificando i parametri di descrizione della macchina. GCC di GNU Project e Clang di LLVM Compiler Infrastructure sono esempi di ottimizzazione di compilatori che seguono questo approccio.

L'architettura della CPU di destinazione: Numero di registri della CPU : in una certa misura, più registri, più facile è l'ottimizzazione delle prestazioni. Le variabili locali possono essere allocate nei registri e non nello stack . I risultati temporanei/intermedi possono essere lasciati nei registri senza scrivere e rileggere dalla memoria.

RISC vs CISC : i set di istruzioni CISC hanno spesso lunghezze di istruzione variabili, spesso hanno un numero maggiore di possibili istruzioni che possono essere utilizzate e ciascuna istruzione potrebbe richiedere quantità di tempo diverse. I set di istruzioni RISC tentano di limitare la variabilità in ciascuno di questi: i set di istruzioni sono generalmente di lunghezza costante, con poche eccezioni, di solito ci sono meno combinazioni di registri e operazioni di memoria e il tasso di emissione delle istruzioni (il numero di istruzioni completate per periodo di tempo, di solito un multiplo intero del ciclo di clock) è di solito costante nei casi in cui la latenza della memoria non è un fattore. Ci possono essere diversi modi per svolgere un determinato compito, con CISC che di solito offre più alternative rispetto a RISC. I compilatori devono conoscere i costi relativi tra le varie istruzioni e scegliere la migliore sequenza di istruzioni (vedi selezione istruzioni ).
Pipeline : una pipeline è essenzialmente una CPU suddivisa in una catena di montaggio . Consente l'uso di parti della CPU per istruzioni diverse suddividendo l'esecuzione delle istruzioni in varie fasi: decodifica dell'istruzione, decodifica dell'indirizzo, recupero della memoria, recupero del registro, calcolo, memorizzazione dei registri, ecc. Un'istruzione potrebbe essere nella fase di memorizzazione dei registri , mentre un altro potrebbe essere in fase di recupero del registro. I conflitti di pipeline si verificano quando un'istruzione in una fase della pipeline dipende dal risultato di un'altra istruzione precedente nella pipeline ma non ancora completata. I conflitti della pipeline possono portare a stalli della pipeline : in cui la CPU spreca cicli in attesa che un conflitto si risolva.

I compilatori possono pianificare o riordinare le istruzioni in modo che gli stalli della pipeline si verifichino meno frequentemente.

Numero di unità funzionali : alcune CPU hanno più ALU e FPU . Ciò consente loro di eseguire più istruzioni contemporaneamente. Potrebbero esserci restrizioni su quali istruzioni possono essere abbinate a quali altre istruzioni ("pairing" è l'esecuzione simultanea di due o più istruzioni) e quale unità funzionale può eseguire quale istruzione. Hanno anche problemi simili ai conflitti di pipeline.

Anche in questo caso, le istruzioni devono essere programmate in modo che le varie unità funzionali siano completamente alimentate con le istruzioni da eseguire.

L'architettura della macchina

Dimensioni e tipo della cache (256 kiB–12 MiB) (mappato direttamente, associativo a 2/4-/8-/16 vie, completamente associativo): tecniche come l'espansione in linea e lo svolgimento del ciclo possono aumentare la dimensione del codice generato e ridurre la località del codice. Il programma può rallentare drasticamente se una sezione di codice molto utilizzata (come i loop interni in vari algoritmi) improvvisamente non può essere inserita nella cache. Inoltre, le cache che non sono completamente associative hanno maggiori possibilità di collisioni della cache anche in una cache non riempita.
Velocità di trasferimento cache/memoria: danno al compilatore un'indicazione della penalità per i mancati cache. Viene utilizzato principalmente in applicazioni specializzate.

Uso previsto del codice generato

Debug: Durante la scrittura di un'applicazione, un programmatore ricompila e testa spesso, quindi la compilazione deve essere veloce. Questo è uno dei motivi per cui la maggior parte delle ottimizzazioni viene deliberatamente evitata durante la fase di test/debug. Inoltre, il codice del programma viene solitamente "passato attraverso" (vedi Animazione del programma ) utilizzando un debugger simbolico e l'ottimizzazione delle trasformazioni, in particolare quelle che riordinano il codice, può rendere difficile mettere in relazione il codice di output con i numeri di riga nel codice sorgente originale. Questo può confondere sia gli strumenti di debug che i programmatori che li utilizzano.
Uso generico: Molto spesso ci si aspetta che il software preconfezionato venga eseguito su una varietà di macchine e CPU che possono condividere lo stesso set di istruzioni, ma hanno caratteristiche di temporizzazione, cache o memoria diverse. Di conseguenza, il codice potrebbe non essere sintonizzato su una particolare CPU o potrebbe essere sintonizzato per funzionare al meglio sulla CPU più popolare e tuttavia funzionare ancora in modo accettabile su altre CPU.
Uso speciale: Se il software è compilato per essere utilizzato su una o poche macchine molto simili, con caratteristiche note, il compilatore può adattare pesantemente il codice generato a quelle macchine specifiche, a condizione che tali opzioni siano disponibili. Casi speciali importanti includono codice progettato per processori paralleli e vettoriali , per i quali vengono impiegati compilatori di parallelizzazione speciali .
Sistemi integrati: Questi sono un caso comune di uso speciale. Il software incorporato può essere strettamente sintonizzato su una CPU e una dimensione di memoria esatte. Inoltre, il costo o l'affidabilità del sistema possono essere più importanti della velocità del codice. Ad esempio, i compilatori per software embedded di solito offrono opzioni che riducono la dimensione del codice a scapito della velocità, perché la memoria è il costo principale di un computer embedded. Potrebbe essere necessario che i tempi del codice siano prevedibili, piuttosto che il più velocemente possibile, quindi la memorizzazione nella cache del codice potrebbe essere disabilitata, insieme alle ottimizzazioni del compilatore che lo richiedono.

Temi comuni

In larga misura, le tecniche di ottimizzazione del compilatore hanno i seguenti temi, che a volte sono in conflitto.

Ottimizza il caso comune: Il caso comune può avere proprietà uniche che consentono un percorso veloce a spese di un percorso lento . Se il percorso veloce viene preso più spesso, il risultato è una migliore prestazione complessiva.
Evita la ridondanza: Riutilizza i risultati già calcolati e archiviali per un uso successivo, invece di ricalcolarli.
Meno codice: Rimuovere calcoli non necessari e valori intermedi. Meno lavoro per la CPU, la cache e la memoria di solito si traduce in un'esecuzione più veloce. In alternativa, nei sistemi embedded , meno codice comporta un costo del prodotto inferiore.
Meno salti utilizzando il codice in linea retta , chiamato anche codice branch-free: Codice meno complicato. I salti ( rami condizionali o incondizionati ) interferiscono con il precaricamento delle istruzioni, rallentando così il codice. L'utilizzo dell'inlining o dello srotolamento del ciclo può ridurre la ramificazione, al costo di aumentare le dimensioni del file binario della lunghezza del codice ripetuto. Questo tende a fondere diversi blocchi di base in uno.
Località: Codice e dati a cui si accede strettamente insieme nel tempo dovrebbero essere collocati vicini nella memoria per aumentare la località spaziale di riferimento .
Sfrutta la gerarchia della memoria: Gli accessi alla memoria sono sempre più costosi per ogni livello della gerarchia di memoria , quindi posiziona gli elementi più comunemente usati prima nei registri, poi nelle cache, poi nella memoria principale, prima di andare su disco.
Parallelizzare: Riordina le operazioni per consentire l'esecuzione di più calcoli in parallelo, a livello di istruzione, memoria o thread.
Informazioni più precise è meglio: Più precise sono le informazioni del compilatore, meglio può utilizzare una o tutte queste tecniche di ottimizzazione.
Le metriche di runtime possono aiutare: Le informazioni raccolte durante un'esecuzione di test possono essere utilizzate nell'ottimizzazione guidata dal profilo . Le informazioni raccolte in fase di esecuzione, idealmente con un sovraccarico minimo , possono essere utilizzate da un compilatore JIT per migliorare dinamicamente l'ottimizzazione.
Riduzione della forza: Sostituisci operazioni complesse o difficili o costose con operazioni più semplici. Ad esempio, sostituendo la divisione per una costante con la moltiplicazione per il suo reciproco o utilizzando l'analisi della variabile di induzione per sostituire la moltiplicazione con un indice di loop con l'addizione.

Tecniche specifiche

Ottimizzazioni del ciclo

Alcune tecniche di ottimizzazione progettate principalmente per operare su loop includono:

Analisi delle variabili di induzione: Approssimativamente, se una variabile in un ciclo è una semplice funzione lineare della variabile indice, come j := 4*i + 1, può essere aggiornata in modo appropriato ogni volta che la variabile del ciclo viene modificata. Questa è una riduzione della forza e può anche consentire alle definizioni della variabile indice di diventare codice morto . Queste informazioni sono utili anche per l' eliminazione del controllo dei limiti e l' analisi delle dipendenze , tra le altre cose.

Fissione ad anello o distribuzione ad anello: La fissione dell'anello tenta di spezzare un anello in più anelli sullo stesso intervallo di indice, ma ognuno occupa solo una parte del corpo dell'anello. Ciò può migliorare la località di riferimento , sia i dati a cui si accede nel ciclo che il codice nel corpo del ciclo.

Loop fusion o loop combination o loop ramming o loop jamming: Un'altra tecnica che tenta di ridurre il sovraccarico del ciclo. Quando due cicli adiacenti ripetono lo stesso numero di volte indipendentemente dal fatto che quel numero sia noto in fase di compilazione, i loro corpi possono essere combinati purché non facciano riferimento ai dati dell'altro.

Inversione del ciclo: Questa tecnica cambia un ciclo while standard in un ciclo do/while (noto anche come repeat/until ) avvolto in un if condizionale, riducendo il numero di salti di due, nei casi in cui il ciclo viene eseguito. In questo modo si duplica il controllo delle condizioni (aumentando la dimensione del codice), ma è più efficiente perché i salti di solito causano uno stallo della pipeline . Inoltre, se la condizione iniziale è nota in fase di compilazione ed è nota per essere priva di effetti collaterali , la protezione if può essere ignorata.

Scambio di loop: Queste ottimizzazioni scambiano i loop interni con i loop esterni. Quando le variabili di ciclo indicizzano in un array, tale trasformazione può migliorare la località di riferimento, a seconda del layout dell'array.

Movimento del codice invariante per loop: Se una quantità viene calcolata all'interno di un ciclo durante ogni iterazione e il suo valore è lo stesso per ogni iterazione, può migliorare notevolmente l'efficienza per issarla all'esterno del ciclo e calcolarne il valore solo una volta prima dell'inizio del ciclo. Ciò è particolarmente importante con le espressioni di calcolo dell'indirizzo generate da loop su array. Per una corretta implementazione, questa tecnica deve essere utilizzata con l' inversione del ciclo , poiché non tutto il codice è sicuro per essere issato all'esterno del ciclo.

Ottimizzazione del nido di loop: Alcuni algoritmi pervasivi come la moltiplicazione di matrici hanno un comportamento della cache molto scarso e accessi alla memoria eccessivi. L'ottimizzazione del nido di loop aumenta il numero di riscontri nella cache eseguendo l'operazione su piccoli blocchi e utilizzando un interscambio di loop.

Inversione del ciclo: L'inversione del ciclo inverte l'ordine in cui i valori vengono assegnati alla variabile indice. Questa è un'ottimizzazione sottile che può aiutare a eliminare le dipendenze e quindi consentire altre ottimizzazioni. Inoltre, su alcune architetture, l'inversione del ciclo contribuisce a un codice più piccolo, poiché quando l'indice del ciclo viene decrementato, la condizione che deve essere soddisfatta affinché il programma in esecuzione esca dal ciclo è un confronto con zero. Si tratta spesso di un'istruzione speciale, senza parametri, a differenza del confronto con un numero, che richiede il confronto con il numero. Pertanto, la quantità di byte necessaria per memorizzare il parametro viene salvata utilizzando l'inversione del ciclo. Inoltre, se il numero di confronto supera la dimensione della parola della piattaforma, nell'ordine di ciclo standard, sarebbe necessario eseguire più istruzioni per valutare il confronto, il che non è il caso dell'inversione del ciclo.

Svolgimento del ciclo: Lo svolgimento duplica il corpo del ciclo più volte, al fine di ridurre il numero di volte in cui viene testata la condizione del ciclo e il numero di salti, che danneggiano le prestazioni compromettendo la pipeline delle istruzioni. Un'ottimizzazione "meno salti". Lo svolgimento completo di un ciclo elimina tutto il sovraccarico, ma richiede che il numero di iterazioni sia noto al momento della compilazione.

Divisione del ciclo: La suddivisione del ciclo tenta di semplificare un ciclo o eliminare le dipendenze suddividendolo in più cicli che hanno gli stessi corpi ma iterano su diverse porzioni contigue dell'intervallo di indici. Un utile caso speciale è il loop peeling , che può semplificare un ciclo con una prima iterazione problematica eseguendo tale iterazione separatamente prima di entrare nel ciclo.

Disattivazione del loop: L'annullamento della commutazione sposta un condizionale dall'interno di un ciclo all'esterno del ciclo duplicando il corpo del ciclo all'interno di ciascuna delle clausole if e else del condizionale.

Pipeline software: Il ciclo viene ristrutturato in modo tale che il lavoro svolto in un'iterazione venga suddiviso in più parti e svolto in più iterazioni. In un ciclo stretto, questa tecnica nasconde la latenza tra il caricamento e l'utilizzo dei valori.

Parallelizzazione automatica: Un ciclo viene convertito in codice multi-thread o vettorizzato (o anche entrambi) per utilizzare più processori contemporaneamente in una macchina multiprocessore a memoria condivisa (SMP), comprese le macchine multi-core.

Ottimizzazioni del flusso di dati

Le ottimizzazioni del flusso di dati , basate sull'analisi del flusso di dati , dipendono principalmente da come determinate proprietà dei dati vengono propagate dai bordi di controllo nel grafico del flusso di controllo . Alcuni di questi includono:

Eliminazione della sottoespressione comune: Nell'espressione (a + b) - (a + b)/4, "sottoespressione comune" si riferisce al duplicato (a + b). I compilatori che implementano questa tecnica si rendono conto che (a + b)non cambierà e quindi calcolano il suo valore solo una volta.

Piegatura e propagazione costanti: sostituendo le espressioni costituite da costanti (ad es. 3 + 5) con il loro valore finale ( 8) in fase di compilazione, anziché eseguire il calcolo in fase di esecuzione. Utilizzato nella maggior parte delle lingue moderne.

Riconoscimento ed eliminazione della variabile di induzione: vedere la discussione sopra sull'analisi delle variabili di induzione .

Classificazione degli alias e analisi dei puntatori: in presenza di puntatori , è difficile effettuare delle ottimizzazioni, poiché potenzialmente qualsiasi variabile può essere stata modificata quando viene assegnata una locazione di memoria. Specificando quali puntatori possono alias quali variabili, i puntatori non correlati possono essere ignorati.

Eliminazione negozio morto: rimozione di assegnazioni a variabili che non vengono successivamente lette, sia perché termina la durata della variabile, sia a causa di una successiva assegnazione che sovrascriverà il primo valore.

Ottimizzazioni basate su SSA

Queste ottimizzazioni vanno fatte dopo aver trasformato il programma in un apposito form chiamato Static Single Assignment , in cui ogni variabile è assegnata in un'unica posizione. Sebbene alcune funzionino senza SSA, sono più efficaci con SSA. Molte ottimizzazioni elencate in altre sezioni beneficiano anche senza modifiche speciali, come l'allocazione dei registri.

Numerazione del valore globale: GVN elimina la ridondanza costruendo un grafico dei valori del programma e quindi determinando quali valori vengono calcolati da espressioni equivalenti. GVN è in grado di identificare una ridondanza che l' eliminazione della sottoespressione comune non può, e viceversa.

Diffusa propagazione costante condizionale: Combina la propagazione costante, il ripiegamento costante e l' eliminazione del codice morto e migliora ciò che è possibile eseguendo separatamente. Questa ottimizzazione esegue simbolicamente il programma, propagando contemporaneamente valori costanti ed eliminando porzioni del grafico del flusso di controllo che ciò rende irraggiungibili.

Ottimizzazioni del generatore di codice

Allocazione del registro: Le variabili usate più frequentemente dovrebbero essere conservate nei registri del processore per un accesso più veloce. Per trovare quali variabili inserire nei registri, viene creato un grafico di interferenza. Ogni variabile è un vertice e quando due variabili vengono utilizzate contemporaneamente (hanno un liverange intersecante) hanno un bordo tra di loro. Questo grafico è colorato usando ad esempio l'algoritmo di Chaitin usando lo stesso numero di colori dei registri. Se la colorazione fallisce, una variabile viene "versata" in memoria e la colorazione viene ritentata.

Selezione delle istruzioni: La maggior parte delle architetture, in particolare le architetture CISC e quelle con molte modalità di indirizzamento , offrono diversi modi di eseguire una particolare operazione, utilizzando sequenze di istruzioni completamente diverse. Il compito del selettore di istruzioni è quello di fare un buon lavoro nel complesso scegliendo quali istruzioni implementare con quali operatori nella rappresentazione intermedia di basso livello . Ad esempio, su molti processori della famiglia 68000 e sull'architettura x86, è possibile utilizzare modalità di indirizzamento complesse in istruzioni come "lea 25(a1,d5*4), a0", consentendo a una singola istruzione di eseguire una quantità significativa di operazioni aritmetiche con meno spazio di archiviazione.

Programmazione delle istruzioni: La pianificazione delle istruzioni è un'importante ottimizzazione per i moderni processori pipeline, che evita stalli o bolle nella pipeline raggruppando le istruzioni senza dipendenze insieme, facendo attenzione a preservare la semantica originale.

rimaterializzazione: La rimaterializzazione ricalcola un valore invece di caricarlo dalla memoria, impedendo l'accesso alla memoria. Questo viene eseguito in tandem con l'assegnazione del registro per evitare fuoriuscite.

Fattore di codice: Se più sequenze di codice sono identiche, o possono essere parametrizzate o riordinate per essere identiche, possono essere sostituite con chiamate a un sottoprogramma condiviso. Questo può spesso condividere il codice per l'impostazione della subroutine e talvolta la ricorsione in coda.

Trampolini: Molte CPU hanno istruzioni di chiamata di subroutine più piccole per accedere alla memoria insufficiente. Un compilatore può risparmiare spazio utilizzando queste piccole chiamate nel corpo principale del codice. Le istruzioni di salto in poca memoria possono accedere alle routine a qualsiasi indirizzo. Questo moltiplica il risparmio di spazio dal factoring del codice.

Riordinare i calcoli: Basati sulla programmazione lineare intera , i compilatori di ristrutturazione migliorano la località dei dati ed espongono più parallelismo riordinando i calcoli. I compilatori che ottimizzano lo spazio possono riordinare il codice per allungare le sequenze che possono essere scomposte in subroutine.

Ottimizzazioni funzionali del linguaggio

Sebbene molti di questi si applichino anche a linguaggi non funzionali, hanno origine o sono particolarmente critici in linguaggi funzionali come Lisp e ML .

Ottimizzazione della chiamata in coda: Una chiamata di funzione consuma spazio nello stack e comporta un sovraccarico relativo al passaggio dei parametri e allo svuotamento della cache delle istruzioni. Gli algoritmi ricorsivi di coda possono essere convertiti in iterazione attraverso un processo chiamato eliminazione della ricorsione di coda o ottimizzazione della chiamata di coda.

Deforestazione ( fusione di strutture dati ): Nei linguaggi in cui è comune applicare una sequenza di trasformazioni a un elenco, la deforestazione tenta di rimuovere la costruzione di strutture dati intermedie.

Valutazione parziale

Altre ottimizzazioni

Eliminazione del controllo dei limiti: Molti linguaggi, come Java , impongono il controllo dei limiti di tutti gli accessi agli array. Si tratta di un grave collo di bottiglia delle prestazioni su alcune applicazioni come il codice scientifico. L'eliminazione del controllo dei limiti consente al compilatore di rimuovere in modo sicuro il controllo dei limiti in molte situazioni in cui può determinare che l'indice deve rientrare nei limiti validi; ad esempio, se è una semplice variabile di ciclo.

Ottimizzazione dell'offset di diramazione (a seconda della macchina): Scegli lo spostamento del ramo più breve che raggiunge l'obiettivo.

Riordino dei blocchi di codice: Il riordino dei blocchi di codice altera l'ordine dei blocchi di base in un programma al fine di ridurre i rami condizionali e migliorare la località di riferimento.

Eliminazione del codice morto: Rimuove le istruzioni che non influenzeranno il comportamento del programma, ad esempio le definizioni che non hanno usi, chiamate codice morto . Ciò riduce la dimensione del codice ed elimina il calcolo non necessario.

Fattorizzazione di invarianti ( invarianti di loop ): Se un'espressione viene eseguita sia quando una condizione è soddisfatta che quando non è soddisfatta, può essere scritta solo una volta al di fuori dell'istruzione condizionale. Allo stesso modo, se alcuni tipi di espressioni (ad es. l'assegnazione di una costante a una variabile) appaiono all'interno di un ciclo, possono essere spostate fuori da esso perché il loro effetto sarà lo stesso indipendentemente dal fatto che vengano eseguite molte volte o solo una volta . Questo è anche noto come eliminazione totale della ridondanza. Un'ottimizzazione simile ma più potente è l' eliminazione della ridondanza parziale (PRE).

Espansione in linea o espansione macro: Quando un codice richiama una procedura , è possibile inserire direttamente il corpo della procedura all'interno del codice chiamante anziché trasferirvi il controllo. Ciò consente di risparmiare l'overhead relativo alle chiamate di procedura, oltre a fornire un'opportunità per molte diverse ottimizzazioni specifiche dei parametri, ma ha un costo di spazio; il corpo della procedura viene duplicato ogni volta che la procedura viene richiamata in linea. In genere, l'inlining è utile nel codice critico per le prestazioni che effettua un numero elevato di chiamate a procedure di piccole dimensioni. Un'ottimizzazione "meno salti". Anche le affermazioni dei linguaggi di programmazione imperativi sono un esempio di tale ottimizzazione. Sebbene le istruzioni possano essere implementate con chiamate di funzione , sono quasi sempre implementate con l'inline del codice.

Salta infilatura: In questa ottimizzazione, vengono uniti salti condizionali consecutivi basati interamente o parzialmente sulla stessa condizione.; Ad esempio, a ,if (c) { foo; } if (c) { bar; }if (c) { foo; bar; }; e a .if (c) { foo; } if (!c) { bar; }if (c) { foo; } else { bar; }

Compressione macro: Un'ottimizzazione dello spazio che riconosce sequenze di codice comuni, crea sottoprogrammi ("macro di codice") che contengono il codice comune e sostituisce le occorrenze delle sequenze di codice comuni con chiamate ai sottoprogrammi corrispondenti. Questa operazione viene eseguita in modo più efficace come ottimizzazione del codice macchina , quando tutto il codice è presente. La tecnica è stata utilizzata per la prima volta per risparmiare spazio in un flusso di byte interpretativo utilizzato in un'implementazione di Macro Spitbol sui microcomputer . Il problema di determinare un insieme ottimale di macro che minimizzi lo spazio richiesto da un dato segmento di codice è noto per essere NP-completo , ma un'euristica efficiente raggiunge risultati quasi ottimali.

Riduzione delle collisioni della cache: (ad es. interrompendo l'allineamento all'interno di una pagina)

Riduzione altezza pila: Riorganizzare l'albero delle espressioni per ridurre al minimo le risorse necessarie per la valutazione delle espressioni.

Riordino di prova: Se abbiamo due test che sono la condizione per qualcosa, possiamo prima occuparci dei test più semplici (es. confrontare una variabile con qualcosa) e solo successivamente dei test complessi (es. quelli che richiedono una chiamata di funzione). Questa tecnica integra la valutazione pigra , ma può essere utilizzata solo quando i test non dipendono l'uno dall'altro. La semantica di cortocircuito può rendere questo difficile.

Ottimizzazioni interprocedurali

L'ottimizzazione interprocedurale funziona sull'intero programma, oltre i limiti delle procedure e dei file. Opera a stretto contatto con le controparti intraprocedurali, realizzate con la collaborazione di una parte locale e di una parte globale. Le tipiche ottimizzazioni interprocedurali sono: inline della procedura , eliminazione del codice morto interprocedurale, propagazione costante interprocedurale e riordino della procedura . Come al solito, il compilatore deve eseguire un'analisi interprocedurale prima delle sue effettive ottimizzazioni. Le analisi interprocedurali includono l'analisi degli alias, l'analisi dell'accesso agli array e la costruzione di un grafico di chiamata .

L'ottimizzazione interprocedurale è comune nei moderni compilatori commerciali di SGI , Intel , Microsoft e Sun Microsystems . Per molto tempo, il GCC open source è stato criticato per la mancanza di potenti analisi e ottimizzazioni interprocedurali, anche se ora sta migliorando. Un altro compilatore open source con un'infrastruttura di analisi e ottimizzazione completa è Open64 .

A causa del tempo e dello spazio aggiuntivi richiesti dall'analisi interprocedurale, la maggior parte dei compilatori non la esegue per impostazione predefinita. Gli utenti devono utilizzare le opzioni del compilatore in modo esplicito per indicare al compilatore di abilitare l'analisi interprocedurale e altre costose ottimizzazioni.

Considerazioni pratiche

Può esistere un'ampia gamma di ottimizzazioni che un compilatore può eseguire, da quelle semplici e dirette che richiedono poco tempo di compilazione a quelle elaborate e complesse che richiedono una notevole quantità di tempo di compilazione. Di conseguenza, i compilatori spesso forniscono opzioni al loro comando o procedura di controllo per consentire all'utente del compilatore di scegliere la quantità di ottimizzazione da richiedere; ad esempio, il compilatore IBM FORTRAN H ha consentito all'utente di non specificare alcuna ottimizzazione, ottimizzazione solo a livello di registri o ottimizzazione completa. Negli anni 2000, era comune per i compilatori, come Clang , avere un numero di opzioni di comando del compilatore che potevano influenzare una varietà di scelte di ottimizzazione, a partire dal familiare -O2switch.

Un approccio per isolare l'ottimizzazione è l'uso dei cosiddetti ottimizzatori post-pass (alcune versioni commerciali dei quali risalgono al software mainframe della fine degli anni '70). Questi strumenti prendono l'output eseguibile da un compilatore di ottimizzazione e lo ottimizzano ulteriormente. Gli ottimizzatori post-pass di solito funzionano a livello di linguaggio assembly o codice macchina (in contrasto con i compilatori che ottimizzano le rappresentazioni intermedie dei programmi). Un esempio è il Portable C Compiler (pcc) degli anni '80, che aveva un passaggio opzionale che eseguiva post-ottimizzazioni sul codice assembly generato.

Un'altra considerazione è che gli algoritmi di ottimizzazione sono complicati e, soprattutto quando vengono utilizzati per compilare linguaggi di programmazione grandi e complessi, possono contenere bug che introducono errori nel codice generato o causano errori interni durante la compilazione. Errori di compilazione di qualsiasi tipo possono essere sconcertanti per l'utente, ma soprattutto in questo caso, poiché potrebbe non essere chiaro che la logica di ottimizzazione sia in errore. In caso di errori interni, il problema può essere parzialmente migliorato da una tecnica di programmazione "fail-safe" in cui la logica di ottimizzazione nel compilatore è codificata in modo tale da intercettare un errore, inviare un messaggio di avviso e il resto della compilazione procede a buon fine.

Storia

I primi compilatori degli anni '60 erano spesso principalmente interessati alla semplice compilazione del codice in modo corretto o efficiente, in modo tale che i tempi di compilazione fossero una delle principali preoccupazioni. Un notevole compilatore di ottimizzazione precoce è stato il compilatore IBM FORTRAN H della fine degli anni '60. Un altro dei primi e importanti compilatori di ottimizzazione, che ha aperto la strada a diverse tecniche avanzate, è stato quello per BLISS (1970), descritto in The Design of an Optimizing Compiler (1975). Alla fine degli anni '80, l'ottimizzazione dei compilatori era sufficientemente efficace da far diminuire la programmazione in linguaggio assembly. Questo si è evoluto con lo sviluppo di chip RISC e funzionalità avanzate del processore come la pianificazione delle istruzioni e l'esecuzione speculativa, che sono stati progettati per essere presi di mira ottimizzando i compilatori piuttosto che dal codice assembly scritto dall'uomo.

Elenco delle analisi del codice statico

Guarda anche

Riferimenti

link esterno

Citazioni da CiteSeer
Manuali di ottimizzazione di Agner Fog - documentazione sull'architettura del processore x86 e sull'ottimizzazione del codice di basso livello

Languages

In other projects