Il linguaggio assembly - DEIdepoli/fi2ae/slides_pw/old-lucidi-06/... · un corpo Esecuzione della...

1

1

Il linguaggio assembly

Chiamata a proceduraPH cap. 2.7 e app. A.6

2

Chiamata a procedura in C

f = f + 1;if (f == g)

res = prod(f,g);else f = f -1;. . . . . .

f = f + 1;if (f == g)

res = prod(f,g);else f = f -1;. . . . . .

int prod (int x, int y){ int out;out = x * y;return out;

}


}

2

3

Protocollo chiamata a procedura

Il procedura chiamante deve eseguire le seguenti operazioni:

Predisporre i parametri di ingresso in un posto accessibile alla procedura chiamata

Trasferire il controllo alla procedura chiamata

La procedura chiamata deve eseguire le seguenti operazioni:

Allocare lo spazio di memoria necessario ai propri dati locali (record di attivazione)

Eseguire il codice (corpo della procedura chiamata)

Memorizzare il risultato in un luogo accessibile al chiamante

Restituire il controllo al chiamante

4

Allocazione dei registri

Convenzioni per l'allocazione dei registri nelle le chiamate a procedura:

$a0-$a3 ($f12-$f15) registri argomento usati dal chiamante per il passaggio dei parametri

Se i parametri sono più di 4 si passano mediante lo stack

$v0,$v1 ($f0, …, $f3) registri valore sono usati dalla procedura per memorizzare i valori di ritorno

$ra (return address) registro di ritorno per memorizzare l'indirizzo della prima istruzione del chiamante da eseguire una volta terminata la procedura

3

5

Istruzione jal

E' necessaria un'apposita istruzione per cambiare il flusso di

esecuzione (salto a procedura) e memorizzare l'indirizzo di

ritorno (istruzione successiva alla chiamata di procedura)

jal Indirizzo_Procedura (jump and link)

Salta all'indirizzo con etichetta Indirizzo_Procedura e

memorizza il valore corrente del Program Counter

(indirizzo dell'istruzione successiva PC+4) in $ra

La procedura chiamata come ultima istruzione esegue jr $ra

per effettuare il salto all'indirizzo di ritorno

6

Chiamata a procedura: responsabilità

Il programma chiamante deve:

Mettere i valori dei parametri da passare alla procedura chiamata nei registri $a0-$a3 (eventualmente nello stack)

Utilizzare l'istruzione jal addr per saltare alla procedura e salvare il valore di (PC+4) nel registro $ra

La procedura chiamata deve:

Eseguire il proprio codice

Memorizzare il risultato nei registri $v0, $v1

Restituire il controllo al chiamante con l'istruzione jr $ra

4

7

// . . . res = prod(f,g);// . . .

# $s5 contiene f# $s6 contiene g# $s1 contiene res

move $a0, $s5 # argomento fmove $a1, $s6 # argomento gjal prod # chiama prod(f,g)

lab: move $s1, $v0 # res = f*g

Esempio 1 – funzione chiamante

C :

MIPS :

8

Esempio 1 - funzione chiamata

prod:

mult $t0, $a0, $a1 //out = $t0 = x*y

move $v0, $t0 // $v0 = out

jr $ra // return


}

C :

MIPS :MIPS :

5

9

Esempio 1 - funzione chiamata

prod:

mult $v0, $a0, $a1 // $v0 = $t0 = x*y

jr $ra // return

int prod (int x, int y) { return x * y;}

C :

MIPS :MIPS :

10

int v[ ]; // $s2int k; // $s3// . . .swap (v, k);// . . .

int v[ ]; // $s2int k; // $s3// . . .swap (v, k);// . . .

Esempio 2 (chiamante)

#$s2 contiene indiriz. v

#$s3 contiene k

move $a0, $s2 // v

move $a1, $s3 // k

jal swap

#$s2 contiene indiriz. v

#$s3 contiene k

move $a0, $s2 // v

move $a1, $s3 // k

jal swap

C :

MIPS :k

6

11

