MIPS

Esercitazione

Il linguaggio assembler

MIPScorso di

Didattica delle Applicazioni dell’Informatica

modulo A

Angelo Ciaramella

[email protected]

Sommario

• Riepilogo del set di istruzioni del MIPSIstruzioni matematicheIstruzioni di accesso alla memoriaIstruzioni di salto branch e cicliIstruzioni per la chiamata a procedure e subroutine

•Esempio• ordinamento di un vettore

•Esercizi• Codifica nel linguaggio assembler MIPS di un programma

scritto in C• Codifica nel linguaggio C di un programma in MIPS

Il linguaggio di progrmmazione

� La notazione con cui è possibile descrivere gli algoritmi.

�Programma: è la rappresentazione di un algoritmo

in un particolare linguaggio di programmazione.

�Ogni linguaggio di programmazione dispone di un

insieme di “parole chiave” (keywords)

�Ogni linguaggio è caratterizzato da una sintassi e

da una semantica

Il linguaggio di programmazione

� Il linguaggio macchina �è direttamente eseguibile dall’elaboratore, senza nessuna traduzione.

�Il linguaggio assembler �Le istruzioni corrispondono univocamente a quelle macchina, ma vengono espresse tramite nomi simbolici (parole chiave).�Il programma prima di essere eseguito deve essere tradotto in linguaggio macchina (assemblatore).�Vincolo: necessità di conoscere in dettaglio le caratteristiche della macchina (registri, dimensione dei dati, set di istruzioni)�Anche semplici algoritmi implicano la specifica di molte istruzioni

�Il linguaggio ad alto livello.�Sono i linguaggi di terza generazione. Le istruzioni esprimono una serie di azioni. Il programma prima di essere eseguito deve essere tradotto in linguaggio macchina (traduttore)�Il programmatore può astrarre dai dettagli legati all’architettura ed �esprimerei propri algoritmi in modo simbolico�Sono indipendenti dalla macchina (astrazione)

Traduttore e assemblatore

Sviluppo di un programma

� I traduttori sono programmi particolari che provvedono a convertire il codice di programmi scritti in un dato linguaggio di programmazione(sorgenti), nella corrispondente rappresentazione in linguaggio macchina (eseguibili)

�Compilatori�Accettano in ingresso l’intero programma e producono in uscita la rappresentazione dell'intero programma in linguaggio macchina.

�Interpreti�Traducono ed eseguono direttamente ciascuna istruzione del programma sorgente, istruzione per istruzione.

Interpetri e compilatori

� Compilatori�Per ogni programma da tradurre, lo schema viene percorso

una volta sola prima dell’esecuzione.

�Interpreti�Lo schema viene attraversato tante volte quante sono

le istruzioni che compongono il programma;

ad ogni attivazione dell'interprete su una particolare

istruzione, segue l’esecuzione dell’istruzione stessa.

�L’esecuzione di un programma compilato è più veloce

dell'esecuzione di un programma interpretato

Architettura degli elaboratori

• Dalla nascita dell’elaboratore a programma memorizzato, intorno al 1950, oggi poche sono state le innovazioni di rilievonell’area dell’organizzazione e dell’architettura degli elaboratori.

• L’architettura RISC (Reduced Instruction Set Computer) rappresenta un notevole passo in avanti rispetto alla tendenza storica dell’architettura per i processori.

• Contrariamente esiste una architettura CISC (ComplexInstruction Set Computer) che richiedono un insieme di istruzioni più ricchi con un gran numeri di istruzioni complesse.

Processore MIPS

• Uno dei primi processori RISC a chip singolo comparso sul mercato fu sviluppato da MIPS Technology Inc.

• Il sistema s’ispirava a un elaboratore sperimentale, anch’essodi nome MIPS sviluppato a Stanford

• I modelli MIPS a 32 bit sono R2000 e R3000. Il modelloMIPS R4000 è a 64 bit.

• Le operazioni aritmetiche vengono effettuate tra registri e cisono istruzioni dedicate per lo scambio di informazioni tramemoria e registri.

Introduzione

• Il MIPS (Acronimo di Million InstructionPer Second, milioni di istruzioni per secondo) è un'unità di misura della potenza di un microprocessore.

• Le istruzioni a cui si fa riferimento sono quelle assemblydel processore in esame.

