Transcript CA-sp06-m06-InstAddr - FAMU

FAMU-FSU College of Engineering
Computer
Architecture
EEL 4713/5764, Spring 2006
Dr. Michael Frank
Module #6 – MIPS ISA, part 1:
Instructions and Addressing
1
Course Instructional Objectives #2&3
As the syllabus says:


At the completion of this course, students should be able to…
CIO #2 (ao). (AsmML) Derive machine code from assembly instructions.
CIO #3 (aco). (CAsm) Derive assembler code from an equivalent C code representation
These CIOs relate to following Program Outcomes:


Students graduating from the BSEE and BSCpE degree programs will have:
PO (a). (Apply) An ability to apply knowledge of mathematics, science and engineering;
PO (c). (Design) An ability to design a system, component, or process to meet desired needs;
PO (o). (Topics) EE: A knowledge of electrical engineering applications selected from the …digital
systems… areas; CpE: A knowledge of computer science and computer engineering topics
including …computer architecture.

Under “assessment instruments,” the syllabus says:
2. AsmML (a) Apply-3, (o) Topics-3

Students will solve exam problems in which they must hand-assemble MIPS (or similar)
assembly language instructions to their binary machine-language representations.
3. CAsm
(a) Apply-3, (c) Design-3, (o) Topics-3