void swap (int v[], int k) { int temp;

temp = v[k];v[k] = v[k+1];v[k+1] = temp;

}

void swap (int v[], int k) { int temp;

temp = v[k];v[k] = v[k+1];v[k+1] = temp;

}

Esempio 2 (proc. chiamata) PH. p. 122

swap:sll $t1, $a1, 2 # $t1 = k*4add $t0, $a0,$t1 # $t0 addr. v[k]lw $t1, 0($t0) # temp = v[k]lw $t2, 4($t0) # $t2 = v[k+1]sw $t2, 0($t0) # v[k] = $t2sw $t1, 4($t0) # v[k+1] = tempjr $ra

swap:sll $t1, $a1, 2 # $t1 = k*4add $t0, $a0,$t1 # $t0 addr. v[k]lw $t1, 0($t0) # temp = v[k]lw $t2, 4($t0) # $t2 = v[k+1]sw $t2, 0($t0) # v[k] = $t2sw $t1, 4($t0) # v[k+1] = tempjr $ra

MIPS :

#$a0 base address di v#$a1 contiene k#$t1 usato per temp

#$a0 base address di v#$a1 contiene k#$t1 usato per temp

k

12

Esempio 3: fattoriale.text

main: # read int in $t0li $v0, 5syscallmove $t0, $v0

# parametro in $a0move $a0, $t0

# calcola ($t0)!jal fact # chiamata# risultato in $t1.move $t1, $v0

# stampa il fat.leli $v0, 1move $a0, $t1syscall# . . . . .

fact: li $v0,1 #risultato

# ripete fino a che# $a0 <= 1

loop: ble $a0, 1, fine

# $v0 = $v0 * $a0mul $v0, $v0, $a0

# $a0 = $a0 - 1 sub $a0, $a0, 1j loop

# risultato in $v0fine: jr $ra # return

7

13

Chiamata a procedura - Problemi

Problemi:la procedura chiamante vuole passare più di 4 argomenti alla procedura chiamata la procedura chiamata vuole ritornare più di due valori alla procedura chiamante il programma chiamante ha bisogno di mantenere inalterati dei registri che la procedura chiamata potrebbe modificareallocare lo spazio necessario per le variabili locali della procedura chiamata gestire procedure annidate (procedure che richiamano al loro interno altre procedure) e procedure ricorsive (procedure che invocano dei “cloni” di se stesse)

14

Soluzione : uno stack

Lo stack (pila) è una struttura dati costituita da una coda LIFO

(last-in-first-out)

I dati sono inseriti nello stack con l'operazione push

I dati sono prelevati dallo stack con l'operazione pop

E' necessario un puntatore al top dello stack per salvare i

registri che servono al programma chiamato

Il registro $sp (stack pointer o puntatore allo stack) contiene

l'indirizzo del top dello stack e viene aggiornato ogni volta che

viene inserito o estratto il valore di un registro

8

15

Gestione dello stack

Lo stack cresce da indirizzi di memoria alti verso indirizzi di memoria bassi

Il registro $sp contiene l'indirizzo all’ultima posizione occupata in cima allo stack

L'inserimento di un dato nello stack (operazione di push) avviene decrementando $sp per allocare lo spazio

Il prelevamento di un dato dallo stack (operazione di pop) avviene incrementando $sp (per eliminare il dato) e riducendo quindi la dimensione dello stack

16

Tutto lo spazio di cui ha bisogno una procedura ( stack frame, activation record, procedure frame) viene esplicitamente allocato nello stack dal programmatore in una sola volta, all' inizio della procedura

Lo spazio nello stack viene allocato sottraendo a $sp il numero di byte necessari. Esempio:

addi $sp, $sp, -24 # alloca 24 byte nello stack# = 6 word

addi $sp, $sp, -24 # alloca 24 byte nello stack# = 6 word


9

17

Al rientro da una procedura il record di attivazione viene rimosso (deallocato) incrementando $sp della stessa quantità di cui lo si era decrementato alla chiamata. Esempio:

