Esercizi C MIPS PDF

Preview

Summary

Esercizi in C MIPS...

Description

esercizio linguaggio m acchina – esame 9 luglio 2015 prima parte – traduzione in assembler Si

deve

tradurre

in

linguaggio

macchina

simbolico

(linguaggio

assemblatore)

MIPS

il

frammento

di

programma C riportato sotto, costituito dalla sezione dichiarativa delle variabili globali che contiene la sola variabile vett , e dalla funzione ricorsiva f_ric. Non si tenti di accorpare od ottimizzare insieme istruzioni C indipendenti. La memoria ha indirizzi da

32 bit ,

è indirizzabile per

byte

e gli interi sono da

32 bit .

Si

facciano le ipotesi seguenti:



il fame pointer non è in uso



le variabili locali sono allocate nei registri se possibile

Si chiede

di svolgere i quattro punti seguenti:

1.

Si descriva

l’area di attivazione della funzione f_ric, secondo il modello MIPS, nella tabella predisposta.

2.

Si traduca

in linguaggio macchina MIPS la sezione dichiarativa della variabile globale vett nella tabella

predisposta, in cui è già stata inserita la direttiva . data che definisce l’indirizzo di impianto delle variabili globali. 3.

Si traduca

in linguaggio macchina MIPS il codice della funzione f_ric, coerentemente con le specifiche e

le risposte ai punti precedenti, usando la tabella predisposta. Se lo si ritiene utile, prima della traduzione si derivino gli alberi associati alle espressioni presenti nel codice. 4.

Si risponda

alla domanda sulla

mappatura della memoria

così come richiesto al punto

/ sezione dichiarativa variabili globali / #define N 10 int vett [N];

/ funzione f_ric / int f_ric (int  p, int i)  int j;

/ variabili locali /

j = i; if (j == -1)  return 0;  else  p = vett [i]; return f_ric (p, i - 1);  / end if /  / f_ric /

/ chiamata ricorsiva /

4.

punto

1

– (numero di righe non significativo)

area di attivazione di f_ric

contenuto simbolico

spiazz. rispetto a stack pointer

ra

4

s0 (assegnato a varloc j)

0

a1 (assegnato a param i)

salvato prima di chiamata

indirizzi alti

 sp max estensione del prologo chiamante

indirizzi bassi

Si noti che la funzione è ricorsiva, pertanto essa funziona sia come chiamante (caller) sia come chiamato (callee). Il chiamante salva il secondo parametro “a1” (assegnato a “i”) in pila per poterlo poi riavere inalterato. Tuttavia, si può notare che in effetti il chiamante non usa il secondo parametro dopo la chiamata; dunque si può evitare di salvare tale parametro in pila. Va anche bene salvare sempre, prudenzialmente, tutti i parametri passati (qui entrambi), a prescindere da che poi il chiamante ne abbia ancora bisogno con i loro valori originali. IL MODELLO DI CHIAMATA A FUNZIONE USUALE PREVEDE CHE IL CHIAMANTE SALVI I PARAMETRI IN PILA SOLO SE DOPO LA CHIAMATA A FUNZIONE ESSO NECESSITA DI RITROVARLI INALTERATI. QUI IL MODELLO NON VIENE RISPETTATO RIGOROSAMENTE SOLO PER MOSTRARE COME SALVARE UN PARAMETRO IN PILA. punto

VETT:

2

– codice MIPS della sezione dichiarativa globale (num. righe non signif.)

.data

0x 1000 0000

// indirizzo di impianto dati

.space

40

// dichiarazione variabile globale

punto

F_RIC:

IF:

THEN:

ELSE:

3

– codice MIPS di

(num. righe non signif.)

addiu $sp, $sp, -8

// costruisci area

.eqv

RA, 4

// spiazzamento di ra salvato

.eqv

S0, 0

// spiazzamento di s0 salvato

sw

$ra, RA($sp)

// salva ind rientro

sw

$s0, S0($sp)

// salva reg s0 (varloc J)

move

$s0, $a1

// aggiorna varloc j

li

$t0, -1 (o addi $t0, $0, -1) // carica cost -1

bne

$s0, $t0, ELSE

// se j != -1 va’ a ELSE

move

$v0, $0 (o add $v0, $0, $0)

// prepara valusc

j

ENDIF

// va’ a ENDIF

la

$t0, VETT

// carica ind VETT

move

$t1, $a1

