Loop Optimization

Introduzione

In questo capitolo verrano descritte trasformazioni di alto livello per l'ottimizzazione di programmi scritti in linguaggi imperativi per architetture ad alte performance (incluse macchine superscalari, vettoriali e multiprocessore).

Steps dell'applicazione di una trasformazione:

1. Decidere quale parte di programma da ottimizzare, e quale trasformazione applicare.

2. Verificare che la trasformazione può essere applicata.

3. Trasformare il programma (step su cui è presente il focus del corso).

Correttezza di una trasformazione

L'applicazione di una trasformazione deve lasciare il programma intatto.

Trasformazione legale: Una trasformazione è legale se i programmi originale e trasformato producono esattamente lo stesso output per ogni esecuzione identica.

Trasformazione legale (seconda definizione): Una trasformazione è legale se i programmi originale e trasformato producono esattamente lo stesso output per ogni esecuzione identica e sematicamente corretta.

Esecuzione identica: due esecuzioni sono identiche se hanno lo stesso input e se ogni coppia corrispondente di operazioni non deterministiche nelle due esecuzioni producono lo stesso risultato.

Operazione semicommutativa: Definiamo semicommutative trasformazioni che sono commutative algebricamente ma non dal punto di vista computazionale.

Scope di una trasformazione

1. Statement: solitamente espressioni aritmetiche

2. Basic Block

3. Innermost loop: parte del codice che è eseguita più di frequente, di conseguenza trasformazioni a questo livello sono molto efficaci dal punto di vista computazionale.

4. Perfect loop nest: ogni ciclo contiene solo un ciclo innestato e non altre istruzioni, eccetto il loop più interno.

5. General loop nest

6. Procedure

Data Dependencies

Possono essere control dependencies, derivanti da istruzioni di controllo del program flow, o data dependencies (RAW, WAR, WAW).

Queste ultime dipendono dall'uso delle stesse variabili (memerizzate in registri) da parte di istruzioni diverse:

1. Flow dependency: $S_{4}$ ha una flow dependence con $S_{3}$ ($\left.S_{3} \rightarrow S_{4}\right)$ quando $S_{3}$ deve essere eseguita prima perchè scrive un valore che è letto da $S_{4}$.

2. Antidependence: $S_{6}$ una una antidependence con $S_{5}$ (denoted by $\left.S_{5} \nrightarrow S_{6}\right)$ quando $S_{6}$ scrive una variabile letta da $S_{5}$.

3. Output dependence: $S_{8}$ ha una output dependence con $S_{7}$ (denoted by $S_{7}$ ㅇ $\left.S_{8}\right)$ quando entrambe le istruzioni scrivono la stessa variabile.

Note

• Stride: distanza tra accessi consecutivi ad un array, ad esempio un loop che accede ogni 4 elementi di un array è uno stride-4 loop. Più basso è lo stride, migliore è la memory locality.

• Mutiply/Add availability: molto frequenti nel processing di segnali, per questo motivo spesso sono previste negli ISP. Questa strategia comporta importanti incrementi prestazionali. Altri incrementi importanti sono forniti dal riutilizzo di cache lines.

• Gli algoritmi di dependence analysis assumono che i loop abbiano incrementi unitari del contatore associato, altrimenti il compilatore potrebbe non riuscire a normalizzare l'indice per gestire le loop-carried dependencies. Esempio di loop-carried dependency:

  do i = 2, n
  	a[i] = a[i] + c
  	b[i] = a[i-1] * b[i]
  end do

  Nel codice sopra non ci sono dipendenze all'interno delle singole iterazioni del loop, ma sono presenti dipendenze tra iterazioni contigue.

• Un iterazione può essere definita come un vettore di $d$ elementi $I = (i_1, \dots, i_d)$ dove ogni indice $i_p$ resta nell'intervallo previsto. Il loop più esterno corrisponde all'indice più a sinistra nell'array.

• Nel contesto di un loop, un istruzione in una generica iterazione $J$ dipende da un istruzione in una generica iterazione $I$ se e solo se almeno un accesso ad una variabile è in scrittura e $I \prec J \wedge \forall p: f_{p}(I)=g_{p}(J)$, cioè è presente una dipendenza quando i valori dei pedici delle variabili sono gli stessi in iterazioni differenti del ciclo.

• Distance Vector: Per una dipendenza $X \Rightarrow Y$ il distance vector è definito come:

  $$Y-X=\left(y_{1}-x_{1}, \ldots, y_{d}-x_{d}\right)$$

  Nota che il distance vector fa riferimento a dipendenze tra iterazioni dei loop, non a elementi di un array.