E’ necessario liberare lo spazio allocato per evitare di esaurire la memoria disponibile (memoria heap)

addi $sp, $sp, 24 # dealloca 24 byte nello stackaddi $sp, $sp, 24 # dealloca 24 byte nello stack


18


Per inserire elementi nello stack

sw $t0, offset($sp) # salvataggio di $t0

Per recuperare elementi dallo stack

lw $t0, offset($sp) # ripristino di $t0

10

19


IndirizziMemoria

$sp

alti

bassi

addi $sp, $sp,-8sw $t1, 4($sp)sw $t0, 0($sp)

12$sp

alti

bassi

45

$t0=45$t1=12

$t0=45$t1=12

20

Lo stack

Quando si chiama una procedura il contenuto dei registri non temporanei ($t0-$t9) utilizzati dal chiamato vanno:

salvati nello stack all’inizio dell'esecuzione della proceduraripristinati alla fine

Esempio ( P.H. 2.7 p. 81):int somma_algebrica (int g, int h, int i, int j) {

int f;f = (g + h) - (i + j);return f;

}

11

21

Esempio (cont.)

# g,h,i e j associati a $a0, …, $a3;# f associata ad $s0# il calcolo di f richiede 3 registi: $s0, $t0, $t1# necessario salvare i 3 registri nello stack

# esempio:somma_algebrica:

addi $sp,$sp,-12 # alloca nello stack# lo spazio per i 3 registri

sw $t1, 8($sp) # salvataggio di $t1sw $t0, 4($sp) # salvataggio di $t0sw $s0, 0($sp) # salvataggio di $s0

22

Esempio (cont.)

$t0$s0

Memoria

$sp prima (dopo)l’attivazione

indirizzi alti

indirizzi bassi

$t1

$sp

12

23

Esempio (cont.)# g,h,i e j associati a $a0, …, $a3;

add $t0, $a0, $a1 # $t0 <- g + hadd $t1, $a2, $a3 # $t1 <- i + jsub $s0, $t0, $t1 # f <- $t0 - $t1add $v0, $s0, $zero # restituisce f copiandolo

# nel reg. di ritorno $v0# ripristino del vecchio contenuto dei registri# estraendoli dallo stack

lw $s0, 0($sp) # ripristino di $s0lw $t0, 4($sp) # ripristino di $t0lw $t1, 8($sp) # ripristino di $t1addi $sp, $sp, 12 # deallocazione dello stack

# per eliminare 3 registri

jr $ra #ritorno al prog. chiamante

24

Lo stack

Per evitare di salvare inutilmente il contenuto dei registri, i registri sono divisi in due classi:

registri temporanei: $t0, …, $t9$f4, .. $f11, $f16, .., $f19

il cui contenuto non è salvato dal chiamato nello stack; registri non-temporanei: $s0, …, $s7 ($f20, …, $f31)“salvati” nello stack e ripristinati

Nell'esempio precedente: dato che il chiamante non si aspetta che $t0 e $t1 siano preservati durante la chiamata a procedura, si possono eliminare due store e due load.E' necessario salvare e ripristinare $s0 perché il chiamante si aspetta che tale registro non venga modificato

13

25

Convenzioni uso dei registri

Nome Numero Utilizzo

$zero$at$v0 - $v1$a0 - $a3

0

valori di ritorno

costante 01

2-34-7

riservato all’assembler

argomenti$t0 - $t7$s0 - $s7$t8 - $t9$k0 - $k1

8-15

temp.neo non preservato

temp.neo non preservato16-2324-2526-27

temporaneo preservato

riservato per il kernel$gp$sp

28 pointer to global area29 stack pointer

$fp 30 frame pointer$ra 31 return address

26

Convenzioni uso dei registri

Registri usati per le operazioni floating point

Nome

$f0-$f3

$f4-$f11

$f12 - $f15

$f16 - $f19

$f20 - $f31

Utilizzo

Argomenti di una procedura

Valori di ritorno da procedura

Registri temporanei (non salvati)

Registri temporanei (non salvati)

