Calcolatori elettronici - Appunti

PROCEDURE ANNIDATE.

Si supponga per esempio che il programma principale chiami la procedura A con un

parametro uguale a 3, mettendo il valore 3 nel registri $a0 e usando l’istruzione jal A.

L’indirizzo di ritorno da A al main è dunque contenuto in $ra. Si supponga poi che la

procedura A chiami la procedura B con un passandole il valore 7 posto in $a0. si

jal B

verificano 2 problemi:

Ð dato che A non ha ancora finito il suo lavoro, si verifica un conflitto nell’uso del

registro $a0;

Ð si verifica anche un conflitto nell’utilizzo di $ra: l’istruzione di provvede a

jal B

salvare l’indirizzo di ritorno della procedura B verso la procedura a in $ra,

eliminando l’indirizzo di ritorno della procedura A verso il main.

Una soluzione consiste nel salvare nello stack tutti i registri che devono essere preservati.

Ð Il programma chiamante memorizza nello stack qualsiasi registro argomento ($a0-

$a3) o registri temporaneo ($t0-$t9) di cui avrà bisogno dopo la chiamata;

Ð Il programma chiamato invece salva nello stack il registro di ritorno $ra e gli altri

registri che utilizza ($s0-$s7).

Esempio: programma che calcola il fattoriale di un numero n.

int fattoriale (int n)

{ if (n<1) return (1);

else return (n*fact(n-1);

}

Il parametro n corrisponde al registro argomento $a0.

Il programma innanzitutto salva nello stack due registri: l’indirizzo di ritorno e $a0. Si

aggiorna lo stack per fare posto a 2 elementi e si salvano l’indirizzo di ritorno e il

parametro n.

Fattoriale: addi $sp, $sp, -8

sw $ra, 4($sp)

sw $a0, 0($sp)

La prima volta che la proceduta fattoriale viene chiamata, l’istruzione sw salva un indirizzo

nel programma che l’ha chiamata. Le due istruzioni successive verificano se n è minore di

1, saltando a L1 se n≥1 16

Le istruzioni

slti $t0, $a0, 1

beq $t0, $zero, L1

Se n<1, fattoriale restituisce il valore 1 mettendolo in un registro valore. Quindi ripristina

dallo stack i due valori salvati e salta all’indirizzo di ritorno.

addi $v0, $zero, 1

addi $sp, $sp, 8

jr $ra

prima dell’aggiornamento della stack pointer si sarebbero dovuti ripristinare $a0 e $ra, ma

dato che quando n è minore di 1 non cambiano, è possibile non farlo.

Se n non è minore di 1 si salta a L1: il parametro n viene decrementato di 1 e viene

nuovamente chiamata la procedura Fattoriale passandole tale valore.

L1: addi $sa, $sa, -1

jal Fattoriale

l’istruzione successiva è quella a cui la procedura Fattoriale ritornerà; il vecchio indirizzo

di ritorno e il vecchio parametro sono ripristinati, oltre ad eseguire l’aggiornamento dello

stack pointer: lw $a0, 0($sp) # ind. = L1+8

lw $ra, 4($sp)

addi $sp, $sp, 8

Successivamente nel valore $vo viene memorizzato il prodotto del valore corrente per il

vecchio parametro $a0; qui si suppone l’esistenza di un’operazione di moltiplicazione,

analizzata più avanti. Infine la procedura fattoriale salta nuovamente all’indirizzo di ritorno.

mul $v0, $a0, $v0

jr $ra

Gestione dello stack

Al 1° richiamo salva nello stack:

1) l’indirizzo di ritorno che è nella zona del chiamante

(nome attribuito JALM + 4);

2) il valore di $a0 = n.

Al 2° richiamo salva nello stack:

1) l’indirizzo della procedura Fattoriale (indicato da L1+8);

2) il valore di $a0 = n-1.

Al 3° richiamo salva nello stack L1+8 e $a0 = n-2.

. . . . .

Al n-mo richiamo salva nello stack L1+8 e $a0 = 0.

Esempi di esecuzione al variare di n:

n=0

$ra = JALM+4

$a0 = n = 0

n=1

$ra = JALM+4 1^esecuzione

$a0 = n = 1