• Dependence Vector: A volte non è semplice capire la distanza esatta della relazione di dipendenza a compile time (la quale può anche variare tra iterazioni diverse dei loop). Definiamo il dependence vector per una dipendenza $I \rightarrow J$ come il vettore $W = (w_1, \dots, w_d)$, dove:

  $$w_{p}= \begin{cases}< & i_{p}<j_{p} \\ = & i_{p}=j_{p} \\ > & i_{p}>j_{p}\end{cases}$$

Ottimizzazioni (47 in totale)

General Purpose

1. Loop-Based Strength Reduction

   Scope fino al singolo statement, riduzione di un operatore utilizzando un operatore meno costoso. Gli incrementi prestazionali sono maggiori se applicato nel contesto dei loop.

   Expr	Init	Use	Update
   c * i	T = c	T	T = T + c
   c^i	T = c	T	T = T * c
   (-1)^i	T = -1	T	T = -T
   x / c	T = 1 / c	x * T

2. Induction Variable Elimination

   Definiamo l'induction variable come una variabile il cui valore deriva dal numero di iterazioni già eseguite dal un loop che la contiene. L'uso di strength reduction può portare all'eliminazione di inductions variable, riducendo la pressione sull'uso dei registri.

3. Loop-Invariant Code Motion

   Computazione all'interno di un loop, ma risultato loop invariant. La computazione può essere spostata all'esterno del loop.

   Una definizione più generica di questo processo è code hoisting, cioè lo spostamento di una qualunque computazione in un punto più recente della procedura.

4. Loop Unswitching

   Caso in cui un loop contiene un condizionale con una test condition che è loop independent. Il loop è replicato in entrambi i branch del condizionale, risparmiando il costo del confronto per ogni iterazione del ciclo.

   // og
   do ...
   	if ...
   		expr1
    	else
    		expr2
   end do
   // becomes
   if ...
   	do ... expr1; end do
   else
   	do ... expr2; end do

Loop Reordering

Focus principale delle trasformazioni che riguardano i loop, dal momento che migliorando il parallelismo e la memory locality questa tipologia di trasformazioni può portare importanti incrementi prestazionali.

1. Loop Interchange

   Scambia il livello di nesting di due loop in un perfect loop nest. Può essere utilizzata per:

   • Vettorizzazione

   • Migliorare performance tramite parallelizzazione.

   • Ridurre lo stride.

   • Aumentare il numero di espressioni loop invariant nel loop più interno.

   Esempio:

   do i = 1,n
   	do j = 1,n
   		tot[i] = tot[i] + a[i,j]
   	end do
   end do

   Diventa:

   do j = 1,n
   	do i = 1,n
   		tot[i] = tot[i] + a[i,j]
   	end do
   end do

   Se a è troppo grande per essere memorizzata in cache, lo scambio, riducendo il loop originariamente interno dal stride-n a stride-1, migliora le performance riducendo il numero di cache miss.

   Nella versione originale tot[i] può essere memorizzato in un registro, migliorando le performance se a è abbastanza piccola da essere contenuta in un registro.

   Scambiare i bound dei loop è semplice se lo spazio delle iterazioni è rettangolare.

