Register Allocation

Register Allocation: procedura che mappa le variabili nei registri.

• L'accesso ai registri è molto più veloce dell'accesso alla memoria centrale.

• Il mapping dalle variabili ai registri è di tipo many-to-one.

• Il numero di live variables può essere maggiore del numero di registri.

• Per liberare registri quando necessario, le variabili memorizzate in essi devono essere prima salvare in memoria centrale.

Scopes dell'allocazione delle variabili nei registri:

1. For expressions (naive).

2. For basic blocks.

3. For one procedure (quella su cui ci concentreremo).

4. For the entire program (impossibile nella pratica).

Vantaggi di unità di allocazione piccola:

• Facile da integrare con la fase di Instruction Selection.

• Più semplice e veloce di soluzioni più complesse.

• Prono ad applicazioni di compilazione dinamica.

Liveness Interference

Criterio per l'allocazione delle variabili nei registri: Se gli intervalli di liveness di due variabili sono disgiunti, può essere utilizzato lo stesso registro per memorizzare entrambe le variabili (in istanti di tempo diversi). Bisogna cioè evitare di utilizzare lo stesso registro per memorizzare due variabili che sono alive in contemporanea.

Liveness interference relation: Una relazione binaria e simmetrica tra due variabili $a$ e $b$ che denota il fatto che i liveness intervals di $a$ e $b$ sono sovrapposti.

Graph Coloring

La relazione di interferenza può essere rappresentata come un grafo non orientato. I registri possono essere rappresentati assegnando un colore distinto a ciascuno di essi. L'assegnamento dei registri consiste nella colorazione dei nodi del grafo in modo che nodi adiacenti abbiano colori diversi (problema analogo alla colorazione delle mappe politiche).

Se non è possibile trovare una soluzione dato un certo grafo ed un certo numero di registri -> spill delle variabili in memoria, nuova assegnazione dei colori. Per effettuare tale operazione vengono utilizzare euristiche a complessità lineare.

Algoritmo

Definiamo $S$ come lo stack in cui inserisco i nodi estratto dal grafo delle interferenze, e $K$ come il numero di registri a disposizione.

1. Costruisco l'interference graph.

2. Per ogni nodo $p$, estraggo $p$ e lo inserisco in $S$ se il nodo in questione ha $< K$ vicini.

3. Ripeto la stessa procedura per i nodi rimasti, però li marco come potential spills.

4. Riparto dall'interference graph; tramite una procedura iterativa estraggo i nodi da $S$. Ad ogni passo estraggo un nodo $p$ e gli assegno un colore.

   Se il nodo $p$ appena estratto non è marcato come potential spill, assegno un colore al nodo corrispondente nel grafo in modo che non sia in conflitto con i colori dei vicini. Se il nodo è marcato come potential spill, tento comunque l'assegnazione di un colore. Se cioò non è possibile, marco la variabile come actual spill, e la spillo in memoria.

Il passo 4 termina quando $S = \empty$. Quando ciò accade, avremo colorato tutto il grafo.

Repeat until successful:
	Build: Construct Liveness Interference Graph G
  Repeat until graph is empty:
  	Simplify: Reduce the graph removing colorable nodes
  	Spill: Select from remaining nodes a candidate for spilling
	Select: Assign registers or mark nodes as spilled
	Start over: Modify code to manage spills

Iteriamo Simplify e Spill finchè il grafo non è vuoto:

Simplify

Se $G$ contiene un nodo $m$ con meno di $K$ vicini ->

• Costruzione di $G' = G \backslash \{ m \}$.

• Push di $m$ in $S$

• Ripeti fino ad un fixed point (nessun nodo t.c. $< K$ vicini)

Spill

• Se $G \neq 0$, tutti i nodi rimanenti hanno $\geq K$ vicini. Sceglie un nodo $s$ e lo assegna come candidato per lo spilling.

