Intermediate Representation

Introduzione

Solitamente i compilatori sono divisi in due parti:

• Front End: Tra i diversi compiti ritroviamo l'analisi lessicale, sintattica e semantica.

• Back End: Fulcro del lavoro svolto dal compilatore, si occupa della generazione del codice, dell'allocazione dei registri, e di ottimizzazioni target-dependent.

Questa struttura ha diversi vantaggi, tra cui:

• Portabilità: Abbiamo un solo front-end per ogni linguaggio, ed un solo back-end per ogni piattaforma HW ($N+M$ Invece che $N \times M$).

• Modularizzazione e separazione del lavoro.

Il funzionamento di questa architettura è reso possibile dall'Intermediate Representation (IR), che può essere definita letteralmente come una rappresentazione intermedia tra il linguaggio sorgente di alto livello e il linguaggio target (solitamente linguaggio macchina). è composta principalmente da:

• Intermediate Language: definito come "una rappresentazione funzionale del codice sorgente".

• Metadata: informazioni accessorie del codice sorgente utile per implementare eventuali ottimizzazioni.

IR Structure

IR Trees

Sono una tipologia di IR tale per cui il codice viene rappresentato con una struttura ad albero, in cui ciascun nodo rappresenta un costrutto base (ad esempio fetch. store, jump, etc.) ed i figli di un dato nodo rappresentano gli operandi del nodo padre. Sono presenti due tipologie di nodo:

• Expressions: computazione di valori

• Statements: side-effects, control flow

Expressions

Tipo	Significato	Note
CONST(i)	Costante intera (e.g. *uint_t) i
NAME(n)	Costante simbolica (o label) n	Assembly label
TEMP(t)	Variabile temporanea (temporary) t	la variabile temporanea verrà poi mappata in un registro.
BINOP(o, e1, e2)	Operatore binario o applicato ad e1 e e2	Esempio: PLUS, MINUS, MUL, DIV, AND, OR, etc.
MEM(e)	word_size bytes, all'indirizzo e
CALL(f, l)	Chiamata a funzione (f) con lista di argomenti l

Recall:

• Temporary variables let you store and reuse the value of expressions. They can be used to improve the performance or readability of methods.

• Fetch: instruction which gets value from memory into a CPU register, for example:

  mov register, [address]

Statements

Tipo	Significato
MOVE(TEMP t,e)	Esegue e e sposta il risultato in t
MOVE(MEM(e1), e2)	Esegue e1, esegue e2 e mette il risultato di e2 all'indirizzo puntato dal risultato di e1
JMP(l)	Salta all'etichetta l
CJUMP(o,e1,e2,t,f)	Esegue e1, e2, confronta i risultati. if true -> jump(t); else -> jump(f)
LABEL(n)	Definisce la costante simbolica n come l'indirizzo del nodo corrente

---

Ad esempio:

Porzione di IR Tree

Rappresenta il contenuto della cella di memoria presente a fp + k, dove fp è il frame pointer e k è una costante che rappresenta l'offset di una certa variabile rispetto al frame pointer.

Basic Blocks

La struttura più generale di un IR tree è composta da una serie di Basic Blocks connessi tramite jumps e labels. Questi ultimi sono sotto-alberi che non contengono ulteriori salti, cioè consistono in una serie di istruzioni che sono sempre eseguite dall'inizio alla fine, senza variazioni del flow di esecuzione.

• Primo statement: LABEL

• Ultimo statement: JUMP oppure CJUMP

• Nessun altro LABEL, JUMP o CJUMP statement

Costruzione di un Basic Block

Si esegue una scansione lineare della sequenza di istruzioni, e:

• Se si incontra una LABEL -> viene creato un nuovo basic block, e il vecchio, se presente, viene chiuso.

• Se si incontra un JUMP o CJUMP -> si chiude il B.B. attuale e se ne inizia uno nuovo

Inoltre:

• Ogni B.B. aperto senza LABEL ne riceve una nuova

• Ogni B.B. chiuso senza JUMP o CJUMP riceve una nuova "jump to next B.B." LABEL

• Un B.B. finale con solamente un'istruzione LABEL è inserito alla fine.

Esempio di suddivisione in B.B. di un semplice frammento di codice:

void func() {
  int a = 1;
  int b = 2;
  if(b == 2) {
    ++b;
  }
  int c = 3;
  int d = 4;
  while(a < 5) {
    ++a;
  }
  int e = 5;
  int f = 6;
  return;
}