2. Loop Skewing

   Utilizzato principalmente in combinazione con loop interchange, si applica a cicli innestati.

   Skewing: aggiunta di uno skewing factor (indice del loop esterno moltiplicato per una constante $f$) ai bounds dell'indice del loop più interno, e sottrazione della stessa quantità dagli utilizzi dell'indice nel ciclo interno.

   Può tornare particolarmente utile nel caso si acceda sequenzialmente a matrici prima per riga e poi per colonna (o viceversa) in modo da rendere il loop più esterno parallelizzabile: nessuno dei due cicli dell'esempio può essere parallelizzato in forma originale, ma dopo lo skewing le diagonali possono essere parallelizzate.

   // og
   do i=2, n-1
   	do j=2, m-1
   		a[i,j]=a[i-1,j]+a[i,j-1]+a[i+1,j]+a[i,j+1];
   	enddo
   enddo
   // skewed version
   // Dependence (1,0), (0,1)
   do i=2, n-1
   	do j=i+2, i+m-1
   		j'=j-i;
   		a[i,j'] = a[i-1,j']+a[i,j'-1]+a[i+1,j']+a[i,j'+1];
   	enddo
   enddo

3. Loop Reversal

   Cambia la direzione in cui viene effettuata l'iterazione del loop (ad esempio da zero ad n diventa da n a zero). Il cambiamento può essere propagato nel dependence vector negando l'entry corrispondente al loop in questione.

4. Strip Mining

   Modifica della granularità di un loop. Può essere utilizzata in ambito di vettorizzazione del codice.

   // og
   do i = 1,n
   	a[i] = a[i] + c
   end do

   // strip mined
   // divide n in strips of 64
   tn = bn/64c
   // loop on each strip at a time
   do ti = 1, tn, 64
   	a[ti:ti+63] = a[ti:ti+63] +c
   end do
   // cleanup
   do i = tn+1, n
   	a[i] = a[i] + c
   end do

   Ad esempio do i = 1, n divide n in strips di 64 elementi (tn = floor(n/64)). Poi il loop iterererà su una strip alla volta, e sugli elementi restanti (do i = tn+1, n). In questo modo il codice vettoriale può effettuare le operazioni direttamente sulle strips:

   ; R9=addr(a[ti]), F8=c
   LV VI, R9 ; load strip ti
   ADDSV V1, F8, V1 ; sum
   SV VI, R9 ; store strip

5. Cycle Shrinking

   Versione specializzata di strip mining.

   Trasformazione che converte un ciclo seriale in due cicli innestati, loop esterno (seriale) ed un loop interno (parallelizzato, come l'operazione vettoriale dell'esempio precedente a[ti:ti+63] = a[ti:ti+63] +c). Questa ottimizzazione è utile per permettere l'applicazione di strip mining al ciclo interno dal momento che l'elemento (o gli elementi) dell'array con cui esso lavora sono costanti per tutto lo spazio delle iterazioni del ciclo.

   Utilizzato in casi in cui il ciclo in questione ha dipendenze fra dati (cosa ad esempio non valida per l'esempio della trasformazione precedente) a distanza costante. In caso in cui i dati in questione sono memorizzati tramite matrici si utilizza Loop Tiling, una generalizzazione di Cycle Shrinking / Strip Mining.

6. Loop Tiling

   Generalizzazione multidimensionale di strip mining. L'obbiettivo primario è quello di migliorare il riutilizzo della cache (ad esempio un loop che manipola una matrice che è troppo grande per essere memorizzata in cache). Idea: blockwise matrix operations. Aumenta il numero di loop innestati dividendo la matrice in sottomatrici su cui effettuare la stessa operazione del loop originale.

   // original
   do i = 1, n
   	do j = 1, n
   		a[i,j] = b[j,i]
   	end do
   end do

   // tiled loop
   do ti=1, n, 64
   	do tj=1, n, 64
   		do i=ti, min(ti+63,n)
   			do j=tj, min(tj+63,n)
   				a[i,j] = b[j,i]
   			end do
   		end do
   	end do
   end do

7. Loop Distribution

   Suddivisione di un singolo loop in più loops. Ogni loop ha lo stesso spazio delle iterazioni del loop originale ma contiene un sottoinsieme delle istruzioni. Possibili utilizzi:

   • Perfect loop nests

   • Sottoloop con meno dipendenze

   • Miglioramenti di cache e TLB locality

   • Miglioramento del riutilizzo di registri

   Ad esempio posso avere un loop che lavora con due arrays, uno con dipendenze, l'altro senza. In questo modo posso parallelizzare il loop che accede al primo array.

8. Loop Fusion

   Inverso di loop distribution. Possibili miglioramenti:

   • Overhead minore

   • Miglior parallelismo

   • Miglior utilizzo di registri, operazioni vettoriali, data cache, TLB

   Per $n$ grandi questa trasformazione migliora le prestazioni su macchine vettoriali. Nota che per fondere due loop questi devono avere gli stesso bounds (condizione che può essere ottenuta via peeling).

   Non può essere eseguita se esistono due statements con dipendenze nel loop fuso.

Loop Restructuring

Trasformazioni che modificano la stuttura dei cicli.

1. Loop Unrolling

   Replicazione del corpo del ciclo per un certo numero di volte $u$, chiamato unrolling factor, usando $u$ come nuovo step. È la tecnica usata dalle macchine VLIW per generare le istruzioni. Miglioramenti:

   • Overhead minore

   • Miglior parallelismo

   • Miglioramenti nella locality di registri, data cache e TLB.

   Può essere necessario un loop epilogue nel caso in cui non è noto a compile time se il numero di iterazioni del loop sarà esattamente un multiplo di $u$.

   // original 
   do i = 2, n-1
   	a[i] = a[i] +a[i-1] *a[i+1]
   end do
   // after loop unrolling
   do i = 2, n-2, 2
   	a[i] = a[i] +a[i-1] *a[i+1]
   	a[i+1] =a[i+1] +a[i] *a[i+2]
   end do
   // epilogue
   if (mod(n-2,2) = 1) then
   	a[n-1] =a[n-1] +a[n-2] *a[n]
   end if

   Nota che, se $u > 2$, il loop epilogue è un loop e non un condizionale.

2. Loop Coalescing

   Contrario di tiling: abbiamo dei cicli innestati, li trasformiamo in un singolo ciclo. Dal momento che non modifica l'ordine delle iterazioni è sempre legale. Viene utilizzato un singolo iteratore da cui estraiamo gli iteratori dei precedenti due cicli all'interno del corpo del ciclo tramite manipolazione algebrica:

   // original
   do all i = 1, n
   	do all j=1, m
   		a[i,j] = a[i,j] + c
   	end do
   end do

   // coalesced loop
   do all t = 1, n * m
   	i = floor(t-1) + 1
   	j = (t-1 mod m) + 1
   	a[i,j] = a[i,j] + c
   end do all

3. Loop Collapsing

   Versione specializzata di loop coalescing in cui viene ridotta la dimensionalità di array multidimensionali modificati da cicli innestati (entrambi stride-1).

   // original
   do all i = 1, n
   	do all j=1, m
   		a[i,j] = a[i,j] + c
   	end do all
   end do all
   // collapsed loop
   real ta[n * m]
   equivalence(ta, a)
   do all t = 1, n * m
   	ta[t] = ta[t] + c
   end do all

4. Loop Peeling

   Permette loop fusion rimuovendo iterazioni iniziali o finali da un ciclo ed eseguendole separatamente. Utile per rimuovere dipendenze in modo da migliorare la parallelizzazione.

5. Loop Normalization

   Modifica i loop in modo che l'iteratore inizi da 1 (o 0), e sia incrementata di 1 ad ogi iterazione.

6. Loop Spreading

   Modifica due loop seriali fra loro in modo che parte della computazione all'interno del secondo loop venga spostata nel primo in modo che i due possano essere eseguiti in parallelo.

   // original loops
   do i = 1, n/2
   	a[i+1] += a[i]
   end do
   do i = 1, n-3
   	b[i+1] += b[i] + a[i+3]
   end do
   
   // after spreading
   do i = 1, n/2
   	COBEGIN
   	a[i+1] = a[i+1] + a[i]
   	if (i > 3) then
   		b[i-2] += b[i-3] + a[i]
   	end if
   	COEND
   end do
   do i = n/2-3, n-3
   	b[i+1] += b[i] + a[i+3]
   end do

Loop Replacement Transformation

Trasformazioni che modificano completamente la struttura dei cicli.

1. Reduction Recognition

   Trasformazione che calcola uno scalare a partire da un array. La riduzione può essere parallelizzata se l'operazione eseguita è associativa. La parallelizzazione maggiore si ottiene utilizzando un albero per eseguire la riduzione: si sommano gli elementi pair-wise in modo ricorsivo a partire dalle foglie. Il numero di operazioni passa da $O(n)$ a $O(\log{n})$.

2. Loop Idiom Recognition

   Termine generale per identificare il riconoscimento di istruzioni hardware specializzate, tipiche di macchine vettoriali o di architetture parallele (e.g. SIMD), che supportano la riduzione direttamente a livello hardware.

3. Array Statement Scalarization

   Nei linguaggi in cui alcune operazioni possono essere espresse con notazione degli array. Ad esempio:

   a[2:n-1] = a[2:n-1] +a[1:n-2]

   Verrà convertita in una versione scalare:

   // è necessario un array temporaneo per non
   // rompere la dipendenza con a[i-1] che viene
   // modificata ad ogni iterazione
   do i = 2, n-1
   	T[i] = a[i] + a[i-1]
   end do
   do i = 2, n-1
   	a[i] = T[i]
   end do

   Il problema può essere risolto invertendo il ciclo, eliminando così le antidipendenze.

Memory Access Transformations

Ottimizzazioni dell'uso della memoria per migliorare il riutilizzo e la parallelizzazione. L'utilizzo efficiente dei registri e della cache di primo livello è essenziale.

1. Array Padding

   Data locations inutilizzate vengono inserite tra le celle di un array, o tra array diversi, oppure array vengono memorizzati in modo interleaved. Utile per mitigare conflitti di bank, cache e TLB. Grazie al padding si ottiene uno stride-1 tra le varie banks, in modo che il padding $p$ rispetti il seguente vincolo: $\gcd{(s + p, B)} = 1$, con $s$ lo stride originario e $B$ il numero di banks.

   Gli svantaggi sono utilizzo di memoria maggiore, e conflitti con altre ottimizzazioni come ad esempio loop collapsing.

2. Scalar Expansion

   In caso di variabili usate come temporary all'interno del corpo di cicli, tali variabili creano antidipendenze fra iterazioni. Allocando una temporary per ogni iterazione (un array di dimensioni uguale al numero di iterazioni del ciclo ad esempio) risolve questo problema.

3. Array Contraction

   Riduzione di una delle dimensioni dell'array se questa non viene utilizzata all'interno di un ciclo innestato.

   real T[n,n]
   do i = 1, n
   	do all j = 1, n
   		T[i,j] = a[i,j] * 3
   		b[i,j] = T[i,j]+b[i,j]/T[i,j]
   	end do all
   end do
   // contraction
   real T[n]
   do i = 1, n
   	do all j = 1, n
   		T[j] = a[i,j] * 3
   		b[i,j] = T[j] +b[i,j]/T[j]c
   	end do all
   end do

4. Scalar Replacement

   Simile ad Array Contraction, quanto un elemento di un array è utilizzato di frequente in un loop innestato, può essere memorizzato in un registro e salvato in memoria quando il loop interno smette di iterare.

5. Code Colocation

   Si applica tipicamente a instruction cache. Aumenta la dimensione del codice, ma diminuisce il numero di salti.

   Migliora l'accesso della memoria facendo in modo che codice correlato sia memorizzato nelle stesse aree di memoria.

   Ottenuto tramite profiling della frequenza con cui determinati costrutti vengono eseguiti.

6. Displacement Minimization

   Simile a code colocation, ma relativo ai Basic Block: consiste nel posizionamento in aree di memoria contigue di B.B. eseguiti spesso nello stesso execution flow.

   Il posizionamento di B.B. è un problema di ottimizzazione complesso. Il target di un branch o di un jump è specificato relativamente al valore del program counter (PC), se il controllo è trasferito in un'area di memoria al di fuori del range dell'offset, è necessaria una sequenza di più istruzioni per effettuare il salto con un conseguente peggioramento prestazionale. Il codice quindi dovrebbe essere organizzato in modo da salvare in memoria sezioni di codice correlato tali per cui siano vicine.

Partial Evaluation

Trasformazioni che fanno riferimento alla precomputazione a compile time di parti del codice.

1. Constant Propagation

   // og
   n = 64
   c = 3
   do i = 1, n
   	a[i] = a[i] + c
   end d
   // propagated code
   do i = 1, 64
   	a[i] = a[i] + 3
   end do

2. Constant Folding

   Se un espressione contiene un operazione con valori costanti come operandi, il compilatore può sostuirla con il risultato.

3. Copy Propagation

   Se alcune variabili sono riassegnate, il compilatore può propagare la variabile originale in modo da eliminare copie ridondanti.

4. Forward Substitution

   Generalizzazione di Copy Propagation, utilizzo di una variabile è sostituito dalla sua definizione.

   // original code
   np1 = n + 1
   do i = 1, n
   	a[np1] = a[np1] + a[i]
   // forward substitution
   do all i = 1, n
   	a[n+1] = a[n+1] + a[i]
   end do all

5. Algebraic Simplification

   Il compilatore applica regole algebriche per ottimizzare alcune operazioni (e.g. $\cdot 0, + 0, \cdot 1, + 1$)

6. Strength Reduction

   Operatori costosi sono sostuiti con operatori meno costosi (e.g. $x \cdot 2$ diventa diventa $x \cdot x$, etc.). Il codice della funzione è ottimizzato e la chiamata originaria è sostituita con la nuova versione, che occupa più spazio ma è più efficiente.

7. Superoptimizing

   Trasformazione che cerca di sostituire una sequenza di istruzioni con l'alternativa ottimale tramite ricerca esaustiva (iniziando da una sequenza di una sola istruzione, e in caso la sostituzione non sia effettuabile, reitera il processo aumentando il numero di istruzioni prese in considerazione).

Redundancy Elimination

Trasformazioni con l'obbiettivo di eliminare due tipi di computazioni: quelle che non sono raggiungibili, e quelle che non servono alcuna utilità.

Spesso è utile per "ripulire" tali computazioni dopo che altre ottimizzazioni hanno modificato la struttura del codice.

1. Unreachable-Code Elimination

   Codice che non verrà raggiunto da nessuna path del CFG della procedura, ad esempio un condizionale che è sempre vero o sempre falso, oppure un loop che itera zero volte. Spesso codice non raggiungibile viene generato da constant propagation, ad esempio $x \le 0$ può diventare $\text{const} \le 0$ e di conseguenza uno dei branch del condizionale può diventare non raggiungibile.

2. Useless-Code Elimination

   Se il compilatore verifica che un valore genenerato da una computazione non è utilizzato, il codice associato a tale computazione verrà rimosso.

3. Dead-Variable Elimination

   Spesso dopo loop optimization alcune variabili non verranno mai usate. In tal caso le dead variables saranno rimosse dal codice.

4. Common-Subexpression Elimination

   Spesso Alcune computazioni lavorano con le stesse sottoespressioni, le quali possono essere calcolate una sola volta, salvate in memoria, e riutilizzate quando necessario. È comunque presente un tradeoff che vede da un lato un incremento prestazionale, dall'altro una maggiore pressione sui registri.

5. Short Circuiting

   Utilizzato su espressioni booleane, se il valore può essere determinato dal primo operando dell'espressione, la parte rimanente dell'espressione non verrà computata.

Procedure Call Transformation

Trasformazioni che effettuano una rimozione di chiamate oppure di overhead da queste ultime.

1. Leaf Procedure Optimization

   Leaf procedures sono utili per ridurre l'utilizzo dello stack frame: non è necessario salvare l'indirizzo di ritorno sullo stack, ma quest'ultimo può essere salvato in un registro. Inoltre se non utilizza variabili, si può anche evitare di scrivere lo stack frame.

2. Cross-Call Register Allocation

   Se una chiamata a procedura non utilizza i registri del caller, il callee può evitare di salvarli (modifica a livello di ABI).

3. Parameter Promotion

   Quando un parametro è passato per riferimento, il calcolo dell'indirizzo è effettuato dal chiamante, ma la load è effettuata dal chiamato.

   Se il compilatore identifica correttamente i chiamanti di una leaf procedure, espanderà il loro stack frame per includere i dati di quest'ultima, che eviterà di effettuare una nuova allocazione sullo stack.

4. Procedure Inlining

   Sostituisce una chiamata a procedura con una copia del corpo della procedura chiamata. Non può essere effettuata con chiamate ricorsive a meno che non abbia un numero limitato di passi.

   È utile per migliorare la precisione dell'analisi del compilatore, rimuovendo la necessità di effettuare inter procedure analysis da parte del compilatore, e anche per migliorare le prestazioni riducendo il costo di modificare il flow di esecuzione del programma con un salto.

   Uno svantaggio importante di questa trasformazione è un aumento nella dimensione del codice.

5. Procedure Cloning

   Specializzazione ottimizzata di una procedura, ad esempio con diversi tipologie di parametri. Verrà generata una versione specializzata per ogni versione richiesta nel codice.

6. Loop Pushing

   Simile ad hoisting, ma include una call. Sposta un loop innestato dal chiamante ad una versione clonata della procedura chiamata. In questo modo rimuove l'overhead della chiamata, e può permette la parallelizzazione dei cicli.

   // og
   do i = 1, n
   	call f(x, i)
   end do
   
   subroutine f(a, j)
   real a[*]
   a[j] = a[j] + c
   return

   // loop pushing
   call f_2(x)
   
   subroutine f_2(a)
   real a[*]
   do all i = 1, n
   	a[i] = a[i] + c
   end do all
   return

7. Tail Recursion Elimination

   Ottimizzazione potente in linguaggi funzionali. Si ha una procedura che chiama se stessa e ritorna il valore della chiamata ricorsiva.

   Questa trasformazione trasforma la ricorsione in un ciclo.

   Meno comune per linguaggi imperativi.

8. Function Memoization

   Memorizza il risultato di una chiamata a procedura, i queli verrano utilizzati in caso tale procedura venga chiamata nuovamente. Utile per funzioni particolarmente onerose (e.g. funzioni trigonometriche in alcuni casi).