ISA e Linguaggio Assemby MIPS

Da Wikiversità, l'università aperta.

Indice

[modifica] Architettura MIPS

Microprocessore MIPS R4400 prodotto da Toshiba.

L'architettura MIPS (originariamente acronimo di Microprocessor without Interlocked Pipeline Stages) è un'architettura RISC e load-store sviluppata da John Hennessy nel 1981. l'architettura MIPS sono attualmente usante in molti sistemi enbedded cone nei router Cisco e Fonera, e nelle console per video game come per esempio il Nintendo 64 e la Sony PlayStation, PlayStation 2 e nella PlayStation Portatile.

[modifica] I Registri del MIPS

Il processore MIPS è a 32 bit, ed anche i suoi 32 registri di tipo general purpose sono anchessi a 32 bit.

  • Il registro $0 ritorna sempre il valore 0.
  • Il registro $31 è usato dalla procedura jal per memorizzare l'idirizzo di una procedura o di un salto.
  • HI e LO sono usati per accedere al risultato delle operazioni di moltiplicazione e divisione, e sono accessibili dai comandi mfhi (move from high) e mflo (move from low).
  • Vengono utilizzate delle convenzioni/usi specifici sui noi nomi utilizzati per i registri:
Registers
Name Number Use Callee must preserve?
$zero $0 constant 0 N/A
$at $1 assembler temporary no
$v0–$v1 $2–$3 Values for function returns and expression evaluation no
$a0–$a3 $4–$7 function arguments no
$t0–$t7 $8–$15 temporaries no
$s0–$s7 $16–$23 saved temporaries yes
$t8–$t9 $24–$25 temporaries no
$k0–$k1 $26–$27 reserved for OS kernel no
$gp $28 global pointer yes
$sp $29 stack pointer yes
$fp $30 frame pointer yes
$ra $31 return address N/A

[modifica] Istruzioni MIPS

[modifica] Tabella riassuntiva delle istruzioni