• Tali istruzioni sono in genere molto semplici, ad esempio una singola somma o un singolo test per decidere se una condizione è vera o è falsa.

• Un normale programma per computer è composto da migliaia o milioni di queste istruzioni, normalmente generate in modo automatico da un compilatore.

Istruzioni di trasferimento dati

• Gli operandi delle istruzioni aritmetiche devono provenire da un limitato numero di locazioni detti registri

• La dimensione di un registro nella architettura MIPS è di 32 bit

• Il MIPS ha 32 registri rappresentati nella notazione $0, $1, …, $31

• Le operazioni aritmetiche avvengono solo sui registri, quindi il processore MIPS deve possedere delle istruzioni di trasferimento dati fra la memoria e i registri

Allocazione dei registri

Operandi del MIPS

Istruzioni aritmetiche

Ogni istruzione aritmetica del MIPS deve avere esattamente tre variabili

Istruzioni aritmetiche

Esempio

add a,b,c # la somma di b e c è posta in a add a, a, d # la somma di b, c e d è posta in a


• L’istruzione che trasferisce dalla memoria ai registri è chiamata load word (lw)

formato: nome dell’operazione, registro da caricare, indirizzo di inizio della matricee registro contenente l’indice dell’elemento della matrice da caricare nel registrospecificato

• L’istruzione che serve a trasferire un dato dai registri alla memoria è chiamata store(sw).

formato: nome dell’operazione, registro da memorizzare, indirizzo di inizio dellamatrice e il nome del registro che contiene l’indice relativo all’elemento della matriceda memorizzare.


Procedura swap in MIPS

lw $15, 0($2)lw $16, 4($2)sw $16, 0($2)sw $15, 4($2)jr $31

Procedura in linguaggio C

swap (int v[ ], int k){ int temp;temp = v[k]v[k] = v[k+1];v[k+1] = temp;}

Istruzioni di scelta

Il processore MIPS ha due istruzioni di tipo condizionale

- beq register1, register2, L1

Questa istruzione dice di andare all’istruzione la cui etichetta è L1, se il valoredi register1 è uguale a quello di register2 (branch equal)

- bne register1, register2, L1

Questa istruzione dice di andare all’istruzione la cui etichetta è L1, se il valoredi register1 è diverso da quello di register2 (branch not equal)

Istruzioni di scelta

Esempio di salto condizionato

Codice Cif (i == j) go to L1;

f = g + h;

L1: f = f - i;

Codice MIPSRegistri usati : $s0 ... $s4 = f ... j

beq $s3, $s4, L1 #branchadd $s0, $s1, $s2 #skipped

L1: sub $s0, $s0, $s3 #always ex.

Istruzione if-then-else

Esempio

Registri $s0, $s1, $s2, $s3, $s4 = f, g, h, i, j

bne $s3, $s4, ELSE #branchadd $s0, $s1, $s2 #skippedj EXITELSE: sub $s0, $s1, $s2EXIT: ...

Costrutto if - then - else

Ciclo sugli array

Esempio di ciclo

Loop: g = g + A [i];i = i + j;if (i != h) goto Loop

....

Codice MIPS

Registri usati : $s1, $s2, $s3, $s4 = g, h, i, j, ar ray base = $s5

LOOP: add $t1, $s3, $s3 #$t1 = 2 • iadd $t1, $t1, $t1 #$t1 = 4 • iadd $t1, $t1, $s5 #$t1 = ad r.lw $t0, 0 ($t1) #loadadd $s1, $s1, $t0 #g = g + A [i]add $s3, $s3, $s4 #i = i + jbne $s3, $s2, LOOP

Istruzioni di salto incondizionato

Istruzioni di salto incondizionato (jump)

- j address

- jr $s3 # address in reg. $3

Questa istruzione consente un salto incondizionato all’indirizzo specificato (j) o l’indirizzo centenuto nel registro specificato(jr)

Ciclo while

Esempio di ciclo while

while (save [i] == k)i = i + j;....

Codice MIPS$s3, $s4, $s5 = i, j, k, array base = $s6

LOOP: add $t1, $s3, $s3 #$t1 = 2 • iadd $t1, $t1, $t1 # $t1 = 4 • iadd $t1, $t1, $s5 #$ t1 = adr.lw $t0, 0 ($t1) #loadbne $t0, $s5, EXIT #exit if <>add $s3, $s3, $s4 #i = i + jj LOOPEXIT: ...

