Transcript instr

CENG 311
MIPS INTRODUCTION
Instruction Set Architecture
Application
Operating
System
Compiler
CPU
Firmware
Memory I/O system
Digital Design
Circuit Design
Software
Interface Between
HW and SW
Instruction Set
Architecture,
Memory, I/O
Hardware
Levels of Representation
temp = v[k];
High Level Language
Program
v[k] = v[k+1];
v[k+1] = temp;
Compiler
lw $15,
lw $16,
sw$16,
sw$15,
Assembly Language
Program
Assembler
Machine Language
Program
0000
1010
1100
0101
1001
1111
0110
1000
1100
0101
1010
0000
Rd
Machine Interpretation
R egDst
R egWr 5
1111
1001
1000
0110
5
Rs
5
D on’t Care
(Rt)
0101
1100
0000
1010
1000
0110
1001
1111
16
32
busB
32
32
A LU Src
ExtOp
32
Mem Wr
Mux
imm16
MemtoReg
busA
WrEn A dr
D ata In
32
C lk
D ata
Memory
32
Mux
Rw Ra Rb
32 32-bit
R egist ers
A LU ctr
ALU
32
C lk
1010
0000
0101
1100
Rt
Extender
Control Signal
Specification
0110
1000
1111
1001
Mux
busW
0($2)
4($2)
0($2)
4($2)
Computer Architecture?
. . . the attributes of a [computing] system as seen by the
programmer, i.e. the conceptual structure and functional
behavior, as distinct from the organization of the data flows
and controls the logic design, and the physical
implementation.
Amdahl, Blaaw, and Brooks, 1964
SOFTWARE
Requirements for ISA
#include <iostream.h>
main()
{
int *a = new int[100];
int *p = a;
int k;
What primitive operations
do we need?
(i.e., What should be
implemented in hardware?)
for (k = 0; k < 100; k++)
{
*p = k;
p++;
}
cout << "entry 3 = " << a[3] << endl;
}
Design Space of ISA
Five Primary Dimensions
• Operations
• Number of explicit operands
• Operand Storage
• Memory Address
• Type & Size of Operands
add, sub, mul, . . .
How is it specified?
( 0, 1, 2, 3 )
Where besides memory?
How is memory location
specified?
byte, int, float, vector, . . .
How is it specified?
Other Aspects
•
•
•
•
Successor instruction
Conditions
Encoding
Parallelism
How is it specified?
How are they determined?
Fixed or variable? Wide?
Basic ISA Classes
Accumulator:
1 address
1+x address
add A
addx A
acc acc + mem[A]
acc acc + mem[A + x]
add
tos tos + next (JAVA VM)
Stack:
0 address
General Purpose Register:
2 address
3 address
add A B
add A B C
A A + B
A B + C
add Ra Rb Rc
load Ra Rb
store Ra Rb
Ra Rb + Rc
Ra mem[Rb]
mem[Rb] Ra
Load/Store:
3 address
Accumulator
Instruction set: Accumulator is implicit operand
one explicit operand
add, sub, mult, div, . . .
clear
Example: a*b - (a+c*b)
clear
0
add c
2
mult b
6
a
4
add a
10
b
3
time
c
st tmp
10
2
tmp
clear
0
add a
4
mult b
12
sub tmp
2
9 instructions

Stack Machines
Instruction set:
add, sub, mult, div . . . Top of stack (TOS) and TOS+1 are
implicit
push A, pop A TOS is implicit operand, one explicit operand
Example: a*b - (a+c*b)
push a
time
push b
mult
C
-+*
C*B
B
A
B
+*
A
A*B
push a
A
A*B
A*B
A
C
A
A*B
A
A*B
push c
A*B
push b
mult
add
+
*
sub
*
a
a
b
9 instructions

c
b
2-address ISA
Instruction set: Two explicit operands, one implicit
add, sub, mult, div, …
one source operand is also destination
add a,b a <- a + b
Example: a*b - (a+c*b)

add tmp1, b
mult tmp1, c
add tmp1, a
add tmp2, b
mult tmp2, a
sub tmp2, tmp1
6 instructions
tmp1, tmp2
3, ?
6, ?
10, ?
10, 3
10, 12
10, 2
a
b
c
tmp1
tmp2
4
3
2
3-address ISA