Esempio di suddivisione in Basic Blocks

Control Flow Graphs (CFGs)

Definizione

Un CFG di un programma è un grafo diretto $G(B, E)$ tale per cui:

• È presente un nodo $i \in B$ per ogni istruzione IR ($stat_i$)

• Sono presenti due nodi addizionali, all'inizio e alla fine, chiamati rispettivamente $i_{in}$ ed $i_{out}$.

• È presente un solo arco $(i, i') \in E$ se l'istruzione $stat_{i'}$ è eseguita direttamente dopo l'istruzione $stat_i$.

• Ogni nodo può avere al massimo due nodi figli.

• Per la prima istruzione ($stat_0$), è presente un arco $(i_{in},i_0)$.

• Un arco $(j , i_{out})$ è aggiunto per ogni nodo $j$ associato ad un istruzione ($stat_j$) che precede un punto di terminazione del programma.

Basic Blocks nel CFG

Un B.B. consiste in una sequenza di nodi $\left\langle i_{0}, \ldots, i_{n}\right\rangle$ tale per cui:

• Non sono presenti archi $\left(i_{0}, i_{1}\right) \ldots\left(i_{n-1}, i_{n}\right)$, cioè ci si muove fra le istruzioni in modo sequenziale: $i_0 \rightarrow i_1, i_1 \rightarrow i_2, \dots, i_{n-1} \rightarrow i_n$.

• Nessun arco del CFG è collegato ad un nodo della sequenza di istruzioni associata al B.B. eccetto $i_0$ come destinazione.

• Nessun arco del CFG è collegato ad un nodo della sequenza di istruzioni associata al B.B. eccetto $i_n$ come sorgente.

Cicli nei CFG

Una prima definizione di ciclo (e.g. while loop, ma anche goto) può essere la seguente: un ciclo è definito come un circuito orientato all'interno del CFG. Questa definizione però non si applica a tutti i possibili casi.

Una definizione più accurata di ciclo è invece la seguente: il più grande insieme di nodi tali per cui ognuno di essi è raggiungibile da ogni altro nodo dell'insieme, detto anche maximal strongly connected component (o maximal SCC).

Dominance Relation

Introduciamo la definizione di relazione di dominanza: un nodo $d$ domina un nodo $n$ se $d$ è presente prima di $n$ in ogni percorso dal nodo iniziale $s_0$ ad $n$. Inoltre ogni nodo domina se stesso.

Nota: la dominance relation è una relazione d'ordine parziale.

Esempio di Albero di Dominanza

Immediate dominator

Dati due nodi disgiunti $n$ ed $m$, $m$ è l'immediate dominator di $n$ se:

$$m \operatorname { dom } n \land \forall d ( d \operatorname { dom } n \implies d \text { dom } m)$$

In pratica non deve essere presente nessun altro nodo dominante tra $n$ ed $m$.

Static Single Assignment (SSA)

Diverse ottimizzazioni richiedono la rappresentazione di definizioni ed usi di variabili. Static Single Assignment (SSA) è una rappresentazione che viene utilizzata per identificare le variabili e le loro definizioni. È una IR tale per cui ogni variabile ha solamente una definizione all'interno del programma (anche se dichiarata all'interno di un ciclo). Per questo motivo viene definita statica. Da Wikipedia:

In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR), which requires that each variable be assigned exactly once, and every variable be defined before it is used.

Wikipedia

Vantaggi

1. Semplificazione della data-flow analysis.

2. Riduzione di complessità spaziale e temporale della rappresentazione di usi e definizioni di variabili.

   Più nello specifico, assumendo di avere $N$ usi ed $M$ definizioni per ciascuna variabile, in $N+M$ istruzioni SSA IR ha un costo quasi lineare di $\Theta(N+M)$. È un ottimo miglioramento rispetto all'utilizzo di strutture dato esplicite per usi e definizioni, che hanno costo quadratico.

3. Maggiore facilità nell'allocazione di registri.

4. Usi non correlati della stessa variabile vengono eliminati, ad esempio:

   for i ← 1 to 100 do A[i] ← 0
   for i ← 1 to 20 do s ← s +B[i]

   Non è più necessario usare lo stesso registro per memorizzare la variabile di controllo dei due cicli.

Algoritmo

Data una generica variabile $a$:

1. Ogni nuova definizione di $a$ è modificata per definire una nuova variabile $a_i$ ($a_1, a_2, ...$).

2. Ogni utilizzo della variabile è modificato alla versione più recente.

Ad esempio:

a ← x + y
b ← a - 1
a ← y + b
b ← x * 4
a ← a + b

Diventa:

a1 ← x + y
b1 ← a1 - 1
a2 ← y + b1
b2 ← x * 4
a3 ← a2 + b2

$\phi$ Function

A compile time non è sempre facile trovare la definizione più recente di una variabile. In particolare se un' istruzione ha più di un predecessore, il concetto di "definzione più recente" perde di significato.

La definizione da usare per assegnare un nuovo valore dipende dal control-flow, il quale può essere risolto solo a runtime. Per questo motivo a ciascuna variabile che viene assegnata dopo un punto di confluenza di più flussi di esecuzione viene associato un costrutto chiamato $\phi$ function.

La funzione $\phi$ viene risolta a runtime dopo l'allocazione dei registri, ed ha tanti argomenti quanti sono i nodi predecessori del nodo corrente.

Esempio:

Esempio di funzione

Risoluzione della $\phi$ function

Nella pratica risolvere la funzione significa eseguire una mov. In particolare un istruzione di mov è posizionata prima di ogni arco entrante nel B.B. A compile time data-flow analysis verrà utilizzata per associare un eventuale utilizzo $a_i$ ed una definizione $a_j$ di una variabile.

Dominance relation e SSA

Se $x$ è il j-esimo argomento di una $\phi$ function in un blocco $n$, la definizione di $x$ è sempre eseguita prima del j-esimo predecessore di $n$.

Questo significa che se passiamo un qualche variabile in input ad una $\phi$ function, il nodo a cui tale assegnamento di variabile appartiene domina eventuali altri nodi in cui tale variabile viene definita. Se così non fosse, avremmo bisogno di un altra funzione in questi ultimi.

Dalla $\phi$ function a SSA

Ipotesi: il nodo iniziale contiene una definizione implicita ad uninitialized per ciascuna variabile.

Algoritmo:

1. Inserire le $\phi$ functions.

2. Numerare in modo univoco le variabili.

Nota che l'aggiunta di funzioni non è necessaria alla definizione di ciascuna variabile a ciascun collegamento fra vertici, ma solamente se uno specifico vertice è raggiunto da multiple definizioni diverse della stessa variabile.

Path Convergence Criterion (PCC)

È necessario aggiungere una $\phi$ function $a \leftarrow \phi(...)$ in un vertice $z$ per una certa variabile $a$ se:

• Esistono almeno due B.B. che definiscono la variabile in precedenza:

  $$x : a \leftarrow \dots \\ y : a \leftarrow \dots$$
• Esistono due percorsi non vuoti $P_{xz}$, da $x$ a $z$, e $P_{yz}$, da $y$ a $z$, tali per cui:

  • $P_{xz}$ e $P_{yz}$ non hanno nodi in comune nessun vertice eccetto $z$;

  • $z$ non appare in nessuno dei due percorsi se non alla fine.

Algoritmo

while: $\exists$ blocchi $x$, $y$, $z$ t.c. essi soddisfanno il PCC e $z$ non contiene una $\phi$ function per una certa variabile $a$

do: inserisci $a \leftarrow \phi (\dots)$ nel vertice $z$

Nota che in questo caso parliamo di B.B. come vertici perchè nel CFG i B.B., che sono insiemi di nodi (singole istruzioni) possono essere compressi in blocchi senza alterare la struttura del grafo stesso.

Dominance Frontier Criterion

Dominance Frontier

La dominance frontier (DF) di un nodo $x$ è l'insieme di tutti i vertici $w$ tali per cui $x$ domina almeno un predecessore di $w$, ma non domina $w$.

• Nota che se $x$ dominasse tutti i predecessori di $w$, allora dominerebbe anche $w$.

• Intuitivamente la DF è il confine tra i vertici dominati e non dominati, e di conseguenza è un punto di convergenza per percorsi disgiunti.

Algoritmo

• Per ogni vertice $x$ costruiamo la $DF(x)$ associata

• Per ogni variabile $a$ definita in un vertice $x$, inseriamo una $\phi$ function in ogni vertice $y$ t.c. $y \in DF(x)$.

Nota che questo criterio è equivalente al PCC.