ECE 232
Hardware Organization and Design
Lecture 6
MIPS Assembly Instructions, cont’d
Maciej Ciesielski
www.ecs.umass.edu/ece/labs/vlsicad/ece232/sp$r2002/index_232.html
ECE 232 L6.Assemb.1
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Administrative issues
° Homework #2 assigned today, due Th., Feb. 21 in class.
° Excuses that cannot be tolerated
• Forgot to buy the textbook
• Forgot to do the homework
• Dog ate the homework, etc … (you are pretty creative at those)
° Solving the textbook problem
• Putting one copy of text on reserve in Physical Science Library
° Change in late homework policy
• 25% per day – to allow to post solutions in 3-4 days
° Midterm exam I – Th., March 7, 6:30 pm
• Morrill Science Center (Bldg II) room 131
• No excuses (forgot, overslept, overate, etc)
• Only legitimate reasons (in writing) can be accepted
ECE 232 L6.Assemb.2
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Outline
° Review: MIPS instructions, formats
• MIPS instructions: data transfers, arithmetic, logical
• Pseudo-instruction example: loading large constant
• MIPS register organization
° Implementing loops
° Implementing switch/case statement
° Procedures and subroutines
• Stacks and pointers
° Running a program
• Compiler, Assembler, Linker, Loader
ECE 232 L6.Assemb.3
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
MIPS Addressing Modes/Instruction Formats
All instructions are 32-bit wide
• Register (direct)
op
rs
rt
rd ... fnc
register
• Immediate
op
rs
rt
immed
• Base+index
op
rs
rt
immed
+
register
• PC-relative
op
rs
rt
PC
ECE 232 L6.Assemb.4
Adapted from Patterson 97 ©UCB
Memory
immed
Memory
+
Copyright 1998 Morgan Kaufmann Publishers
MIPS: Software conventions for registers
R0 $zero constant 0
R16 $s0
R1 $at
reserved for assembler
...
R2 $v0
value registers &
R23 $s7
R3 $v1
R4 $a0
function results
arguments
callee saves
(caller can clobber)
R24 $t8 temporary (cont’d)
R25 $t9
R5 $a1
R26 $k0 reserved for OS kernel
R6 $a2
R27 $k1
R7 $a3
R28 $gp pointer to global area
R8 $t0
temporary: caller saves
R29 $sp
Stack pointer
...
(callee can clobber)
R30 $fp
Frame pointer
R15 $t7
ECE 232 L6.Assemb.5
R31 $ra
Adapted from Patterson 97 ©UCB
return Address
Copyright 1998 Morgan Kaufmann Publishers
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
ECE 232 L6.Assemb.6
Adapted from Patterson 97 ©UCB
$r5
0000 … 0000
Copyright 1998 Morgan Kaufmann Publishers
Loading large numbers
° Pseudo-instruction li $t0, big: load 32-bit constant
lui $t0, upper
ori $t0, $t0, lower
# $t0[31:16]  upper
# $t0  ($t0 Or [0ext.lower])
upper
Or
0000 0000 0000 0000
31
0000 0000 0000 0000
$to:
0
16 15
upper
lower
lower
32-bit constant
ECE 232 L6.Assemb.7
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Loop with variable array index
° Compile the following loop, with A[ ] = array with base address in
$s5; variables g, h, i, j associated with registers $s1, $s2, $s3, $s4.
Loop: g = g + A[i];
i = i + j;
if (i  h) go to Loop;
MIPS instructions:
Loop:
ECE 232 L6.Assemb.8
add
add
add
lw
add
add
bne
$t1, $s3, $s3
$t1, $t1, $t1
$t1, $t1, $s5
$t0, 0 ($t1)
$s1, $s1, $t0
$s3, $s3, $s4
$s3, $s2, Loop
Adapted from Patterson 97 ©UCB
# $t1  i+i = 2i
# $t1  2i+2i = 4i
# $t1  address of A[i]
# $t0  A[i]
# $s1  g + A[i]
# $s3  i + j
# if (i  h) go to Loop
Copyright 1998 Morgan Kaufmann Publishers
While loop
° Base address of A[i] is in $s6; variables i, j, k are in $s3, $s4, $s5.
° Compile the following while loop
while (A[i] == k)
i = i + j;
into MIPS instructions:
Loop:
add $t1, $s3, $s3
add $t1, $t1, $t1
add $t1, $t1, $s6
lw $t0, 0 ($t1)
bne $t0, $s5, Exit
add $s3, $s3, $s4
j Loop
# $t1  i+i = 2i
# $t1  2i+2i = 4i
# $t1  address of A[i]
# $t0  A[i]
# if (A[I]  k) go to Exit
# $s3  i + j
# go to Loop
Exit:
ECE 232 L6.Assemb.9
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Switch/case statement
° Variables f - k are in $s0 - $s5. Register $t2 contains constant 4.
° Compile the following switch statement into MIPS instructions
switch (k) {
case 0: f = i + j; break;
/* k=0 */
case 1: f = g + h; break;
/* k=1 */
case 2: f = g - h; break;
/* k=2 */
case 3: f = i - j; break;
/* k=3 */
}
° Use the switch variable k to index the jump address table.
First, test for k, if in correct range (0-3).
slt
bne
slt
beq
ECE 232 L6.Assemb.10
$t3, $s5, $zero
$t3, $zero, Exit
$t3, $s5, $t2
$t3, $zero, Exit
# test if k , 0
# if k < 0, go to Exit
# test if k < 4
# if k  4, go to Exit
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Switch statement, cont’d
° Access jump table T [ ] with addresses L0,L1,L2,L3:
add $t1, $s5, $s5
# $t1  2k
add $t1, $t1, $t1
# $t1  4k
add $t1, $t1, $t4
# $t1  address of T [k]
lw $t0, 0 ($t1)
# $t0  T [k]
° Use jump register instruction to jump via $t1 to the right address
jr $to
# jump based on register $t0
L0: add $s0, $s3, $s4
# k = 0, so f=$s0  i + j
j Exit
# go to Exit
L1: add $s0, $s1, $s2
# k = 1, so f=$s0  g + h
j Exit
# go to Exit
L2: sub $s0, $s1, $s2
# k = 2, so f=$s0  g + h
j Exit
# go to Exit
L3: sub $s0, $s3, $s4
# k = 3, so f=$s0  i - j
Exit:
ECE 232 L6.Assemb.11
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Stacks in Procedure Calls
Stacking of Subroutine Calls and Returns:
A
A:
CALL B
B:
A B
CALL C
A B C
C:
RET
A B
RET
A
Some machines provide a memory stack as part of the architecture
(e.g., VAX)
Sometimes stacks are implemented via software convention
(e.g., MIPS)
ECE 232 L6.Assemb.12
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Memory Stacks
Useful for stacked environments/subroutine call and return
Stacks that Grow Up vs. Stacks that Grow Down:
Next
Empty?
SP
Last
Full?
c
b
a
inf. Big
0 Little
grows
up
grows
down
0 Little
inf. Big
Memory
Addresses
How is empty stack represented?
Little --> Big/Last Full
Little --> Big/Next Empty
POP:
Read from Mem(SP)
Decrement SP
POP:
Decrement SP
Read from Mem(SP)
PUSH:
Increment SP
Write to Mem(SP)
PUSH:
Write to Mem(SP)
Increment SP
ECE 232 L6.Assemb.13
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Call-Return Linkage: Stack Frames
High Mem
Arguments
Callee save
registers
Reference args and
local variables at
fixed (positive) offset
from FP
(old FP, RA)
Local variables
FP
Grows and shrinks during
expression evaluation
SP
Low Mem
° Many variations on stacks possible (up/down, last pushed / next )
° Block structured languages contain link to lexically enclosing frame
° Compilers normally keep scalar variables in registers, not memory!
ECE 232 L6.Assemb.14
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Compiling a leaf procedure (not nested)
° int leaf_example (int g, int h, int i, int j)
{
int f;
f = (g + h) – (i + j);
return f;
}
° Let parameter variables g, h, i, j, correspond to the argument registers
$a0, $a1, $a2, $a3. Will use temp. registers $t0= (g + h) and $t1=(i + j).
Function f will be stored in $s0.
° Steps:
° Save the old values of registers ($s0, $t0, $t1) on stack (push)
° Issue a jal sub_address instruction ($ra  ret_addr, j sub_address)
° Perform the computation for $t0, $t1, $s0 using argument registers
° Copy the value of f into a return value register $v0
° Restore the old values of the saved registers from stack (pop)
° Finally, jump back to the calling routine, jr $ra
(PC  return_address=PC+4)
ECE 232 L6.Assemb.15
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Compiling a leaf procedure, cont’d
Leaf_example:
# label of the procedure
Save the old values of registers ($s0, $t0, $t1) on stack (push)
sub $sp, $sp, 12
sw $t1, 8 ($sp)
…….
# adjust stack to make room for 3 items
# save reg $t1 on stack
# repeat for $t0, $s0
Perform the computation for $t0, $t1, $s0 using argument registers
add $t0, $a0, $a1
add $t1, $a2, $a3
sub $s0, $t0, $t1
# $t0  g + h
# $t1  i + j
# $s0  (g + h) – (i + j)
Copy the value of f into a return value register $v0
# returns f ($v0  $s0 + 0)
Restore the old values of the saved registers from stack (pop)
lw $s0, 0 ($sp)
# restore reg. $s0 for the caller
…….
# repeat for $t0, $t1 …
add $sp, $sp, 12
# adjust the stack to delete 3 items
add $v0, $s0, $zero
Finally, jump back to the calling routine (PC  return address)
jr $ra
ECE 232 L6.Assemb.16
# PC  $ra
Adapted from Patterson 97 ©UCB
Copyright 1998 Morgan Kaufmann Publishers
Descargar

ECE 232 Hardware Design and Organization