Instruction set: Three explicit operands, ZERO implicit
add, sub, mult, div, …
add a,b,c a <- b + c
Example: a*b - (a+c*b)
mult tmp1, b, c
add tmp1, tmp1, a
mult tmp2, a, b
sub tmp2, tmp2, tmp1
4 instructions
tmp1, tmp2
6, ?
10, ?
10, 12
10, 2
a
b
c
tmp1
tmp2
4
3
2
Adding Registers to an ISA



A place to hold values that can be named within the
instruction
Like memory, but much smaller
Byte
Address Data
 32-128 locations
0 00110110
1 00001100
How many bits to specify a register?
2
3
4
r0
r31
•
•
•
2n-1-4
2n-1
3-address General Purpose Register ISA

Instruction set: Three explicit operands, ZERO implicit
add, sub, mult, div, …
add a,b,c a <- b + c
Example: a*b - (a+c*b)
mult r1, b, c
add r1, r1, a
mult r2, a, b
sub r2, r2, r1
4 instructions
r1, r2
6, ?
10, ?
10, 12
10, 2
a
b
c
4
3
2
LOAD / STORE ISA

Instruction set:
add, sub, mult, div, … only on operands in
registers
ld, st, to move data from and to memory, only
way to access memory
Example: a*b - (a+c*b)
ld r1, c
ld r2, b
mult r1, r1, r2
ld r3, a
add r1, r1, r3
mult r2, r2, r3
sub r3, r2, r1
7 instructions
r1, r2, r3
2, ?, ?
2, 3, ?
6, 3, ?
6, 3, 4
10, 3, 4
10, 12, 4
10, 12, 2
a
b
c
4
3
2
Using Registers to Access Memory

Registers can hold memory addresses
Given
int x; int *p;
p = &x;
*p = *p + 8;
Instructions
ld r1, p
ld r2, 0(r1)
add r2, r2, 0x8
st r2, 0(r1)

// r1 <- p
// r2 <- mem[r1]
// increment x by 8
// mem[r1] <- r2
Many different ways to address operands
 not all Instruction sets include all modes
x 0x26cf0
...
p 0x26d00 0x26cbf0
Making Instructions Machine Readable





So far, still too abstract
 add r1, r2, r3
Need to specify instructions in machine readable form
Bunch of Bits
Instructions are bits with well defined fields
 Like a floating point number has different fields
Instruction Format
 Establishes a mapping from “instruction” to binary
values
 Which bit positions correspond to which parts of the
instruction (operation, operands, etc.)
A "Typical" RISC




32-bit fixed format instruction (3 formats)
32 64-bit GPR (R0 contains zero)
3-address, reg-reg arithmetic instruction
Single address mode for load/store:
base + displacement
 no indirection
see: SPARC, MIPS, MC88100, AMD2900, i960, i860
PARISC, PowerPC, DEC Alpha, Clipper,
CDC 6600, CDC 7600, Cray-1, Cray-2, Cray-3
Example: MIPS
Register-Register
31
26 25
Op
21 20
Rs1
16 15
Rs2
11 10
6 5
Rd
0
Opx
Register-Immediate
31
26 25
Op
21 20
Rs1
16 15
0
immediate
Rd
Branch
31
26 25
Op
Rs1
21 20
16 15
Rs2/Opx
0
immediate
Jump / Call
31
26 25
Op
0
target
A Program
2n-1
#include <iostream.h>
Stack
main()
{
int *a = new int[100];
int *p = a;
int k;
for (k = 0; k < 100; k++)
{
*p = k;
p++;
}
.cc file
bits
Data
Text
cout << "entry 3 = " << a[3] << endl;
add r,s1,s2
}
0
Reserved
Stored Program Computer

Instructions: a fixed set of built-in operations

Instructions and data are stored in the (same) computer
memory

Fetch Execute Cycle
while (true){
fetch instruction
execute instruction
}
What Must be Specified?
Instruction

Fetch
Instruction

Decode
Operand
Fetch
Execute
Result


Store

Next
Instruction

Instruction Format
 how do we tell what operation to
