Progettazione del compilatore - Generazione di codice

La generazione del codice può essere considerata come la fase finale della compilazione. Attraverso la generazione del codice postale, il processo di ottimizzazione può essere applicato al codice, ma ciò può essere visto come parte della fase di generazione del codice stessa. Il codice generato dal compilatore è un codice oggetto di un linguaggio di programmazione di livello inferiore, ad esempio il linguaggio assembly. Abbiamo visto che il codice sorgente scritto in un linguaggio di livello superiore viene trasformato in un linguaggio di livello inferiore che si traduce in un codice oggetto di livello inferiore, che dovrebbe avere le seguenti proprietà minime:

  • Dovrebbe avere il significato esatto del codice sorgente.
  • Dovrebbe essere efficiente in termini di utilizzo della CPU e gestione della memoria.

Vedremo ora come il codice intermedio viene trasformato in codice oggetto di destinazione (codice assembly, in questo caso).

Grafico aciclico diretto

Directed Acyclic Graph (DAG) è uno strumento che rappresenta la struttura dei blocchi di base, aiuta a vedere il flusso di valori che scorre tra i blocchi di base e offre anche l'ottimizzazione. DAG fornisce una facile trasformazione sui blocchi di base. DAG può essere compreso qui:

  • I nodi foglia rappresentano identificatori, nomi o costanti.

  • I nodi interni rappresentano gli operatori.

  • I nodi interni rappresentano anche i risultati delle espressioni o degli identificatori / nome in cui i valori devono essere memorizzati o assegnati.

Example:

t0 = a + b
t1 = t0 + c
d = t0 + t1

[t 0 = a + b]

[t 1 = t 0 + c]

[d = t 0 + t 1 ]

Ottimizzazione dello spioncino

Questa tecnica di ottimizzazione funziona localmente sul codice sorgente per trasformarlo in un codice ottimizzato. Con localmente, si intende una piccola porzione del blocco di codice a portata di mano. Questi metodi possono essere applicati sia ai codici intermedi che ai codici target. Viene analizzata una serie di dichiarazioni e viene verificata la seguente possibile ottimizzazione:

Eliminazione ridondante delle istruzioni

A livello di codice sorgente, l'utente può eseguire quanto segue:

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }
 
int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }
 
int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }
 
int add_ten(int x)
   {
   return x + 10;
   }

A livello di compilazione, il compilatore cerca istruzioni di natura ridondante. Il caricamento e la memorizzazione multipli di istruzioni possono avere lo stesso significato anche se alcune di esse vengono rimosse. Per esempio:

  • MOV x, R0
  • MOV R0, R1

Possiamo cancellare la prima istruzione e riscrivere la frase come:

MOV x, R1

Codice irraggiungibile

Il codice non raggiungibile è una parte del codice del programma a cui non si accede mai a causa dei costrutti di programmazione. I programmatori potrebbero aver scritto accidentalmente un pezzo di codice che non potrà mai essere raggiunto.

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

In questo segmento di codice, il printf L'istruzione non verrà mai eseguita poiché il controllo del programma ritorna prima che possa essere eseguito, quindi printf può essere rimosso.

Ottimizzazione del flusso di controllo

Esistono casi in un codice in cui il controllo del programma salta avanti e indietro senza eseguire attività significative. Questi salti possono essere rimossi. Considera il seguente pezzo di codice:

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

In questo codice, l'etichetta L1 può essere rimossa mentre passa il controllo a L2. Quindi, invece di saltare a L1 e quindi a L2, il controllo può raggiungere direttamente L2, come mostrato di seguito:

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

Semplificazione delle espressioni algebriche

Ci sono occasioni in cui le espressioni algebriche possono essere rese semplici. Ad esempio, l'espressionea = a + 0 può essere sostituito da a stesso e l'espressione a = a + 1 può essere semplicemente sostituita da INC a.

Riduzione della forza

Ci sono operazioni che consumano più tempo e spazio. La loro "forza" può essere ridotta sostituendoli con altre operazioni che consumano meno tempo e spazio, ma producono lo stesso risultato.

Per esempio, x * 2 può essere sostituito da x << 1, che prevede un solo spostamento a sinistra. Sebbene l'output di a * a e 2 sia lo stesso, 2 è molto più efficiente da implementare.

Accesso alle istruzioni della macchina

La macchina di destinazione può distribuire istruzioni più sofisticate, che possono avere la capacità di eseguire operazioni specifiche in modo molto efficiente. Se il codice di destinazione può accogliere direttamente quelle istruzioni, ciò non solo migliorerà la qualità del codice, ma produrrà anche risultati più efficienti.

Generatore di codici