Istruzione SLT

Istruzione imposta ad 1 se minore (set on - less than)

Esempio - slt $8, $19,$20

Il registro $8 viene messo ad uno se il valore nel registro $19 è minoredel registro $20

Esempio

slt $1, $10, $11 #$1 = 1 if $10 < $11 bne $1, $0, LESS

Istruzione switch

Esempio di istruzione switch

Riepilogo delle istruzioni

Istruzioni con operandi immediati

Istruzioni con operandi immediati

- addi $29, $29, 4 # $29 = $29 + 4

l‘istruzione di somma ha una costante come operando

- slti $8, $18, 10 $8 = 1 se $18 < 10

permette di fare un controllo immediato per l’istru zione di confronto di minoranza

- lui $16, 61

permette di caricare in un registro i 16 bit più sig nificativi che corrispondonoal numero decimale senza segno 61

Ciclo for

Esempio di ciclo for in C

for (i = 0; i< n ; i = i + 1 ) in C

Codice MIPSInizializzazioneadd $19, $0, $0 # i = 0

Istruzione di incrementoaddi $19, $19, 1 # i = i + 1

Ciclo

for: slt $8, $19, $5 # i l registro $8 = 0 se $19 ≥ $5 (i ≥n)beq $8, $0, exit #salta a exit se $19 ≥ $5 (i ≥n)

….

j for #salta alla condizione del ciclo

exit: …

Procedure

- La procedura è un metodo usato per strutturare i programmi in modo da essere più“leggibile”

- Nel programma una volta eseguita una procedura si ritorna all’istruzione successivaalla sua chiamata

- Il MIPS fornisce un’istruzione che forza il salto ad un indirizzo e simultaneamentesalva quello dell’istruzione successiva nel registro $31 (indirizzo di ritorno)

L’Istruzione salto con collegamento (jump and link, jal):

- jal Indirizzo della procedura

L’istruzione che effettua il rientro dalla chiamata a procedura:

- jr $31

Le due istruzioni sono eseguite usando il Program Counter

Procedure

- Se una procedura a sua volta richiama un’altra procedura si deve salvare il vecchio indirizzo di ritorno $31 in una pila (stack) gestita con una politica di tipo LIFO

- Sulla pila si possono fare le seguenti operazioni:

Push inserire un elemento sulla pila Pop estrarre un elemento in cima alla pila

Esempio

Procedura Swap in C

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

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

}

La procedura swap scambia l’elemento k e l’elemento k+1di un vettore v usando una variabile temporanea

Esempio (Swap in MIPS)

Swap: # Salvataggio registri utilizzati dalla procedura addi $29, $29, -12 #crea lo spazio sulla pila per tre registrisw $2, 0($29) #salva $2 sulla pilasw $15, 4($29) #salva $15 sulla pilasw $16, 8($29) #salva $16 sulla pila# Corpo della proceduramuli $2, $5, 4 #registro $2 = k * 4add $2, $4, $2 #registro $2 = v + (k*4)lw $15, 0($2) # il registro $2 contiene l’indirizzo di v[k]lw $16, 4($2) # $15 = v[k] e $16 = v[k+1]sw $16, 0($2) #v[k] = registro $16sw $15, 4($2) #v[k+1] = registro $15 (temp) # Rispristino dei registrilw $2, 0($29) #rispristina $2 dalla pilalw $15, 4($29) #rispristina $15 dalla pilalw $16, 8($29) #rispristina $16 dalla pilaaddi $29,$29, 12 # ripristina il puntatore alla pila# Ritorno alla procedura chiamante jr $31

Esempio (Sort)

La procedura ordina un vettore di 10000 interi. La procedura richiama la procedura Swap vista in precedenza

Codice C

Int v[10000];Int i,j;

sort (int v[ ], int n ){for (i=0;i<n;i=i+1) {

for(j=i-1; j>=0 && v[j]> v[j+1]; j=j-1) {swap(v,j) }

}}

Esempio (Sort in MIPS)

- I due parametri della procedura sort (v ed n) sono rispettivamente nei registri$4 e $5, mentre $19 e $17 sono destinati a i e j

Procedura in MIPSSort: # Salvataggio dei registri usati successivamente da swap