perform?
Location of operands and result
 where other than memory?
 how many explicit operands?
 how are memory operands located?
 which can or cannot be in memory?
Data type and Size
Operations
 what are supported
Successor instruction
 jumps, conditions, branches
fetch-decode-execute is implicit!
MIPS ISA Categories




Arithmetic
 add, sub, mul, etc
Logical
 and, or, shift
Data Transfer
 load, store
 MIPS is LOAD/STORE architecture
Conditional Branch


implement if,
for, while… statements
Unconditional Jump
 support function calls (procedure or methods calls)
MIPS Instruction Set Architecture




3-Address Load Store Architecture.
Register and Immediate addressing modes for operations.
Immediate and Displacement addressing for Loads and
Stores.
Examples:
add
$1, $2, $3
#
$1 = $2 + $3
addi
$1, $1, 4
#
$1 = $1 + 4
lw
sw
$1, 100 ($2)
$1, 100 ($2)
#
#
$1 = Memory[$2 + 100]
Memory[$2 + 100] = $1
lui
addi
$1, 100
$1, $3, 100
#
#
$1 = 100 << 16
$1 = $3 + 100
MIPS Integer Registers





Registers: fast memory, Integral
part of the CPU.
Programmable storage 232 bytes
31 x 32-bit GPRs (R0 = 0)
32 x 32-bit FP regs (paired DP)
32-bit HI, LO, PC
r0
r1
°
°
°
r31
PC
lo
hi
0
MIPS Instruction Formats
R-type: Register-Register
31
26 25
Op
21 20
Rs
16 15
Rt
Rd
11 10
6 5
shamt
0
func
I-type: Register-Immediate
31
26 25
Op
21 20
Rs
16 15
0
immediate
Rt
J-type: Jump / Call
31
26 25
Op
0
target
Terminology
Op = opcode
Rs, Rt, Rd = register specifier
R Type:
31
26 25
Op
21 20
Rs
op
rs
rt
rd
shmt
func
<OP> rd, rs, rt
16 15
Rt
11 10
Rd
6 5
shmt
0
func
a 6-bit operation code.
a 5-bit source register.
a 5-bit target (source) register.
a 5-bit destination register.
a 5-bit shift amount.
a 6-bit function field.
Operand Addressing: Register direct
Example: ADD $1, $2, $3
op
rs
000000
00010
rt
# $1 = $2 + $3
rd
shmt
00011 00001 00000
func
100000
I-Type <op> rt, rs, immediate
31
26 25
Op
21 20
Rs
16 15
0
Rt
Immediate
Immediate: 16 bit value
Operand Addressing: Register Direct and Immediate
Add Immediate Example
addi $1, $2, -100
# $1 = $2 + (-100)
op
rs
rt
immediate
001000
00010
00001
1111 1111 1001 1100
Rt becomes the destination register!
I-Type <op> rt, rs, immediate
31
26 25
Op
21 20
Rs
16 15
Rt
0
Immediate
Memory
Register
Base+index
+
Register
Load Word Example
lw
$1, 100($2)
# $1 = Mem[$2+100]
op
rs
rt
immediate
010011
00010
00001
0000 0000 0110 0100
Successor Instruction
Instruction
Fetch
Instruction
Decode
Operand
Fetch
Execute
Result
Store
Next
Instruction
main()
{
int x,y,same; // $0 == 0 always
x = 43;
// addi $1, $0,
y = 2;
// addi $2, $0,
same = 0;
// addi $3, $0,
if (x == y)
same = 1;
// execute only if x
// addi $3, $0, 1
}
43
2
0
== y
The Program Counter

Special register (pc) that points to instructions

Contains memory address (like a pointer)
Instruction fetch is



inst = mem[pc]
To fetch next sequential instruction pc

Size of instruction?
= pc + ?
The Program Counter
x = 43; // addi $1, $0, 43
y = 2;
// addi $2, $0, 2
same = 0;
// addi $3, $0, 0
if (x == y)
same = 1; // addi $3, $0, 1 execute if x == y
PC
0x10000
0x10004
0x10008
0x1000c
0x10000
0x10004
0x10008
0x1000c
addi
addi
addi
addi
$1,
$2,
$3,
$3,
$0,
$0,
$0,
$0,
43
2
0
1
Clearly, this is not correct
We cannot always execute both 0x10008 and 0x1000c
I-Type <op> rt, rs, immediate
31
26 25
Op
21 20
Rs
16 15
0
Rt
Immediate
Memory
+
PC
+
4
PC relative addressing
Branch Not Equal Example
bne $1, $2, 100 # If ($1!= $2) goto [PC+4+100]
 +4 because by default we increment for sequential
 more detailed discussion later in semester

