Come ottimizzare un bytecode misto stack / registro con flusso di controllo ed effetti collaterali?

C'è una grande quantità di ricerche su questo argomento, quindi consiglio vivamente di leggere un libro di compilatori. Il libro di Muchnik può funzionare bene come riferimento. Mi piace molto Modern Compiler Implementation ma penso che sia fuori stampa.

Se sei il tipo che impara meglio leggendo il codice, il compilatore Scala fa tutto quanto sopra, e la JVM si adatta a tutti i punti elenco elencati per la tua VM.

Più precisamente:

• Consiglio vivamente una rappresentazione che non usi lo stack. È doloroso mantenerlo coerente quando si modifica il codice: se si rimuove un'istruzione che spinge un valore nello stack su un ramo è necessario aggiungere una caduta anche sugli altri rami, altrimenti lo stack sarà incoerente nel punto di unione . Puoi generare codice basato su stack facilmente dal codice basato su registri dopo che tutti i passaggi di ottimizzazione sono stati eseguiti

• Vorresti rimuovere "codice morto". Se la rappresentazione è già in una forma semplice (penso che ANF sia molto più semplice di CPS e l'ho usato con successo - grosso modo, rompe tutte le espressioni in semplici due-operandi e temporanee) puoi semplicemente contrassegnare come "live" tutti gli effetti Istruzioni. Avresti quindi bisogno di informazioni "Liveness", che calcolano quali compiti vengono utilizzati in seguito (ti piacerebbe andare indietro iniziando con tutte le istruzioni live e contrassegnare come "live" i loro input, e così via). I bit complicati sono nei punti di unione nel CFG, dove è necessario approssimare in modo conservativo (in pratica, conoscere sempre meno il tuo programma per tenere conto dell'incertezza su quale ramo è stato preso)

• Penso che il modo più semplice sia mantenere il flusso di controllo come struttura dati primaria e calcolare le informazioni sul flusso di dati (come Liveness) ogni volta che ne hai bisogno

• se hai la possibilità, usa un albero piuttosto che un CFG. Un albero conserva la struttura del tuo programma (while, ifs), mentre i salti condizionali e incondizionati sono molto più potenti e ti impegni a ricalibrare ciò che è stato buttato via dall'AST (ad esempio, trovando i dominatori nel CFG)

• probabilmente eseguirai un codice morto alcune volte nella tua pipeline, poiché ogni passaggio di ottimizzazione potrebbe produrre più codice morto. Va bene, e di solito è meglio che rendere ogni passaggio di ottimizzazione più intelligente e inutilmente complesso.

Ogni cosa a cui ti stai riferendo richiede / ha il proprio algoritmo di ottimizzazione individuale. Un ottimizzatore è una raccolta di algoritmi di ottimizzazione, eseguiti in una sequenza, spesso anche ripetuti fino a quando non vengono apportate modifiche.

I know for a start, a forward traversal following jumps will tell us where the reachable instructions are and let us eliminate unreachable instructions. But how about the others: optimizing away code computing un-used values, or redundant GOTOs?

Le espressioni non utilizzate sono ottimizzate (cioè eliminate) un'istruzione alla volta, identificando l'ultimo valore non utilizzato ed eliminando l'istruzione che genera quel valore. Un'istruzione alla volta, l'intera espressione inutilizzata può essere rimossa. L'algoritmo di base identifica una singola istruzione il cui valore non è utilizzato e l'algoritmo viene ripetuto fino a quando non vengono apportate modifiche.

I rami ridondanti sono gestiti con la loro ottimizzazione specifica che cerca i rami ai rami. Talvolta il codice viene riorganizzato per migliorare la caduta del ramo condizionale. Esistono anche ottimizzazioni orientate al ciclo per rimuovere i rami incondizionati alla fine del ciclo (a favore dei rami condizionali).

In sintesi, ogni trasformazione è una ottimizzazione individuale e un compilatore ottimizzante ne ha centinaia, alcuni dei quali vengono ripetuti fino a quando non possono corrispondere ai pattern che stanno cercando.

But that doesn't seem to work in the case where there are side effects whose order I need to preserve, since a dataflow graph would just ignore them. Presumably I'll need a controlflow graph in addition to the dataflow graph, but I'm not sure how the two graphs would work together to help me optimize the bytecode.

L'analisi del flusso di dati prende necessariamente in considerazione il flusso di controllo.

L'analisi del flusso di controllo implica l'identificazione dei blocchi di base , che sono sequenze di istruzioni non interrotte dalla ramificazione, ad es. iniziando da un'etichetta e terminando con un'istruzione di ramo o un'altra etichetta. Un'ulteriore analisi del flusso di controllo collega i blocchi di base, identificando i loop, i costrutti if-then-else, ecc.