Registri salvati

14

27

Procedure foglia - chiamante

Procedura foglia è una procedura che non contiene al suo interno chiamate ad altre procedure

non serve salvare $ra (perchè nessuno altro lo modifica)

Nel caso di procedure foglia, il chiamante salva nello stack:

i registri argomento e i registri temporanei di cui vuole preservare il contenuto ($a0-$a3, $t0-$t9,...)

Eventuali argomenti aggiuntivi da passare al chiamato oltre a quelli che possono essere contenuti nei registri $a0-$a3

28

Procedure foglia - chiamato

Nel caso di procedure foglia, il chiamato alloca nello stack:

I registri non temporanei che vuole utilizzare ( $s0-$s7)

Strutture dati locali (es: array, matrici) e le variabili localiche non sono associate a registri

Lo stack pointer $sp è aggiornato di conseguenza;alla fine i registri vengono ripristinati e lo stack pointer riportato al valore che aveva prima della chiamata

15

29

Record di attivazione procedure foglia

$sp prima (dopo)l’attivazione

$sp

Memoriaindirizzi alti

indirizzi bassi

Registri $s salvati

Variabili locali

30

Convenzioni per il salvataggio dell’ambiente

Riassunto convenzione del MIPS:per ottimizzare il numero di accessi alla memoria, il chiamante e il chiamato salvano solo i registri di un particolare gruppo il chiamante, se vuole che siano preservati, salva

i registri temporanei $t0-$t9 ($f4-$f11, $f16-$f19), i registri argomento $a0-$a3 ( $f12-$f15) eventuali argomenti aggiuntivi

il chiamato salva nello stack$ra;se li usa, i registri $s0-$s8 ($f20-$f31) e strutture dati locali (es: array, matrici) e variabili locali.

16

31

Struttura di una procedura

Ogni procedura ha:

un prologo

Salvataggio dell'ambiente

un corpo

Esecuzione della procedura vera e propria

un epilogo

Ripristino dell'ambiente

32

Prologo

Definizione di un nome-etichetta per la procedura (es:

proc_name:)

Determinazione della dimensione del record di attivazione

Per determinare la dimensione del record di attivazione si deve

stimare lo spazio per:

registri per variabili locali

registri interi da salvare

registri floating-point da salvare

altri registri particolari

17

33

Prologo

Allocazione dello spazio sullo stack: aggiornare il valore di $sp:

addi $sp,$sp,-dim_record_attivaz# lo stack pointer viene decrementato# della dimensione prevista per il# record di attivazione

Salvataggio dei registri per i quali è stato allocato spazio nello stack:

sw reg,dim_record_attivaz-N($sp)

N (N >= 4) viene incrementato di 4 ad ogni salvataggio

34

Esempio prologo

Record di attivazione di 16 byte :

addi $sp,$sp,-16sw $s0, 12($sp)sw $s1, 8($sp)sw $s2, 4($sp)

sw $ra, 0($sp)

$s1$s2

$sp prima(dopo) $s0

$sp $ra

18

35

Corpo della procedura

Stesura delle istruzioni per l'esecuzione delle funzionalità previste dalla procedura

36

Epilogo

Ripristino dei registri salvati: lw reg, dim_record_attivaz - N($sp)

Rimozione dello spazio allocato sullo stack:

addi $sp,$sp,dim_record_attivaz

Restituzione del controllo al chiamante:jr $ra

19

37

Esempio epilogo

Record di attivazione di 16 byte :

lw $s0, 12($sp)lw $s1, 8($sp)lw $s2, 4($sp)lw $ra, 0($sp)

addi $sp,$sp, 16

$s1$s2

$sp prima(dopo) $s0

$sp $ra

38

Procedure annidate e ricorsivePH 2.7 Appendice A.6

20

39

Procedure annidate e ricorsive

Procedure annidateannidate: richiamano al loro interno altre procedure Devono salvare nello stack un ambiente più ampio :

l'indirizzo di ritorno la procedura chiamata all'interno di un'altra riscrive il