op
rs
rt
immediate
000101
00001
00010
0000 0000 0110 0100
The Program Counter
x = 43; // addi $1, $0, 43
y = 2;
// addi $2, $0, 2
if (x == y)
same = 1; // addi $3, $0, $1 execute if x == y
PC
0x10000
0x10004
0x10008
0x1000c
0x10010
Understand branches
0x10000
0x10004
0x10008
0x1000c
0x10010
addi $1, $0, 43
addi $2, $0, 2
addi $3, $0, 0
bne $1, $2, 4
addi $3, $0, 1
Successor Instruction
Instruction
Fetch
Instruction
Decode
Operand
Fetch
Execute
Result
Store
Next
Instruction
int equal(int a1, int a2) {
int tsame;
tsame = 0;
if (a1 == a2)
tsame = 1;
// only if a1 == a2
return(tsame);
}
main()
{
int x,y,same; // r0 == 0 always
x = 43;
// addi $1, $0, 43
y = 2;
// addi $2, $0, 2
same = equal(x,y); // need to call function
// other computation
}
The Program Counter


Branches are limited to
16 bit immediate
Big programs?
x = 43; // addi $1, $0, 43
y = 2;
// addi $2, $0, 2
same = equal(x,y);
0x10000 addi $1, $0, 43
0x10004 addi $2, $0, 2
0x10008 “go execute equal”
0x30408 addi $3, $0, 0
0x3040c beq $1, $2, 8
0x30410 addi $3, $0, 1
“return $3”
J-Type:
31
<op> target
26
Op
Target Address
PC
$31
+
4
Jump and Link Example
jal 0x0fab8
# PC<- 0x0fab8, $31<-PC+4
$31 set as side effect, used for returning, implicit operand
op
Target
000011
00 0000 0000 0011 1110 1010 1110
Please note, The address is a WORD ADDRESS!
R Type:
31
26 25
Op
<OP> rd, rs, rt
21 20
Rs
16 15
Rt
11 10
Rd
6 5
shamt
0
func
Jump Register Example
jr $31
# PC <- $31
op
rs
000000
11111
rt
rd
shmt
00000 00000 00000
func
001000
Instructions for Procedure Call and Return
int equal(int a1, int a2) {
int tsame;
tsame = 0;
if (a1 == a2)
tsame = 1;
return(tsame);
}
main()
{
int x,y,same;
x = 43;
y = 2;
same = equal(x,y);
// other computation
}
0x10000 addi $1, $0, 43
0x10004 addi $2, $0, 2
0x10008 jal 0x30408
??
0x1000c
0x30408
0x3040c
0x30410
0x30414
addi $3, $0, 0
bne $1, $2, 4
addi $3, $0, 1
jr $31
PC
0x10000
0x10004
0x10008
0x30408
0x3040c
0x30410
0x30414
0x1000c
$31
??
??
??
0x1000c
0x1000c
0x1000c
0x1000c
0x1000c
MIPS Arithmetic Instructions
Instruction
Example
Meaning
Comments
add
subtract
add immediate
add unsigned
subtract unsigned
add imm. unsign.
multiply
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
$1 = $2 + $3
$1 = $2 – $3
$1 = $2 + 100
$1 = $2 + $3
$1 = $2 – $3
$1 = $2 + 100
Hi, Lo = $2 x $3
3 operands
3 operands
+ constant
3 operands
3 operands
+ constant
64-bit signed product
Hi, Lo = $2 x $3
Lo = $2 ÷ $3,
Hi = $2 mod $3
Lo = $2 ÷ $3,
Hi = $2 mod $3
$1 = Hi
$1 = Lo
64-bit unsigned product
Lo = quotient,
Hi = remainder
Unsigned quotient
Unsigned remainder
Used to get copy of Hi
Used to get copy of Lo
multiply unsigned multu $2, $3
divide
div $2,$3
divide unsigned
divu $2,$3
Move from Hi
Move from Lo
mfhi $1
mflo $1
Which add for address arithmetic? Which for integers?
MIPS Logical Instructions
Instruction
and
or
xor
nor
and immediate
or immediate
xor immediate
shift left logical
shift right logical
shift right arithm.
shift left logical
shift right logical
shift right arithm.
Example
and $1,$2,$3
or $1,$2,$3
xor $1,$2,$3
nor $1,$2,$3
andi $1,$2,10
ori $1,$2,10
xori $1, $2,10
sll $1,$2,10
srl $1,$2,10
sra $1,$2,10
sllv $1,$2,$3
srlv $1,$2, $3
srav $1,$2, $3
Meaning
$1 = $2 & $3
$1 = $2 | $3
$1 = $2 $3
$1 = ~($2 | $3)
$1 = $2 & 10
$1 = $2 | 10
$1 = ~$2 &~10
$1 = $2 << 10
$1 = $2 >> 10
$1 = $2 >> 10
$1 = $2 << $3
$1 = $2 >> $3
$1 = $2 >> $3
Comment
Bitwise AND
Bitwise OR
Bitwise XOR
Bitwise NOR
Bitwise AND reg, const
Bitwise OR reg, const
Bitwise XOR reg, const
Shift left by constant
Shift right by constant
Shift right (sign extend)
Shift left by var
Shift right by var
Shift right arith. by var
MIPS Data Transfer Instructions
Instruction
SW R3, 500(R4)
SH R3, 502(R2)
SB R2, 41(R3)
Comment
Store word
Store half
Store byte
LW R1, 30(R2)
LH R1, 40(R3)
LHU R1, 40(R3)
LB R1, 40(R3)
LBU R1, 40(R3)
LUI R1, 40
Load word
Load half word
Load half word unsigned
Load byte
Load byte unsigned
Load Upper Immediate (16 bits shifted left by 16)
Why do we need LUI?
LUI
R5
R5
0000 … 0000
MIPS Compare and Branch
Compare and Branch
beq
rs, rt, offset
bne
rs, rt, offset
if R[rs] == R[rt] then PC-relative branch
<>
Compare to zero and Branch
blez
bgtz
rs, offset
rs, offset
bltz
rs, offset
bgez rs, offset
bltzal rs, offset
bgeal rs, offset