// copia arg i

sll

$t1, $t1, 2

// allinea indice

addu

$t0, $t0, $t1

// calcola ind elem (

lw

$t1, ($t0)

// carica elem v[i]

sw

$t1, ($a0)

// aggiorna

addiu $sp, $sp, -4

 )

p

// 1) decrementa reg sp (

 )

sw

$a1, ($sp)

// 2) salva param i (push)

addi

$a1, $a1, -1

// calcola i – 1 (

jal

F_RIC

// chiama f_ric

lw

$a1, ($sp)

// 3) ripristina param i (pop)

addiu $sp, $sp, 4 ENDIF:

f_ric

 )

// 4) incrementa reg sp

lw

$s0, S0($sp)

// ripristina reg s0

lw

$ra, RA($sp)

// ripristina ind rientro

addiu $sp, $sp, 8 jr

$ra

// elimina area // rientra

Le istruzioni (1-2) realizzano l’operazione “PUSH” di “a1” (param “i”) sulla cima della pila; le istruzioni (3-4) realizzano l’operazione “POP” di “a1” (param “i”) dalla cima della pila.



Qui si usa una somma “addu” (oppure “addiu”) di tipo “senza segno” (unsigned), poiché si tratta di

un’operazione per calcolare un indirizzo, ossia un numero naturale sempre positivo o nullo. Infatti, giacché il risultato di un’operazione su indirizzi sarà sempre un numero naturale, va usata l’aritmetica senza segno.



Invece per un’operazione su variabili di tipo intero relativo (positive, nulle o negative), come per varabili di

tipo “int” nel calcolo di un’espressione algebrica, va usata l’aritmetica “con segno”.

Note varie:



l’istruzione “li” è sostituibile con l’istruzione “addi” poiché la costante –1 da caricare è a solo 16 bit



la pseudo-istruzione “move” è facilmente espandibile tramite un’istruzione “addi”



formalmente il registro “s0” va salvato in pila a cura del chiamato, poiché è assegnato alla variabile locale “j”, ma giacché la funzione in realtà non lo modifica, ottimizzando molto si potrebbe evitare di salvarlo (così però deviando dal modello rigoroso di area di attivazione)



il parametro “i” allocato nel registro “a1” viene modificato dal chiamante per passarlo al chiamato ricorsivo, e se si prende il ramo ELSE è salvato in pila prima della modifica così causando un’estensione della pila, e poi è ripristinato subito dopo il rientro da “jal” (il ramo THEN non ha effetto); in realtà si potrebbe evitare di salvarlo perché dopo il rientro non viene più usato; si veda il modello di chiamata a funzione illustrato a lezione



invece il parametro “p” allocato nel registro “a0” non viene modificato dalla funzione, pertanto senz’altro non viene salvato (e dunque neppure ripristinato)



AVVERTENZA: si badi bene che lo statement C di assegnamento “*p = vett [i]” USA il parametro puntatore “p”, ma non ne modifica il valore, ossia non cambia l’indirizzo che costituisce il valore di “p” ! ciò che viene modificato, assegnandogli il valore dell’elemento con indice “i” del vettore, è l’oggetto puntato da “p” (si riveda il punto precedente)



i registri temporanei “t0-t7” non vengono salvati (non vengono date indicazioni che la funzione si aspetti di poterli riavere inalterati dopo la chiamata ricorsiva)

Potrebbero esserci altre piccole ottimizzazioni di codice.

punto

4

– mappatura della memoria

Si considerino le ipotesi seguenti relative all’allocazione del programma in codice eseguibile in memoria:



il programma è collocato in memoria secondo il modello standard di MIPS, e l’ordine delle funzioni nel codice è prima main, poi f_ric

 

la dimensione di main è di

1024 byte

il valore del registro sp immediatamente prima che main effettui il passaggio di parametri alla prima invocazione di f_ric è pari a



0x 7FFF 0000

si ricorda che la memoria è indirizzabile a

byte

si chiedono: l’indirizzo della prima istruzione di main:

0x 0040 0000 (standard MIPS)

l’indirizzo della prima istruzione di f_ric:

0x 0040 0000

 1024 (dec)  0x 0040 0000  0x 0000 0400  0x 0040 0400

il valore di sp subito prima della seconda invocazione di f_ric:

0x 7FFF 0000

 (8  4) dec  0x 7FFF

0000

 0x 0000 000C  0x 7FFE FFF4