contenuto di $ra

Procedure ricorsivericorsive: contengono una chiamata a se stesse al loro interno Devono salvare nello stack

l'indirizzo di ritorno eventuali risultati intermedi

40

Chiamato - Salvataggio del return address

Problema: il registro $ra memorizza un solo valore alla volta

fA: . . .

. . .

jal fB

. . .

li $v0, 10

syscall

fA: . . .

. . .

jal fB

. . .

li $v0, 10

syscall

fB: . . .

jal fC

. . .

. . .

. . .

jr $ra

fB: . . .

jal fC

. . .

. . .

. . .

jr $ra

fC: . . .

. . .

. . .

jr $ra

fC: . . .

. . .

. . .

jr $ra

dopo il primo jal, $ra punta qui

21

41

fA: . . .

. . .

jal fB

. . .

li $v0, 10

syscall

fA: . . .

. . .

jal fB

. . .

li $v0, 10

syscall

fB: . . .

jal fC

. . .

. . .

. . .

jr $ra

fB: . . .

jal fC

. . .

. . .

. . .

jr $ra

fC: . . .

. . .

. . .

jr $ra

fC: . . .

. . .

. . .

jr $ra


Problema: il registro $ra memorizza un solo valore alla volta

??non può ritornare poichèl'originale $ra è perso !

dopo il secondo jal, $ra punta qui

$ra non puntapiù qui !

42


Problema: il registro $ra memorizza un solo valore alla voltaSoluzione: salvare/ripristinare il registro $ra (usando lo stack) all'ingresso/uscita della funzione

fA: . . .

. . .

jal fB

. . .

li $v0, 10

syscall

fA: . . .

. . .

jal fB

. . .

li $v0, 10

syscall

fB: # push $ra

jal C

. . .

. . .

. . .

# pop in $ra

jr $ra

fB: # push $ra

jal C

. . .

. . .

. . .

# pop in $ra

jr $ra

fC: # push $ra

. . .

# pop in $ra

jr $ra

fC: # push $ra

. . .

# pop in $ra

jr $ra

. . . rendendo possibile ilritorno dalla funzione !

salvare significa che $rapuò essere modificato . . .

22

43

Chiamante - Salvataggio registri

Problema: la funzione chiamata può usare registri $t0-$t9 che ilchiamante vuole preservare

...

lw $t0, a

...

...

jal fun

...

...

# $t0 è stato

# cambiato !

add $t0, $t0, $v0

...

...

lw $t0, a

...

...

jal fun

...

...

# $t0 è stato

# cambiato !

add $t0, $t0, $v0

...

fun: ...

# usa $t0

lw $t0, x

...

jr $ra

fun: ...

# usa $t0

lw $t0, x

...

jr $ra

44

Chiamante - Salvataggio registri

Problema: la funzione chiamata può usare registri $t0-$t9 che ilchiamante vuole preservareSoluzione: salva/ripristina registri nello lo stack

. . .lw $t0, a. . .# push $t0jal func# pop $t0. . .# $t0 è stato# preservatoadd $t0, $t0, $v0. . .

. . .lw $t0, a. . .# push $t0jal func# pop $t0. . .# $t0 è stato# preservatoadd $t0, $t0, $v0. . .

func: ...# usa $t0lw $t0, x...jr $ra

func: ...# usa $t0lw $t0, x...jr $ra

23

45

Convenzioni chiamata a funzione

ChiamanteChiamante

salva i registri temporaneinello stack(se li vuole riusare )

salva i valori degli argomenti nello stack(se li vuole riusare )

chiama la funzione con l'istruzione jaljal

ChiamatoChiamato

salva $ra nello stack

salva registri $s0 . . .

alloca le variabili locali nello stack

Il linguaggio assembly - DEIdepoli/fi2ae/slides_pw/old-lucidi-06/... · un corpo Esecuzione della...

Documents

Transcript of Il linguaggio assembly - DEIdepoli/fi2ae/slides_pw/old-lucidi-06/... · un corpo Esecuzione della...