if R[rs] <= 0 then PC-relative branch
>
<
>=
if R[rs] < 0 then branch and link (into R 31)
>=
Remaining set of compare and branch take two instructions
Almost all comparisons are against zero!
MIPS jump, branch, compare instructions
Instruction
branch on equal
Example
beq $1,$2,100
branch on not eq. bne $1,$2,100
set on less than
slt $1,$2,$3
set less than imm. slti $1,$2,100
set less than uns. sltu $1,$2,$3
set l. t. imm. uns. sltiu $1,$2,100
jump
j 10000
jump register
jr $31
jump and link
jal 10000
Meaning
if ($1 == $2) go to PC+4+100
Equal test; PC relative branch
if ($1!= $2) go to PC+4+100
Not equal test; PC relative
if ($2 < $3) $1=1; else $1=0
Compare less than; 2’s comp.
if ($2 < 100) $1=1; else $1=0
Compare < constant; 2’s comp.
if ($2 < $3) $1=1; else $1=0
Compare less than; natural numbers
if ($2 < 100) $1=1; else $1=0
Compare < constant; natural numbers
go to 10000
Jump to target address
go to $31
For switch, procedure return
$31 = PC + 4; go to 10000
For procedure call
Signed v.s Unsigned Comparison
R1= 0…00 0000 0000 0000 0001
R2= 0…00 0000 0000 0000 0010
R3= 1…11 1111 1111 1111 1111
 After executing these instructions:
slt r4,r2,r1
slt r5,r3,r1
sltu r6,r2,r1
sltu r7,r3,r1
What are values of registers r4 - r7? Why?
r4 =
; r5 =
; r6 =
; r7 =
;