Ci si aspetta che un generatore di codice abbia una comprensione dell'ambiente di runtime della macchina di destinazione e del suo set di istruzioni. Il generatore di codice dovrebbe prendere in considerazione le seguenti cose per generare il codice:

  • Target language: Il generatore di codice deve essere consapevole della natura della lingua di destinazione per la quale il codice deve essere trasformato. Quel linguaggio può facilitare alcune istruzioni specifiche della macchina per aiutare il compilatore a generare il codice in un modo più conveniente. La macchina di destinazione può avere l'architettura del processore CISC o RISC.

  • IR Type: La rappresentazione intermedia ha varie forme. Può essere in struttura AST (Abstract Syntax Tree), notazione polacca inversa o codice a 3 indirizzi.

  • Selection of instruction: Il generatore di codice prende la rappresentazione intermedia come input e la converte (mappa) nel set di istruzioni della macchina di destinazione. Una rappresentazione può avere molti modi (istruzioni) per convertirla, quindi diventa responsabilità del generatore di codice scegliere con saggezza le istruzioni appropriate.

  • Register allocation: Un programma ha un numero di valori da mantenere durante l'esecuzione. L'architettura della macchina di destinazione potrebbe non consentire la conservazione di tutti i valori nella memoria o nei registri della CPU. Il generatore di codice decide quali valori mantenere nei registri. Inoltre, decide i registri da utilizzare per mantenere questi valori.

  • Ordering of instructions: Alla fine, il generatore di codice decide l'ordine in cui verrà eseguita l'istruzione. Crea programmi per le istruzioni per eseguirli.

Descrittori

Il generatore di codice deve tenere traccia sia dei registri (per disponibilità) che degli indirizzi (posizione dei valori) durante la generazione del codice. Per entrambi vengono utilizzati i seguenti due descrittori:

  • Register descriptor: Il descrittore di registro viene utilizzato per informare il generatore di codice sulla disponibilità dei registri. Il descrittore di registro tiene traccia dei valori memorizzati in ogni registro. Ogni volta che è richiesto un nuovo registro durante la generazione del codice, questo descrittore viene consultato per la disponibilità del registro.

  • Address descriptor: I valori dei nomi (identificatori) utilizzati nel programma potrebbero essere memorizzati in posizioni diverse durante l'esecuzione. I descrittori di indirizzo vengono utilizzati per tenere traccia delle posizioni di memoria in cui sono memorizzati i valori degli identificatori. Queste posizioni possono includere registri della CPU, heap, stack, memoria o una combinazione delle posizioni menzionate.

Il generatore di codice mantiene entrambi i descrittori aggiornati in tempo reale. Per un'istruzione load, LD R1, x, il generatore di codice:

  • aggiorna il descrittore di registro R1 che ha valore x e
  • aggiorna il descrittore indirizzo (x) per mostrare che un'istanza di x è in R1.

Generazione di codice

I blocchi di base comprendono una sequenza di istruzioni a tre indirizzi. Il generatore di codice accetta queste sequenze di istruzioni come input.

Note: Se il valore di un nome si trova in più di una posizione (registro, cache o memoria), il valore del registro sarà preferito rispetto alla cache e alla memoria principale. Allo stesso modo il valore della cache sarà preferito rispetto alla memoria principale. Alla memoria principale viene data a malapena alcuna preferenza.

getReg: Il generatore di codice utilizza la funzione getReg per determinare lo stato dei registri disponibili e la posizione dei valori del nome. getReg funziona come segue:

  • Se la variabile Y è già nel registro R, utilizza quel registro.

  • Altrimenti, se è disponibile un registro R, utilizza quel registro.

  • Altrimenti, se entrambe le opzioni precedenti non sono possibili, sceglie un registro che richiede un numero minimo di istruzioni di caricamento e memorizzazione.

Per un'istruzione x = y OP z, il generatore di codice può eseguire le seguenti azioni. Supponiamo che L sia la posizione (preferibilmente registro) in cui deve essere salvato l'output di y OP z:

  • Chiama la funzione getReg, per decidere la posizione di L.

  • Determina la posizione attuale (registro o memoria) di y consultando il Descrittore dell'indirizzo di y. Sey non è attualmente nel registro L, quindi genera la seguente istruzione per copiare il valore di y per L:

    MOV y ', L

    dove y’ rappresenta il valore copiato di y.

  • Determina la posizione attuale di z utilizzando lo stesso metodo utilizzato nel passaggio 2 per y e genera la seguente istruzione:

    OP z ', L

    dove z’ rappresenta il valore copiato di z.

  • Ora L contiene il valore di y OP z, a cui si intende assegnare x. Quindi, se L è un registro, aggiorna il suo descrittore per indicare che contiene il valore dix. Aggiorna il descrittore dix per indicare che è archiviato nella posizione L.

  • Se yez non ha più alcun utilizzo, possono essere restituiti al sistema.

Altri costrutti di codice come i cicli e le istruzioni condizionali vengono trasformati in linguaggio assembly in modo assembly generale.