Ottimizzazione interprocedurale - Interprocedural optimization
L'ottimizzazione interprocedurale ( IPO ) è una raccolta di tecniche di compilazione utilizzate nella programmazione di computer per migliorare le prestazioni in programmi contenenti molte funzioni di piccola o media lunghezza utilizzate di frequente . IPO differisce dall'ottimizzazione di altri compilatori perché analizza l'intero programma; altre ottimizzazioni considerano solo una singola funzione, o anche un singolo blocco di codice.
L'IPO cerca di ridurre o eliminare i calcoli duplicati, l'uso inefficiente della memoria e di semplificare le sequenze iterative come i loop. Se c'è una chiamata a un'altra routine che si verifica all'interno di un ciclo, l'analisi IPO può determinare che è meglio incorporarla . Inoltre, IPO può riordinare le routine per un migliore layout di memoria e località .
L'IPO può anche includere le tipiche ottimizzazioni del compilatore a livello di intero programma, ad esempio l' eliminazione del codice morto (DCE), che rimuove il codice che non viene mai eseguito. A tale scopo, il compilatore verifica i rami che non vengono mai presi e rimuove il codice in quel ramo. IPO cerca anche di garantire un migliore utilizzo delle costanti. I compilatori moderni offrono IPO come opzione in fase di compilazione. L'effettivo processo IPO può verificarsi in qualsiasi fase tra il codice sorgente leggibile dall'uomo e la produzione di un programma binario eseguibile finito.
Per le lingue che si compilano file per file, una IPO efficace tra unità di traduzione (file modulo) richiede la conoscenza dei "punti di ingresso" del programma in modo che possa essere eseguita un'ottimizzazione dell'intero programma ( WPO ). In molti casi, questo viene implementato come un passaggio LTO ( link-time optimization ), perché l'intero programma è visibile al linker.
Analisi
L'obiettivo di qualsiasi ottimizzazione della velocità è di far funzionare il programma il più rapidamente possibile; il problema è che non è possibile per un compilatore analizzare correttamente un programma e determinare cosa farà , tanto meno cosa il programmatore intendeva che facesse. Al contrario, i programmatori umani iniziano dall'altra parte con uno scopo e tentano di produrre un programma che lo raggiunga, preferibilmente senza dedicare molta attenzione al processo.
Per vari motivi, inclusa la leggibilità, i programmi vengono spesso suddivisi in una serie di procedure, che gestiscono alcuni casi generali. Tuttavia, la generalità di ciascuna procedura può comportare uno spreco di sforzi in usi specifici. L'ottimizzazione interprocedurale rappresenta un tentativo di ridurre questo spreco.
Supponiamo che esista una procedura che valuta F (x) e che il codice richieda il risultato di F (6) e successivamente di nuovo F (6). Questa seconda valutazione è quasi certamente superflua: il risultato avrebbe invece potuto essere salvato e richiamato in seguito, assumendo che F sia una funzione pura . Questa semplice ottimizzazione viene sventata nel momento in cui l'implementazione di F (x) diventa impura; ovvero, la sua esecuzione implica il riferimento a parametri diversi dall'argomento esplicito 6 che sono stati modificati tra le invocazioni, o effetti collaterali come la stampa di un messaggio in un log, il conteggio del numero di valutazioni, l'accumulo del tempo di CPU consumato, la preparazione di tabelle interne in modo da facilitare le successive invocazioni per i parametri correlati, e così via. Perdere questi effetti collaterali attraverso la mancata valutazione una seconda volta può essere accettabile, oppure no.
Più in generale, a parte l'ottimizzazione, la seconda ragione per utilizzare le procedure è evitare la duplicazione di codice che produrrebbe gli stessi risultati, o quasi gli stessi risultati, ogni volta che viene eseguita la procedura. Un approccio generale all'ottimizzazione sarebbe quindi invertirlo: alcune o tutte le invocazioni di una determinata procedura sono sostituite dal rispettivo codice, con i parametri opportunamente sostituiti. Il compilatore cercherà quindi di ottimizzare il risultato.
WPO e LTO
L'ottimizzazione dell'intero programma ( WPO ) è l'ottimizzazione del compilatore di un programma che utilizza le informazioni su tutti i moduli del programma. Normalmente, le ottimizzazioni vengono eseguite su una base per modulo, "compiland" ; ma questo approccio, sebbene più facile da scrivere e testare e meno impegnativo di risorse durante la compilazione stessa, non consente la certezza sulla sicurezza di una serie di ottimizzazioni come l' inlining aggressivo e quindi non può eseguirle anche se si rivelassero effettivamente guadagni di efficienza che non cambiano la semantica del codice oggetto emesso.
L'ottimizzazione del tempo di collegamento ( LTO ) è un tipo di ottimizzazione del programma eseguita da un compilatore a un programma al momento del collegamento . L'ottimizzazione del tempo di collegamento è rilevante nei linguaggi di programmazione che compilano programmi file per file e quindi collegano questi file insieme (come C e Fortran ), piuttosto che tutti in una volta (come il just-in-time di Java compilazione (JIT)).
Una volta che tutti i file sono stati compilati separatamente in file oggetto , tradizionalmente un compilatore collega (unisce) i file oggetto in un unico file, l' eseguibile . Tuttavia, in LTO come implementato dalla GNU Compiler Collection (GCC) o LLVM , il compilatore è in grado di eseguire il dump della sua rappresentazione intermedia ( GIMPLE bytecode o LLVM bitcode) su disco in modo che tutte le diverse unità di compilazione che andranno a costituire un unico eseguibile può essere ottimizzato come un singolo modulo quando il collegamento finalmente avviene. Questo espande l'ambito delle ottimizzazioni interprocedurali per comprendere l'intero programma (o, piuttosto, tutto ciò che è visibile al momento del collegamento). Con l'ottimizzazione del tempo di collegamento, il compilatore può applicare varie forme di ottimizzazione interprocedurale all'intero programma, consentendo un'analisi più approfondita, una maggiore ottimizzazione e, in definitiva, migliori prestazioni del programma.
In pratica, LTO non ottimizza sempre l'intero programma: le funzioni della libreria , in particolare gli oggetti condivisi collegati dinamicamente , sono intenzionalmente tenute fuori per evitare duplicazioni eccessive e per consentire l'aggiornamento. Il collegamento statico si presta naturalmente al concetto di LTO, ma funziona solo con archivi di libreria che contengono oggetti IR rispetto ai file oggetto solo codice macchina. A causa di problemi di prestazioni, nemmeno l'intera unità viene sempre utilizzata direttamente: un programma potrebbe essere partizionato in uno stile LTO divide et impera come WHOPR di GCC. E naturalmente, quando il programma in costruzione è esso stesso una libreria, l'ottimizzazione manterrebbe ogni simbolo disponibile esternamente (esportato), senza sforzarsi di rimuoverlo come parte di DCE.
Una forma molto più limitata di WPO è ancora possibile senza LTO, come esemplificato dal -fwhole-program passaggio di GCC . Questa modalità fa assumere a GCC che il modulo da compilare contenga il punto di ingresso (di solito main() ) dell'intero programma, in modo che ogni altra funzione in esso non venga utilizzata esternamente e possa essere ottimizzata in modo sicuro. Poiché si applica a un solo modulo, non può veramente comprendere l'intero programma. (Può essere combinato con LTO nel senso di un modulo grande, utile quando il linker non sta comunicando a GCC su quali punti di ingresso o simboli vengono utilizzati esternamente.)
Esempio
Program example;
integer b; {A variable "global" to the procedure Silly.}
Procedure Silly(a,x)
if x < 0 then a:=x + b else a:=-6;
End Silly; {Reference to b, not a parameter, makes Silly "impure" in general.}
integer a,x; {These variables are visible to Silly only if parameters.}
x:=7; b:=5;
Silly(a,x); write(x);
Silly(x,a); write(x);
Silly(b,b); write(b);
End example;
Se i parametri a Silly vengono passati per valore , le azioni della procedura non hanno effetto sulle variabili originali e poiché Silly non fa nulla al suo ambiente (legge da un file, scrive su un file, modifica le variabili globali come b , ecc. .) il suo codice e tutte le invocazioni possono essere completamente ottimizzate, lasciando il valore di un indefinito (che non ha importanza) in modo che rimangano solo le istruzioni print e queste per valori costanti.
Se invece i parametri vengono passati per riferimento , l'azione su di essi all'interno di Silly influisce effettivamente sugli originali. Questo di solito viene fatto passando l'indirizzo macchina dei parametri alla procedura in modo che le regolazioni della procedura siano nell'area di memorizzazione originale. Pertanto, nel caso della chiamata per riferimento, la procedura Silly ha un effetto. Supponiamo che le sue invocazioni siano espanse sul posto, con parametri identificati dall'indirizzo: il codice è pari a
x:=7; b:=5;
if x < 0 then a:=x + b else a:=-6; write(x); {a is changed.}
if a < 0 then x:=a + b else x:=-6; write(x); {Because the parameters are swapped.}
if b < 0 then b:=b + b else b:=-6; write(b); {Two versions of variable b in Silly, plus the global usage.}
Il compilatore potrebbe quindi in questo esempio piuttosto piccolo seguire le costanti lungo la logica (così com'è) e scoprire che i predicati delle istruzioni if sono costanti e quindi ...
x:=7; b:=5;
a:=-6; write(7); {b is not referenced, so this usage remains "pure".}
x:=-1; write(-1); {b is referenced...}
b:=-6; write(-6); {b is modified via its parameter manifestation.}
E dal momento che le assegnazioni di un , b e x consegnare nulla al mondo esterno - non appaiono nelle dichiarazioni di uscita, né come input per i calcoli successivi (i cui risultati, a loro volta fanno portare a uscita, altrimenti sono anche inutili) - non c'è nessun punto neanche in questo codice, quindi il risultato è
write(7);
write(-1);
write(-6);
Un metodo variante per il passaggio di parametri che sembrano essere "per riferimento" è il copy-in, copy-out in cui la procedura lavora su una copia locale dei parametri i cui valori vengono copiati di nuovo negli originali all'uscita dalla procedura. Se la procedura ha accesso allo stesso parametro ma in modi diversi rispetto a invocazioni come Silly (a, a) o Silly (a, b) , possono sorgere discrepanze. Quindi, se i parametri fossero passati da copy-in, copy-out in ordine da sinistra a destra, allora Silly (b, b) si espanderebbe in
p1:=b; p2:=b; {Copy in. Local variables p1 and p2 are equal.}
if p2 < 0 then p1:=p2 + b else p1:=-6; {Thus p1 may no longer equal p2.}
b:=p1; b:=p2; {Copy out. In left-to-right order, the value from p1 is overwritten.}
E in questo caso, copiare il valore di p1 (che è stato modificato) in b è inutile, perché viene immediatamente sovrascritto dal valore di p2 , il cui valore non è stato modificato all'interno della procedura dal suo valore originale di b , e quindi la terza affermazione diventa
write(5); {Not -6}
È probabile che tali differenze di comportamento causino perplessità, esacerbate dalle domande sull'ordine in cui i parametri vengono copiati: sarà da sinistra a destra sia in uscita che in entrata? Questi dettagli probabilmente non sono spiegati accuratamente nel manuale del compilatore e, se lo sono, probabilmente verranno ignorati come non rilevanti per l'attività immediata e da tempo dimenticati nel momento in cui si presenta un problema. Se (come è probabile) i valori temporanei sono forniti tramite uno schema di archiviazione dello stack, allora è probabile che il processo di copia indietro sarà nell'ordine inverso al copia-in, il che in questo esempio significherebbe che p1 sarebbe l'ultimo valore restituito a b invece.
Il processo di espansione di una procedura in linea non deve essere considerato come una variante della sostituzione testuale (come nelle espansioni macro ) perché possono verificarsi errori di sintassi quando i parametri vengono modificati e la particolare invocazione utilizza costanti come parametri. Perché è importante essere sicuri che le costanti fornite come parametri non avranno il loro valore modificato (le costanti possono essere mantenute in memoria proprio come lo sono le variabili) per evitare che gli usi successivi di quella costante (fatti tramite riferimento alla sua posizione di memoria) vadano male, a tecnica comune è che il compilatore generi codice copiando il valore della costante in una variabile temporanea il cui indirizzo viene passato alla procedura, e se il suo valore viene modificato, non importa; non viene mai copiato di nuovo nella posizione della costante.
In altre parole, un programma di test scritto con cura può riferire se i parametri vengono passati per valore o riferimento e, se usati, quale tipo di schema di copia in entrata e in uscita. Tuttavia, la variazione è infinita: parametri semplici potrebbero essere passati per copia mentre aggregati di grandi dimensioni come gli array potrebbero essere passati per riferimento; costanti semplici come zero potrebbero essere generate da codici macchina speciali (come Clear o LoadZ) mentre costanti più complesse potrebbero essere archiviate in memoria contrassegnate come di sola lettura con qualsiasi tentativo di modificarlo con conseguente chiusura immediata del programma, ecc.
Generalmente
Questo esempio è estremamente semplice, sebbene le complicazioni siano già evidenti. Più probabilmente si tratterà di molte procedure, con una varietà di proprietà deducibili o dichiarate dal programmatore che potrebbero consentire alle ottimizzazioni del compilatore di trovare qualche vantaggio. Qualsiasi parametro di una procedura potrebbe essere di sola lettura, essere scritto, essere letto e scritto, o essere ignorato del tutto dando origine a opportunità come costanti che non necessitano di protezione tramite variabili temporanee, ma ciò che accade in una data invocazione può ben dipendere da una complessa rete di considerazioni. Altre procedure, in particolare procedure simili a funzioni, avranno determinati comportamenti che in specifiche invocazioni possono consentire di evitare del lavoro: ad esempio, la funzione Gamma , se invocata con un parametro intero, potrebbe essere convertita in un calcolo che coinvolge fattoriali interi.
Alcuni linguaggi informatici consentono (o addirittura richiedono) asserzioni sull'uso dei parametri e potrebbero inoltre offrire l'opportunità di dichiarare che le variabili hanno i loro valori limitati a qualche insieme (per esempio, 6 <x ≤ 28) fornendo così ulteriore grist per il processo di ottimizzazione per macinare e anche fornire controlli utili sulla coerenza del codice sorgente per rilevare errori. Ma questo non è mai abbastanza - solo ad alcune variabili possono essere dati vincoli semplici, mentre altre richiederebbero specifiche complesse: come si potrebbe specificare che la variabile P deve essere un numero primo e, in tal caso, è o non è incluso il valore 1? Le complicazioni sono immediate: quali sono gli intervalli validi per un giorno del mese D dato che M è un numero di mese? E tutte le violazioni sono degne di risoluzione immediata? Anche se tutto ciò potesse essere gestito, quale beneficio potrebbe derivarne? E a quale costo? Le specifiche complete equivarrebbero a una nuova dichiarazione della funzione del programma in un'altra forma e, a parte il tempo che il compilatore impiegherebbe per elaborarle, sarebbero quindi soggette a bug. Invece, sono consentite solo specifiche semplici con il controllo dell'intervallo di tempo di esecuzione fornito.
Nei casi in cui un programma non legge alcun input (come nell'esempio), si potrebbe immaginare che l'analisi del compilatore venga portata avanti in modo che il risultato non sia altro che una serie di istruzioni di stampa, o possibilmente alcuni cicli che generano opportunamente tali valori. Riconoscerebbe quindi un programma per generare numeri primi e convertirlo al metodo più noto per farlo, o presentare invece un riferimento a una libreria? Improbabile! In generale, sorgono considerazioni arbitrariamente complesse (il problema Entscheidungs ) per impedirlo e non c'è altra scelta che eseguire il codice solo con miglioramenti limitati.
Storia
Per i linguaggi procedurali, o simili all'ALGOL, l'analisi e l'ottimizzazione interprocedurali sembrano essere entrate nella pratica commerciale all'inizio degli anni '70. Il compilatore di ottimizzazione PL / I di IBM ha eseguito analisi interprocedurali per comprendere gli effetti collaterali sia delle chiamate di procedura che delle eccezioni (espresse, in termini PL / I come "sulle condizioni") e negli articoli di Fran Allen . Il lavoro sulla compilazione del linguaggio di programmazione APL era necessariamente interprocedurale.
Le tecniche di analisi e ottimizzazione interprocedurale sono state oggetto di ricerca accademica negli anni '80 e '90. Sono riemersi nel mondo dei compilatori commerciali nei primi anni '90 con i compilatori sia della Convex Computer Corporation (l '"Application Compiler" per Convex C4) e di Ardent (il compilatore per Ardent Titan ). Questi compilatori hanno dimostrato che le tecnologie potevano essere rese sufficientemente veloci da essere accettabili in un compilatore commerciale; successivamente le tecniche interprocedurali sono apparse in numerosi sistemi commerciali e non commerciali.
Flag e implementazione
Simile a Unix
La GNU Compiler Collection ha funzioni integrate a tutti i livelli di ottimizzazione. A -O1 questo si applica solo a quelli chiamati solo una volta ( -finline-functions-once ), a -O2 questo vincolo è rilassato ( -finline-functions ). Per impostazione predefinita, questo è un comportamento solo per file singolo, ma con l'ottimizzazione del tempo di collegamento -flto diventa un intero programma. L'interfaccia della riga di comando di Clang è simile a quella di GCC, con l'eccezione che non ci sono -fwhole-program opzioni.
I file oggetto prodotti da LTO contengono una rappresentazione intermedia (IR) specifica del compilatore che viene interpretata al momento del collegamento. Per assicurarsi che funzioni bene con le librerie statiche , i linker GNU più recenti hanno un'interfaccia "linker plugin" che consente al compilatore di convertire i file oggetto in un formato di codice macchina quando necessario. Questo plugin aiuta anche a guidare il processo LTO in generale. In alternativa, un oggetto "fat LTO" può essere prodotto per contenere sia il codice macchina che l'IR, ma questo richiede più spazio.
Poiché sia GCC che LLVM (clang) sono in grado di produrre un IR da una varietà di linguaggi di programmazione, l'IPO del tempo di collegamento può avvenire anche oltre i confini linguistici. Questo è più comunemente dimostrato con C e C ++, ma LLVM lo rende possibile anche per Rust e tutti gli altri compilatori basati su LLVM.
Opzioni non LTO
GCC e Clang eseguono IPO per impostazione predefinita al livello di ottimizzazione 2. Tuttavia, il grado di ottimizzazione è limitato quando LTO è disabilitato, poiché l'IPO può avvenire solo all'interno di un file oggetto e le funzioni non statiche non possono mai essere eliminate. Quest'ultimo problema ha una soluzione non LTO: l' -fwhole-program interruttore può essere utilizzato per assumere che solo main() non sia statico, cioè visibile dall'esterno.
Un'altra tecnica non LTO è "sezioni funzione" ( -ffunction-sections in GCC e Clang). Inserendo ciascuna funzione nella propria sezione nel file oggetto, il linker può eseguire la rimozione del codice inattivo senza un IR rimuovendo le sezioni non referenziate ( --gc-sections ). Un'opzione simile è disponibile per le variabili, ma causa la produzione di codice molto peggiore.
Altro
I compilatori Intel C / C ++ consentono l'IPO dell'intero programma. Il flag per abilitare le ottimizzazioni interprocedurali per un singolo file è -ip , il flag per abilitare l'ottimizzazione interprocedurale su tutti i file nel programma è -ipo .
Il compilatore MSVC , integrato in Visual Studio, supporta anche l'ottimizzazione interprocedurale sull'intero programma.
Un'interfaccia indipendente dal compilatore per abilitare le ottimizzazioni interprocedurali dell'intero programma è tramite la INTERPROCEDURAL_OPTIMIZATION proprietà in CMake .