$ra = L1+8 2^esecuzione

$a0 = n-1 = 0 17

Le istruzioni

Alla prima iterazione salta a L1;

$a0=0;

$ra=L1+8.

Alla seconda iterazione non salta a L1: ritorna a L1+8, dove $a0=1; ra=JALM+4;

$v0*1=$v0 e ritorna al main.

n=2

$ra = JALM+4 1^ esecuzione

$a0 = n = 2

$ra = L1+8 2^ esecuzione

$a0 = n-1 = 1

$ra = L1+8 3^ esecuzione

$a0 = n-2 = 0

Alla 1^iterazione salta a L1; a0 diventa 1; ra=L1+8;

Alla 2^iterazione salta a L1; a0 diventa 0; ra=l1+8;

Alla 3^ iterazione: non salta a L1, quindi v0=1 e torna a L1+8, a0=1; ra=L1+8; v0*1=v0;

torna a L1+8, a0=2, ra=JALM+4, v0=1*a0=2 e torna al main program.

fatt.

Salva indirizzo di

ritorno e valore a0 Richiamo

nello stack no

sì a0<1

v0=1 dec a0

Preleva a0 Ritorno all’ultima

chiamata effettuata

(2 casi: n-1 volte si

ritorna alla routine

Ultima iterazione Iter. intermedie

fatt. all’indirizzo

L1+8 e si preleva

a0 dallo stack, solo v0=a0*v0

l’ultima si torna al

Ritorno main (JALM+4)) e

si aggiorna SP 18

Le istruzioni

Fattoriale: addi $sp, $sp, -8

sw $ra, 4($sp)

sw $a0, 0($sp)

slti $t0, $a0, 1

beq $t0, $zero, L1

addi $v0, $zero, 1

addi $sp, $sp, 8

jr $ra

L1: addi $sa, $sa, -1

jal Fattoriale

lw $a0, 0($sp) # ind. = L1+8

lw $ra, 4($sp)

addi $sp, $sp, 8

mul $v0, $a0, $v0

jr $ra

Commenti ai programmi per il calcolo del fattoriale:

Limite massimo di cui possiamo calcolare il fattoriale?

Il numero massimo di cui possiamo calcolare il fattoriale è limitato dal valore stesso che il

fattoriale assume, in quanto questo risultato deve essere contenuto in un registro: non

deve superare i 32 bit!!!

Cosa accade se il numero che passiamo al sottoprogramma è maggiore del numero

32

massimo di cui vogliamo calcolare il fattoriale, cioè cosa accade se n!>2 -1? Il risultato

che viene restituito sono i soli 32 bit meno significativi del n! calcolato.

Nel fare la moltiplicazione, il processore utilizza 2 registri: Hi, in cui mette i 32 bit più alti,

più significativi del numero (n!) e Lo, in cui mette i 32 bit meno significativi (RICORDA:

moltiplicare 2 numero da 32 bit = numero da 64 bit!).

Come si modifica il programma per controllare a tempo di esecuzione se ho superato il

numero massimo di cui posso calcolare il fattoriale? Se il registro Hi contiene un numero

diverso da 0, significa che il risultato del fattoriale supera i 32 bit a disposizione.

Lezione del 5/11/07

GESTIONE CARATTERI

La maggior parte dei calcolatori utilizza 8 bit per rappresentare i caratteri e la codifica

ASCII è quella più utilizzata. L’elaborazione di testi è talmente diffusa che il MIPS offre

istruzioni apposite per trasferire i byte: (lb) prende un byte dalla memoria,

load byte

mettendolo negli 8 bit meno significativi di un registro (quelli a destra), mentre store byte

(sb) prende il bit corrispondente agli 8 bit meno significativi di un registro e lo mette in

memoria.

Esempio: programma che copia la stringa y nella stringa x, usando il byte

Null come carattere di fine stringa.

In realtà ci sono 3 modi per capire se una stringa è finita:

1. il primo valore contenuto nella stringa di caratteri ne codifica la lunghezza;

2. c’è una variabile ulteriore, oltre alla stringa, che è la lunghezza della stringa stessa;

3. le stringhe sono terminate dal carattere Null (ATTENZIONE: null è diverso da 0, ma

null in codice ASCII è rappresentato da 000, mentre 0=048).

