Progettazione del compilatore - Ottimizzazione del codice

L'ottimizzazione è una tecnica di trasformazione del programma, che cerca di migliorare il codice facendogli consumare meno risorse (cioè CPU, memoria) e fornire alta velocità.

Nell'ottimizzazione, i costrutti di programmazione generale di alto livello sono sostituiti da codici di programmazione di basso livello molto efficienti. Un processo di ottimizzazione del codice deve seguire le tre regole indicate di seguito:

  • Il codice di uscita non deve in alcun modo modificare il significato del programma.

  • L'ottimizzazione dovrebbe aumentare la velocità del programma e, se possibile, il programma dovrebbe richiedere un numero inferiore di risorse.

  • L'ottimizzazione dovrebbe essere di per sé veloce e non dovrebbe ritardare l'intero processo di compilazione.

Gli sforzi per un codice ottimizzato possono essere effettuati a vari livelli di compilazione del processo.

  • All'inizio, gli utenti possono modificare / riorganizzare il codice o utilizzare algoritmi migliori per scrivere il codice.

  • Dopo aver generato il codice intermedio, il compilatore può modificare il codice intermedio calcolando gli indirizzi e migliorando i loop.

  • Durante la produzione del codice macchina di destinazione, il compilatore può utilizzare la gerarchia della memoria e i registri della CPU.

L'ottimizzazione può essere classificata ampiamente in due tipi: indipendente dalla macchina e dipendente dalla macchina.

Ottimizzazione indipendente dalla macchina

In questa ottimizzazione, il compilatore prende il codice intermedio e trasforma una parte del codice che non coinvolge alcun registro della CPU e / o posizioni di memoria assolute. Per esempio:

do
{
   item = 10;
   value = value + item; 
} while(value<100);

Questo codice comporta l'assegnazione ripetuta dell'elemento identificativo, che se mettiamo in questo modo:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

non dovrebbe solo salvare i cicli della CPU, ma può essere utilizzato su qualsiasi processore.

Ottimizzazione dipendente dalla macchina

L'ottimizzazione dipendente dalla macchina viene eseguita dopo che il codice di destinazione è stato generato e quando il codice viene trasformato in base all'architettura della macchina di destinazione. Coinvolge i registri della CPU e può avere riferimenti di memoria assoluti piuttosto che riferimenti relativi. Gli ottimizzatori dipendenti dalla macchina si sforzano di sfruttare al massimo la gerarchia della memoria.

Blocchi di base

I codici sorgente generalmente hanno un numero di istruzioni, che vengono sempre eseguite in sequenza e sono considerate come i blocchi di base del codice. Questi blocchi di base non hanno alcuna istruzione di salto tra di loro, cioè, quando viene eseguita la prima istruzione, tutte le istruzioni nello stesso blocco di base verranno eseguite nella loro sequenza di apparizione senza perdere il controllo del flusso del programma.

Un programma può avere vari costrutti come blocchi di base, come IF-THEN-ELSE, istruzioni condizionali SWITCH-CASE e cicli come DO-WHILE, FOR e REPEAT-UNTIL, ecc.

Identificazione di base del blocco

Possiamo utilizzare il seguente algoritmo per trovare i blocchi di base in un programma:

  • Cerca le istruzioni di intestazione di tutti i blocchi di base da cui inizia un blocco di base:

    • Prima affermazione di un programma.
    • Dichiarazioni che sono target di qualsiasi ramo (condizionale / incondizionato).
    • Dichiarazioni che seguono qualsiasi dichiarazione di filiale.

  • Le dichiarazioni di intestazione e le istruzioni che le seguono formano un blocco di base.

  • Un blocco di base non include alcuna istruzione di intestazione di nessun altro blocco di base.

I blocchi di base sono concetti importanti sia dal punto di vista della generazione del codice che dell'ottimizzazione.