• push di $s$ in $S$, computazione di $G' = G \backslash \{ s \}$

• Ritorno a Simplify.

Al termine avremo lo stack pieno con alcuni nodi marcati come candidati per lo spilling. Ripartendo dal grado che rappresenta le interference relation della procedura poi avremo che:

Select

• Per ogni nodo $s \in S$, assegna un colore ad esso e lo estrae dallo stack con una pop:

  Se $s$ non interferisce con i nodi estratti in precedenza, il colore appena assegnatogli va bene (nota che se il nodo non è marcato per lo spilling sarà sicuramente colorabile, mentre se è marcato per lo spilling potrebbe non esserlo), in caso contrario il nodo verrà marcato come actual spill.

  Alla fine di questo passo, se sono presenti actual spill, questi vengono eseguiti nel codice, e poi salta a Start over. Il ciclo viene iterato finchè non riusciamo a risolvere il problema di graph coloring per tutti i nodi del grafo.

Esempio di applicazione dell'algoritmo:

Liveness Interference graph del frammento di codice sulla destra

Colorazione del grafo con K=4

Linear Scan (LinearScanRegisterAllocation)

Per ogni Basic Block controlla quali variabili sono live tramite una scansione lineare del codice $O(V)$, con $V$ numero delle variabili. Se il numero di registri $R$ è molto grande, la complessità diventa $O(V \times R)$. Il risultato è lo stesso di graph coloring nel 95% dei casi, ed è più efficiente.

Per ogni live interval, in ordine di starting point incrementale:

1. Controllo se è possibile liberare registri non più utilizzati, se presenti, e in caso affermativo li libero.

2. Se non sono presenti registri liberi -> Procedura di spill:

   Seleziono la variabile attiva con l'end point maggiore e confronto quest'ultimo con l'endpoint del nuovo intervallo. Spillo in memoria (nello stack) quello che ha l'end point maggiore fra i due.

Pseudocodice: $\text{LinearScanRegisterAllocation}$

$\text{active} \leftarrow\{\}$ $\forall \text{live interval i, in order of increasing start point:}$

• $\text{EXPIREOLDINTERVALS} (i)$

• if $\text{length(active)} =\mathrm{R}$ then $\text{SPILLATINTERVAL}( i)$; else:

• register $[i] \leftarrow$ a register removed from pool of free registers

• add i to active, sorted by increasing end point

Pseudocodice: $\text{ExpireOldIntervals}$

La scelta dell'ordinamento è euristica, di solito la lunghezza di un intervallo corrisponde al range di istruzioni in cui un registro è stato utilizzato per l'ultima volta. Dal momento che pochi valori hanno più di un utilizzo, scegliendo l'intervallo più grande rimanente, riduco i registri con il tempo di utilizzo maggiore.

$\forall$ interval $j \in$ active, in order of increasing end point:

• if endpoint $[j] \geq \operatorname{startpoint}[i]$ then return

• active $=$ active $\backslash\{j\}$

• a add register[j] to pool of free registers

Pseudocodice: $\text{SpillAtInterval}(i)$

• spill $\leftarrow$ last interval in active

• if endpoint $[$ spill $]>$ endpoint $[i]$ then

  • register $[i] \leftarrow$ register $[$ spill]

  • location[spill] $\leftarrow$ new stack location

  • active = active $\backslash\{$ spill $\}$

  • add $i$ to active, sorted by increasing end point

• else location $[i] \leftarrow$ new stack location

Note

• SSA semplifica l'interference analysis dal momento che ogni assegnamento della stessa variabile viene considerato come una variabile diversa.

• Liveness analysis dovrebbe essere eseguita prima della risoluzione delle $\phi$ functions.

• Liveness analysis è veloce grazie alla proprietà di dominanza di SSA (le definizioni dominano gli usi).

• La durata dell'algoritmo di Liveness analysis è proporzionale alla dimensione del grafo da esso costruito, non alla dimensione del CFG.