Students will solve exam problems in which they must hand-compile short C language code
fragments to equivalent assembly language code for a MIPS or similar instruction-set
architecture.
2
Detailed Objectives for CIO#2
CIO #2. AsmML:
(ao) Derive machine code from assembly instructions.
More specifically, given any assembly language instruction for a subset of the
MIPS-32 instruction set (such as the MiniMIPS or MicroMIPS instructions discussed in
the textbook), or a short sequence of such instructions, students should be able to handassemble the instructions to correct binary code, either in binary or hexadecimal
format, and with all instruction fields clearly named and delineated. To accomplish this
task, the student must be able to:
2.1. Identify the type (R/I/J) of a given source instruction.
2.2. Identify the name, location, and size of the bit-fields in any given instruction type
(including op, rs, rt, rd, shamt, imm, jdest).
2.3. Look up the opcode (and extended opcode, if necessary) for the given instruction.
2.4. Select the appropriate bit field for encoding each instruction operand.
2.5. Convert symbolic register names to 5-bit binary codes.
2.6. Convert provided numerical constants to signed or unsigned binary formats.
2.7 Resolve symbolic branch and jump destinations to the correct word offset relative to the
next PC or current segment, as appropriate.
3
Detailed Objectives for CIO#3
CIO #3. CAsm: (aco) Derive assembler code from an equivalent C code repres’n.
More specifically, given any short code fragment or standalone function written in
the ANSI standard C programming language, students should be able to hand-compile
this source to correct working assembly language for the MIPS-32 instruction set, or a
subset thereof such as MiniMIPS or MicroMIPS, while obeying standard MIPS register
usage conventions. To accomplish this, students should be able to:
3.1. Identify which registers a function’s arguments can be found in, and which registers
should be used to return function results.
3.2. Identify appropriate registers to use for storing local program variables.
3.3. Generate correct caller/callee code to save and restore registers using the stack in
accordance with the standard MIPS calling conventions.
3.4. Generate correct code for accessing data stored in arrays of words.
3.5. Generate correct code for the evaluation of C integer arithmetic and logical expressions.
3.6. Translate high-level control-flow constructs including if, if/else, for, and while statements
to equivalent assembly code using branch instructions.
3.7. Correctly use assembler directives for providing static data.
3.8. Correctly use pseudoinstructions for more concise and readable assembly.
4
Part II
Instruction-Set Architecture
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 5
II Instruction Set Architecture
Introduce machine “words” and its “vocabulary,” learning:
• A simple, yet realistic and useful instruction set
• Machine language programs; how they are executed
• RISC vs CISC instruction-set design philosophy
Topics in This Part
Chapter 5 Instructions and Addressing
Chapter 6 Procedures and Data
Chapter 7 Assembly Language Programs
Chapter 8 Instruction Set Variations
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 6
5 Instructions and Addressing
First of two chapters on the instruction set of MiniMIPS:
• Required for hardware concepts in later chapters
• Not aiming for proficiency in assembler programming
Topics in This Chapter
5.1 Abstract View of Hardware
5.2 Instruction Formats
5.3 Simple Arithmetic / Logic Instructions
5.4 Load and Store Instructions
5.5 Jump and Branch Instructions
5.6 Addressing Modes
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 7
5.1 Abstract View of Hardware
...
m  2 32
Loc 0 Loc 4 Loc 8
4 B / location
Memory
up to 2 30 words
Loc
Loc
m 8 m 4
...
EIU
(Main proc.)
$0
$1
$2
$31
ALU
Execution
& integer
unit
Integer
mul/div
Hi
FPU
(Coproc. 1)
FP
arith
$0
$1
$2
Floatingpoint unit
$31
Lo
TMU
Chapter
10
Figure 5.1
June 2005
Chapter
11
Chapter
12
BadVaddr Trap &
(Coproc. 0) Status memory
Cause unit
EPC  Exception
PC
Memory and processing subsystems for MiniMIPS.
Computer Architecture, Instruction-Set Architecture
Slide 8
PCSpim appearance
Data Types
Byte =Byte
8 bits
Halfword= 2 bytes
Halfword
Word =Word
4 bytes
Doubleword
= 8 bytes
Doubleword
MiniMIPS registers hold 32-bit (4-byte) words. Other common
data sizes include byte, halfword, and doubleword.
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 10
$0
$1
$2
$3
$4
$5
$6
$7
$8
$9
$10
$11
$12
$13
$14
$15
$16
$17
$18
$19
$20
$21
$22
$23
$24
$25
$26
$27
$28
$29
$30
$31
0
June 2005
$zero
$at Reserved for assembler use
$v0
Procedure results
$v1
$a0
Procedure
$a1
Saved
arguments
$a2
$a3
$t0
$t1
$t2
Temporary
$t3
values
$t4
$t5
$t6
$t7
$s0
$s1
Saved
$s2
across
$s3
Operands
procedure
$s4
calls
$s5
$s6
$s7
More
$t8
temporaries
$t9
$k0
Reserved for OS (kernel)
$k1
$gp Global pointer
$sp Stack pointer
Saved
$fp Frame pointer
$ra Return address
A 4-b yte word
sits in consecutive
memory addresses
according to the
big-endian order
(most significant
byte has the
lowest address)
Byte numbering:
3
2
3
2
1
0
1
0
When loading
a byte into a
register, it goes
in the low end Byte
But in SPIM, the
endian-ness
depends on the
underlying HW
Register
Conventions
Word
Doublew ord
A doubleword
sits in consecutive
registers or
memory locations
according to the
big-endian order
(most significant
word comes first)
Computer Architecture, Instruction-Set Architecture
Figure 5.2
Registers and
data sizes in
MiniMIPS.
Slide 11
5.2 Instruction Formats
High-level language statement:
a = b + c
Assembly language instruction:
add $t8, $s2, $s1
0
Machine language instruction:
2
5
1
c
0
2
0
000000 10010 10001 11000 00000 100000
ALU-type Register Register Register
Addition
Unused opcode
instruction
18
17
24
Instruction
cache
P
C
$17
$18
Instruction
fetch
Figure 5.3
June 2005
Register
file
Register
readout
Data cache
(not used)
Register
file
ALU
$24
Operation
Data
read/store
Register
writeback
A typical instruction for MiniMIPS and steps in its execution.
Computer Architecture, Instruction-Set Architecture
Slide 12
Add, Subtract, and Specification of Constants
MiniMIPS add & subtract instructions; e.g., compute:
g = (b + c)  (e + f)
add
add
sub
$t8,$s2,$s3
$t9,$s5,$s6
$s7,$t8,$t9
# put the sum b + c in $t8
# put the sum e + f in $t9
# set g to ($t8)  ($t9)
Decimal and hex constants
Decimal
Hexadecimal
25, 123456, 2873
0x59, 0x12b4c6, 0xffff0000
Machine instruction typically contains
an opcode
one or more source operands
possibly a destination operand
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 13
MiniMIPS Instruction Formats
31
R
31
I
31
J
op
25
rs
20
rt
15
6 bits
5 bits
5 bits
Opcode
Source
register 1
Source
register 2
op
25
rs
20
rt
rd
sh
10
5 bits
Destination
register
15
fn
5
5 bits
6 bits
Shift
amount
Opcode
extension
operand / offset
6 bits
5 bits
5 bits
16 bits
Opcode
Source
or base
Destination
or data
Immediate operand
or address offset
op
25
0
0
jump target address
0
6 bits
1 0 0 0 0 0 0 0 0 0 0 0 26
0 bits
0 0 0 0 0 0 0 1 1 1 1 0 1
Opcode
Memory word address (byte address divided by 4)
Figure 5.4 MiniMIPS instructions come in only three formats:
register (R), immediate (I), and jump (J).
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 14
5.3 Simple Arithmetic/Logic Instructions
Add and subtract already discussed; logical instructions are similar
add
sub
and
or
xor
nor
31
R
$t0,$s0,$s1
$t0,$s0,$s1
$t0,$s0,$s1
$t0,$s0,$s1
$t0,$s0,$s1
$t0,$s0,$s1
op
25
rs
#
#
#
#
#
#
20
rt
set
set
set
set
set
set
15
$t0
$t0
$t0
$t0
$t0
$t0
rd
to
to
to
to
to
to
($s0)+($s1)
($s0)-($s1)
($s0)($s1)
($s0)($s1)
($s0)($s1)
(($s0)($s1))
sh
10
5
fn
0
0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 x 0
ALU
instruction
Source
register 1
Source
register 2
Destination
register
Unused
add = 32
sub = 34
Figure 5.5 The arithmetic instructions add and sub have a format that
is common to all two-operand ALU instructions. For these, the fn field
specifies the arithmetic/logic operation to be performed.
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 15
Arithmetic/Logic with One Immediate Operand
An operand in the range [32 768, 32 767], or [0x0000, 0xffff],
can be specified in the immediate field.
addi
andi
ori
xori
$t0,$s0,61
$t0,$s0,61
$t0,$s0,61
$t0,$s0,0x00ff
#
#
#
#
set
set
set
set
$t0
$t0
$t0
$t0
to
to
to
to
($s0)+61
($s0)61
($s0)61
($s0) 0x00ff
For arithmetic instructions, the immediate operand is sign-extended
31
I
op
25
rs
20
rt
15
operand / offset
0
0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1
addi = 8
Source
Destination
Immediate operand
Figure 5.6 Instructions such as addi allow us to perform an
arithmetic or logic operation for which one operand is a small constant.
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 16
5.4 Load and Store Instructions
op
31
I
25
rs
20
rt
15
operand / offset
0
1 0 x 0 1 1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0
lw = 35
sw = 43
Base
register
Data
register
Offset relative to base
Note on base and offset:
Memory
A[0]
A[1]
A[2]
.
.
.
A[i]
Address in
base register
Offset = 4i
Element i
of array A
The memory address is the sum
of (rs) and an immediate value.
Calling one of these the base
and the other the offset is quite
arbitrary. It would make perfect
sense to interpret the address
A($s3) as having the base A
and the offset ($s3). However,
a 16-bit base confines us to a
small portion of memory space.
Figure 5.7 MiniMIPS lw and sw instructions and their memory
addressing convention that allows for simple access to array elements
via a base address and an offset (offset = 4i leads us to the ith word).
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 17
lw, sw, and lui Instructions
lw
sw
$t0,40($s3)
$t0,A($s3)
lui
$s0,61
op
31
I
25
rs
# load mem[40+($s3)] in $t0
# store ($t0) in mem[A+($s3)]
# “($s3)” means “content of $s3”
# The immediate value 61 is
# loaded in upper half of $s0
# with lower 16b set to 0s
20
rt
15
operand / offset
0
0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1
lui = 15
Unused
Destination
Immediate operand
0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Content of $s0 after the instruction is executed
Figure 5.8 The lui instruction allows us to load an arbitrary 16-bit
value into the upper half of a register while setting its lower half to 0s.
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 18
Initializing a Register
Example 5.2
Show how each of these bit patterns can be loaded into $s0:
0010 0001 0001 0000 0000 0000 0011 1101
1111 1111 1111 1111 1111 1111 1111 1111
Solution
The first bit pattern has the hex representation: 0x2110003d
lui
ori
$s0,0x2110
$s0,0x003d
# put the upper half in $s0
# put the lower half in $s0
Same can be done, with immediate values changed to 0xffff
for the second bit pattern. But, the following is simpler and faster:
nor
June 2005
$s0,$zero,$zero # because (0  0) = 1
Computer Architecture, Instruction-Set Architecture
Slide 19
5.5 Jump and Branch Instructions
Unconditional jump and jump through register instructions
j
jr
verify
$ra
31
J
op
# go to mem loc named “verify”
# go to address that is in $ra;
# $ra may hold a return address
jump target address
25
0 0 0 0 1 0
0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1
j=2
x x x x 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
From PC
31
R
op
Effective target address (32 bits)
25
rs
20
rt
15
rd
10
sh
5
fn
0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
ALU
instruction
Source
register
Unused
Unused
Unused
jr = 8
Figure 5.9 The jump instruction j of MiniMIPS is a J-type instruction which
is shown along with how its effective target address is obtained. The jump
register (jr) instruction is R-type, with its specified register often being $ra.
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 20
Conditional Branch Instructions
Conditional branches use PC-relative addressing
bltz $s1,L
beq $s1,$s2,L
bne $s1,$s2,L
op
31
I
25
rs
20
rt
15
operand / offset
0
0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1
bltz = 1
op
31
I
# branch on ($s1)< 0
# branch on ($s1)=($s2)
# branch on ($s1)($s2)
Source
25
rs
Zero
20
rt
Relative branch distance in words
15
operand / offset
0
0 0 0 1 0 x 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1
beq = 4
bne = 5
Source 1
Figure 5.10 (part 1)
June 2005
Source 2
Relative branch distance in words
Conditional branch instructions of MiniMIPS.
Computer Architecture, Instruction-Set Architecture
Slide 21
Comparison Instructions for Conditional Branching
slt
$s1,$s2,$s3
slti
$s1,$s2,61
31
R
op
20
if ($s2)<($s3), set $s1 to 1
else set $s1 to 0;
often followed by beq/bne
if ($s2)<61, set $s1 to 1
else set $s1 to 0
rt
15
rd
10
sh
5
fn
0
0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0
ALU
instruction
31
I
rs
25
#
#
#
#
#
op
Source 1
register
rs
25
Source 2
register
20
rt
Destination
15
Unused
slt = 42
operand / offset
0
0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1
slti = 10
Source
Figure 5.10 (part 2)
June 2005
Destination
Immediate operand
Comparison instructions of MiniMIPS.
Computer Architecture, Instruction-Set Architecture
Slide 22
Examples for Conditional Branching
If the branch target is too far to be reachable with a 16-bit offset
(rare occurrence), the assembler automatically replaces the branch
instruction beq $s0,$s1,L1 with:
bne
j
L2: ...
$s1,$s2,L2
L1
# skip jump if (s1)(s2)
# goto L1 if (s1)=(s2)
Forming if-then constructs; e.g., if (i == j) x = x + y
bne $s1,$s2,endif
add $t1,$t1,$t2
endif: ...
# branch on ij
# execute the “then” part
If the condition were (i < j), we would change the first line to:
slt
beq
June 2005
$t0,$s1,$s2
$t0,$0,endif
# set $t0 to 1 if i<j
# branch if ($t0)=0;
# i.e., i not< j or ij
Computer Architecture, Instruction-Set Architecture
Slide 23
Compiling if-then-else Statements
Example 5.3
Show a sequence of MiniMIPS instructions corresponding to:
if (i<=j){x = x+1; z = 1;} else {y = y–1; z = 2*z}
Solution
Similar to the “if-then” statement, but we need instructions for the
“else” part and a way of skipping the “else” part after the “then” part.
slt
bne
addi
addi
j
else: addi
add
endif:...
June 2005
$t0,$s2,$s1
$t0,$zero,else
$t1,$t1,1
$t3,$zero,1
endif
$t2,$t2,-1
$t3,$t3,$t3
#
#
#
#
#
#
#
j<i? (inverse condition)
if j<i goto else part
begin then part: x = x+1
z = 1
skip the else part
begin else part: y = y–1
z = z+z
Computer Architecture, Instruction-Set Architecture
Slide 24
5.6 Addressing Modes
Addressing
Instruction
Other elements involved
Some place
in the machine
Implied
Extend,
if required
Immediate
Reg spec
Register
Reg base
Reg file
Reg
data
Constant offset
PC
Pseudodirect
Reg file
Constant offset
Base
PC-relative
Operand
PC
Reg data
Mem
Add addr
Mem
Add addr
Mem
Memory data
Mem
Memory data
Mem
addr Memory Mem
data
Figure 5.11 Schematic representation of addressing modes in MiniMIPS.
June 2005
Computer Architecture, Instruction-Set Architecture
Slide 25
Finding the Maximum Value in a List of Integers
Example 5.5
List A is stored in memory beginning at the address given in $s1.
List length is given in $s2.
Find the largest integer in the list and copy it into $t0.
Solution
Scan the list, holding the largest element identified thus far in $t0.
lw
addi
loop: add
beq
add
add
add
lw
slt
beq
addi
j
done: ...
June 2005
$t0,0($s1)
$t1,$zero,0
$t1,$t1,1
$t1,$s2,done
$t2,$t1,$t1
$t2,$t2,$t2
$t2,$t2,$s1
$t3,0($t2)
$t4,$t0,$t3
$t4,$zero,loop
$t0,$t3,0
loop
#
#
#
#
#
#
#
#
#
#
#
#
#
initialize maximum to A[0]
initialize index i to 0
increment index i by 1
if all elements examined, quit
compute 2i in $t2
compute 4i in $t2
form address of A[i] in $t2
load value of A[i] into $t3
maximum < A[i]?
if not, repeat with no change
if so, A[i] is the new maximum
change completed; now repeat
continuation of the program
Computer Architecture, Instruction-Set Architecture
Slide 26
The 20 MiniMIPS
Instructions
Covered So Far
Copy
Arithmetic
Logic
Memory access
Control transfer
Table 5.1
June 2005
Instruction
Usage
Load upper immediate
Add
Subtract
Set less than
Add immediate
Set less than immediate
AND
OR
XOR
NOR
AND immediate
OR immediate
XOR immediate
Load word
Store word
Jump
Jump register
Branch less than 0
Branch equal
Branch not equal
lui
add
sub
slt
addi
slti
and
or
xor
nor
andi
ori
xori
lw
sw
j
jr
bltz
beq
bne
Computer Architecture, Instruction-Set Architecture
rt,imm
rd,rs,rt
rd,rs,rt
rd,rs,rt
rt,rs,imm
rd,rs,imm
rd,rs,rt
rd,rs,rt
rd,rs,rt
rd,rs,rt
rt,rs,imm
rt,rs,imm
rt,rs,imm
rt,imm(rs)
rt,imm(rs)
L
rs
rs,L
rs,rt,L
rs,rt,L
op fn
15
0
0
0
8
10
0
0
0
0
12
13
14
35
43
2
0
1
4
5
Slide 27
32
34
42
36
37
38
39
8