I blocchi di base svolgono un ruolo importante nell'identificazione delle variabili, che vengono utilizzate più di una volta in un singolo blocco di base. Se una qualsiasi variabile viene utilizzata più di una volta, la memoria del registro allocata a quella variabile non deve essere svuotata a meno che il blocco non termini l'esecuzione.

Grafico del flusso di controllo

I blocchi di base in un programma possono essere rappresentati mediante grafici di flusso di controllo. Un grafico del flusso di controllo mostra come il controllo del programma viene passato tra i blocchi. È uno strumento utile che aiuta nell'ottimizzazione aiutando a individuare eventuali loop indesiderati nel programma.

Ottimizzazione del loop

La maggior parte dei programmi viene eseguita come un ciclo nel sistema. Diventa necessario ottimizzare i loop per risparmiare cicli e memoria della CPU. I loop possono essere ottimizzati con le seguenti tecniche:

  • Invariant code: Un frammento di codice che risiede nel ciclo e calcola lo stesso valore ad ogni iterazione è chiamato codice invariante del ciclo. Questo codice può essere spostato fuori dal ciclo salvandolo per essere calcolato una sola volta, invece che a ogni iterazione.

  • Induction analysis : Una variabile è chiamata variabile di induzione se il suo valore viene alterato all'interno del ciclo da un valore invariante del ciclo.

  • Strength reduction: Esistono espressioni che consumano più cicli della CPU, tempo e memoria. Queste espressioni dovrebbero essere sostituite con espressioni più economiche senza compromettere l'output dell'espressione. Ad esempio, la moltiplicazione (x * 2) è costosa in termini di cicli della CPU rispetto a (x << 1) e produce lo stesso risultato.

Eliminazione del codice morto

Il codice morto è una o più dichiarazioni di codice, che sono:

  • O mai giustiziato o irraggiungibile,
  • Oppure, se eseguito, il loro output non viene mai utilizzato.

Pertanto, il codice morto non ha alcun ruolo in alcuna operazione del programma e quindi può essere semplicemente eliminato.

Codice parzialmente morto

Esistono alcune istruzioni di codice i cui valori calcolati vengono utilizzati solo in determinate circostanze, ovvero, a volte i valori vengono utilizzati ea volte non lo sono. Tali codici sono noti come parzialmente dead-code.

Il grafico del flusso di controllo sopra mostra un pezzo di programma in cui la variabile "a" viene utilizzata per assegnare l'output dell'espressione "x * y". Supponiamo che il valore assegnato a "a" non venga mai utilizzato all'interno del ciclo. Immediatamente dopo che il controllo esce dal ciclo, a "a" viene assegnato il valore della variabile "z", che verrà utilizzato successivamente nel programma. Concludiamo qui che il codice di assegnazione di "a" non è mai utilizzato da nessuna parte, quindi è idoneo per essere eliminato.

Allo stesso modo, l'immagine sopra mostra che l'istruzione condizionale è sempre falsa, il che implica che il codice, scritto in caso vero, non verrà mai eseguito, quindi può essere rimosso.

Ridondanza parziale

Le espressioni ridondanti vengono calcolate più di una volta in un percorso parallelo, senza alcuna modifica negli operandi. Mentre le espressioni a ridondanza parziale vengono calcolate più di una volta in un percorso, senza alcuna modifica negli operandi. Per esempio,

[espressione ridondante]

[espressione parzialmente ridondante]

Il codice loop-invariant è parzialmente ridondante e può essere eliminato utilizzando una tecnica di code-motion.

Un altro esempio di codice parzialmente ridondante può essere:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

Assumiamo che i valori degli operandi (y e z) non vengono modificati dall'assegnazione della variabile a a variabile c. Qui, se l'affermazione della condizione è vera, allora y OP z viene calcolato due volte, altrimenti una volta. Il movimento del codice può essere utilizzato per eliminare questa ridondanza, come mostrato di seguito:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

Qui, se la condizione è vera o falsa; y OP z dovrebbe essere calcolato solo una volta.