Transcript (a*b)+

Chapter 3: Instructions
CS 447
Jason D. Bakos
1
Assembly Language
Instructions
• We’re going to use the MIPS R2000
instruction set for the projects in
this course
• Review: Assembly language
instructions are English words that
represent binary machine language
instructions
2
Arithmetic/Logical
Instructions
• Arithmetic instructions are composed of an
operation and three registers
– <op> <destreg> <operand1> <operand2>
– There are 32 32-bit general-purpose integer
registers that we can use (R0 is hardwired to
value 0 for A/L operands)
– Ex: add $1, $2, $3
• When writing assembly language programs,
comments can be added after any instruction by
using the ‘#’ character
• Some architectures only use 2 registers
– The result is stored in the first operand register
– Some of our instructions will use this convention
• Appendix A in the textbook lists all
3
Immediate
Arithmetic/Logical
Instructions
• Most arithmetic/logical instructions have
an “immediate” version
– Immediate instructions have an ‘i’ at the end of
the instruction name
– Immediate instructions allow us to specify an
immediate/constant/literal in lieu of a register
operand
– Ex: add $1, $2, 16
– We only have 16-bits for the immediate, so we
can only represent 216 unique values
– Use decimal numbers for the immediate value in
the assembly-language instruction
4
A/R Instructions
• MIPS R2000 A/L-instructions (complete)
–
–
–
–
–
–
–
–
–
add, addu, addi, addiu
and, andi
div, divu (two registers)
mult, multu (two registers)
nor
or, ori
sll, sllv, sra, srav, srl, srlv
sub, subu
xor, xori
5
Pseudoinstructions
• Pseudoinstructions are assembled into
more than 1 machine instruction
– There’s no real machine instruction for them
– Ex. abs rdest, rsrc
– Assembles into three instructions
• move the contents of rsrc into rdest
• if rdest is greater than 0, skip over the next
instruction
– We haven’t covered conditional branches yet
• subtract rdest from 0
– Appendix A specifies which are
pseudoinstructions
6
Design Considerations
• Making most arithmetic instructions have
3 operands simplifies the hardware
– This is a design decision
– Having a variable number of operands would
greatly complicate the hardware
• Limiting ourselves to 32 registers is also a
design decision to keep things on the
processor die smaller
– Influences clock cycle time
– Gives us more real estate for other things on our
core
• Less registers, less decoding logic, etc.
7
Registers
•
MIPS assembly language also has symbolic names for the registers
– $0 => constant 0
– $1 => $at (reserved for assembler)
– $2,$3 => $v0,$v1 (expression evaluation and results of a function)
– $4-$7 => $a0-$a3 (arguments 1-4)
– $8-$15 => $t0-$t7 (temporary values)
• Used when evaluating expressions that contain more than two
operands (partial solutions)
• Not preserved across function calls
– $16-$23 => $s0->$s7 (for local variables, preserved across function
calls)
– $24, $25 => $t8, $t9 (more temps)
– $26,$27 => $k0, $k1 (reserved for OS kernel)
– $28 => $gp (pointer to global area)
– $29 => $sp (stack pointer)
– $30 => $fp (frame pointer)
– $31 => $ra (return address, for branch-and-links)
8
Memory and Load/Store
Instructions
• As we’ve already seen, a processor
can only use data stored in its
registers as operands and targets
for computation
• Typically, before computation can be
performed, data must be loaded from
main memory
• After the computation is complete,
the results must be stored back to
main memory
9
Memory
• Computer memory is byte-addressed
but the MIPS architecture requires
alignment of loads and stores on the
32-bit (4 byte/word) boundary
– This means that all memory references
must be an even multiple of 4
• When addressing 4-byte words, you
need to provide the address of the
lowest-addressed byte in the word
10
Load/Store Instructions
• Most commonly used:
– lw, sw, lh, sh, lb, sb, la
• Use:
– lw <rdest>, address
– address can be represented as:
• symbolic address (that you declare in SPIM)
• symbolic address with register index
• decimal_offset($basereg)
– This is the way that the instruction is
translated
– loads/stores from contents of
$basereg+decimal_offset
11
Load/Store Instructions
• SPIM treats loads and stores with symbolic
addresses as pseudoinstructions
– loads the address of the data segment as an
immediate into $1
• lui $1, 4097
– data starts at hex address 10010000
– If an index register is provided, adds the
contents of the index reg to $1
• addu $1, $1, rindex
– loads 0($1) into rdest
• lw rdest, offset_of_variable($1)
• This is an example of base-displacement
addressing
• This is why R1 is reserved when you write your
programs
12
Load/Store Instructions
• When loading or storing halfwords
and bytes, the address points to a
aligned word
– The halfword would be the LOWER (least
significant) halfword of the word that
the address is pointing to
– The byte world be the LOWEST (least
significant) byte of the word being that
the address is pointing to
13
Constant-Manipulating
Instructions
• lui rt, imm
– Load the immediate imm into the upper
halfword of register rt
– The lower bits are set to 0
• li rt, imm
– Load the imm into the lower halfword of
register rt
– The upper bits are set to 0
14
Encoding Instructions
• The MIPS architecture has a 32-bit
binary instruction format for each
class of instruction
– A/L, constant manip, comparison,
branch, jump, load/store, data
movement, floating-point
• Even though we’ve only covered 3 of
these classes, let’s look at how we
encode the instructions we’ve
learned…
15
Encoding/Translating A/L
Instructions
• First (most significant, left-most) 6bits of ALL instructions is the opcode
– The opcode defines the instruction
– Doesn’t this only give us 26=64 different
instructions?
• Yes! But all A/L instructions, excluding the
ones which have immediates, has an opcode
of 0 but has a 6-bit field at the end of the
instruction that specifies the operation
16
Encoding/Translating A/L
Instructions
• Non-immediate A/L instructions:
–
–
–
–
–
–
6
5
5
5
5
6
bits
bits
bits
bits
bits
bits
–
–
–
–
–
–
opcode (usually 0)
rs (operand 1)
rt (operand 2)
rd (destination)
0’s or shift amount
operation code
17
Encoding/Translating A/L
Instructions
• Immediate A/L instructions
–
–
–
–
6 bits – opcode (now unique)
5 bits – rs (operand 1)
5 bits – rt (destination)
16 bits – immediate (understood to be 0extended)
18
Encoding/Translating
Load/Store Instructions
• 6 bits – opcode
• 5 bits – rs (base register)
• 5 bits – rt (load from/store to)
– Sometimes the whole register isn’t used
• Half words and bytes
• 16 bits – offset
19
Encoding/Translating
Constant-Manip. Instructions
• 6 bits – opcode
• 5 bits – 0’s
• 5 bits – rt dest. register
– Half of this register will be assigned 0’s
• 16 bits – immediate
20
Examples
•
Let’s compile the following C++ code segment into
assembly code:
–
–
z=(a*b)+(c/d)-(e+f*g);
lw $s0,a
lw $s1,b
mult $s0,$s1
mflo $t0
# new instruction
lw $s0,c
lw $s1,d
div $s0,$s1
mflo $t1
add $t0,$t0,$t1
lw $s0,e
lw $s1,f
lw $s2,g
mult $s1,$s2
mflo $t1
add $t1,$s0,$t1
sub $t0,$t0,$t1
sw $t0,z
21
Examples
• Note: There were many ways we
could have compiled the C++
statement
• Now let’s assemble the first three
instructions to machine code
– Assume the variables are all stored as
words and are stored sequencially,
starting with a, from the start of the
data segment…
22
Examples
• lw $s0,a
– We know s0 is $16
– There are a few different ways we can
do this, too…
– First, we need to convert this instruction
to a small series of instructions…
–
lui $1,4097
# 4097 is 1001 in hex
lw 16,0($1)
# 0 offset because a is first var
…
00111100000000010001000000000001 => 3C011001
10001100000100000000000000000000 => 8C100000
23
Examples
• mult $s0, $s1
–
00000010000100010000000000011000 => 02110018
24
Branch/Jump Instructions
•
•
Branch and jump instructions are needed for program control
– if-statements (conditionals)
– loops
– procedure calls
Most common:
– b <label> -- unconditional branch
• label is a memory address (we can be symbolic ones, of
course)
– beq, bgez, bgezal, bgtz, blez, etc.
• Conditional branches, where we’re comparing a register
to 0 or two registers to determine if we’re going to
branch or not
• Also have al (and-link) variants, that link a return address
(instruction following branch) into $31 so we can return
• Branch targets are 16-bit immediate offset
– offset in words… it is shifted to the left 2 bits to get
byte length
25
Branch/Jump Instructions
– j, jal
• Unconditionally branches to a 26-bit
pseudodirect address (not offset)
– jalr, jr
• Unconditionally branches to an address
stored in a register
26
Encoding/Translating
Branch/Jump Instructions
• See Appendix A
– These are very similar to the encoding
we covered before
27
Data Movement and
Comparison Instructions and
Their Encoding
• I’m going to leave the study of these
instructions (from Appendix A) up to
you as an exercise!
28
Examples
• if ((a>b)&&(c=d)) e=0; else e=f;
lw $s0,a
next0:
nope:
yup:
out:
lw $s1,b
bgt $s0,$s1,next0
b nope
lw $s0,c
lw $s1,d
beq $s0,$s1,yup
lw $s0,f
sw $s0,e
b out
xor $s0,$s0,$s0
sw $s0,e
…
29
Examples
• Again, there are many other ways we
could have tackled this…
• You will eventually come up with
your own strategies for “compiling”
the types of constructs you want to
perform…
30
Examples
• How about a for loop?
•
for (i=0;i<a;i++) b[i]=i;
lw $s0,a
xor $s1,$s1,$s1
loop0:
blt $s1,$s0,loop1
b out
sll $s2,S1,2
loop1:
sw $s1,b($s2)
addi $s1,$s1,1
b loop0
out:
…
31
Examples
• How about a pretest while loop?
•
while (a<b) {
a++;
}
loop0:
loop1:
out:
lw $s0,a
lw $s1,b
blt $s0,$s1,loop1
b out
addi $s0,Ss0,1
sw $s0,a
b loop0
…
32
Examples
• How about a posttest while loop?
•
do {
a++;
} while (a<b);
lw $s0,a
lw $s1,b
loop0:
addi $s0,$s0,1
sw $s0,a
blt $s0,$s1,loop0
…
33
Procedure Calls
• How about a procedure call?
– The full-blown C/Pascal recursive
procedure call convention is beyond the
scope of this class, so we’ll skip it for
now…
– This is described in detail in Appendix A
• You can arbitrarily implement your
own procedure call convention…
34
Procedure Calls
• Say we want to write a procedure
that computes the factorial of a
number, like this:
int factorial (int val) {
int temp=val;
while (val)
temp*=(--val);
return temp;
}
35
Procedure Calls
• Let’s adopt the following simple
convention:
– We’ll pass the arguments through $a0-$a3
• Only allows for up to 4 arguments
– We’ll set our return value in $v0
– The return address will be stored in $ra
• This limits us to 1-level of procedure calls
– We’ll assume the callee (procedure) will save
registers $s0-$s7 starting at memory address
FF000000 when it’s called, and restore the
registers before it returns
• This may not be necessary for all procedures
36
Procedure Calls
• So here’s our procedure…
factorial:
loop0:
loop1:
out:
lui $t1,0xFF00
sw $s0,0($t1)
sw $s1,4($t1)
…
sw $s7,28($t1)
move $s0,$a0
move $s1,$a0
bgtz $s0,loop1
b out
mult $s0,$s1
mflo $s1
subi $s0,$s0,1
b loop0
move $v0,$s1
lw $s0,0($t1)
…
jr $31
# new instruction
# load back registers
37
Procedure Calls
• In order to call our procedure…
– load a value into $a0
– bal factorial
– look in $v0 for the result!
38
I/O
• Doing I/O with SPIM is also
described in Appendix A, but we’re
going to use the system calls that
are set up for us to do I/O…
39
I/O
• SPIM provides some operating
system services through the syscall
instruction
• To use the system calls:
– load system call code (from pg. a49) into
$v0 and argument into $a0…
– return values in $v0 (or $f0 for fp
results)
40
Example I/O
str:
.asciiz
“the answer = “
.text
li
$v0,4
la
$a0, str
syscall
li
$v0,1
la
$a0,5
syscall
(Refer to page A-49)
41
Lecture 3a:
Supplemental Notes for Chapter 3
CS 447
Jason Bakos
42
Review of Branch
Instructions
•
•
•
•
b <label>
– Unconditional branch
– Pseudoinstruction
beq <r1>, <r2>, <label>
– Branch if equal
4
r1
r2
offset
6
5
5
16
bgez <r1>, label
– Branch if greater than or equal 0
1
r1
1
offset
6
5
5
16
4
r1
0x11
offset
6
5
5
16
bgezal <r1>, label
– Branch if greater than or equal 0 and link
43
Review of Branch
Instructions
•
•
•
•
bgtz <r1>, <label>
– Branch if greater than zero
7
r1
0
offset
6
5
5
16
blez <r1>, <label>
– Branch if less than or equal 0
6
r1
0
offset
6
5
5
16
1
r1
0x10
offset
6
5
5
16
1
r1
0
offset
6
5
5
16
bltzal <r1>, label
– Branch if less than 0 and link
bltz <r1>, label
– Branch if less than 0
44
Review of Branch
Instructions
•
bne <r1>, <r2>, <label>
– Branch if not equal
5
r1
r2
offset
6
5
5
16
•
beqz <r1>, <label>
– Branch if equal 0
– Pseudoinstruction
•
bge <r1>, <r2>, label
– Branch if greater than or equal
– Pseudoinstruction
•
bgeu <r1>, <r2>, label
– Branch if greater than or equal unsigned
– Pseudoinstruction
45
Review of Branch
Instructions
•
bgt <r1>, <r2>, <label>
– Branch if greater than
– Pseudoinstruction
•
bgtu <r1>, <r2>, <label>
– Branch if greater than unsigned
– Pseudoinstruction
•
blte <r1>, <r2>, label
– Branch if less than or equal
– Pseudoinstruction
•
blteu <r1>, <r2>, label
– Branch if less than or equal unsigned
– Pseudoinstruction
46
Review of Branch
Instructions
• blt <r1>, <r2>, <label>
– Branch if less than
– Pseudoinstruction
•
bltu <r1>, <r2>, <label>
– Branch if less than unsigned
– Pseudoinstruction
•
bnez <r1>, label
– Branch if not equal zero
– Pseudoinstruction
47
Notes on Branch
Instructions
• Offset field represents offset in instruction
words (bytes/4)
– starting from the next instruction
• next instruction would be offset 0
• can be negative (as can offset in load/store)
• Branch pseudoinstructions assemble into
the equivalent comparison instruction
followed by a bgtz
• And-link instructions load the address of
the next instruction into $31 ($ra) if the
branch is taken
48
Notes on Comparison
Instructions
• There is a comparison instruction for every conditional
branch instruction
– They work just like the conditional branch
instructions, but instead, if the comparison is
evaluated true, the destination register is set to the
value 1, and 0 otherwise
• slt and sltu follow the R-type format
• Comparison instructions aren’t really useful, except for
slti and sltiu (unsigned), which are immediate
comparison instructions
– They follow the I-type format
– Immediates are sign-extended!!!
– Use these, followed by a bltz to compare a register and
immediate and branch based on result
•
seq, sge, sgeu, sgt, sgtu, sle, sleu, sne are
pseudoinstructions
49
Jump Instructions
•
•
•
•
j <label>
– Unconditional jump (used when b instruction is used)
2
target
6
26
3
target
6
26
jal <label>
– Jump and link (used for procedure call)
jalr <r1>, <r2>
– Jump and link register (same as above, but links into r2)
0
r1
0
r2
0
9
6
5
5
5
5
6
0
r1
0
0x8
6
5
16
6
jr <r1>
– Jump register (used to return from a procedure)
50
Notes on Pseudodirect
Addressing
• j and jal use pseudodirect
addressing
– To compute the effective branch target
address, the MS 6 bits of the PC are
added to the address in the instruction
51
A More Robust Procedure
Calling Convention
• We’ll use $a0-$a3 to pass parameters to a
procedure
• We’ll use $v0 and $v1 for procedure
returns
• We want to save $s0-$s7 across procedure
calls
• We want to be able to have multiple levels
of procedure calls and we want to be able
to call procedures recursively
– This means we need to somehow save
arguments, state registers, and return
addresses for each procedure call
52
A More Robust Procedure
Calling Convention
• Solution:
Use a stack! When each procedure is
called, push arguments, return address,
and saved registers onto a stack
NOTE: The stack frames can be FIXED
size using this convention
To create a better procedure calling
convention, we would also allow for
variable numbers of arguments and local
variable storage on the stack, but we will
make this simpler
53
A More Robust Procedure
Calling Convention
• For calling procedures:
– Caller must move arguments into argument
registers and jal to procedure
– Callee must save arguments, return address,
and machine state (registers) on stack, and
decrement $sp by 13*4=52
• $sp always points to next stack position
• stack grows down
– Upon completion, callee must set the return
value register(s), restore the $s registers,
restore $ra, increment $sp by 52, and jump back
to the caller
• $sp is already initialized when you start your
program
54
More Notes
• You can use whatever procedure
calling convention you want in your
programs, but I recommend using
this one
• Your programs’ procedures will
share a static memory space (no
scope)
– In order to implement scope, we’d have
to allocate local space on the stack
55