Registrati assegnazione e fuoriuscita, il modo più semplice?

Question

Sto cercando un modo per assegnare le variabili locali ai registri. Sono a conoscenza di un paio di metodi seri per farlo (vale a dire, quelli menzionati su Wikipedia ) , ma mi sono bloccato su come "Rovesciare" è compiuto. Inoltre, la letteratura è abbastanza intimidatorio. Spero ci sia qualcosa di più semplice in grado di soddisfare le mie priorità:

1. Correttezza - un algoritmo che genera codice corretto indipendentemente dal numero di variabili locali ci sono
.
2. Semplicità -. Qualcosa che posso capire senza dover leggere troppo letteratura
3. Efficienza - ha bisogno di essere migliore rispetto al metodo attuale, che è:

Tradurre un x = y # z operazione:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

Come sto mira Intel 386, alcuni vincoli rilevanti sono:

• Le operazioni binarie prendono due argomenti, uno dei quali è una sorgente e destinazione. operazioni unarie prendere un singolo argomento.
• Le operazioni possono accedere solo una locazione di memoria; operazioni binarie devono pertanto almeno un argomento in un registro.
• C'è un massimo di sei registri disponibili: %eax %ebx %ecx %edx %esi %edi. (%ebp potrebbe anche essere incluso come ultima risorsa.)
• Ci sono casi particolari, come per la divisione intera e tornare registri, ma li possono ignorare per il momento.

Ci sono tre passi il compilatore passa attraverso in questo momento:

• i386ification:. Tutte le operazioni vengono convertiti in una forma a = a # b (o a = #a per operazioni unarie)
• Analisi Liveness:. I set di variabili in tempo reale prima e dopo ogni operazione sono determinati
• Registra allocazione:. Un grafico di interferenza è costruito e colorato

E poi il compilatore tiri i suoi pastelli in aria e non sa cosa fare.

Esempio

public int mf(int cr, int ci) {
    int i = 0;
    int zr = 0;
    int zi = 0;

    while (i < 100 && zr*zr + zi*zi < 4) {
        int t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;

        i = i + 1;
    }
    return i;
}

Ecco il grafico interferenza piuttosto carina per la funzione, e il CFG informazioni vitalità. L'immagine CFG richiede una certa scorrimento verticale, purtroppo.

• grafico disturbo per una funzione di 14 variabili
• grafico di controllo del flusso per una funzione, con informazioni vitalità

Sette colori sono stati utilizzati. Vorrei versare uno di loro (o l'insieme di variabili assegnato quel colore). Il metodo di scelta che non è troppo importante. Che cosa diventa difficile è come trattare con le variabili versato.

Diciamo che spill "rosa", che è l'insieme di variabili t, $t4, $t7. Ciò significa che tali operazioni si riferiscono a una di queste variabili verranno accedervi dalla sua posizione sul telaio pila, piuttosto che attraverso un registro. Questo dovrebbe funzionare per questo esempio.

Ma cosa succede se il programma è stato:

...
a = a + b
...

ed entrambi a e b dovevano essere rovesciato? Non posso emettere un addl b, a istruzione con due indirizzi di memoria. Avrei bisogno di un altro registro di riserva per tenere temporaneamente uno degli operandi, e questo significa versare altro colore. Ciò suggerisce un metodo generale di:

1. Se tutte le variabili possono essere colorati con colori r, grande!
2. In caso contrario, versare alcuni colori e le loro variabili associate.
3. Se un'operazione che esiste che accede due variabili versato, versare un altro colore e utilizzare il registro di ricambio per l'archiviazione temporanea per tutti tali operazioni.

A questo punto ho il sospetto che un sacco più roba viene versato del necessario, e mi chiedo se c'è qualche modo più intelligente per rovesciare le cose, come la fuoriuscita di una parte della vita di una variabile, piuttosto than tutta variabile stessa. Ci sono alcune semplici tecniche (ish) che potrei usare qui? Di nuovo, non sto puntando particolarmente elevato - non certo da richiedere la lettura di qualcosa di troppo in profondità. ; -)

Problemi specifici

Il principale problema specifico è: quando viene versato una variabile, in che modo incide le istruzioni generate? Fare tutte le istruzioni utilizzando tale esigenza variabile per accedervi direttamente in memoria (dalla sua posizione stack)? Come sarà questo lavoro se un'operazione utilizza due variabili versato? (L'architettura non consente istruzioni per accedere due locazioni di memoria distinte.)

problemi secondari sono:

• Come faccio a determinare dove inserire istruzioni di load / store, per la correttezza (e meno importante, l'efficienza)?
• Posso versare una variabile solo per quella parte della sua vita, quando non è in uso immediato, e unspill in un secondo momento? In modo che tutte le istruzioni agiscono sui registri unspilled. Una variabile può vivere in diversi registri in tempi diversi.
• Posso essere un po 'più efficiente con casi particolari. Ad esempio, %eax viene utilizzato per il valore di ritorno, quindi sarebbe bello se la variabile da restituire successo da assegnare a tale registro per il momento è stato rilevato il ritorno. Allo stesso modo, alcuni registri sono "callee-save", quindi se meno variabili capitato di essere sotto tensione al momento di una chiamata di funzione, dopo averli assegnati ai non-callee-save registri significherebbe posso evitare di memorizzare questi registri.
• Sarebbe SSA forma di aiuto molto (se non del tutto)? Essere in grado di eliminare sottoespressioni comuni e valutare le costanti potrebbe ridurre (?) Registrare la pressione, ma per il resto avrebbe avuto effetto?

Gli aspetti io non sono preoccupato per (in questo momento) sono:

• allocazione Stack e ottimizzazione: è implementato ingenuamente già, e possono essere ottimizzati utilizzando il grafico di interferenza, se necessario
.
• l'efficienza in fase di compilazione, basta che termina. (NP-completezza non implica un dato algoritmo dovrebbe essere evitato.)

Aggiornamento

Ci scusiamo per i tempi di inattività - ho pensato a delle risposte fornite e cercando di trovare un approccio facile da prendere per iniziare ad attuare alcune delle idee. Per essere onesti, sono stato procrastinare ...: - \

Ho trovato molto bella presentazione (PPT, purtroppo):

http: //www.cs. princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

Il che risponde alla domanda su come affrontare specifiche esigenze di funzionamento (come l'utilizzo stesso registro per la sorgente e la destinazione, o che necessitano di un certo registro per alcune operazioni). Quello che non sono sicuro è se il ciclo Liveness-Coloring-allocazione termina.

Cercherò di fare qualche lavoro effettivo presto e si spera di chiudere la questione.

Answer 1

Ho usato un approccio goloso in un allocatore JVM una volta, che ha funzionato abbastanza bene. Fondamentalmente partire dall'alto di un blocco di base con tutti i valori memorizzati nello stack. Poi basta scansionare le istruzioni in avanti, il mantenimento di un elenco di registri che contengono un valore, e se il valore è sporco (deve essere scritto indietro). Se un'istruzione utilizza un valore che non è in un registro (o non nel registro corretta), emettere un carico (o spostare) per metterlo in un registro libera prima dell'istruzione. Se un'istruzione scrive un valore, assicurarsi che sia in un registro e segnare sporca dopo l'istruzione.

Se hai bisogno di un registro, fuoriuscita di un registro utilizzato dal deallocando il valore da esso, e la scrittura alla pila se è sporco e vivere. Alla fine del blocco di base, scrivere di nuovo tutti i registri sporchi e dal vivo.

Questo schema mette in chiaro esattamente dove tutti i carichi / negozi vanno, li generano, come si va. È facilmente adattabile alle istruzioni che prendono un valore in memoria, o che possono assumere due argomenti in memoria, ma non entrambe.

Se sei OK di avere tutti i dati nello stack ad ogni confine blocco di base, questo sistema funziona abbastanza bene. Dovrebbe dare risultati simili a scansione lineare all'interno di un blocco di base, come fa fondamentalmente le cose molto simili.

È possibile ottenere arbitrariamente complicato su come decidere quali valori versare e che registra da allocare. Alcuni lookahead può essere utile, ad esempio mediante marcatura ogni valore con uno specifico registro deve essere in un certo punto nel blocco di base (es eax per un valore di ritorno, o ecx per una quantità di spostamento) e preferendo che registrare quando il valore viene dapprima allocato (ed evitando che il registro per altre allocazioni). Ma è facile separare la correttezza dell'algoritmo dalle euristiche di miglioramento.

Ho usato questo allocatore in un compilatore SSA, YMMV.

Answer 2

In primo luogo: Non c'è un modo intelligente per farlo. Il problema è NP-completo; -)

Come si fa rovesciarsi:

Si esegue l'algoritmo di allocazione registrarsi e ottenere un elenco di variabili si deve versare. Ora è possibile allocare po 'di spazio sullo stack all'inizio della funzione. Collegare ogni versato variabile anche un posto in pila. Se si vuole essere memoria intelligente si fondono con le gamme dal vivo che non si sovrappongono. Ogni volta che è necessario versare un registro salvarlo memoria e caricarlo, quando serve di nuovo.

Come gestire EAX:

Segna registro di cui riempiva, ma non memorizzare qualsiasi variabile in esso (preassegnazione). Questo renderà il generatore di codice chiaro che il registro. Per essere intelligente memorizzare il valore in un altro registro, se vantaggioso.

Facile e modi corretti per gestire fuoriuscite:

Basta versare tutto. Questo assume che vanno dal vivo di ogni variabile è l'intero programma. Questo può essere aumentata utilizzando cose come LRU o l'uso del numero di scegliere quale registri dovrebbe essere liberato.

La cosa migliore da fare è probabilmente scansione lineare allocazione dei registri . Dovrebbe essere abbastanza facile da implementare anche quando si utilizza pre-allocazione. Vi suggerisco di guardare nella carta collegato.

risposte specifiche

1. Che cosa significa per te la correttezza? Anche i semplici algoritmi accantonamenti sono corrette se non si commette un errore di programmazione. Di correzione (matematica) la correttezza è molto più difficile. Entrambi i carichi e negozi devono essere inserite prima del valore / registro è necessario nuovamente. Entrambe devono essere inserito dopo il valore viene memorizzato / creato.

2. Sì. Se si programma in questo modo. Se il vostro algoritmo in grado di gestire un valore in più registri durante il suo livetime puoi utilizzare tali ottimizzazioni.

3. E 'di nuovo a voi per implementare alcuni miglioramenti. Una possibilità potrebbe essere quella di solo eax blocco quando ce n'è bisogno, non per l'intero programma.

4. In determinate condizioni di SSA aiuta. grafici inferenza di codice SSA sono cordale , il che significa che non v'è alcun ciclo con più di 3 nodi. Questo è un caso speciale di colorazione dei grafi, in cui una colorazione minimo può essere trovato in tempo polinomiale. Conversione in SSA non significa necessariamente più o meno pressione registro. Mentre modulo SSA di solito ha più variabili, questi tendono ad avere livetimes più piccoli.