07/01/2010

1

Traduzione da C a 68000

Vittorio Zaccaria

Dicembre 2009

Catena di compilazione

Analisi sintattica e trattamento degli errori linguaggio di alto livelloutilizzo di linguaggi

i t di (IR)g

Generazione del codice macchina

Ottimizzazione del codice macchina

assembly

facoltativa

codice oggetto (sinonimi

intermedi (IR)

Assemblaggio e collegamentocodice oggetto (sinonimi binario, eseguibile, linguaggio macchina)

07/01/2010

2

Analisi sintattica e generazione del codice

• Analisi sintatticaverifica se il programma è int a;

ling. sorgente di alto livello

– verifica se il programma è sintatticamente corretto

– segnala errori e warnings

• Generazione di codice– il programma viene 

tradotto in linguaggio macchina

int a;

char c;

a = c + 1;

A: DS.L 1 // int a

C: DS.B 1 // char cmacchina

– il codice macchina prodottoè in forma simbolica (.S)

MOVE.B C, D0

ADDI.B #1, D0

MOVE.L D0, A

ling. macchina simbolico

Assemblaggio e collegamento

• Assemblaggio: risolve simboli assemblatore

A: DS.L 1 // int a

C: DS.B 1 // char c

– indirizzo di memoria– etichetta d’istruzione– Spiazzamento– L’istruzione simbolica viene 

tradotta in codifica numerica

• Collegamento tab. dei simboli

codici operativiMOVE.B 1010...ADDI.B 1100...

MOVE.B C, D0

ADDI.B #1, D0

MOVE.L D0, A

ling. macchinasimbolico

– unisce più moduli eseguibili

– per esempio programma e librerie standard (IO ecc)

A 1010...C 1101...

10101101................

11000001................

ling. macchina numerico

07/01/2010

3

Note aggiuntive su assemblaggio e linker

Assemblaggio

• Genera per ogni modulo:l b ll d i i b li d l d l d il di– la tabella dei simboli del modulo, generando il codice oggetto

– I riferimenti simbolici esterni • Funzioni (extern)

• Variabili globali

• Modulo assemblato da indirizzo 0;• Modulo assemblato da indirizzo 0; – Direttiva ORG: serve a posizionare l’area istruzioni e  viene gestito dal loader e dal Sistema Operativo (modulo di gestione della memoria)

07/01/2010

4

Assemblaggio

• Etichette di salto: causano il problema forward references (risolto in 2 passi)references (risolto in 2 passi)

...CMP.L #0, D0BGE LABEL_POSNEG.L D0NEG.L D0

LABEL_POS ...

Assemblaggio

• Costruzione tabella simboli modulo: indirizzi numerici di tutti i simbolinumerici di tutti i simboli– Contiene anche cosanti simboliche (EQU)

• Per etichette che definiscono variabili – Variabili non inizializzate vengono allocate in .bss– Variabili inizializzate messe in .data

• Etichette associate ai salti– Viene calcolato l’offset (se possibile)– Indirizzo assoluto (se possibile)

07/01/2010

5

Linker

• Collega piu’ di un modulo oggetto/libreria

• Genera un unico programma binario eseguibile (in formato rilocabile)

• Unico spazio di indirizzamento

Tecniche di traduzione da C ad assembly 68000

Note generali

07/01/2010

6

Schema di compilazione da C adassembly 68K

• Ispirato a GCC• Fa uso di:• Fa uso di: 

– banco di registri– classi d’istruzioni– modi d’indirizzamento e organizzazione del sottoprogramma

• Consiste inT d i t t t C– Traduzione statement C

– Traduzione invocazioni funzioni C– Traduzione delle strutture di controllo

Application Binary Interface

• Specifica di:– Dimensione dei tipi di dati

– Allineamento dati e istruzioni

– Convenzioni di chiamata delle funzioni (passaggio parametri)

– Chiamate al sistema operativop

– Struttura dell’eseguibile

07/01/2010

7

Ingombro in memoria delle variabili

• Unita’ minima indirizzabile: singolo byte

• In C (Linux):– sizeof (char)      = 1 byte

– sizeof (short int) = 2 byte

– sizeof (int)        = 4 byte

– sizeof (long int)     = 8 byte (non utilizzabile su M68k)

– sizeof (array)     = somma ingombri elementi

– sizeof (struct)    = somma ingombri campi

• Non considereremo floating point

‐ 13 ‐

Posizione in memoria delle variabili C

• Globali: allocate a indirizzo prefissato

• Locali: allocate sulla pila

• Dinamiche: allocate sullo heap (gestito a sua volta all’interno dell’area dati del processo) 

MEM

D/A Op Op

MEM

….D/A

Utilizzo tipico dei registri da parte del compilatorenel calcolo di un’espressione o statement.

07/01/2010

8

Convenzioni per uso dei registri

• D0‐D7 per variabili di tipo carattere o intero

• A0‐A7 per variabili di tipo indirizzo• registri A0‐A5: indici a vettori

• registro A6 (o FP) come puntatore all’area di attivazione

• registro A7 (o SP) come puntatore alla pila (uSP o sSP)

• Il registro SR contiene i bit di esitog– Aggiornato da (MOVE – CMP – ADD SUB NEG ecc – AND OR NOT ecc)

– Usato da istruzioni Bcc e DBcc

‐ 15 ‐

Dimensionamento dati

• 8 bit  per carattere• 32 bit per intero• 32 bit per intero• Le istruzioni assembly devono avere un suffisso:

– B per dato da 8 bit byte– W per dato da 16 bit parola– L per dato da 32 bit parola lunga o doppia

• Es:– MOVE.B D1, D2 // D2 ← [D1] 8 bit meno signif.– MOVE.W D1, D2 // D2 ← [D1] 16 bit meno signif.– MOVE.L D1, D2 // D2 ← [D1] registro completo

‐ 16 ‐

07/01/2010

9

Dimensionamento indirizzi

• Registri d’indirizzo (A0‐A5):16 bi i fi i d 64 K b– a 16 bit per memoria fisica max da 64 K byte

– a 32 bit per memoria fisica max da 4 G byte

• Suffissi:– W per indirizzo da 16 bit indirizzo corto

– L per indirizzo da 32 bit indirizzo lungo

• Es.:– MOVEA.W A1, A2  // A2 ← [A1] 16 bit meno signif.

– MOVEA.L A1, A2  // A2 ← [A1] registro completo

‐ 17 ‐

Variabili globali − conversione

char c;ORG 1000 // decimale

C: DS.B 1int a;int b = 5;int vet [10];

int ∗ punt;short int d;

A: DS.L 1 // oppure DS.B 4B: DC.L 5 // inizializzazioneVET: DS.L 10 // oppure DS.B 40PUNT: DS.L 1 // oppure DS.B 4D: DS.W 1 // oppure DS.B 2

tab dei simboliDS riserva solo spazio senza inizializzarloDC riserva spazio e lo inizializzail puntatore (di ogni tipo) è equiparato all’intero

‐ 18 ‐

tab. dei simboliC 1000A 1001B 1005

VET 1009PUNT 1039D 1043

07/01/2010

10

Variabile globale − struct

struct s {ORG 1000 // decimale

S: DS.B 5 // = somma ingombri di c e achar c;int a;

}

S.C: EQU 0 // spiazzamento di c in sS.A: EQU 1 // spiazzamento di a in s

tab. dei

•Allocazione spazio per l’intera struct

•Definizione dei simboli di spiazzamento l’ li l ti d ll t t

‐ 19 ‐

sim.S 1000

S.C 0

S.A 1

per l’accesso agli elementi della struct

•Utilizzo del ‘.’ per differenziare gli spiazzamenti da altre struct

Tecniche di traduzione da C ad assembly 68000

Traduzione di:Semplici statementS di llStrutture di controllo

Invocazione delle funzioniEspressioni

07/01/2010

11

Traduzione semplici statement

Regola base per la traduzione dei semplici statement C

• Assumiamo che lo statement sia una semplice manipolazione della variabile

• Assumere che la variabile sia sempre collocata in memoria

• Come tradurre gli statement C– Caricando le variabili nei registri all’inizio dello statement (o non 

appena serve)– Memorizzandole alla fine dello statementMemorizzandole alla fine dello statement

• Ogni variabile cambiata deve essere memorizzata il prima possibile.

‐ 22 ‐

07/01/2010

12

Esempio, variabile globale intera

int a;...a = a + 1;...

A: DS.L 1 // spazio per int

MOVE.L A, D0 // D0 ← [A]ADDI.L #1, D0 // D0 ← [D0] + 1MOVE.L D0, A // A ← [D0]

oppure (ottimizza senza passare per il registro D0)

‐ 23 ‐

ADDI.L #1, A // A ← [A] + 1

dato che ADDI può lavorare direttamente in memoria

Variabile globale per puntatore

int a;int ∗ punt;...

A: DS.L 1 // spazio per intPUNT: DS.W 1 // spazio per punt

// punt = &apunt = &a;∗punt = ∗punt + 1;...

pMOVEA.W #A, A0 // A0 ← AMOVE.W A0, PUNT // PUNT ← [A0]// ∗punt = ∗punt + 1MOVEA.W PUNT, A0 // A0 ← [PUNT]MOVE.L (A0), D0 // D0 ← [[A0]]ADDI.L #1, D0 // D0 ← [D0] + 1MOVE.L D0, (A0) // [A0] ← [D0]

‐ 24 ‐

, ( ) // [ ] [ ]

non confondere tra assegnamento a puntatore (che ne modifica la cella di memoria) e a oggetto puntato (che non modifica la cella di memoria del puntatore)

07/01/2010

13

Variabili locali

int f (...)

{... // LINK e altre EQU

A: EQU 8 // vedi area di attivazioneint a;...a = a + 1;...

}

MOVE.L A(FP), D0 // D0 ← [A + [FP]]ADDI.L #1, D0 // D0 ← [D0] + 1MOVE.L D0, A(FP) // A + [FP] ← [D0]

oppure (ottimizza senza passare per il registro D0)

ADDI.L #1, A(FP) // A + [FP] ← [A + [FP]] +

‐ 25 ‐

1

dato che ADDI può lavorare direttamente in memoria

Tecniche di ottimizzazione

int a;int b;

A: DS.L 1B: DS.L 1

1

A: DS.L 1B: DS.L 1

1

A: DS.L 1B: DS.L 1

1int c;...a = a + b;c = a + 2;...

C: DS.L 1// a = a + bMOVE.L A, D0MOVE.L B, D1ADD.L D0, D1MOVE.L D1, A// c = a + 2MOVE.L A, D0

C: DS.L 1// a = a + bMOVE.L A, D0ADD.L B, D0MOVE.L D0, A// c = a + 2MOVE.L A, D0ADDI.L #2, D0

C: DS.L 1// a = a + bMOVE.L A, D0ADD.L B, D0MOVE.L D0, A// c = a + 2ADDI.L #2, D0MOVE.L D0, C

codice C di alto livello sorgente

ADDI.L #2, D0MOVE.L D0, C

codice 68000 “plain” ossia non ottimizzato

MOVE.L D0, C

unifica tramite semi-ortogonalità di ADD

elimina tenendo varin registro dato D0

‐ 26 ‐

eliminataunificate

07/01/2010

14

Traduzione strutture di controllo

If‐then

Test !CONDvero

if(COND){...Body...

}

vero

Body

Resto del programma

07/01/2010

15

If‐then

// var. globaleint a;

A: DS.L 1 // riserva mem per a

...// condizione

if (a == 5) {// ramo then...

} /∗ end if ∗/... // seguito

...

MOVE.L A, D0 // D0 ← [A]

CMPI.L #5, D0 // esiti ← [D0] −5

BNE FINE // se != 0 va’ a FINE

... // ramo then

‐ 29 ‐

... // ramo thenFINE: ... // seguito

va modificato com’è ovvio per “>”, “<“, “<=”, “==” e “!=”idem se a è variabile locale od oggetto puntato

If‐then‐else

if(COND)

Test !CONDvero

{...b_then...

}else{

b_then

BRA

b else...b_else...}

Resto del programma

b_else

07/01/2010

16

If‐then‐else

// var. globaleint a;

A: DS.L 1 // riserva mem per a...

...// condizione

if (a >= 5) {// ramo then...

} else {// ramo else

MOVE.L A, D0 // D0 ← [A]CMPI.L #5, D0 // esiti ← [D0] − 5BLT ELSE // se < 0 va’ a ELSE... // ramo thenBRA FINE // va’ a FINE

ELSE: ... // ramo elseFINE: ... // seguito

‐ 31 ‐

...

} /∗ end if ∗/... // seguito

va modificato com’è ovvio per “>”, “<“, “<=”, “==” e “!=”idem se a è variabile locale od oggetto puntato

While

Test !CONDwhile(COND){...Body...

}

Test !CONDvero

Body

}

Resto del programma

BRA

07/01/2010

17

While

// var. globaleint a;

A: DS.L 1 // riserva mem per a

...// condizione

while (a >= 5) {// corpo...

} /∗ end while ∗/

...

CICLO: MOVE.L A, D0 // D0 ← [A]CMPI.L #5, D0 // esiti ← [D0] − 5BLT FINE // se < 0 va’ a

FINE... // corpo del cicloBRA CICLO // torna a CICLO

‐ 33 ‐

// seguito...

FINE: ... // seguito del ciclo

va modificato com’è ovvio per “>”, “<“, “<=”, “==” e “!=”idem se a è variabile locale od oggetto puntato

For

INIZ

for(INIZ; COND; INCR){...Body...

}

Test !CONDvero

Body

Resto del programma

INCRBRA

07/01/2010

18

For// variabile globaleint a;

A: DS.L 1 // riserva mem per a

......// testata del ciclofor (a = 1; a <= 5; a++) {

// corpo del ciclo...

} /∗ end for ∗/// seguito del ciclo

...

MOVE.L #1, D0 // D0 ← 1MOVE.L D0, A // A ← [D0]

CICLO: MOVE.L A, D0 // D0 ← [A]CMPI.L #5, D0 // esiti ← [D0]

− 5BGT FINE // se > 0 va’ a

FINE... // corpo del

a = 1

a <= 5

++

‐ 35 ‐

...

la variabile di conteggio a viene aggiornata in fondo al corpo del ciclo (“a++” è post-incremento)

cicloMOVE.L A, D0 // D0 ← [A]ADDI.L #1, D0 // D0 ← [D0]

+ 1MOVE.L D0, A // A ← [D0]BRA CICLO // torna a CICLO

FINE: ... // seguito del ciclova modificato per “>” “<“ “<=” e “a ” “++a” “ a”

a++

Invocazione di funzioni

Passaggio parametri

Creazione record di attivazioneCreazione record di attivazione

(anche chiamato stack frame o area di attivazione)

07/01/2010

19

Passaggio parametri

F(a,b,c)Record di attivazione o

U i i i i ’ i li il l i di

{Z = g(x, y, z)

}

Record di attivazione o registri

Record di attivazione o registri

• Usare registri in input puo’ implicare il salvataggio di tali registri se si invocano altre funzioni innestate.

• Usare registri in output puo’ implicare un salvataggio da parte di chi chiama (caller)

Passaggio parametri

• In questa lezione tratteremo il passaggio t i i d di tti i ( i iparametri via record di attivazione (sia in 

ingresso che in uscita)

• Riserveremo un opportuno spazio nel record di attivazione per tali parametri

07/01/2010

20

Record di attivazione

Variabili locali

Altre variabili

Variabili blocchi innestati C (FP)

Record di attivazione(stack frame)composto da:

Par. in ingresso

Ind. Rit.

Prev. stack frame pointer 

( t)FP

innestati C (FP)

Salvataggio registri usati

f(a,b,c)Record di attivazione f

SP

g(r,s,t)Record di attivazione g

chiamaPrev. FP SP

FP

SP

Records funzioni precedenti

Struttura di una chiamata a funzione (M68K)

Posiziona mento parametri a b c nel

Main(){ parametri a,b,c nel 

record di attivazione di f

{...r=f(a,b,c)

}

f(a,b,c){

int x,y;

Salto ad f

Creazione spazio per x, y sul record di attivazione

Main

f...return d;

}

Salvataggio altre info temporane sul record di 

attivazione

…

f

d viene salvato al posto di c (nel record di attivazione di f)  al 

ritorno dalla funzione 

07/01/2010

21

Chiamata/ritorno da sottoprog.

• Chiamata– BSR (branch to subroutine) salto “vicino”

– JSR (jump to subroutine) salto “lontano”

Rit

SP      ← [SP] − 4[SP] ← [PC]PC ← i.e. dest. 

• Ritorno– RFS (return from subroutine)

‐ 41 ‐

PC    ← [[SP]]SP ← [SP] + 4

Record di attivazione

i - … idem eventuali altri registri …

i 12 t l i t l t

int f (int p, int q)

{

int a;

int b;

area della funzione f

i - 12 eventuale registro salvato

i - 8 variabile locale b

i - 4 variabile locale a

i puntatore al record del chiamante

i + 4 indirizzo di rientro al chiamante

int b;

...

return ...

}

‐ 42 ‐

i + 4 indirizzo di rientro al chiamante

i + 8 parametro p

i + 12 parametro q

area del chiamante

A7 (o SP)

A6 (o FP) = i

07/01/2010

22

Gestione record di attivazione// chiamante... // impila parametri// funzionei f (i i ) {

F: LINK FP, #−8P: EQU 8 // spi. par. pQ: EQU 12 // spi. par. qA EQU 4 // iint f (int p, int q) {

int a; // dich.int b; // dich.... // elaborareturn ... // uscita

}

A: EQU -4 // spi. var. aB: EQU -8 // spi. var. b

... // elabora

... // sovrascrive QUNLK FPRFS

EQU dichiara il simbolo senza riservare

‐ 43 ‐

EQU dichiara il simbolo senza riservare spazio di memoria; lo spazio viene riservato dal chiamante (impilando i parametri) e da LINK (nella funzione)

tab. dei sim.

p 8

Q 12

A -4

B -8

Riassumendo• I record di attivazione formano una lista concatenata• Creazione del record:

LINK A6, #‐N(N è la dimensione delle variabili locali)

• Deallocazione del record:UNLK A6

• I parametri – sono allocati in ordine inverso – hanno spiazzamento positivo rispetto a FP 

• le variabili locali hanno spiazzamento negativo rispetto a FP

07/01/2010

23

Schema di sottoprogramma

SUB1:LINK A6, #-N // riservo spazio per le var locali di

SUB1MOVEM L D1- -(SP) // salvo i registri che usoMOVEM.L D1 ..., (SP) // salvo i registri che uso...// preparazione a chiamata di un’altra funzione con due parametriMOVE.L ..., -(SP) // push secondo parametroMOVE.L ..., -(SP) // push primo parametroBRS SUB2 // chiamataADDA.L #4, SP // pop (n-1)parametri * dim parametri MOVE.L (SP)+, ... // spilo e uso il valore in uscita di SUB2

// so rascritto al primo parametro

‐ 45 ‐

// sovrascritto al primo parametro...MOVE.L ..., spiaz.(A6) // salvo in stack il valore restituito da

SUB1 in posizione (+4 per ind.rit. + 4(n), n numero di parametri, 4 dim parametri) rispetto a FP

MOVEM.L (SP)+,D1-... // ripristino i registriUNLK A6 // elimino var. localiRTS // ritorno al chiamante

Conversione espressioni

07/01/2010

24

Albero sintattico

• Esempio di statement C:Z=(A+B)*(C-D)+5

**

++

5ALBEROSINTATTICO

==

Z

A B C D

++ ‐

Albero intermedioannotato con 

ZZ

t

Risultato temporaneoContenuto in un registro

Valore di una variabile In memoria

legenda

loads e stores

++ ‐**

++

55

store

AA

load load load load

BB CC DDIpotesi variabiliglobali

07/01/2010

25

Tile

• Ogni istruzione e’ rappresentabile come un til il l h f d lbtile, il quale ha una forma ad albero.

• E’ un pattern 

MOVE Da, indirizzo var

indirizzo_var

tile

, _

store

Da

(globale)

Altro esempio di tile

MOVE indirizzo_var, Daload

Da

tile

indirizzo_var

07/01/2010

26

Altro esempio di tile

• Operazioni binarie aritmetiche (ADD, MUL, SUB etc.)

SUB Da, Db(Db-Da) ‐

Db

Db Da

SUB #cost, Da‐Da

Dacost

ATTENZIONE ALL’ORDINE OPERANDI

Instruction selection

• Copertura totale d ll’ lb i

ZZ

storedell’albero con i 

tile delle istruzioni a disposizione

++ ‐**

++ 55

e

AA

load load load load

BB CC DD

07/01/2010

27

Allocazione deiregistri

• Allocare i registri i ti ll

ZZ

storassociati alle load

• I registri associati ai trasferimenti  ++ ‐

**

++ 55

e

D1 D2

D2

D2

temporanei sono bloccati

AA

load load load load

BB CC DD

D0 D1 D2 D3

Generazione del codice

• Visitare l’albero in post‐ordine

ZZ

storp

– Scegliere sempre strada a sinistra

– Ultima volta che si esce dal nodo numerarlo e  generare istruzione ++ ‐

**

++ 55

e

generare istruzione

AA

load load load load

BB CC DD

07/01/2010

28

Codice generato

MOVE.L A, D0MOVE.L B, D1

ZZ

stor,ADD.L D0, D1MOVE.L C, D2MOVE.L D, D3SUB.L D3, D2MULS D1, D2ADD.L #5, D2 ++ ‐

**

++ 55

e

D1 D2

D2

D2

. #5,MOVE.L D2, Z

AA

load load load load

BB CC DD

D0 D1 D2 D3

Chiamate di funzioni• Il tile associato ad una chiamata di funzione (passaggio via record di attivazione)(p gg )

funzione(x,y,z)

MOVE.L Dc, -(A7)MOVE.L Db, -(A7)MOVE.L Da, -(A7)BSR FunzioneADDA #8 A7

Dc

Da Db Dc

ADDA #8, A7MOVE.L (A7)+, Dc