Category Name Instruction syntax Meaning Format/opcode/funct Notes/Encoding
Arithmetic Add add $d,$s,$t $d = $s + $t R 0 2016 adds two registers, executes a trap on overflow
000000ss sssttttt ddddd--- --100000
Add unsigned addu $d,$s,$t $d = $s + $t R 0 2116 as above but ignores an overflow
000000ss sssttttt ddddd--- --100001
Subtract sub $d,$s,$t $d = $s - $t R 0 2216 subtracts two registers, executes a trap on overflow
000000ss sssttttt ddddd--- --100010
Subtract unsigned subu $d,$s,$t $d = $s - $t R 0 2316 as above but ignores an overflow
000000ss sssttttt ddddd000 00100011
Add immediate addi $t,$s,C $t = $s + C (signed) I 816 - Used to add sign-extended constants (and also to copy one register to another "addi $1, $2, 0"), executes a trap on overflow
001000ss sssttttt CCCCCCCC CCCCCCCC
Add immediate unsigned addiu $t,$s,C $t = $s + C (signed) I 916 - as above but ignores an overflow, C still sign-extended
001001ss sssttttt CCCCCCCC CCCCCCCC
Multiply mult $1,$2 LO = (($1 * $2) << 32) >> 32;
HI = ($1 * $2) >> 32;		 R 0 1816 Multiplies two registers and puts the 64-bit result in two special memory spots - LO and HI. Alternatively, one could say the result of this operation is: (int HI,int LO) = (64-bit) $1 * $2 . See mfhi and mflo for accessing LO and HI regs.
Divide div $x, $y LO = $x / $y     HI = $x % $y R 0 1A16 Divides two registers and puts the 32-bit integer result in LO and the remainder in HI.[1]
Divide unsigned divu $x, $y LO = $x / $y     HI = $x % $y R 0 1B16 Divides two registers and puts the 32-bit integer result in LO and the remainder in HI.
Data Transfer Load double word ld $x,C($y) $x = Memory[$y + C] I 2316 - loads the word stored from: MEM[$y+C] and the following 7 bytes to $x and the next register.
Load word lw $x,C($y) $x = Memory[$y + C] I 2316 - loads the word stored from: MEM[$y+C] and the following 3 bytes.
Load halfword lh $x,C($y) $x = Memory[$y + C] (signed) I 2116 - loads the halfword stored from: MEM[$y+C] and the following byte. Sign is extended to width of register.
Load halfword unsigned lhu $x,CONST($y) $x = Memory[$y + C] (unsigned) I 2516 - As above without sign extension.
Load byte lb $x,C($y) $x = Memory[$y + C] (signed) I 2016 - loads the byte stored from: MEM[$y+C].
Load byte unsigned lbu $x,C($y) $x = Memory[$y + C] (unsigned) I 2416 - As above without sign extension.
Store double word sd $x,C($y) Memory[$y + C] = $x I - stores two words from $1 and the next register into: MEM[$y+C] and the following 7 bytes. The order of the operands is a large source of confusion.
Store word sw $x,C($y) Memory[$y + C] = $x I 2B16 - stores a word into: MEM[$y+C] and the following 3 bytes. The order of the operands is a large source of confusion.
Store half sh $x,C($y) Memory[$y + C] = $x I 2916 - stores the first half of a register (a halfword) into: MEM[$y+C] and the following byte.
Store byte sb $x,C($y) Memory[$y + C] = $x I 2816 - stores the first fourth of a register (a byte) into: MEM[$y+C].
Load upper immediate lui $x,C $x = C << 16 I F16 - loads a 16-bit immediate operand into the upper 16-bits of the register specified. Maximum value of constant is 216-1
Move from high mfhi $x $x = HI R 0 1016 Moves a value from HI to a register. Do not use a multiply or a divide instruction within two instructions of mfhi (that action is undefined because of the MIPS pipeline).
Move from low mflo $x $x = LO R 0 1216 Moves a value from LO to a register. Do not use a multiply or a divide instruction within two instructions of mflo (that action is undefined because of the MIPS pipeline).
Move from Control Register mfcZ $x, $y $x = Coprocessor[Z].ControlRegister[$y] R 0 Moves a 4 byte value from Coprocessor Z Control register to a general purpose register. Sign extension.
Move to Control Register mtcZ $x, $y Coprocessor[Z].ControlRegister[$y] = $x R 0 Moves a 4 byte value from a general purpose register to a Coprocessor Z Control register. Sign extension.
Logical And and $d,$s,$t $d = $s & $t R 0 2416 Bitwise and
000000ss sssttttt ddddd--- --100100
And immediate andi $t,$s,C $t = $s & C I 816 - 001100ss sssttttt CCCCCCCC CCCCCCCC
Or or $x,$y,$z $x = $y | $z R 0 2516 Bitwise or
Or immediate ori $x,$y,C $x = $y | C I D16 -
Exclusive or xor $x,$y,$3 $x = $y ^ $z R 0 2616
Nor nor $x,$y,$z $x = ~ ($y | $z) R 0 2716 Bitwise nor
Set on less than slt $x,$y,$z $x = ($y < $z) R 0 2A16 Tests if one register is less than another.
Set on less than immediate slti $x,$y,C $x = ($y < C) I A16 - Tests if one register is less than a constant.
Bitwise Shift Shift left logical sll $x,$y,C $x = $y << C R 0 0 shifts C number of bits to the left (multiplies by 2CONST)
Shift right logical srl $x,$y,C $x = $y >> C R 0 216 shifts CONST number of bits to the right - zeros are shifted in (divides by 2C). Note that this instruction only works as division of a two's complement number if the value is positive.
Shift right arithmetic sra $x,$y,C $x = $y >> C + \
\bigg(\bigg(\sum_{n=1}^{CONST}2^{31-n}\bigg)\cdot $2 >> 31 \bigg) 		R 0 316 shifts C number of bits - the sign bit is shifted in (divides 2's complement number by 2C)
Conditional branch Branch on equal beq $s,$t,C if ($s == $t) go to PC+4+4*C I 416 - Goes to the instruction at the specified address if two registers are equal.
000100ss sssttttt CCCCCCCC CCCCCCCC
Branch on not equal bne $x,$y,C if ($x != $y) go to PC+4+4*C I 516 - Goes to the instruction at the specified address if two registers are not equal.
Unconditional jump Jump j C PC = PC+4[31:28] . C*4 J 216 - Unconditionally jumps to the instruction at the specified address.
Jump register jr $x goto address $x R 0 816 Jumps to the address contained in the specified register
Jump and link jal C $31 = PC + 4; PC = PC+4[31:28] . C*4 J 316 - For procedure call - used to call a subroutine, $31 holds the return address; returning from a subroutine is done by: jr $31

[modifica] Note Sugli Operandi in Memoria

  • Il MIPS indirizza il singolo byte (8 bit)
  • Gli indirizzi delle parole sono multipli di 4, poichè le parole sono composte da 4 byte; quindi gli indirizzi di due parole consecutive differiscono di 4 unità e le parole iniziano sempre ad indirizzi multipli di 4, cioè 0, 4, 8, 12, ...

[modifica] Realizzazione di procedure mediante assembler MIPS

Per eseguire una procedura, devono essere effettuati i seguenti passi:

  1. Il chiamante deve mettere i parametri della procedura in un luogo accessibile alla procedura chiamata,
  2. e deve trasferire il controllo alla procedura chiamata,
  3. la procedura chiamata acquisire le risorse necessarie alla memorizzazione dei dati,
  4. ed esegue il compito richiesto,
  5. Infine mettere il risultato in un luogo accessibile al programma chiamante,
  6. e restituire il controllo al punto di origine.

In particolare per la chiamata di una procedura si utilizza l'apposita istruzione jal (jump-and-link), che salta a un indirizzo e contemporaneamente salva l’indirizzo dell’istruzione successiva nel registro $ra. In pratica jal salva il valore di PC+4 nel registro $ra, che contiene l’indirizzo della prossima istruzione, creando un “collegamento” all’indirizzo di ritorno dalla procedura. L’indirizzo di ritorno è necessario perché la stessa procedura può essere richiamata in più parti del programma.

Mentre per il ritorno da una procedura chiamata viene utilizzata l’istruzione jr(Jump-register), che salta all'indirizzo contenuto in $ra, restituendo il controllo al chiamante.

[modifica] Le convenzioni

Sono necessarie delle convenzioni poichè le procedure dei linguaggi di alto livello possono essere compilate separatamente e anche perchè i programmatori assembler possono implementare/chiamare procedure, realizzate da compilatori o da altri programmatori.

Le principali convenzioni, non imposte dall’hardware ad eccezione di $ra! sono:

  • $a0 - $a3: 4 registri argomento per il passaggio dei parametri.
  • $v0-$v1: 2 registri valore per la restituzione dei valori.
  • $ra: registro di ritorno per tornare al punto di origine.
  • Il programma chiamante mette i valori dei parametri da passare alla procedura nei registri $a0-$a3 e utilizza l’istruzione jal X per saltare alla procedura X.
  • Il programma chiamato esegue le operazioni richieste, memorizza i risultati nei registri $v0-$v1 e restituisce il controllo al chiamante con l’istruzione jr $ra.

[modifica] L’uso dello stack

Spesso, una procedura necessita di salvare i valori di alcuni registri, perché chiama un’altra procedura che li cambia o perché non deve alterarli per il programma chiamante. Come soluzione viene utilizzato lo stack (pila) che è una struttura del tipo last-in first-out dove è possibile memorizzare il valore di un registro, tramite le operazioni dette di Push e recuperare l’ultimo valore inserito con le operazioni di Pop. Per la gestione dello stack si utilizza un puntatore allo stack (stack pointer) che contiene l’indirizzo del dato introdotto più recentemente nello stack.

Lo stack cresce a partire da indirizzi di memoria alti verso indirizzi di memoria bassi, quindi quando vengono inseriti dei dati nello stack il valore dello stack pointer diminuisce, viceversa, quando sono estratti dati dallo stack, il valore dello stack pointer aumenta. Il registro allocato dal MIPS come stack pointer è $sp.

[modifica] Riempimento dello Stack

Per effettuare le operazioni di Push nello stack viene utilizzata l'istruzione sw(store-word).

Esempio: Vogliamo memorizzare nello stack i valori di $t0, $t1, $t2.

  addi $sp, $sp, -12  #Diminuisco il valore dello stack pointer di dodici, facendo spazio per 12/4=3 word.
  sw $t0, 8($sp)      #Carico il valori di $t0 nell'indirizzo $sp+8.
  sw $t1, 4($sp)      #Carico il valori di $t1 nell'indirizzo $sp+4.
  sw $t2, 0($sp)      #Carico il valori di $t2 nell'indirizzo $sp+0.

[modifica] Svuotamento dello stack

Per effettuare le operazioni di Pop nello stack viene incrementato, tramite l'istruzione addi(add-immediate), il registro puntatore $sp di una quantità pari al numero di parole che si vogliono togliere moltiplicato per 4. Nel caso volessimo salvare il contenuto della memoria nei registri viene utilizzata l'istruzione lw(load-word).

Esempio: Vogliamo togliere dallo stack i dati memorizzati nell'esempio precedente.

 addi $sp, $sp, 12  #Aumento il valore dello stack pointer di dodici, rimuovendo dallo stack le prime 12/4=3 parole.

[modifica] Il compito di salvare i registri

Con l'utilizzo delle procedure si può affrontare il problema del compito di salvare i registri in due modi diversi:

  1. Salvataggio da parte del chiamato: la procedura ha la responsabilità di non alterare nessun registro ed il chiamante quindi si aspetta che nessun registro sia modificato. C'è però l'inconveniente che i registri salvati dalla procedura potrebbero non essere usati dal chiamante e quindi vengono quindi salvati e ripristinati inutilmente.
  2. Salvataggio da parte del chiamante: la procedura può alterare qualunque registro ed è compito del chiamante salvare i registri che desidera non siano modificati nello stack. Anche in questo caso si ha un inconveniente, per il quale se la procedura non usa i registri che il chiamante utilizza (ad esempio, usa un solo registro) il chiamante salva inutilmente tutti i registri che usa.

Per ovviare agli incovenienti visti si usa un approccio ibrido mediante specifiche convenzioni che determinano quali registri sono preservati e quali non lo sono; riduce la necessità di salvare registri in memoria.

  • $t0-$t9: registri temporanei che non sono preservati in caso di chiamata di procedura.
  • $s0-$s7: registri che devono essere preservati, se utilizzati devono essere salvati e ripristinati dal programma chiamato.
  • $a0-$a3: registri che non sono preservati.

[modifica] Procedure annidate

La possibilità di avere delle procedure annidate ha come effetto collaterale la possibilità di confilitti. Per esempio nel caso in cui una procedura A chiama un’altra procedura B jal B altera $ra, che serve ad A per ritornare al programma chiamante. Anche in questo caso sono state create delle convenzioni in modo tale che:

  • $ra è un registro preservato.
  • Il programma chiamante memorizza nello stack i registri argomento ($a0 - $a3) o i registri temporanei ($t0 - $t9) di cui ha ancora bisogno dopo la chiamata.
  • Il programma chiamato salva nello stack il registro di ritorno $ra e gli altri registri ($s0 - $s7) che utilizza.

Queste convenzioni garantiscono la correttezza, perché sono applicate “ricorsivamente”. Infatti, sono a prova di ricorsione.

[modifica] Creazione di variabili locali nelle procedure

Le procedure possono definire variabili locali, che sono visibili solo internamente; e che vengono create all’inizio dell’esecuzione della procedura e distrutte al ritorno. Per memorizzare queste variabili locali si usa ancora lo stack.

Questo meccanismo presenta però un ulteriore problema: la dimensione dello stack può cambiare durante l’esecuzione della procedura e quindi diventa difficile riferire una variabile rispetto al registro $sp, poichè si avrebbero diversi offset nel corso del programma. Per ovviare si utilizza quindi un registro, per convenzione $fp(frame-pointer), per riferire l’inizio dello stack frame. Percui all'inizio dell’esecuzione, la procedura deve:

       addi $sp, $sp, -dim    #Creare spazio nello stack per valori da salvare.
                              #Salvare nello stack i valori che serviranno, $fp compreso.
       addi $fp, $sp, dim-4   #Aggiornare $fp.

[modifica] Passaggio di più di 4 parametri

Stack more 4 arguments.jpg

Se ci fosse la necessita di inviare più di 4 parametri essi devono esser posti in cima allo stack dal chiamante, in modo che la procedura chiamata li possa trovare appena sopra $fp.

[modifica] Convenzioni nell’uso della memoria

Mips memory.jpg
  • Il codice macchina MIPS è posto nel segmento text, a partire dall’indirizzo 0040 0000 hex.
  • Il segmento static data è utilizzato dal compilatore per oggetti:
    • la cui lunghezza non varia durante l’esecuzione, ed è conosciuta dal compilatore,
    • che durano per tutta l’esecuzione del programma.
  • Il registro $gp (global pointer) è posto a 1000 8000 hex e può essere utilizzato dall’istruzione lw (con un offset a 16 bit) per accedere al primo blocco di 64K che conterrà le variabili statiche di uso più frequente.
  • Il segmento dynamic data, detto anche heap contiene dati allocati dal programma durante l’esecuzione (es. in C tramite malloc) e quindi può espandersi, verso indirizzi più alti o ritirarsi.
  • Lo stack parte dall’indirizzo 7FFF FFFC hex e si espande verso indirizzi più bassi.

Tutto questo però è in teoria poichè nella realtà ci si riferisce ad uno spazio virtuale.

[modifica] I formati delle istruzioni del MIPS

Il MIPS adotta istruzioni a lunghezza costante di 32 bit, come per le parole di memoria ed i registri. Con 32 bit infatti è possibile esprimere tutte le istruzioni, suddivise in 3 categorie:

  • Istruzioni che devono indicare 3 registri (add, sub, and, slt, ecc.).
  • Istruzioni che devono indicare due registri e una costante, in particolare:
    • lw e sw
    • Istruzioni che riferiscono un operando immediato (addi, andi, ori, ecc.)
    • Salti condizionati (due registri per il confronto + costante per il salto)
  • Istruzioni di salto incondizionato, che non riferiscono alcun registro ma indicano una costante.


[modifica] Formato-R

Il formato-R (register) è utilizzato per istruzioni aritmetiche e logiche.

Formato-R Istruction.jpg
Formato-R Istruction.jpg
  • op: codice operativo
  • rs: primo operando sorgente (registro)
  • rt: secondo operando sorgente (registro)
  • rd: registro destinazione
  • shamt: shift amount (per operazioni di scalamento)
  • funct: seleziona una variante specifica dell’operazione base definita nel campo op. Per esempio: campo funct per le istruzioni add, sub, and, or, slt
                                        ADD:   100 000
                                        SUB:   100 010
                               op = 0   AND:   100 100
                                        OR:    100 101
                                        SLT:   101 010

[modifica] Formato-I

Il formato-I (immediate) è utilizzato per istruzioni di trasferimento, immediate e di branch.

Immagine da inserire

  • rs:
    • nel caso di istruzioni immediate: registro sorgente
    • nel caso di lw e sw: registro base al cui contenuto va sommato address
  • rt:
    • nel caso di istruzioni immediate: registro destinazione
    • nel caso di lw e sw: primo registro che compare nell’istruzione (registro destinazione per lw e registro sorgente per sw)
  • const/address: costante da sommare a 16 bits (-2^15 ... +2^15 -1)

[modifica] Indirizzamento immediato

  • L’operando è una costante.
  • Usato dalle versioni “immediate” delle istruzioni aritmetiche (ad es. addi) che usano due operandi registro (sorgente e destinazione) e un operando immediato.
  • La costante è contenuta nel “immediate” nel formato-I
  • Essendo un intero a 16 bit, ha ancora valori da –2^15 a +2^15-1
  • Nelle versioni “unsigned” delle istruzioni esso viene interpretato come “unsigned” (da 0 a 2^16-1)

[modifica] Indirizzamento tramite base o spiazzamento

  • L’operando è in memoria.

P.es.

         lw       $t1, 32($t0)  # $t0 contiene un indirizzo base
                                # 32 è uno spiazzamento da sommare al contenuto di $t0
  • Lo spiazzamento è espresso come intero con segno a 16 bit, quindi può valere da –2^15 a +(2^15-1)


[modifica] Codifica delle istruzioni di salto condizionato

Anche per le istruzioni beq(Branch-on-equal) e bne(Branch-on-not-equal) si può usare il Formato-I, vediamo subito un semplice esempio:

           bne $s0, $s1, Esci # vai alla etichetta Esci se $s0 è diverso da $s1

Considerando che i campi op, rs ed rt sono rispettivamente di 6 bit il primo e 5 bit gli ultimi due, si hanno a disposizione i rimanenti 16 bit per la codifica dell'etichetta. Se però si codificasse direttamente l’indirizzo con 16 bit nessun programma potrebbe avere dimensioni maggiori di 2^16, per cui si utilizza un indirizzamento relativo al Program-Counter(PC-relative), secondo il quale si specifica un registro da sommare all’indirizzo di salto, quindi il Program Counter sarà pari alla somma del registro e dell' indirizzo di salto. Considerando che normalmente i salti condizionati vengono usati nei cicli e nei costrutti if; i salti sono in genere ad istruzioni vicine, conviene quindi usare il registro PC, che ha l’indirizzo dell’istruzione, successiva a quella corrente. Nonostante questa ultima miglioria si è comunque limitati sulla distanza delle istrazioni dei salti, quindi per sfruttare al meglio i 16 bit a disposizione, si può considerare l’indirizzo in istruzioni, moltiplicando per 4 la costante, effettuando uno shift di due bit; in modo tale che a partire da PC si può saltare fino a una distanza di ±2^15-1 istruzioni rispetto all’istruzione successiva a quella corrente e questo è sufficiente. Questa modalità d'indirizzamento è usato solo nelle istruzioni di salto condizionato, mentre le istruzioni jump e jump-and-link (chiamata di procedure) utilizzano un altro modo di indirizzamento.

[modifica] Formato-J (jump) [per istruzioni di salto incondizionato j e jal]

Queste istruzioni non specificano alcun registro ed i salti della jump e jal non sono in genere “locali”; per cui si ha il bisogno di un formato che permette di specificare una costante con più di 16 bit.

                                       Immagine da inserire

Indirizzamento pseudo-diretto (per i salti incondizionati):

                  j 10000       # vai alla locazione 10000 (espresso come indirizzo di parola)

I 26 bit all’interno dell’istruzione jump contengono un indirizzo in parole, questi 26 bit vengono concatenati con i 4 bit più significativi del PC. L’indirizzo in byte si ottiene poi moltiplicando per 4 (ovvero, concatenando altri due bit 00) per ottenere un indirizzo a 32 bit.

Se l’indirizzo specificato in un salto condizionato è troppo lontano, l’assembler risolve il problema inserendo un salto incondizionato al posto di quello condizionato invertendo la condizione originale per cui l'istruzione

                  beq     $s0, $s1, L1

viene sostituita con

                  bne     $s0, $s1, L2
                  j       L1
               L2:
Icona
Questa voce non è ancora inserita in una categoria.
(vedi anche l'elenco delle voci segnalate da categorizzare, e l'elenco delle voci senza alcuna categoria)


Errore nella funzione Cite: Sono presenti dei marcatori <ref> ma non è stato trovato alcun marcatore <references/>

Estratto da "http://it.wikiversity.org/wiki/ISA_e_Linguaggio_Assemby_MIPS"
Strumenti personali