Compilatore Design – Ottimizzazione del Codice

l’Ottimizzazione è un programma di trasformazione tecnica, che cerca di migliorare il codice facendo consumare meno risorse (cioè CPU, Memoria) e consegnare ad 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 output 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 meno numero di risorse.

• L’ottimizzazione dovrebbe essere rapida e non dovrebbe ritardare il processo di compilazione complessivo.

Gli sforzi per un codice ottimizzato possono essere fatti 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 mediante calcoli di 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 categorizzata ampiamente in due tipi : indipendente dalla macchina e dipendente dalla macchina.

Ottimizzazione indipendente dalla macchina

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

do{ item = 10; value = value + item; } while(value
This code involves repeated assignment of the identifier item, which if we put this way:
Item = 10;do{ value = value + item; } while(value
should not only save the CPU cycles, but can be used on any processor.
Machine-dependent Optimization
Machine-dependent optimization is done after the target code has been generated and when the code is transformed according to the target machine architecture. It involves CPU registers and may have absolute memory references rather than relative references. Machine-dependent optimizers put efforts to take maximum advantage of memory hierarchy.
Basic Blocks
Source codes generally have a number of instructions, which are always executed in sequence and are considered as the basic blocks of the code. These basic blocks do not have any jump statements among them, i.e., when the first instruction is executed, all the instructions in the same basic block will be executed in their sequence of appearance without losing the flow control of the program.
A program can have various constructs as basic blocks, like IF-THEN-ELSE, SWITCH-CASE conditional statements and loops such as DO-WHILE, FOR, and REPEAT-UNTIL, etc.
Basic block identification
We may use the following algorithm to find the basic blocks in a program:



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

Prima dichiarazione di un programma.
 Istruzioni che sono target di qualsiasi ramo (condizionale / incondizionato).
 Istruzioni che seguono qualsiasi istruzione di ramo.



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


Un blocco di base non include alcuna istruzione di intestazione di qualsiasi 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 variabile viene utilizzata più di una volta, la memoria del registro allocata a tale variabile non deve essere svuotata a meno che il blocco non finisca l’esecuzione.
Control Flow Graph 
 I blocchi di base di un programma possono essere rappresentati mediante control flow graph. Un grafico del flusso di controllo descrive come il controllo del programma viene passato tra i blocchi. È uno strumento utile che aiuta nell’ottimizzazione aiutando a localizzare eventuali loop indesiderati nel programma.

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


Codice invariante: 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 solo una volta, piuttosto che con ogni iterazione.


Analisi di induzione: una variabile è chiamata variabile di induzione se il suo valore è alterato all’interno del ciclo da un valore invariante del ciclo.


Riduzione della forza: esistono espressioni che consumano più cicli, tempo e memoria della CPU. 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 


Eliminazione del codice morto 
 Il codice morto è una o più istruzioni di codice, che sono:

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

Pertanto, il codice morto non ha alcun ruolo in alcuna operazione di 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, ad esempio, a volte vengono utilizzati i valori e talvolta 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 viene utilizzata la variabile ‘a’ 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 lascia il ciclo, a ‘a’ viene assegnato il valore della variabile ‘z’, che verrà utilizzata in seguito nel programma. Concludiamo qui che il codice di assegnazione di ‘ a ‘ non viene mai utilizzato da nessuna parte, quindi è idoneo per essere eliminato.

 Allo stesso modo, l’immagine sopra raffigura che l’istruzione condizionale è sempre falsa, il che implica che il codice, scritto nel caso vero, non verrà mai eseguito, quindi può essere rimosso.
Ridondanza parziale 
 Le espressioni ridondanti vengono calcolate più di una volta nel percorso parallelo, senza alcuna modifica degli operandi.mentre le espressioni ridondanti parziali vengono calcolate più di una volta in un percorso, senza alcuna modifica degli operandi. Ad esempio,

Il codice Loop-invariante è parzialmente ridondante e può essere eliminato utilizzando una tecnica di movimento del codice.
 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 vengano modificati dall’assegnazione della variabile a alla variabile c. Qui, se l’istruzione condition è true, y OP z viene calcolata 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 calcolata solo una volta.


Pubblicità