addi $29, $29, -36 #riserva spazio sulla pila per 9 registrisw $15, 0($29) #salva $15 sulla pilasw $16, 4($29) #salva $16 sulla pilasw $17, 8($29) #salva $17 sulla pilasw $18, 12($29) #salva $18 sulla pilasw $19, 16($29) #salva $19 sulla pilasw $20, 20($29) #salva $20 sulla pilasw $24, 24($29) #salva $24 sulla pilasw $28, 28($29) #salva $28 sulla pilasw $31, 32($29) #salva $31 sulla pila


# Corpo della procedura# I maggiori problemi restano nel passaggio dei parametri alla procedura (v ed n in# $4 e $5). Una soluzione è quella di copiare i parametri per la procedura sort# per renderli disponibili alla procedura swap

# Spostamento parametri move $18, $4 #copia parametro $4 in $18move $20, $5 #copia parametro $5 in $20

# Ciclo più esternoadd $19, $0, $0 # i = 0

for1tst: slt $8, $19, $20 # registro $8 = 0 se $19 ≥ $20 (i ≥n)beq $8, $0, exit1 # salta ad exit1 se $19 ≥ $20 (i ≥n)


# Ciclo più internoaddi $17, $19, -1 #j = i -1for2tst:

slti $8, $17, 0 # registro $8 = 1 se $17 < 0 (j<0)bne $8, $0, exit2 # salta ad exit2 se $17 < 0 (j<0)

muli $15, $17, 4 #registro $15 = j*4add $16, $4, $15 # registro $16 = v + (j*4)lw $24, 0($16) # registro $24 = v[j]lw $25, 4($16) # registro $25 = v[j+1]slt $8, $25, $24 # registro $8 = 0 if $25 ≥ $24beq $8, $0, exit2 # salta ad exit2 se $25 ≥ $24

# Passaggio parametri e chiamata

move $4, $18 #il primo parametro di swap è vmove $5, $17 # il secondo parametro di swap è j jal swap


# Ciclo più internoaddi $17, $17, -1 #j = j -1j for2tst #salta alla condizione del ciclo più interno

# Ciclo più esternoexit2: addi $19, $19, 1 #i = i + 1

j for1tst #salta alla condizione di ciclo più esterno

# Rispristino dei registriexit1: lw $15, 0($29) #ripristina $15 dalla pila

lw $16, 4($29) #rispristina $16 dalla pilalw $17, 8($29) #rispristina $17 dalla pilalw $18, 12($29) #rispristina $18 dalla pilalw $19, 16($29) #rispristina $19 dalla pilalw $20, 20($29) #rispristina $20 dalla pilalw $24, 24($29) #ripristina $24 dalla pilalw $28, 28($29) #ripristina $28 dalla pilalw $31, 32($29) #rispristina $31 dalla pilaaddi $29,$29,36 #ripristina il puntatore alla pila

# Ritorna alla chiamata della procedura jr $31

Allocazione dei registri

GNU MIPS C register allocation-$zero 0 constant 0-$at 1 assembler-$v0 ... $v1 2-3 result value registers-$a0 ... $a3 4-7 arguments-$t0 ... $t7 8-15 temporary variables-$s0 ... $s7 16-23 saved-$t8 ... $t9 24-25 temporary variables-$k0 ... K1 26-27 operating system-$gp 28 global pointer-$sp 29 stack pointer-$fp 30 frame pointer-$ra 31 return address

Esercizio

Procedura sum_minint v[100];int n;n = 100;int sum_min(int v[ ], int n) {

int minimo, j, sum;sum = 0;for (j = 0; j < n; j = j + 1){

sum = sum + v[j]; }

minimo = calc_min(v,n);

operazione = sum – minimo;return operazione

}

Procedura calc_minint calc_min(int v [ ], int n){int k;

min = v[0];for (k = 1; k<n; k = k + 1){

if v[k] < minmin = v[k];

}

return min}

Tradurre nel linguaggio macchina MIPS la procedura sum_min (e la procedura chiamata calc_min) che effettua la somma tutti i valori del vettore v e sottrae alla somma il minimo

Esercizio (soluzione)

Registri usati da sum_min:

$a0 - vettore v$a1 - parametro n$v0 - registro per la variabile di return$t0 - indice j$t1 - variabile sum$t2 - variabile minimo$s0 - registro per copiare $a0$s1 - registro per copiare $a1$t3-$t7 - registri per variabili temporanee$t8-$t9 - registri per variabili temporanee

(load -store)

Registri usati da calc_min:

$a0 - vettore v$a1 - parametro n$v1 - registro per la variabile di return$t0 - indice k$t8 - variabile min$t3-$t7,$t9 - registri per variabili temporanee

(load -store)

È permesso l’uso di:move

Esempio:move $4, $20 # copia nel registro $4 il contenuto del registro $20

Esercizio (soluzione di sum_min)

Salvataggio registrisum_min:

addi $sp, $sp, -36sw $s0, 0($sp)sw $s1, 4($sp)sw $t0, 8($sp)sw $t1, 12($sp)sw $t3, 16($sp)sw $t4, 20($sp)sw $t5, 24($sp)sw $t8, 28($sp)sw $ra, 32($sp)

Corpo della procedura

move $s0, $a0 # copia di $a0 in $s0move $s1, $a1 # copia di $a1 in $a1add $t1, $0, $0 # inizializzazione di sum (sum = 0)add $t0, $0, $0 # inizializzazione di j (j = 0)


Ciclo for

For: slt $t3, $t0, $s1 beq $t3, $0, EXIT # controllo (j < n)muli $t4, $t0, 4 # aggiornamento indice del ciclo ($t4 = j*4)add $t5, $s0, $t4 # $t5 = v + j*4lw $t8, 0($t5) # $t8 = v[j]add $t1, $t1, $t8 # sum = sum + v[j]addi $t0, $t0, 1 # j = j + 1j For # salto alla label For

Opzione EXITEXIT:

move $a0,$s0move $a1, $s1 # copia dei registri usati in calc_minjal calc_min # chiamata alla funzione calc_minadd $v0, $t1, $v1 # calcolo di sum - minimo


Ripristino registri

lw $s0, 0($sp)lw $s1, 4($sp)lw $t0, 8($sp)lw $t1, 12($sp)lw $t3, 16($sp)lw $t4, 20($sp)lw $t5, 24($sp)lw $t8, 28($sp)lw $ra, 32($sp)addi $sp, $sp, 36

jr $ra # ritorno alla procedura chiamante

Esercizio (soluzione di calc_min)

Salvataggio registricalc_min:

addi $sp, $sp, -28sw $t0, 0($sp)sw $t1, 4($sp)sw $t2, 8($sp)sw $t3, 12($sp)sw $t4, 16($sp)sw $t8, 20($sp)sw $t9, 24($sp)sw $ra, 28($sp)

Corpo della procedura

lw $t8, 0($a0) # min = v[0]

addi $t0, $t0, 1 # k = 1


For: slt $t1, $t0, $a1 # k< nbeq $t1, $0, EXIT muli $t2, $t0, 4add $t3, $a0, $t2 # aggiornamento indice klw $t9, 0($t3) # caricamento di v[k]slt $t4, $t9, $t8 # v[k] < minbeq $t4, $0, L1 move $t8, $t9

L1 : addi $t0, $t0, 1j For

EXIT:move $v1, $t8


Ripristino registri

lw $t0, 0($sp)lw $t1, 4($sp)lw $t2, 8($sp)lw $t3, 12($sp)lw $t4, 16($sp)lw $t8, 20($sp)lw $t9, 24($sp)lw $ra, 28($sp)addi $sp, $sp, 28

jr $ra # ritorno alla procedura chiamante

Esercizio (potenza di un numero)

Programma in C per il calcolo della potenza di un numero

int power (int base, int n){

int i, p;i = 0;p = 1;

while (i < n){i = i + 1;p = p * base;

}

}

Esercizio (soluzione)

Salvataggio registrisub $sp, $sp, 12sw $s0, 0($sp) sw $t1, 4($sp) sw $t0, 8($sp)

Corpo del programmaadd $t0, $0, $0addi $s0,$0, 1

LOOP: slt $t1, $t0, $a1 # i>=n esco dal ciclobeq $t1, $0, EXITaddi $t0, $t0, 1 # i=i+1;mul $s0, $s0, $a0 # p=p*base;j LOOP

EXIT:add $v0, $s0, $0 # p nel registro di ritorno

lw $s0, 0($sp)lw $t1, 4($sp)lw $t0, 8($sp)add $sp, $sp, 12jr, $ra

Assumiamo $a0 = base; $a1 = n; $t0 = i ; $t1 = flag; $s0 = p

Ripristino registri

MIPS

Documents

Transcript of MIPS