1 Università di Pavia - corso di Calcolatori Elettronici C code: L1:g = g + A[i]; i = i + j; if (i...

1Università di Pavia - corso di Calcolatori Elettronici

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

MIPS code:

L1: add $t1, $s3, $s3 # $t1 = 2 * i

add $t1, $t1, $t1 # $t1 = 4 * iadd $t1, $t1, $s5 # $t1 = indirizzo di A[i]

lw $t0, 0($t1) # $t0 = A[i]

add $s1, $s1, $t0 # g = g + A[i]

add $s3, $s3, $s4 # i = i + j

bne $s3, $s2, L1 # vai a L1 se i h

Attribuzione dei registri alle variabili:

g = $s1, h = $s2, i = $s3, j = $s4, indirizzo di inizio del vettore A = $s5

Control Loop (addendum 1 alla slide n. 45)


C code: while (save [i] == k)i = i + j;

MIPS code:Loop: add $t1, $s3, $s3 # $t1 = 2 * i

add $t1, $t1, $t1 # $t1 = 4 * i add $t1, $t1, $s6 # $t1 = indirizzo di

save[i]lw $t0, 0($t1) # $t0 = save[i]bne $t0, $s5, Exit # vai a Exit se save[i] kadd $s3, $s3, $s4 # i = i + jj Loop # vai a Loop

Exit:

Attribuzione dei registri alle variabili: i = $s3, j = $s4, k = $s5, indirizzo di inizio del vettore save = $s6

Ciclo While (addendum 2 alla slide n. 45)


Switch (k) slt $t3, $s5, $zero # k <0?case 0: f=i+j; break; bne $t3, $zero, Exitcase 1: f=g+h; break; slt $t3, $s5, $t2 # k >3?case 2: f=g-h; break; beq $t3, $zero, Exitcase 3: f=i-j; break; add $t1, $s5, $s5

add $t1, $t1, $t1 # $t1=4*kadd $t1, $t1, $t4lw $t0, 0($t1)jr $t0 #vai a indir. letto

L0: add $s0, $s3, $s4 #k=0, f=i+jj Exit

L1: add $s0, $s1, $s2 #k=1, f=g+hj Exit

L2: sub $s0, $s1, $s2 #k=2, f=g-hj Exit

L3: sub $s0, $s3, $s4 #k=3, f=i-jExit:

f = $s0, g = $s1, h = $s2, i = $s3, j = $s4, k = $s5; $t2 = 4 ;$t4 =indirizzo tabella etichette

Case/Switch (addendum alla slide n. 47)


int proc (int g, int h, int i, int j)

{ int f;

f=(g+h)-(i+j); proc: addi $sp, $sp, -12 # 3 push

return f; sw $t1, 8($sp)

} sw $t0, 4($sp)

g, h, i, j = $a0…$a3 sw $s0, 0($sp) f = $s0 add $t0, $a0, $a1 # calc. f

add $t1, $a2, $a3

sub $s0, $t0, $t1

add $v0, $s0, $zero # $v0=f

lw $s0, 0($sp) # 3 pop

lw $t0, 4($sp)

lw $t1, 8($sp)

addi $sp, $sp, 12

jr $ra # ritorno

Uso dello stack (addendum 1 alla slide n. 48)

Per convenzione:

$t0-$t9 temporanei da non salvare

$s0-$s7 da conservare

si potevano risparmiare 2 push/pop


int fatt (int n) fatt: addi $sp, $sp, -8

{ sw $ra, 4($sp)

if (n<1) return(1); sw $a0, 0($sp)

else return(n*fatt(n-1)); slti $t0, $a0, 1

} beq $t0, $zero, L1

addi $v0, $zero, 1 addi $sp, $sp, 8 n = $a0 jr $ra

L1: addi $a0, $a0, -1

jal fatt

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

lw $ra, 4($sp)

addi $sp, $sp, 8

mul $v0, $a0, $v0

jr $ra

Procedure annidate (addendum 2 alla slide n. 48)


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 fatt (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

n = 1


$a0 = n = 0

$ra = JALM+4

$a0 = n = 1

$ra = JALM+4

$a0 = n-1 = 0

$ra = L1+8

1^ esecuzione

2^ esecuzione

Alla 1^ iterazione:salta a L1; a0 = 0; ra=L1+8.

Alla 2^ iterazione:non salta a L1; v0=1 e ritorna a L1+8, dove a0=1; ra=JALM+4; v0*1=v0 e ritorna al main.


Esempi di esecuzione al variare di n:

n = 2


$a0 = n = 2

$ra = JALM+4

$a0 = n-1 = 1

$ra = L1+8

1^ esecuzione

2^ esecuzione

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.

$a0 = n-2 = 0

$ra = L1+8 3^ esecuzione



fatt.

Salva indirizzo di ritorno e valore a0

nello stack

a0<1

v0=1 dec a0

Preleva a0

Ritorno all’ultima chiamata

effettuata (2 casi: n-1 volte si ritorna alla routine fatt.

all’indirizzo L1+8 e si preleva a0

dallo stack, solo l’ultima si torna

al main (JALM+4)) e si aggiorna SP

v0=a0*v0

Richiamo fatt

Ritorno

Ultima iterazione Iter. intermedie

sì no

Fatto con il ritorno alla routine fatt che aveva chiamato


Fattoriale senza ricorsione (addendum 7 a n. 48)

n nello stack

FATT=1

a0<2

n dallo stackFATT=FATT*a0

a0=a0-1

sì no

ritorno


n = $a0

fatt: addi $sp, $sp, -4 # agg.$SP per salvat. nsw $a0, 0($sp) # salvataggio naddi $v0, $zero, 1 # $v0 = fattoriale =1

Ciclo: slti $t0, $a0, 2 # test per $a0 < 2beq $t0, $zero, L1 # salta se $a0 >= 2lw $a0, 0($sp) # ripristino naddi $sp, $sp, 4 # aggiornamento $SPjr $ra

L1: mul $v0, $a0, $v0 # fatt = fatt * $a0addi $a0, $a0, -1 # $a0 = $a0 -1j Ciclo

Fattoriale senza ricorsione (addendum 8 a n. 48)


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

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

i = i + 1;} strcpy: addi $sp, $sp, -4

sw $s0, 0($sp) # salva $s0 nello stackadd $s0, $zero, $zero # i = 0

L1: add $t1, $a1, $s0 # ind. y[i] in $t1lb $t2, 0($t1) # $t2 = y[i]add $t3, $a0, $s0 # ind. x[i] in $t3sb $t2, 0($t3) # x[i] = y[i]addi $s0, $s0, 1 # i = i + 1bne $t2, $zero, L1 # se y[i] 0 vai a L1lw $s0, 0($sp) # ripristina $s0 dallo stack addi $sp, $sp, 4

jr $ra # ritornoIndirizzo stringa x = $a0; ind. y = $a1; i = $s0

Gestione caratteri (addendum 9 alla slide n. 48)


Pseudo Istruzioni (addendum 1 alla slide n. 57)

• Versioni modificate delle istruzioni vere, trattate dall’assemblatore

• Esempi:Pseudo istruzione: move $t0, $t1 # $t0 = $t1Istruzione vera: add $t0, $zero, $t1

Pseudo istruzione: blt $s1, $s2, LabelIstruzioni vere: slt $at, $s1, $s2

bne $at, $zero, Label

• Altri esempi:

bgt, bge, ble; branch condizionati a locazioni distanti trasformati in un branch e una jump, li, etc.


azz1 (int vett[], int dim){

int i;for (i=0; i<dim; i++)

vett[i] = 0;}azz1: move $t0, $zero # i = 0L1: add $t1, $t0, $t0 # 4 * i

add $t1, $t1, $t1add $t2, $a0, $t1 # $t2 = indirizzo di vett[i]sw $zero, 0($t2) # vett[i] = 0addi $t0, $t0, 1 # i = i + 1slt $t3, $t0, $a1 # i < dim ?bne $t3, $zero, L1 # se i < dim vai a L1jr $ra

Indirizzo vett = $a0, dim = $a1, i = $t0

Vettori e puntatori (addendum 2 alla slide n. 57)


azz2 (int *vett, int dim){ // *p è l’oggetto puntato da p

int *p; // &vett è l’indirizzo di vettfor (p=&vett[0]; p<&vett[dim]; p++)

*p = 0;}azz2: move $t0, $a0 # p = indir vett[0]

add $t1, $a1, $a1 # 4 * dimadd $t1, $t1, $t1add $t2, $a0, $t1 # $t2 = indir di vett[dim]

L2: sw $zero, 0($t0) # mem puntata da p = 0addi $t0, $t0, 4 # p = p + 4slt $t3, $t0, $t2 # p < &vett[dim] ?bne $t3, $zero, L2 # se è vero vai a L2jr $ra

Indirizzo vett = $a0, dim = $a1, p = $t0

Vettori e puntatori (addendum 3 alla slide n. 57)


• Shifts:

shift left logical 8 bit 00000000D 000000D00 sll $t2, $s0, 8

shift right logical 4 bit 000000D00 0000000D0 srl $t2, $s0, 4

• Formato R per l’istruzione sll $t2, $s0, 8 :

000000 00000 10000 01010 01000 000000

op rs rt rd shamt funct

• AND bit a bit $t1=00003C00 $t2=00000D00

AND $t0, $t1, $t2 $t0=00000C00

• OR bit a bit OR $t0, $t1, $t2 $t0=00003D00

Operazioni logiche (addendum 1 alla slide n. 71)


c1 = b0c0 + a0c0 + a0b0 ; c1 = a0b0 + (a0 + b0)c0

c2 = b1c1 + a1c1 + a1b1 ; c2 = a1b1 + (a1 + b1)c1 =

= a1b1 + (a1 + b1) (a0b0 + (a0 + b0)c0)

c3 = b2c2 + a2c2 + a2b2; c3 = a2b2 + (a2 + b2)c2 =

= a2b2 + (a2 + b2)c2 = a2b2 + (a2 + b2) (a1b1 + (a1 + b1) (a0b0

+ (a0 + b0)c0))

c1 = g0 + p0c0

c2 = g1 + p1c1; c2 = g1 + p1 (g0 + p0c0) = g1 + p1g0 + p1p0c0

c3 = g2 + p2c2; c3 = g2 + p2(g1 + p1g0 + p1p0c0) =

= g2 + p2g1 + p2p1g0 + p2p1p0c0

c4 = g3 + p3c3; c4 = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0

CLA: propaga e genera (addendum 1 alla slide n. 84)


Realizziamo un “super” sommatore a 4 bit (CLA a 4 bit).

I “super” segnali “propaga” Pi sono dati da:

P0 = p3 p2 p1 p0; P1 = p7 p6 p5 p4

P2 = p11 p10 p9 p8; P3 = p15 p14 p13 p12

I “super” segnali “genera” Gi sono dati da:

G0 = g3 + p3g2 + p3p2g1 + p3p2p1g0

G1 = g7 + p7g6 + p7p6g5 + p7p6p5g4

G2 = g11 + p11g10 + p11p10g9 + p11p10p9g8

G3 = g15 + p15g14 + p15p14g13 + p15p14p13g12

CLA a 4 bit (addendum 2 alla slide n. 84)


I riporti in ingresso ai 4 CLA del sommatore a 16 bit sono simili ai riporti in uscita da ciascun bit del sommatore a 4 bit c1, c2, c3, c4

C1 = G0 + P0c0

C2 = G1 + P1G0 + P1P0c0

C3 = G2 + P2G1 + P2P1G0 + P2P1P0c0

C4 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0c0

CLA a 4 bit (addendum 3 alla slide n. 84)


Hp. = tempo di risposta di AND e OR Sia Ttot = # porte del cammino più lungo *

RCA Ttot = 16 * 2

CLA Ttot = tempo per produrre C4

2 per produrre C4 a partire da Gi, Pi e c0;

2 per Gi a partire da gi e pi, 1 per Pi da pi;

1 per gi e pi a partire da ai e bi

Ttot = 5

Per 16 bit CLA è 6 volte più veloce di RCA

Velocità RCA e CLA a 16 bit (addendum 1 alla slide n. 85)


Registri e istruzioni in virgola mobile del MIPS (addendum 1 alla slide n. 91)

Registri Commento

$f0, $f1, $f2, … $f31 In doppia precisione un registro corrisponde ad una

coppia pari e dispari, identificato dal nome del

registro pari

ISTRUZIONI ARITMETICHE

Singola precisione Doppia precisione

add.s $f1, $f2, $f3 add.d $f0, $f2, $f4

sub.s $f1, $f2, $f3 sub.d $f0, $f2, $f4

mul.s $f1, $f2, $f3 mul.d $f0, $f2, $f4

div.s $f1, $f2, $f3 div.d $f0, $f2, $f4


Istruzioni in virgola mobile del MIPS (addendum 2 alla slide n. 91)

ISTRUZIONI DI TRASFERIMENTO DATI

lwc1 $f1, 100 ($s2) swc1 $f1, 100 ($s2)

ISTRUZIONI COMPARE (x = eq, ne, lt, le, gt, ge)

c.x.s $f1, $f4 c.x.d $f2, $f4

ISTRUZIONI DI SALTO

bc1t 25 Branch on FP true

bc1f 25 Branch on FP false


Numeri in virgola mobile secondo lo standard IEEE 754 (addendum 1 alla slide n. 92)

Singola Precisione Doppia Precisione

Oggetto rappres.

Exp. Mantissa Exp. Mantissa

0 0 0 0 0

0 # 0 0 # 0 Sub-number

1254 # 12046 # #normalizzato

255 0 2047 0 +/-

255 # 0 2047 # 0 NaN (Not a Number)

1 Università di Pavia - corso di Calcolatori Elettronici C code: L1:g = g + A[i]; i = i + j; if (i...

Documents

Transcript of 1 Università di Pavia - corso di Calcolatori Elettronici C code: L1:g = g + A[i]; i = i + j; if (i...