http://www.windizio.altervista.org/appunti/
File distribuito con licenza Creative Commons BY­NC­SA 2.5 IT
Copyright © 2007 ­ Michele Tartara
Parte I
Linguaggio IR
1 Espressioni (exp - expressions) del linguaggio
CONST un valore costante
NAME indica un'etichetta di destinazione per i salti condizionati (come la LABEL assembly)
TEMP un temporary (simile ad un registro delle macchine reali). Ne possono esistere inniti.
BINOP operazione binaria, applicata su due espressioni (sottoalberi)
MEM il contenuto di una cella di memoria. Se usata come sottoalbero sinistro di una MOVE indica una operazione store, in
tutti gli altri casi una fetch
CALL una chiamata di funzione applicata a una lista di argomenti
ESEQ riceve due parametri, s (un'istruzione) e e (un'espressione). s è valutato per la produzione di side-eect, poi e è valutato
per restituire un risultato
2 Istruzioni (stm - statements) del linguaggio
MOVE(TEMP t,e) valuta l'espressione e e pone il risultato in t
MOVE(MEM(e1 ),e2 ) pone il risultato dell'espressione e1 nella cella di memoria all'indirizzo indicato da e1
EXP(e) valuta l'espressione e e scarta il risultato
JUMP(l) salta all'etichetta indicata da l (e denita, altrove, da LABEL)
CJUMP(o,e1 ,e2 ,t,f ) valuta e1 ed e2 , ne compara i risultati tramite l'operatore o (EQ, NE, LT, GT, LE, GE) e salta all'etichetta
indicata da t se il risultato è vero, da f se il risultato è falso
SEQ(s1 ,s2 ) l'istruzione s1 è seguita dall'istruzione s2
LABEL(n) denisce l'etichetta n assegnandogli l'indirizzo di codice macchina attuale. Si può usare NAME per riferirsi ad
un'etichetta denita da LABEL.
3 Traduzione di espressioni in alberi
3.1 Variabile
Una variabile v che sappiamo essere posta a distanza k dal frame pointer f p può essere rappresentata in un albero come:
MEM(BINOP(PLUS, TEMP f p, CONST k ))
oppure, in forma abbreviata:
MEM(+(TEMP f p, CONST k ))
3.2 Array
In un linguaggio come il C, il nome a di un array rappresenta l'indirizzo e del suo primo elemento. Perciò, considerando una
dimensione delle celle di memoria pari a W , l'accesso all'elemento i-esimo a[i] diventa l'indirizzo del primo elemento sommato a
i volte W :
MEM(+(MEM(e), BINOP(MUL, i, CONST W )))
Nota: Nei compilatori moderni è importante controllare il rispetto dei limiti di un array!
1
http://www.windizio.altervista.org/appunti/
File distribuito con licenza Creative Commons BY­NC­SA 2.5 IT
Copyright © 2007 ­ Michele Tartara
3.2.1 Creazione
Per generare le istruzioni di creazione (dinamica) di un nuovo array, il complilatore deve eseguire i seguenti passi:
1. Determinare quanto spazio è necessario per l'array, tramite questa formula: ((lunghezza dell'array)+1)×(dimensione di un element
Il +1 è necessario per poter memorizzare anche la dimensione dell'array stesso, ai ni del controllo dei limiti.
2. Chiamare una funzione esterna per ottenere lo spazio sullo heap. La chiamata restituirà un puntatore all'inizio dell'array.
3. Generare il codice per salvare la lunghezza dell'array all'oset 0
4. Generare il codice per inizializzare tutte le celle dell'array (opzionale, dipende dal linguaggio che il compilatore tratterà).
3.3 If
Un'istruzione condizionale viene tradotta con una CJUMP.
Tuttavia, se sono presenti più condizioni (ad esempio connesse da &&) è necessario fare attenzione, perchè CJUMP permette
un unica condizione: bisogna tradurre l'istruzione in due CJUMP successive. La prima CJUMP riporta la prima condizione e,
in caso questa sia valutata a true, manda alla seconda CJUMP (che avrà una sua etichetta, creata dal compilatore) la quale
valuterà la seconda condizione e, sul risultato true provocherà il salto all'etichetta del codice da eseguire in caso di condizione
vera dell'istruzione if.
Entrambe le CJUMP, in caso di risultato false, mandano all'etichetta che indica il codice da eseguire in caso di condizione
falsa dell'if.
Ad esempio (supponendo, per semplicità, che a e b siano temporaries e non variabili, e omettendo per essi l'uso di TEMP),
if (a<3 && b>5) then goto t, else goto f
si traduce come
SEQ(CJUMP(LT,a,3,second,f ), SEQ(LABEL(second), CJUMP(GT,b,5,t,f )))
4 Cicli
Possono essere tradotti tramite CJUMP e LABEL tramite opportune equivalenze a codici contenenti solo if e goto.
La presenza di un'istruzione break è modellizzata come un salto incondizionato a done.
4.1 while
while(condizione) {
//body
}
è equivalente a
test :
if not(condition) goto done
//body
goto test
done :
4.2 for
for (i=lo; i<=hi; i++) {
//body
}
è equivalente a
i=lo;
limit=hi;
while(i<=limit) {
//body
i++;
}
2
http://www.windizio.altervista.org/appunti/
File distribuito con licenza Creative Commons BY­NC­SA 2.5 IT
Copyright © 2007 ­ Michele Tartara
L'approccio più frequente e semplice prevede la riscrittura di un for in un while e la successiva traduzione di quest'ultimo in IR,
facendo però attenzione a far sì che i non superi il valore massimo per gli interi nell'architettura considerata. In tal caso il ciclo
deve essere modicato in modo tale che il test venga eseguito in modo tale da impedire che i vada in overow.
5 Funzione
5.1 Chiamata
Semplice uso dell'istruzione CALL.
Nei linguaggi a oggetti, durante la traduzione bisogna anche inserire esplicitamente this (il riferimento all'oggetto stesso) tra
le variabili passate alla chiamata di un metodo.
5.2 Denizione
Una funzione viene tradotta in tre parti di codice assembly:
1. Prologo
(a) Pseudo-istruzioni (come richiesto dal particolare assembly) per annunciare l'inizio di una funzione
(b) Denizione di una label per il nome della funzione
(c) Istruzione per la modica dello stack pointer (per allocare un nuovo frame)
(d) Istruzioni per salvere nel frame gli argomenti che sfuggono (escape ) e per inserire gli altri dentro opportuni temporaries
(e) Istruzioni per salvare i registri callee-save
2. Corpo
Tutte le istruzioni della funzione, come denite dal programmatore
3. Epilogo
(a) Istruzione per inserire il valore di ritorno della funzione nel registro apposito
(b) Istruzioni per ripristinare i registri callee-save
(c) Istruzioni per ripristinare lo stack pointer (per deallocare il frame)
(d) Istruzione di ritorno (JUMP all'indirizzo di ritorno)
(e) Pseudo-istruzioni (come richiesto dal particolare assembly) per annunciare la ne di una funzione
6 Static link
Nei linguaggi a blocchi (che presentano uno static link per determinare la visibilità delle variabili) è necessario che il compilatore
sappia tradurre l'accesso a variabili non locali tramite un'opportuna catena di operazioni di fetch dalla memoria dell'indirizzo
del precedente stack frame lungo gli static link.
Ad esempio, per il programma
int a=0;
function f() {
int b = a;
}
l'esecuzione dell'istruzione di assegnamento è tradotta dal seguente albero:
MOVE(MEM(+(TEMP(fp), CONST(b))), MEM(+(MEM(+(TEMP(fp), CONST(k))), CONST(a))))
3