http://www.windizio.altervista.org/appunti/
File distribuito con licenza Creative Commons BY­NC­SA 2.5 IT
Copyright © 2007 ­ Michele Tartara
Parte I
Generazione del codice
La generazione del codice avviene suddividendo in blocchi (basic blocks ) il codice scritto nella rappresentazione intermedia IR e
poi lavorando su questi in modo indipendente.
In questa fase non si utilizzano ancora i registri eettivamente presenti nell'architettura, bensì degli pseudo-registri che
verranno successivamente fatti corrispondere a registri o alla memoria.
1 Basic blocks
Si denisce basic block un gruppo di istruzioni con un singolo punto di ingresso e un singolo punto di uscita. In particolare, per
un basic block, la prima istruzione è una LABEL, l'ultima istruzione è JUMP o CJUMP e non ci sono altre LABEL, JUMP o
CJUMP in un basic block.
L'algoritmo per dividere in basic block una serie di istruzioni è il seguente:
Eseguire una scansione dalla prima all'ultima istruzione.
Ogni volta che si trova una LABEL: inizia un nuovo blocco (e termina il precedente).
Ogni volta che si trova una JUMP o una CJUMP: termina il blocco (e inizia il successivo).
Al termine dell'algoritmo
Per ogni blocco che non inizia con LABEL: aggiungerne una generata casualmente.
Per ogni blocco che non termina con JUMP o CJUMP: aggiungere una JUMP alla label del blocco successivo.
1.1 Utilità dei basic block
Tutte le istruzioni all'intero di un basic block possono essere considerate in modo unitario, in quanto non prevedono salti
di alcun genere. Ciò permette di poter disporre i basic block nell'ordine che si preferisce all'interno del eseguibile
prodotto dal compilatore , in quanto ogni passaggio da uno all'altro è imposto esplicitamente da un'istruzione di JUMP. Si può
così riorganizzare un programma in modo tale che a un'istruzione di salto condizionale (che, su molte architetture, in caso di
condizione falsa non esegue nulla) segua immediatamente il codice da eseguire nel caso di risultato false, risparmiando così
l'esecuzione di un salto, che spreca cicli di processore e invalida il contenuto della (eventuale) pipeline.
2 Selezione delle istruzioni
Al momento di trasformare gli alberi sinstattici astratti (AST) del linguaggio IR in instruzioni macchina (ma ancora utilizzando i
temporaries invece che registri reali) è necessario utilizzare appositi algoritmi che si occupino di assicurare la completa copertura
dell'albero con le istruzioni a disposizione. Ogni istruzione copre un tile, ossia un gruppo di istruzioni AST.
Esistono diversi algoritmi, adatti a diverse situazioni.
2.1 Maximal Munch
Mira a ottenere una copertura ottimale1 . Non cerca, invece, una copertura ottima2 .
È particolarmente adatto alla selezione delle istruzioni per architetture RISC, in quanto in questo caso la dierenza di costo
tra una copertura ottima e una ottimale è nulla o comunque trascurabile. Lo stesso non vale nel caso di architetture CISC.
L'algoritmo è il seguente:
Partire dalla radice dell'albero.
Trovare il tile più grande possibile (cioè con il numero maggiore di nodi) che sia adatto alla copertura. Se più istruzioni hanno
lo stesso costo, la scelta è arbitraria.
Coprire con esso la radice.
Ripetere lo stesso algoritmo per ogni sottoalbero non coperto che rimane.
Al termine della copertura, invertire l'ordine delle istruzioni generate (le prime che devono essere eseguite sono quelle relative
alle foglie dell'albero).
1 Una copertura si denisce ottimale quando non si possono combinare due tile adiacenti in un singolo tile di costo inferiore alla somma dei costi
dei due separati.
2 Copertura a costo minimo. Non esistono coperture con costo inferiore.
1
http://www.windizio.altervista.org/appunti/
File distribuito con licenza Creative Commons BY­NC­SA 2.5 IT
Copyright © 2007 ­ Michele Tartara
2.2 Architetture CISC
Si dice che le architetture CISC hanno diversi idiomi : ognuna, cioè, presenta una serie di istruzioni molto speciche, utili per
qualche operazione insolita. Per sfruttare l'intera potenza della macchina è necessario fare uso di tali istruzioni. Per fare ciò, è
necessario utilizzare algoritmi piuttosto complicati, che risultano non particolarmente importanti in quanto le architetture RISC
sono, oggi, più comuni.
Un esempio di tali algoritmi è dato dalla programmazione dinamica.
2.2.1 Programmazione Dinamica
È un algoritmo di tipo Divide et Impera : suddivide il problema, risolve i sottoproblemi e inne riunisce i risultati.
Non porta alla determinazione di una soluzione ottimale, ma della soluzione ottima.
L'algoritmo è diviso in due fasi:
1. Assegnazione dei costi (bottom-up: dalle foglie alla radice)
assegna un costo a ogni nodo dell'albero, pari alla somma dei costi delle istruzioni usate per coprire il sottoalbero che parte
dal nodo stesso. Il costo viene calcolato per tutti i tile che possono coprire il nodo.
2. Scelta delle istruzioni (top-down: dalla radice alle foglie)
Per ogni nodo, si sceglie il tile che lo copre con costo totale (costo del tile stesso+costo della copertura delle foglie) minimo.
2.2.2 Caratteristiche delle architetture cisc (e loro gestione)
1. Pochi registri: si generano temporaries e si ada all'allocatore il compito di sfruttare al meglio i registri
2. Classi di registri: alcune operazioni richiedono che alcuni operandi e risultati siano in specici registri (ad es, sui Pentium
eax contiene l'operando sinistro e il risultato delle moltiplicazioni). Per implementare un'istruzione del tipo t1 ← t2 × t3
è necessario utilizzare opportune move per assegnare t2 o t3 a eax eventualmente eliminandole in seguito se è possibile
assegnare il valore di uno dei tali temporaries direttamente al registro.
3. Istruzioni a due indirizzi: le istruzioni possono essere solo nella forma r1 ← r1 ⊕ r2 . Per eseguire una istruzione a tre
valori del tipo t1 ← t2 × t3 è necessario inserire una move.
4. Le operazioni aritmetiche possono indirizzare la memoria: per eseguire operazioni aritmetiche (ADD, MUL, ecc)
su aree di memoria non è necessario caricare prima tali aree in registri. È possibile utilizzare direttamente istruzioni del
tipo:
add[ebp - 8], ecx
che avranno lo stesso tempo di esecuzione della sequenza:
move eax,[ebp-8]; add eax,ecx; mov[ebp-8],eax;
ma al contrario di questa non distruggeranno i valori contenuti nei registri (eax, in questo caso). La scelta di cosa fare
viene quindi demandata al register allocator.
5. Diverse modalità di indirizzamento: usando le istruzioni complesse CISC (come appena visto) è possibile non perdere
il contenuto dei registri ed esse hanno una codica più breve rispetto a un gruppo di istruzioni semplici.
6. Istruzioni di lunghezza variabile: supporto per opcode di lunghezza variabile e modalità di indirizzamento di lunghezza
variabile
7. Istruzioni con eetti collaterali: sono istruzioni che modicano più di un registro (ad esempio, istruzioni con un
autoincremento di un contatore). Sono dicili da modellizzare tramite alberi. Possiamo:
(a) ignorare queste istruzioni e non utilizzarle (sono sempre meno diuse)
(b) provare a modellizzare con trattamenti ad-hoc all'interno dell'albero
(c) usare altri modelli e algoritmi, ad esempio basati du DAG (gra orientati aciclici).
2