19

Le istruzioni

void strcpy (char x[], char y[])

{ int i;

i = 0;

while ((x[i] = y[i]) != 0) /* copia e test byte */

i = i + 1;

}

Si supponga che gli indirizzi di base dei vettori siano: x=$a0; y=$a1; mentre i=$s0.

strcpy: addi $sp, $sp, -4

sw $s0, 0($sp) # salva $s0 nello stack

add $s0, $zero, $zero # i = 0

L1: add $t1, $a1, $s0 # ind. y[i] in $t1

lb $t2, 0($t1) # $t2 = y[i]

add $t3, $a0, $s0 # ind. x[i] in $t3

sb $t2, 0($t3) # x[i] = y[i]

addi $s0, $s0, 1 # i = i + 1

≠

bne $t2, $zero, L1 # se y[i] 0 vai a L1

lw $s0, 0($sp) # ripristina $s0 dallo stack

addi $sp, $sp, 4

jr $ra # ritorno

La procedura aggiorna lo stack pointer e poi salva il registro $s0 nello stack:

addi $sp, $sp, -4

sw $s0, 0($sp)

per inizializzare i=0, l’istruzione successiva pone $s0 a 0, sommando 0 a 0 e mettendo la

somma in $s0.

add $s0, $zero, $zero

Inizia il ciclo. L’indirizzo y[i] è creato sommando i a y[ ] e ponendo il risultato in $t1:

add $t1, $a1, $s0

Non è necessario moltiplicare i per 4, dato che y è un vettore di byte e non di word: non è

necessario rispettare il vincolo di allineamento! Per caricare il carattere presente in y[i] si

usa l’istruzione load byte che mette il carattere in $t2:

lb $t2, 0($t1)

con un calcolo analogo mettiamo l’indirizzo di x[i] in $t3 e il carattere che si trova in $t2

viene scritto nella locazione di memoria così individuata:

add $t3, $a0, $s0

sb $t2, 0($t3)

incrementiamo i e controlliamo se il carattere di fine stringa è Null, cioè se il carattere è 0:

addi $s0, $s0, 1

bne $t2, $zero, L1

se la stringa è terminata, vengono ripristinati i valori di $s0 e dello stack pointer e si esce

dalla procedura.

lw $s0, 0($sp)

addi $sp, $sp, 4

jr $ra

Nota: se invece del registro $s0, veniva usato un registro t, ad esempio $t4, non erano

necessarie le operazioni di push e pop. 20

Le istruzioni

OPERANDI IMMEDIATI.

Molto spesso accade che si necessiti, all’interno di un programma di piccole costanti:

addi $sp, $sp, 4

Possibili soluzioni:

mettere in memoria le costanti tipiche e caricarle da questa soluzione troppo lenta!

œ Æ

Creare registri preservati per le costanti, come il $zero nel MIPS ho a disposizione

œ Æ

solo 32 registri: sono troppo pochi per memorizzare dati, costanti, valori…!

Modifichiamo le istruzioni di le facciamo diventare

œ add, slt, and, or…e addi

=add with immediate… rendi il caso più comune il più veloce possibile.

PRINCIPIO DI PROGETTO 3:

Le operazioni su costante avvengono molto di frequente e includendo le costanti all’interno

dello operazioni aritmetiche queste ultime risultano molto più veloci rispetto a quando le

costanti sono caricate dalla memoria.

addi $29, $29, 4

slti $8, $18, 10

andi $29, $29, 6

ori $29, $29, 4

Dimensioni delle costanti:

addi $29, $29, 4

Il formato utilizzato è il formato ho a disposizione al massimo 16 bit. Se la costante è

I:

lunga al massimo 16 bit, quando la ALU fa la somma, somma un numero di 32 bit a uno di

16: i 16 bit mancanti?

Faccio l’operazione dell’estensione poiché per la somma la ALU lavora con

del segno:

numeri in complemento a 2, quando voglio trasformare un numero da 16 bit a 32 bit, copio

ripetutamente nei 16 bit mancanti il bit di segno

Posso settarli a se la

œ 0 costante è positiva;

Se la costante è negativa?un numero in complemento a 2 negativo h