Multiply / Divide
Start multiply, divide
mult rs, rt
mthi rd
Move to HI or LO
mtlo rd
Registers
HI
LO
Why not Third field for destination?
(Hint: how many clock cycles for multiply or divide vs. add?)
Summary


MIPS has 5 categories of instructions
 Arithmetic, Logical, Data Transfer, Conditional Branch,
Unconditional Jump
3 Instruction Formats: R-type, I-type, J-type.
Next Time
 Assembly Programming
Reading
 Ch. 3, Appendix A
An Example MIPS Program
# Program #1 : (descriptive name)
Programmer: YOUR NAME
# Due Date : Sep. 13, 2002
Course: CS231
# Last Modified: Sep. 12, 2002
Section: 2
#########################################################
# Functional Description: Find the sum of the integers from 1 to N where
# N is a value input from the keyboard.
#########################################################
# Algorithmic Description in Pseudocode:
# main: v0 << value read from the keyboard (syscall 4)
#
if (v0 < = 0 ) stop
#
t0 = 0;
# t0 is used to accumulate the sum
#
While (v0 >= 0) { t0 = t0 + v0; v0 = v0 - 1}
#
Output to monitor syscall(1) << t0; goto main
##########################################################
# Register Usage: $t0 is used to accumulate the sum
#
$v0 the loop counter, counts down to zero
##########################################################
prompt:
result:
bye:
main:
loop:
.data
.asciiz
.asciiz
.asciiz
.globl
.text
li
la
syscall
li
syscall
blez
li
add
addi
bnez
li
la
syscall
li
move
syscall
b
"\n\n Please Input a value for N = "
" The sum of the integers from 1 to N is "
"\n **** Have a good day **** "
main
$v0, 4
$a0, prompt
$v0, 5
$v0, done
$t0, 0
$t0, $t0, $v0
$v0, $v0, -1
$v0, loop
$v0, 4
$a0, result
$v0, 1
$a0, $t0
main
# system call code for print_str
# load address of prompt into a0
# print the prompt message
# system call code for read_int
# reads a value of N into v0
# if ( v0 < = 0 ) go to done
# clear $t0 to zero
# sum of integers in register $t0
# summing in reverse order
# branch to loop if $v0 is != zero
# system call code for print_str
# load address of message into $a0
# print the string
# system call code for print_int
# a0 = $t0
# prints the value in register $a0
done:
li
la
syscall
$v0, 4
$a0, bye
# system call code for print_str
# load address of msg. into $a0
# print the string
li
syscall
$v0, 10
# terminate program
# return control to system
MUST HAVE A BLANK LINE AT THE END OF THE TEXT FILE
Yet Another Example
Write a program that will compute the sum of the even positive values,
minus the odd negative values in an array of words. Stop when a value
of zero is found in the array. For Example:
array:
.word
-29, -30, 75, 34, -2, 90, -11, 98, 1, 0, 76
Pseudo Code for the Algorithm:
$a1 = &array;
$a0 = 0;
loop:
$t0= Mem($a1);
if ($t0 == 0) go to done
$a1 = $a1 + 4;
$t3 = $t0 & 1;
if ($t0 >= 0 & $t3 == 0)
else
if ($t0 < 0 & $t3 != 0)
go to loop
done:
syscall(1) << $a0;
exit
$a0 = $a0 + $t0;
$a0= $a0 - $t0;
Example MIPS Code
Label
array:
Op-Code Dest.
S1,S2
Comments
.data
.word
-29, -30, 75, 34, -2, 90, -11, 98, 1, 0, 76
.text
main:
la
li
$a1,array
$a0, 0
# $a1 = &array
# $a0 = 0
lw
beqz
addi
andi
bnez
bltz
add
b
$t0,0($a1)
$t0, done
$a1, $a1, 4
$t3, $t0, 1
$t3, odd
$t0, loop
$a0, $a0, $t0
loop
# $t0 = Mem($a1)
bgtz
sub
b
$t0, loop
$a0, $a0, $t0
loop
# $a0 = $a0 - $t0
li
syscall
li
syscall
$v0,
1
# Print result syscall(1)
$v0,
10
# exit
loop:
# $a1 = $a1 + 4
# $t3 = LSB of $t0
# branch if odd
# $t2 = $t2 + $t0
odd:
done: