Transcript slides in ppt

CPSC 161
Lecture 3
Prof. L.N. Bhuyan
http://www.cs.ucr.edu/~bhuyan/
.1
1999©UCB
Review of MIPS Instruction Formats
° simple instructions all 32 bits wide
° very structured, no unnecessary baggage
° only three instruction formats
.2
R
op
rs
rt
rd
I
op
rs
rt
16 bit address
J
op
shamt
funct
26 bit address
1999©UCB
MIPS Instructions:
Name
Example
$s0-$s7, $t0-$t9, $zero,
32 registers $a0-$a3, $v0-$v1, $gp,
$fp, $sp, $ra, $at
Memory[0],
30
2
memory Memory[4], ...,
words
Accessed only by data transfer instructions. MIPS uses byte addresses, so
sequential w ords differ by 4. Memory holds data structures, such as arrays,
and spilled registers, such as those saved on procedure calls.
Memory[4294967292]
add
MIPS assembly language
Example
Meaning
add $s1, $s2, $s3
$s1 = $s2 + $s3
Three operands; data in registers
subtract
sub $s1, $s2, $s3
$s1 = $s2 - $s3
Three operands; data in registers
$s1 = $s2 + 100
$s1 = Memory[$s2 + 100]
Memory[$s2 + 100] = $s1
$s1 = Memory[$s2 + 100]
Memory[$s2 + 100] = $s1
Used to add constants
Category
Arithmetic
Comments
Fast locations for data. In MIPS, data must be in registers to perform
arithmetic. MIPS register $zero alw ays equals 0. Register $at is
reserved for the assembler to handle large constants.
Instruction
addi $s1, $s2, 100
lw $s1, 100($s2)
sw $s1, 100($s2)
store word
lb $s1, 100($s2)
load byte
sb $s1, 100($s2)
store byte
load upper immediate lui $s1, 100
add immediate
load word
Data transfer
Conditional
branch
Unconditional jump
.3
$s1 = 100 * 2
16
Comments
Word from memory to register
Word from register to memory
Byte from memory to register
Byte from register to memory
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
branch on not equal
bne
$s1, $s2, 25
if ($s1 != $s2) go to
PC + 4 + 100
Not equal test; PC-relative
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
jump
j
jr
jal
jump register
jump and link
$s1, $s2, 100 if ($s2 < 100) $s1 = 1;
R-format
I- format
I-format
<- R-format
Compare less than constant
else $s1 = 0
2500
$ra
2500
Jump to target address
go to 10000
For switch, procedure return
go to $ra
$ra = PC + 4; go to 10000 For procedure call
<- J-format
<- R-format
<- J-format
1999©UCB
Assembly Operands: Registers
° Naming of 32 MIPS registers:
instead of r0, r1, …, r31, use
• $s0, $s1, … for registers
corresponding to C variables
• $t0, $t1, … for registers
corresponding to temporary variables
• Will explain mapping convention later of
$s0, $s1, … , $t0, $t1, … , to r0, r1, …
° Note: whereas C declares its variables (e.g.,
int fahr), Assembly operands (registers)
are fixed and not declared
.4
1999©UCB
Policy of Use Conventions
Name Register number
$zero
0
$v0-$v1
2-3
$a0-$a3
4-7
$t0-$t7
8-15
$s0-$s7
16-23
$t8-$t9
24-25
$gp
28
$sp
29
$fp
30
$ra
31
.5
Usage
the constant value 0
values for results and expression evaluation
arguments
temporaries
saved
more temporaries
global pointer
stack pointer
frame pointer
return address
1999©UCB
Role of Registers vs. Memory
° What if more variables than registers?
• Compiler tries to keep most frequently used variables in
registers
• Writing less common to memory: spilling
° Why not keep all variables in memory?
• Smaller is faster:
registers are faster than memory
• Registers more versatile:
- MIPS arithmetic instruction can read 2, operate on
them, and write 1 per instruction
- MIPS data transfer only read or write 1 operand per
instruction, and no operation
.6
1999©UCB
Compilation using Registers
°Compile by hand using registers:
f = (g + h) - (i + j);
Register Allocations:
$s1, h: $s2, i: $s3, j: $s4
f: $s0,
g:
°MIPS Instructions:
.7
add $s0,$s1,$s2
# $s0 = g+h
add $t1,$s3,$s4
# $t1 = i+j
sub $s0,$s0,$t1
# f=(g+h)-(i+j)
1999©UCB
MIPS Instruction Encoding
Examples of some Opcodes:
.8
Instruction
Format
Opcode
shamt
funct
Add
R
0
0
32
Sub
R
0
0
34
Shift (by 4)
R
0
4
0
Add (imm)
I
8
n.a
n.a
Lw (load word) I
35
n.a
n.a
Sw (store word) I
43
n.a
n.a
1999©UCB
Data Transfer Instruction: Memory to Reg
° Load: moves data from memory to register
• Syntax:
1) operation name
2) register to be loaded
3) constant and register to access memory
° MIPS name, lw for load word:
• Example:
lw $t0, 8($s3)
Called “offset”
Called “base register”
or “base address register”
or “base address”
.9
1999©UCB
Compilation when Operand is in Memory
Q: Compile by hand using registers:
g = h + A[300]; g:$s1, h:$s2,
$s3:starting (base) address of array A
° Since A[300] is in memory, 1st transfer from memory
to (temporary) register:
lw $t0,300($s3) # Adds 300 to $s3 to
select A[300], puts into $t0
lw $t0,1200($s3) # For byte
addressable machines 300x4
° Next add it to h and place in g
add $s1,$s2,$t0 # $s1= h+A[300]
HW: Compile A[300] = h + A[300]
.10
1999©UCB
Tanslating to MIPS Machine Language
° From the instruction set, Opcode for Lw is 35. Opcode for add
is 0 with funct 32.
° From register assignment table, t0=8, s1=17, s2=18 and s3=19.
° Instruction consists of op=5 bits, rs=5bits, rt=5bits, rd=5bits,
shamt=5bits and funct=6bits for R format and address=16 bits
instead of rd,shamt and funct for I format: total=32 bits
Assembly language lw $t0, 1200($s3) and add $s1,$s2,$t0
translate to:
--------------------------------------------------------------------------op | rs | rt | rd | address/shamt | funct |
35 | 19 | 8 |
0 | 18 | 8 | 17 |
.11
1200
0 |
|
32
|
1999©UCB
Compile with variable index
° What if array index not a constant?
g = h + A[i];
• g:$s1, h:$s2, i:$s4,
$s3:base address of A
° To load A[i] into a register, first turn i into a
byte address; multiply by 4
° How multiply using adds?
• i + i = 2i, 2i + 2i = 4i
add $t1,$s4,$s4 # $t1 = 2*i
add $t1,$t1,$t1 # $t1 = 4*i
.12
1999©UCB
Compile with variable index, con’t
°Next add to base of A:
add $t1,$t1,$s3 #$t1=address of
#A[i] (4*i+$s3)
°Now load A[i] into a temporary register:
lw $t0,0($t1) # Temp $t0 = A[i]
°Finally add to h and put sum in g:
add $s1,$s2,$t0
.13
# g = h + A[i]
1999©UCB
MIPS arithmetic instructions
Instruction
add
subtract
add immediate
add unsigned
subtract unsigned
add imm. unsign.
multiply
multiply unsigned
divide
Example
add $1,$2,$3
sub $1,$2,$3
addi $1,$2,100
addu $1,$2,$3
subu $1,$2,$3
addiu $1,$2,100
mult $2,$3
multu$2,$3
div $2,$3
divide unsigned
divu $2,$3
Move from Hi
Move from Lo
mfhi $1
mflo $1
Meaning
$1 = $2 + $3
$1 = $2 – $3
$1 = $2 + 100
$1 = $2 + $3
$1 = $2 – $3
$1 = $2 + 100
Hi, Lo = $2 x $3
Hi, Lo = $2 x $3
Lo = $2 ÷ $3,
Hi = $2 mod $3
Lo = $2 ÷ $3,
Hi = $2 mod $3
$1 = Hi
$1 = Lo
Comments
3 operands;
3 operands;
+ constant;
3 operands;
3 operands;
+ constant;
64-bit signed product
64-bit unsigned product
Lo = quotient, Hi = remainder
Unsigned quotient & remainder
Used to get copy of Hi
Used to get copy of Lo
Which add for address arithmetic? Which add for integers?
.14
1999©UCB
MIPS logical instructions
Instruction
Example
Meaning
and
and $1,$2,$3 $1 = $2 & $3
3 reg. operands; Logical AND
or
or $1,$2,$3
$1 = $2 | $3
3 reg. operands; Logical OR
xor
xor $1,$2,$3
$1 = $2 $3
3 reg. operands; Logical XOR
nor
nor $1,$2,$3
$1 = ~($2 |$3)
3 reg. operands; Logical NOR
and immediate
andi $1,$2,10 $1 = $2 & 10
Logical AND reg, constant
or immediate
ori $1,$2,10
Logical OR reg, constant
xor immediate
xori $1, $2,10 $1 = ~$2 &~10 Logical XOR reg, constant
shift left logical
sll $1,$2,10
$1 = $2 << 10
Shift left by constant
shift right logical
srl $1,$2,10
$1 = $2 >> 10
Shift right by constant
shift right arithm. sra $1,$2,10
$1 = $2 >> 10
Shift right (sign extend)
shift left logical
sllv $1,$2,$3
$1 = $2 << $3
Shift left by variable
shift right logical
srlv $1,$2, $3 $1 = $2 >> $3
$1 = $2 | 10
shift right arithm. srav $1,$2, $3 $1 = $2 >> $3
.15
Comment
Shift right by variable
Shift right arith. by variable
1999©UCB
MIPS data transfer instructions
Instruction
Comment
SW 500(R4), R3
Store word
SH 502(R2), R3
Store half
SB 41(R3), R2
Store byte
LW R1, 30(R2)
Load word
LH R1, 40(R3)
Load halfword
LHU R1, 40(R3)
Load halfword unsigned
LB R1, 40(R3)
Load byte
LBU R1, 40(R3)
Load byte unsigned
LUI R1, 40
Load Upper Immediate (16 bits shifted left by 16)
LUI
R5
.16
R5
0000 … 0000
1999©UCB
Section 2.6 MIPS decision instructions
°Decision instruction in MIPS:
•beq register1, register2, L1
•beq is “Branch if (registers are) equal”
Same meaning as (using C):
if (register1==register2) go to L1
°Complementary MIPS decision instruction
•bne register1, register2, L1
•bne is “Branch if (registers are) not equal”
Same meaning as (using C):
if (register1!=register2) go to L1
°Called conditional branches
.17
1999©UCB
Compiling C if into MIPS: Summary
°Compile by hand
C if (i == j) f=g+h;
else f=g-h;
Mapping f: $s0, g: $s1,
(true)
i == j
f=g+h
(false)
i == j?
i != j
f=g-h
h: $s2, i: $s3, j: $s4
M
I
P True:
S Exit:
beq $s3,s4, True # branch i==j
sub $s0,$s1,$s2 # f=g-h(false)
j Exit
# go to Exit
add $s0,$s1,$s2
# f=g+h (true)
°Note: Compiler supplies labels, branches not found in HLL code;
often it flips the condition to branch to false part
.18
1999©UCB
Loops in C/Assembly: Summary
Loop:
C
g = g + A[i];
i = i + j;
if (i != h) goto Loop;
(g,h,i,j:$s1,$s2,$s3,$s4 : base of A[]:$s5)
M
I
P
S
.19
Loop: add
add
add
lw
add
add
bne
$t1,$s3,$s3 #$t1= 2*i
$t1,$t1,$t1 #$t1= 4*i
$t1,$t1,$s5 #$t1=addr A
$t1,0($t1) #$t1=A[i]
$s1,$s1,$t1 #g=g+A[i]
$s3,$s3,$s4 #i=i + j
$s3,$s2,Loop# goto Loop
# if i!=h
1999©UCB
Branch Addressing: PC-relative
° Conditional Branch: beq $t0,$t1,label
I
op
6 bits
rs
5 bits
rt
5 bits
address
16 bits
•address just 16 bits (216), program too small!
° Option: always add address to a register
PC = Register + Branch address
• Change register contents => bigger programs
° Which register?
• How use conditional branch? if-else, loops
• Near current instruction => use PC as reg!
• PC-relative addressing (PC+4) +/- 215 words
.20
1999©UCB
Branch Addressing: Jumps, J format
°j label # go to label
• j has only one operand; add format
J
op
6 bits
address
26 bits
• large address allows large programs
• bright idea: address of instruction always
multiple of 4 (instructions always words) => store
number of word, save 2 bits
• Example: j exit # exit = 10000
J
2
2500
• PC = address * 4 + upper 4 bits of old PC
.21
1999©UCB
Branch Addressing: PC-relative Example
Loop: slt $t1,$zero,$a1
beq $t1,$zero,Exit
Set t1=1 if
$zero < $a1
add $t0,$t0,$a0
subi $a1,$a1,1
j
Loop
Exit: add $v0,$t0,$zero
Address
80000
80004
80008
80012
80016
80020
.22
0
4
0
8
2
0
0
9
8
5
8
5
0
4
5
9
8
#
#
#
#
#
#
t1=9,a1=5
no=>Exit
t0=8,a0=4
a1=5
goto Loop
v0=2,t0=8
0
3
0
-1
42
32
20000
0
2
0
32
80020 = 80004 + 4 + 3*4
1999©UCB