L'output dell'analisi del flusso di controllo è una struttura grafica, che significa nodi e amp; bordi; nodi per i blocchi di base e i bordi che li connettono.

L'analisi del flusso di dati di solito assume due forme: l'analisi all'interno dei blocchi di base e l'analisi tra i bordi dei blocchi di base seguendo il flusso di controllo. In genere, anche questi vengono eseguiti in modo bidirezionale, in avanti: rilevamento delle definizioni di raggiungimento e al contrario: rilevamento degli utilizzi esposti. Quindi, otteniamo informazioni sulle definizioni di variabili e usi delle variabili.

L'output del flusso di dati è in genere una variante dei vettori bit, in cui ogni posizione di bit rappresenta una variabile diversa nel programma. Se il bit è impostato, allora c'è una definizione della variabile (per le definizioni, o un uso per gli usi, e se è chiaro, non c'è). (Algoritmi del flusso di dati che operano sul grafico del flusso di controllo e sono algoritmi fixpoint , nel senso che convergono: può essere ripetuto fino a quando non cambia.)

Possiamo considerare che prima e dopo ogni istruzione nel programma ci sono due potenziali vettori bit che rappresentano le definizioni (precedenti) che raggiungono quella posizione e quali usi (successivi) consumano i risultati - sebbene di solito queste informazioni non vengano memorizzate ad ogni istruzioni, ma solo prima dell'inizio e dopo la fine di ogni blocco di base (le informazioni a livello di istruzione sono riproducibili durante l'attraversamento del blocco di base).

Le ottimizzazioni utilizzano queste informazioni sul flusso di dati in vari modi. Ad esempio, quando una definizione di una variabile non ha un utilizzo, questo può essere rilevato, ovvero come vengono identificati i calcoli inutilizzati. Per un altro esempio, è possibile determinare che due variabili sono (o meno) in diretta nello stesso punto del programma e, quindi, hanno bisogno (o non hanno bisogno) di registri differenti della CPU.

SSA è una forma di analisi del flusso di dati che introduce e tiene traccia delle versioni delle variabili in modo che l'informazione sia globalmente corretta (è esente da posizione), mentre algoritmi di flusso di dati più vecchi (probabilmente più semplici) tracciano le variabili direttamente e tale tracciamento deve essere compreso nel contesto della posizione.

Hai appena descritto un linguaggio di programmazione chiamato Forth . È open source e ha molte implementazioni che coprono il relativamente ingenuo, il molto sofisticato.

Una tecnica è quella di trattare ogni cosa nella tua macchina: lo stack, l'heap, il file system, lo schermo, ecc. avendo una lista azioni associata con ogni azione che prende il valore prodotto dall'azione precedente e restituendo un valore aggiornato. Ogni istruzione è essenzialmente un insieme di azioni aggiunte a questi elenchi.

Le azioni avranno ancora bisogno di un ordine relativo, ma non è necessario essere rigorose nel senso che ogni azione sia sequenziale con tutte le altre. Tuttavia, deve essere abbastanza rigoroso in modo che un'azione legga sempre il valore corretto e presenta tale valore alle ultime operazioni sulla variabile. Questo permette a queste azioni di ignorare lo stato del resto del sistema, si preoccupano solo dell'oggetto a cui vengono applicate. Qualsiasi altra informazione che usano è passata quando l'azione è stata aggiunta alla lista, o un'altra azione in un precedente gruppo di azioni temporali ha assegnato il valore.

Seguendo questo, due (o più) istruzioni producono un insieme di azioni su questi elenchi. Ora alcune azioni si annulleranno a vicenda. Dì swap a,b; swap b,a; . Questi hanno un effetto zero sul risultato quando sono uno accanto all'altro. Le azioni rimaste sono le azioni necessarie e sufficienti che devono verificarsi affinché quel codice sia stato eseguito.

Per ottimizzare questo codice:

1. Definisci una nuova istruzione che ha esattamente queste azioni come sua definizione.
2. Trova una serie più breve di istruzioni con le stesse azioni della sua definizione, si spera che con poche / nessuna azione di annullamento.

Vorrei anche fare un passo indietro e guardare la struttura del programma rappresentata dalla sorgente. Se questo è identico alla struttura della macchina, ignoralo, ma se si trova in strutture di ordine superiore prova ad applicare le tue ottimizzazioni a questo livello di grafico. A questo livello di dettagli semantici è molto più semplice applicare ottimizzazioni specifiche in quanto non è necessario riconoscerle da una sequenza di passaggi più piccoli e alcune query comuni su rami, fratelli, ecc. Sono banali.