nota bene: subito prima della seconda invocazione di f_ric la pila ha la max estensione

il valore di sp relativo all’area di attivazione della seconda chiamata di f_ric:

0x 7FFE FFF4

 8 dec  0x 7FFE

FFF4

 0x 0000 0008  0x 7FFE FFEC

nota bene: l’area di attivazione di f_ric (senza estensione per il prologo del chiamante) ha dimensione 8 byte

esercizio linguaggio m acchina – esame 9 luglio 2015 – VARI ANTE I prima parte – traduzione in assembler Si

deve

tradurre

in

linguaggio

macchina

simbolico

(linguaggio

assemblatore)

MIPS

il

frammento

di

programma C riportato sotto, costituito dalla sezione dichiarativa delle variabili globali che contiene la sola variabile vett , e dalla funzione ricorsiva f_ric. Non si tenti di accorpare od ottimizzare insieme istruzioni C indipendenti. La memoria ha indirizzi da

32 bit ,

è indirizzabile per

byte

e gli interi sono da

32 bit .

Si

facciano le ipotesi seguenti:



il fame pointer è in uso



le variabili locali sono allocate nei registri se possibile

Si chiede

di svolgere i quattro punti seguenti:

1.

Si descriva

l’area di attivazione della funzione f_ric, secondo il modello MIPS, nella tabella predisposta.

2.

Si traduca

in linguaggio macchina MIPS la sezione dichiarativa della variabile globale vett nella tabella

predisposta, in cui è già stata inserita la direttiva . data che definisce l’indirizzo di impianto delle variabili globali. 3.

Si traduca

in linguaggio macchina MIPS il codice della funzione f_ric, coerentemente con le specifiche e

le risposte ai punti precedenti, usando la tabella predisposta. Se lo si ritiene utile, prima della traduzione si derivino gli alberi associati alle espressioni presenti nel codice. 4.

Si risponda

alla domanda sulla

mappatura della memoria

così come richiesto al punto

/ sezione dichiarativa variabili globali / #define N 10 int vett [N];

/ funzione f_ric / int f_ric (int  p, int i)  int j;

/ variabili locali /

j = i; if (j == -1)  return 0;  else  p = vett [i]; return f_ric (p, i - 1);  / end if /  / f_ric /

/ chiamata ricorsiva /

4.

punto

1

– (numero di righe non significativo)

contenuto simbolico

spi. rispetto a spi. rispetto a stack pointer

frame pointer

fp

8

0

ra

4



4

s0 (assegnato a varloc j)

0



8

a1 (assegnato a param i)

indirizzi alti

 fp

salvato prima di chiamata

 sp max estensione del prologo chiamante

indirizzi bassi

punto

VETT:

2

– codice MIPS della sezione dichiarativa globale (num. righe non signif.)

.data

0x 1000 0000

// indirizzo di impianto

.space

40

// dichiarazione variabile globale

punto

F_RIC:

3

– codice MIPS di

f_ric

(num. righe non signif.)

addiu $sp, $sp, -12 sw

$fp, 8($sp)

addiu $fp, $sp, -8

// costruisci area // salva fp chiamante // sposta fp

// da qui si usa $fp come reg base per accedere all’area di att.

IF:

THEN:

ELSE:

.eqv

RA, -4

// spi ra salvato (risp. a fp)

.eqv

S0, -8

// spi s0 salvato (risp. a fp)

sw

$ra, RA($fp)

// salva ind rientro

sw

$s0, S0($fp)

// salva reg s0 (varloc J)

move

$s0, $a1

// aggiorna varloc j

li

$t0, -1 (o addi $t0, $0, -1) // carica cost -1

bne

$s0, $t0, ELSE

// se j != -1 va’ a ELSE

move

$v0, $0 (o add $v0, $0, $0)

// prepara valusc

j

ENDIF

// va’ a ENDIF

la

$t0, VETT

// carica ind VETT

move

$t1, $a1

// copia arg i

sll

$t1, $t1, 2

// allinea indice

addu

$t0, $t0, $t1

// calcola ind elem

lw

$t1, ($t0)

// carica elem v[i]

sw

$t1, ($a0)

// aggiorna

addiu $sp, $sp, -4

// 1) decrementa reg sp

sw

$a1, ($sp)

// 2) salva param i (push)

addi

$a1, $a1, -1

// calcola i – 1

jal

F_RIC

// chiama f_ric

lw

$a1, ($sp)

// 3) ripristina param i (pop)

addiu $sp, $sp, 4 ENDIF:

p

// 4) incrementa reg sp

lw

$s0, S0(fp)

// ripristina reg s0

lw

$ra, RA($fp)

// ripristina ind rientro

// fine dell’uso di $fp per accedere all’area di attivazione lw

$fp, 8($sp)

addiu $sp, $sp, 12 jr

$ra

// ripristina fp chiamante // elimina area // rientra

Nota

bene:

l’istruzione

“lw

$fp,

8($sp)”

di

ripristino

del

registro

fp

potrebbe

essere

anche

scritta

semplicemente come “lw $fp, ($fp)”, con base ancora fp; nella prima forma però essa è chiaramente l’inverso dell’istruzione “sw $fp, 8($sp)” di salvataggio iniziale. Insomma:

come nell’esercizio

(registro base sp)

in alternativa

sw $fp, 8($sp) // salva fp

sw $fp, 8($sp) // salva fp (base sp)

lw $fp, 8($sp) // ripristina fp

lw $fp, ($fp) // ripristina fp (base fp)

Note varie:



il registro fp viene salvato e aggiornato nel prologo del chiamato (e dunque ripristinato nell’epilogo del chiamato), come prima operazione (ultima operazione), pertanto nel corpo della funzione i riferimenti al contenuto dell’area sono fatti con spiazzamento rispetto a fp (non rispetto a sp)



l’istruzione “li” è sostituibile con l’istruzione “addi” poiché la costante –1 da caricare è a solo 16 bit



la pseudo-istruzione “move” è facilmente espandibile tramite un’istruzione “addi”



formalmente il registro “s0” va salvato in pila a cura del chiamato, poiché è assegnato alla variabile locale “j”, ma giacché la funzione in realtà non lo modifica, ottimizzando molto si potrebbe evitare di salvarlo (così però deviando dal modello rigoroso di area di attivazione)



per il parametro “i” si vedano le considerazioni fatte nella prima soluzione



idem per il parametro “p”



AVVERTENZA: si badi bene che lo statement C di assegnamento “*p = vett [i]” USA il parametro puntatore “p”, ma non ne modifica il valore, ossia non cambia l’indirizzo che costituisce il valore di “p” ! ciò che viene modificato, assegnandogli il valore dell’elemento con indice “i” del vettore, è l’oggetto puntato da “p” (si riveda il punto precedente)



i registri temporanei “t0-t7” non vengono salvati (non vengono date indicazioni che la funzione si aspetti di poterli riavere inalterati dopo la chiamata ricorsiva)

Potrebbero esserci altre piccole ottimizzazioni di codice.

punto

4

– mappatura della memoria

Si considerino le ipotesi seguenti relative all’allocazione del programma in codice eseguibile in memoria:



il programma è collocato in memoria secondo il modello standard di MIPS, e l’ordine delle funzioni nel codice è prima main, poi f_ric

 

la dimensione di main è di

1024 byte

il valore del registro sp immediatamente prima che main effettui il passaggio di parametri alla prima invocazione di f_ric è pari a



0x 7FFF 0000

si ricorda che la memoria è indirizzabile a

byte

si chiedono: l’indirizzo della prima istruzione di main:

0x 0040 0000 (standard MIPS)

l’indirizzo della prima istruzione di f_ric:

0x 0040 0000

 1024 (dec)  0x 0040 0000  0x 0000 0400  0x 0040 0400

il valore di sp subito prima della seconda invocazione di f_ric:

0x 7FFF 0000

 (12  4) dec  0x 7FFF 0000  0x 0000 0010  0x 7FFE FFF0

nota bene: subito prima della seconda invocazione di f_ric la pila ha la max estensione

il valore di sp relativo all’area di attivazione della seconda chiamata di f_ric:

0x 7FFE FFF0

 12 dec  0x 7FFE FFF0  0x 0000 000C  0x 7FFE FFE4

nota bene: l’area di attivazione di f_ric (senza estensione per il prologo del chiamante) ha dimensione 12 byte

esercizio linguaggio m acchina – esame 9 luglio 2015 – VARI ANTE I I prima parte – traduzione in assembler Si

deve

tradurre

in

linguaggio

macchina

simbolico

(linguaggio

assemblatore)

MIPS

il

frammento

di

programma C riportato sotto, costituito ...