Code Generation

Da IR tree a code generation

Code Generation: fase della pipeline del compilatore in cui il codice assembly per la macchina target viene generato a partire dall'Intermediate representation.

Il Code Generator deve quindi identificare un insieme di istruzioni assembly tali per cui:

1. Tutti i nodi dell'IR tree sono inclusi nell'output

2. Tale insieme ha costo minimo

Con il secondo criterio si fa riferimento a costi in termini di tempo di esecuzione, e di energia.

Top-down Tree Covering

Idea: Greedy algorithm for instruction selection, ricerca della soluzione ottimale ad ogni iterazione dell'algoritmo. Nello specifico il criterio di selezione greedy fa riferimento ad una valutazione del costo delle istruzioni rispetto al numero di nodi coperti.

Algoritmo di selezione dei vertici

1. Al primo step si considera la radice $O$ dell'albero IR.

2. munch(O): scelta di un insieme di istruzioni il più grande possibile che copra $O$ ed eventuali sottoalberi (maximal munch). Le istruzioni generate a questo passo dell'algoritmo vengono aggiunte in append ad una lista che costituirà l'output dell'operazione di code generation.

3. Chiamate $O_1, O_2, \dots, O_k$ le radici dei sottoalberi della radice della porzione di albero appena consumata, a ciascuno di essi viene applicato il passo 2 in maniera ricorsiva e nello stesso ordine in cui sono stati generati.

4. L'algoritmo termina quando la funzione di munching è stata applicata ad ogni nodo dell'albero.

Note:

• L'algoritmo visita l'albero in modo simile ad un algoritmo depth-first, e per ogni nodo aggiunge le istruzioni generate ad una lista. Per produrre il codice finale in output, la lista viene invertita.

• L'algoritmo ha complessità temporale lineare. È veloce, ma non è ottimale.

Dynamic Programming Approach

Un alternativa migliore ad un algoritmo greedy consiste in un'applicazione del paradigma di programmazione dinamica. È possibile partire dalle foglie (bottom-up) e cercare la soluzione ottimale per sottoalberi di dimensione incrementale. Una volta arrivati alla radice è necessario effettuare una visita in preordine dell'albero per effettuare la code generation.

Peephole Optimization

Idea: partendo dalla lista di istruzioni assembly generate ma non ottimizzate, una finestra di dimensione $k$ viene fatta scorrere iterativamente sulla lista di istruzioni per effettuare pattern matching ed eventualemente sostituire pattern noti con snippet di codice diversi ma più veloci ed equivalenti dal punto di vista semantico.