Post on 21-Feb-2019
transcript
1Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Istruzioni: linguaggio macchina
2Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Instructions
• Language of the Machine
• More primitive than higher level languagese.g., no sophisticated control flow
• Very restrictivee.g., MIPS Arithmetic Instructions
• We’ll be working with the MIPS instruction set architecture
– similar to other architectures developed since the 1980's
– used by NEC, Nintendo, Silicon Graphics, Sony
Design goals: maximize performance and minimize cost, reduce design time
3Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
MIPS arithmetic
• All instructions have 3 operands
• Operand order is fixed (destination first)
Example:
C code: A = B + C
MIPS code: add $s0, $s1, $s2
(associated with variables by compiler)
4Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
MIPS arithmetic
• Design Principle: simplicity favors regularity. Why?
• Of course this complicates some things...
C code: A = B + C + D;
E = F - A;
MIPS code: add $t0, $s1, $s2
add $s0, $t0, $s3
sub $s4, $s5, $s0
Hp: A→ $s0, B→ $s1, C→ $s2, D→ $s3, E→ $s4, F→ $s5
• Operands must be registers, only 32 registers provided
• Design Principle: smaller is faster. Why?
5Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Registers vs. Memory
Processor I/O
Control
Datapath
Memory
Input
Output
• Arithmetic instructions operands must be registers, — only 32 32-bit registers provided (word in MIPS architecture)
• Compiler associates variables with registers
• What about programs with lots of variables
6Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Memory Organization
• Viewed as a large, single-dimension array, with an address.
• A memory address is an index into the array
• "Byte addressing" means that the index points to a byte of memory.
0
1
2
3
4
5
6
...
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
7Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Memory Organization
• Bytes are nice, but most data items use larger "words"
• For MIPS, a word is 32 bits or 4 bytes.
• 232 bytes with byte addresses from 0 to 232-1
• 230 words with byte addresses 0, 4, 8, ... 232-4
• Words are alignedi.e., what are the least 2 significant bits of a word address?
0
4
8
12
...
32 bits of data
32 bits of data
32 bits of data
32 bits of data
Registers hold 32 bits of data
8Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Instructions
• Load and store instructions
• Example:
C code: A[8] = h + A[8];
MIPS code: lw $t0, 32($s3)
add $t0, $s2, $t0
sw $t0, 32($s3)
Hp: h→ $s2, indirizzo base di A→ $s3
• Store word has destination last
• Remember arithmetic operands are registers, not memory!
9Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
So far we’ve learned
• MIPS— loading words but addressing bytes— arithmetic on registers only
• Instruction Meaning
add $s1, $s2, $s3 $s1 = $s2 + $s3
sub $s1, $s2, $s3 $s1 = $s2 – $s3
lw $s1, 100($s2) $s1 = Memory[$s2+100]
sw $s1, 100($s2) Memory[$s2+100] = $s1
10Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Instructions, like registers and words of data, are also 32 bits long
– Example: add $t0, $s1, $s2
– registers have numbers, $t0=8, $s1=17, $s2=18
• Instruction Format:
000000 10001 10010 01000 00000 100000
op rs rt rd shamt funct
• Can you guess what the field names stand for?
Machine Language
11Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Consider the load-word and store-word instructions,
– What would the regularity principle have us do?
– New principle: Good design demands a compromise
• Introduce a new type of instruction format
– I-type for data transfer instructions
– other format was R-type for register
• Example: lw $t0, 32($s2)
35 18 8 32
op rs rt 16 bit number
• Where's the compromise?
Machine Language
12Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Instructions are bits
• Programs are stored in memory — to be read or written just like data
• Fetch & Execute Cycle
– Instructions are fetched and put into a special register
– Bits in the register "control" the subsequent actions
– Fetch the “next” instruction and continue
Processor Memory memory for data, programs,
compilers, editors, etc.
Stored Program Concept
13Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Decision making instructions
– alter the control flow,
– i.e., change the "next" instruction to be executed
• MIPS conditional branch instructions:
bne $t0, $t1, Label beq $t0, $t1, Label
• Example: if (i==j) h = i + j;
bne $s0, $s1, Labeladd $s3, $s0, $s1
Label: ....
Hp: i→ $s0, j→ $s1, h→ $s3
Control
14Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• MIPS unconditional branch instructions:j label
• Example:
if (i!=j) beq $s4, $s5, Lab1
h=i+j; add $s3, $s4, $s5
else j Lab2
h=i-j; Lab1: sub $s3, $s4, $s5
Lab2: ...
Hp: h→ $s3, i→ $s4, j→ $s5
• Can you build a simple for loop?
Control if…then…else
15Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• E’ importante disporre di un’istruzione per iterare:
• Esempio:
Loop:g=g+A[i]; Loop: add $t1, $s3, $s3
i=i+j; add $t1, $t1, $t1
if (i≠h) goto Loop add $t1, $t1, $s5
lw $t0, 0($t1)
add $s1, $s1, $t0
add $s3, $s3, $s4
bne $s3, $s2, Loop
Hp: g→ $s1, h→ $s2, i→ $s3, j→ $s4, A→ $s5,
Control Loops
BASIC
BLOCK
16Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
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 * i
add $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
17Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Più comodo disporre di un’istruzione while che ciclare con goto:
• Esempio:
while (save [i] ==k) Loop: add $t1, $s3, $s3
i=i+j; add $t1, $t1, $t1
add $t1, $t1, $s6
lw $t0, 0($t1)
bne $t0, $s5, Exit
add $s3, $s3, $s4
j Loop
Exit: ……..
Hp: i→ $s3, j→ $s4, k→ $s5, save → $s6
Control While loop
18Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
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] ≠ k
add $s3, $s3, $s4 # i = i + j
j 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
19Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• We have: beq, bne, what about Branch-if-less-than?
• New instruction:if $s1 < $s2 then
$t0 = 1
slt $t0, $s1, $s2 else
$t0 = 0
• Can use this instruction to build "blt $s1, $s2, Label"
— can now build general control structures
• Note that the assembler needs a register to do this,— there are policy of use conventions for registers
• bne $t0, $zero, less
• slt+bne = branch on less (less complicated than a specific instruction)
Control Flow
20Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Selezione tra diverse alternative a seconda del valore di una variabile: anziché n if…then…else, una tabella indicizzata (jump address table) contenente indirizzi che corrispondono a etichette nel codice
• jr salto incondizionato a un registro
• switch(k) slt $t3, $s5, $zero
case 0 f=i+j;break; bne $t3, $zero, Exit
case 1 f=g+h;break; slt $t3, $s5, $t2
case 2 f=g-h;break; beq $t3, $zero, Exit
case 3 f=i-j;break; add $t1, $s5, $s5
add $t1, $t1, $t1
add $t1, $t1, $t4
lw $t0, 0($t1)
jr $t0
L0: add $s0, $s3, $s4; j Exit
L1: add $s0, $s1, $s2; j Exit
L2: sub $s0, $s1, $s2; j Exit
L3: sub $s0, $s3, $s4; j Exit
Exit: ……..
Hp: f→ $s0, g→ $s1, h→ $s2, i→ $s3, j→ $s4, k→ $s5, 4→ $t2, indirizzo tabella→ $t4
Control Case/Switch
21Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Switch (k) { slt $t3, $s5, $zero # k <0?
case 0: f=i+j; break; bne $t3, $zero, Exit
case 1: f=g+h; break; slt $t3, $s5, $t2 # k >3?
case 2: f=g-h; break; beq $t3, $zero, Exit
case 3: f=i-j; break; add $t1, $s5, $s5
} add $t1, $t1, $t1 # $t1=4*kadd $t1, $t1, $t4
lw $t0, 0($t1)
jr $t0 #vai a indir. letto
L0: add $s0, $s3, $s4 #k=0, f=i+j
j Exit
L1: add $s0, $s1, $s2 #k=1, f=g+h
j Exit
L2: sub $s0, $s1, $s2 #k=2, f=g-h
j Exit
L3: sub $s0, $s3, $s4 #k=3, f=i-j
Exit:
f = $s0, g = $s1, h = $s2, i = $s3, j = $s4, k = $s5; $t2 = 4; $t4 =indirizzo tabella etichette
Case/Switch
22Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
So far
• Instruction Meaning
add $s1,$s2,$s3 $s1 = $s2 + $s3
sub $s1,$s2,$s3 $s1 = $s2 – $s3
lw $s1,100($s2) $s1 = Memory[$s2+100]
sw $s1,100($s2) Memory[$s2+100] = $s1
bne $s4,$s5,L Next instr. is at Label if $s4 ≠ $s5
beq $s4,$s5,L Next instr. is at Label if $s4 = $s5
j Label Next instr. is at Label
• Formats:
op rs rt rd shamt funct
op rs rt 16 bit address
op 26 bit address
R
I
J
23Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Policy of Use Conventions
Name Register number Usage
$zero 0 the constant value 0
$v0-$v1 2-3 values for results and expression evaluation
$a0-$a3 4-7 arguments
$t0-$t7 8-15 temporaries
$s0-$s7 16-23 saved
$t8-$t9 24-25 more temporaries
$gp 28 global pointer
$sp 29 stack pointer
$fp 30 frame pointer
$ra 31 return address
24Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• $sp=registro stack pointer: punta all’ultima locazione occupata dello stack
• N.B. indirizzi crescenti verso l’alto: push⇒sp-4, pop ⇒sp+4
• int proc(int g, int h, int i, int j) sub $sp, $sp, 12
{ int f; sw $t1, 8($sp)
f=(g+h)+(i+j); sw $t0, 4($sp)
return(f); sw $s0, 0($sp)
add $t0, $a0, $a1
}
g, h, i, j → $a0…$a3 add $t1, $a2, $a3
f → $s0 add $s0, $t0, $t1
add $v0, $s0, $zero
lw $s0, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
add $sp, $sp, 12
jr $ra
Uso dello stack: procedure foglia
Per convenzione:
$t0-$t9 temporanei da non salvare
$s0-$s7 da conservare
si potevano risparmiare 2 push/pop
25Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
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
26Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Pb: procedure che ne chiamano altre ⇒conflitto nel passaggio parametri?
• Sol.: uso dello stack: chiamante salva $a0-$a3 o $t0-$t9 usati dal chiamato;
chiamato salva $ra e $s0-$s7 usati dal chiamante.
int fact(int n) fact sub $sp, $sp, 8
{ sw $ra, 4($sp)
if n<1 return(1); sw $a0, 0($sp)
else return(n•fact(n-1)); slt $t0, $a0, 1
} beq $t0, $zero, L1
add $v0, $zero, 1
add $sp, $sp, 8
n→$a0 jr $ra
L1: sub $a0, $a0, 1
jal fact
lw $a0, 0($sp)
lw $ra, 4($sp)
add $sp, $sp, 8
mult $v0, $a0, $v0
jr $ra
Uso dello stack: procedure annidate
27Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
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
mult $v0, $a0, $v0
jr $ra
Procedure annidate
28Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
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.
Procedure annidate
29Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Esempi di esecuzione al variare di n:
n = 0
n = 1
Procedure annidate
$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=$v0*1 e
ritorna al main.
30Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Esempi di esecuzione al variare di n:
n = 2
Procedure annidate
$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=$v0*1; 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
31Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Procedure annidate
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
32Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Fattoriale senza ricorsione
n nello stack
FATT=1
a0<2
n dallo stackFATT=FATT*a0
a0=a0-1
sì no
ritorno
33Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
n = $a0
fatt: addi $sp, $sp, -4 # agg. $sp per salvat. n
sw $a0, 0($sp) # salvataggio n
addi $v0, $zero, 1 # $v0 = fattoriale = 1
Ciclo: slti $t0, $a0, 2 # test per $a0 < 2
beq $t0, $zero, L1 # salta se $a0 >= 2
lw $a0, 0($sp) # ripristino n
addi $sp, $sp, 4 # aggiornamento $sp
jr $ra
L1: mult $v0, $a0, $v0 # fatt = fatt * $a0
addi $a0, $a0, -1 # $a0 = $a0 -1
j Ciclo
Fattoriale senza ricorsione
34Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Esempio: variabili non memorizzabili in registri (array, strutture)
• procedure frame/activation record: segmento stack contenente registri salvati e variabili locali
• $fp= frame pointer (puntatore all’inizio del frame, comodo perché è un base register stabile nel frame, mentre $sp può cambiare)
Uso stack per variabili locali alle procedure
$fp
$sp
$a0-$a3
$ra
$s0…$s7
Local var.
$fp
$sp
$fp
$sp
N.B. Se si passano più di 4 parametri, i primi in $a0-$a3, gli altri direttamente nello stack
35Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
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 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
Indirizzo stringa x = $a0; ind. Y = $a1; i = $s0
Gestione caratteri
36Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Another example
• Can we figure out the code?
swap(int v[], int k);
{ int temp;
temp = v[k]
v[k] = v[k+1];
v[k+1] = temp;
} swap: add $t1, $a1, $a1
add $t1, $t1, $t1
add $t1, $a0, $t1
lw $t0, 0($t1)
lw $t2, 4($t1)
sw $t2, 0($t1)
sw $t0, 4($t1)
jr $ra
37Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Small constants are used quite frequently (50% of operands) e.g., A = A + 5;
B = B + 1;C = C - 18;
• Solutions? Why not?
– put 'typical constants' in memory and load them.
– create hard-wired registers (like $zero) for constants like one.
• MIPS Instructions:
addi $sp, $sp, 4
slti $t0, $s3, 10
andi $sp, $sp, 6
ori $sp, $sp, 4
• How do we make this work?
Constants
38Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• We'd like to be able to load a 32 bit constant into a register
• Must use two instructions, new "load upper immediate" instruction
lui $t0, 1010101010101010
• Then must get the lower order bits right, i.e.,
ori $t0, $t0, 1010101010101010
1010101010101010 0000000000000000
0000000000000000 1010101010101010
1010101010101010 1010101010101010
ori
1010101010101010 0000000000000000
filled with zeros
How about larger constants?
39Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Assembly provides convenient symbolic representation
– much easier than writing down numbers
– e.g., destination first
• Machine language is the underlying reality
– e.g., destination is no longer first
• Assembly can provide 'pseudoinstructions'
– e.g., “move $t0, $t1” exists only in Assembly
– would be implemented using “add $t0,$t1,$zero”
• When considering performance you should count real instructions
Assembly Language vs. Machine Language
40Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Pseudo Istruzioni
• 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.
41Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Things we are not going to coversupport for procedureslinkers, loaders, memory layoutstacks, frames, recursionmanipulating strings and pointersinterrupts and exceptionssystem calls and conventions
• Some of these we'll talk about later
• We've focused on architectural issues
– basics of MIPS assembly language and machine code
– we’ll build a processor to execute these instructions.
Other Issues
42Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• simple instructions all 32 bits wide
• very structured, no unnecessary baggage
• only three instruction formats
• rely on compiler to achieve performance— what are the compiler's goals?
• help compiler where we can
op rs rt rd shamt funct
op rs rt 16 bit address
op 26 bit address
R
I
J
Overview of MIPS
43Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Instructions:
bne $t4,$t5,Label Next instruction is at Label if $t4 ≠ $t5
beq $t4,$t5,Label Next instruction is at Label if $t4 = $t5
j Label Next instruction is at Label
• Formats:
• Addresses are not 32 bits — How do we handle this with load and store instructions?
op rs rt 16 bit address
op 26 bit address
I
J
Addresses in Branches and Jumps
44Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Instructions:
bne $t4,$t5,Label Next instruction is at Label if $t4≠$t5
beq $t4,$t5,Label Next instruction is at Label if $t4=$t5
• Formats:
• Could specify a register (like lw and sw) and add it to address
– use Instruction Address Register (PC = program counter)
– most branches are local (principle of locality)
• Jump instructions just use high order bits of PC
– address boundaries of 256 MB
op rs rt 16 bit addressI
Addresses in Branches
45Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
To summarize
MIPS operands
Name Example Comments
$s0-$s7, $t0-$t9, $zero, Fast locations for data. In MIPS, data must be in registers to perform
32 registers $a0-$a3, $v0-$v1, $gp, arithmetic. MIPS register $zero always equals 0. Register $at is
$fp, $sp, $ra, $at reserved for the assembler to handle large constants.
Memory[0], Accessed only by data transfer instructions. MIPS uses byte addresses, so
230
memory Memory[4], ..., sequential words differ by 4. Memory holds data structures, such as arrays,
words Memory[4294967292] and spilled registers, such as those saved on procedure calls.
MIPS assembly language
Category Instruction Example Meaning Commentsadd add $s1, $s2, $s3 $s1 = $s2 + $s3 Three operands; data in registers
Arithmetic subtract sub $s1, $s2, $s3 $s1 = $s2 - $s3 Three operands; data in registers
add immediate addi $s1, $s2, 100 $s1 = $s2 + 100 Used to add constants
load word lw $s1, 100($s2) $s1 = Memory[$s2 + 100] Word from memory to register
store word sw $s1, 100($s2) Memory[$s2 + 100] = $s1 Word from register to memory
Data transfer load byte lb $s1, 100($s2) $s1 = Memory[$s2 + 100] Byte from memory to register
store byte sb $s1, 100($s2) Memory[$s2 + 100] = $s1 Byte from register to memory
load upper immediate lui $s1, 100$s1 = 100 * 2
16 Loads constant in upper 16 bits
branch on equal beq $s1, $s2, 25 if ($s1 == $s2) go to
PC + 4 + 100
Equal test; PC-relative branch
Conditional
branch on not equal bne $s1, $s2, 25 if ($s1 != $s2) go to
PC + 4 + 100
Not equal test; PC-relative
branch set on less than slt $s1, $s2, $s3 if ($s2 < $s3) $s1 = 1;
else $s1 = 0
Compare less than; for beq, bne
set less than
immediate
slti $s1, $s2, 100 if ($s2 < 100) $s1 = 1;
else $s1 = 0
Compare less than constant
jump j 2500 go to 10000 Jump to target address
Uncondi- jump register jr $ra go to $ra For switch, procedure return
tional jump jump and link jal 2500 $ra = PC + 4; go to 10000 For procedure call
46Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Modi di indirizzamento
Register addressing operando = registro
Base addressing operando = cost($reg)
Immediate addressing operando = costante
PC relative addressing operando = PC+cost.
Pseudodirect addressing operando = 4 bit PC + 26 istr.
47Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Byte Halfword Word
Registers
Memory
Memory
Word
Memory
Word
Register
Register
1. Immediate addressing
2. Register addressing
3. Base addressing
4. PC-relative addressing
5. Pseudodirect addressing
op rs r t
op rs r t
op rs r t
op
op
rs r t
Address
Address
Address
rd . . . funct
Immediate
PC
PC
+
+
48Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Clear1(int array[], int size)
{
int i;
for (i=0; i<size; i++)
array[i]=0;
}
• clear2(int *array, int size)
{
int *p; // *p= oggetto puntato da p
for (p=&array[0]; p< &array[size]; p++) //&...= indirizzo ...
*p=0;
}
Vettori e puntatori
49Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
azz1 (int vett[], int dim)
{
int i;
for (i=0; i<dim; i++)
vett[i] = 0;
}
azz1: move $t0, $zero # i = 0
L1: add $t1, $t0, $t0 # 4 * i
add $t1, $t1, $t1
add $t2, $a0, $t1 # $t2 = indirizzo di vett[i]
sw $zero, 0($t2) # vett[i] = 0
addi $t0, $t0, 1 # i = i + 1
slt $t3, $t0, $a1 # i < dim ?
bne $t3, $zero, L1 # se i < dim vai a L1
jr $ra
Indirizzo vett = $a0, dim = $a1, i = $t0
Vettori e puntatori
50Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
azz2 (int *vett, int dim)
{ // *p è l’oggetto puntato da p
int *p; // &vett è l’indirizzo di vett
for (p=&vett[0]; p<&vett[dim]; p++)
*p = 0;
}
azz2: move $t0, $a0 # p = indir vett[0]
add $t1, $a1, $a1 # 4 * dim
add $t1, $t1, $t1
add $t2, $a0, $t1 # $t2 = indir di vett[dim]
L2: sw $zero, 0($t0) # mem puntata da p = 0
addi $t0, $t0, 4 # p = p + 4
slt $t3, $t0, $t2 # p < &vett[dim] ?
bne $t3, $zero, L2 # se è vero vai a L2
jr $ra
Indirizzo vett = $a0, dim = $a1, p = $t0
Vettori e puntatori
51Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
Clear1 Clear2
move $t0,$zero move $t0,$a0
loop1: add $t1,$t0,$t0 add $t1,$a1,$a1
add $t1,$t1,$t1 add $t1,$t1,$t1
add $t2,$a0,$t1 add $t2,$a0,$t1
sw $zero, 0($t2) loop2: sw $zero,0($t0)
addi $t0,$t0,1 addi $t0,$t0,4
slt $t3, $t0, $a1 slt $t3,$t0,$t2
bne $t3, $zero, loop1 bne $t3,$zero,loop2
Hp. array→$a0, size→$a1, i→$t0 array→$a0, size→$a1, p→$t0
multiply and add all’interno del loop solo incremento di p
guadagno 7 su 4 (1.75)
Vettori e puntatori
52Università degli Studi di Bergamo - corso di Informatica (modulo di Calcolatori Elettronici) – a.a. 2017/2018
• Instruction complexity is only one variable
– lower instruction count vs. higher CPI / lower clock rate
• Design Principles:
– simplicity favors regularity
– smaller is faster
– good design demands compromise
– make the common case fast
• Instruction set architecture
– a very important abstraction indeed!
Summary