Transcript Document
Lecture 7: MIPS Instruction Set
• Today’s topic
– Procedure call/return
– Large constants
• Reminders
– Homework #2 posted, due 9/17/2014
1
Recap: Procedure Calling
•
Steps required
1.
2.
3.
4.
5.
6.
Place parameters in registers
Transfer control to procedure
Acquire storage for procedure
Perform procedure’s operations
Place result in register for caller
Return to place of call
2
Recap
• The jal instruction is used to jump to the procedure and
save the current PC (+4) into the return address register
• Arguments are passed in $a0-$a3; return values in $v0-$v1
• Since the callee may over-write the caller’s registers,
relevant values may have to be copied into memory
• Each procedure may also require memory space for
local variables – a stack is used to organize the memory
needs for each procedure
3
The Stack
The register scratchpad for a procedure seems volatile –
it seems to disappear every time we switch procedures –
a procedure’s values are therefore backed up in memory
on a stack
High address
Proc A’s values
Proc A
call Proc B
…
call Proc C
…
return
return
Proc B’s values
Proc C’s values
…
Stack grows
this way
Low address
return
4
Example 1
int leaf_example (int g, int h, int i, int j)
{
int f ;
f = (g + h) – (i + j);
return f;
}
5
Example 1
int leaf_example (int g, int h, int i, int j)
{
int f ;
f = (g + h) – (i + j);
return f;
}
Notes:
In this example, the procedure’s
stack space was used for the caller’s
variables, not the callee’s – the compiler
decided that was better.
The caller took care of saving its $ra and
$a0-$a3.
leaf_example:
addi
$sp, $sp, -12
sw
$t1, 8($sp)
sw
$t0, 4($sp)
sw
$s0, 0($sp)
add
$t0, $a0, $a1
add
$t1, $a2, $a3
sub
$s0, $t0, $t1
add
$v0, $s0, $zero
lw
$s0, 0($sp)
lw
$t0, 4($sp)
lw
$t1, 8($sp)
addi
$sp, $sp, 12
jr
$ra
6
Non-Leaf Procedures
• Procedures that call other procedures
• For nested call, caller needs to save on
the stack:
– Its return address
– Any arguments and temporaries needed
after the call
• Restore from the stack after the call
7
Non-Leaf Procedure Example
• C code:
int fact (int n)
{
if (n < 1) return f;
else return n * fact(n - 1);
}
– Argument n in $a0
– Result in $v0
8
Non-Leaf Procedure Example
• MIPS code:
fact:
addi
sw
sw
slti
beq
addi
addi
jr
L1: addi
jal
lw
lw
addi
mul
jr
$sp,
$ra,
$a0,
$t0,
$t0,
$v0,
$sp,
$ra
$a0,
fact
$a0,
$ra,
$sp,
$v0,
$ra
$sp, -8
4($sp)
0($sp)
$a0, 1
$zero, L1
$zero, 1
$sp, 8
$a0, -1
0($sp)
4($sp)
$sp, 8
$a0, $v0
#
#
#
#
adjust stack for 2 items
save return address
save argument
test for n < 1
#
#
#
#
#
#
#
#
#
#
if so, result is 1
pop 2 items from stack
and return
else decrement n
recursive call
restore original n
and return address
pop 2 items from stack
multiply to get result
and return
9
Local Data on the Stack
• Local data allocated by callee
– e.g., C automatic variables
• Procedure frame (activation record)
– Used by some compilers to manage stack storage
10
Memory Layout
• Text: program code
• Static data: global
variables
– e.g., static variables in C,
constant arrays and strings
– $gp initialized to address
allowing ±offsets into this
segment
• Dynamic data: heap
– E.g., malloc in C, new in
Java
• Stack: automatic storage
11
Dealing with Characters
• Instructions are also provided to deal with byte-sized
and half-word quantities: lb (load-byte), sb, lh, sh
• These data types are most useful when dealing with
characters, pixel values, etc.
• C employs ASCII formats to represent characters – each
character is represented with 8 bits and a string ends in
the null character (corresponding to the 8-bit number 0)
12
Example
Convert to assembly:
void strcpy (char x[], char y[])
{
int i;
i=0;
while ((x[i] = y[i]) != `\0’)
i += 1;
}
13
Example
Convert to assembly:
void strcpy (char x[], char y[])
{
int i;
i=0;
while ((x[i] = y[i]) != `\0’)
i += 1;
}
strcpy:
addi $sp, $sp, -4
sw
$s0, 0($sp)
add
$s0, $zero, $zero
L1: add $t1, $s0, $a1
lb
$t2, 0($t1)
add
$t3, $s0, $a0
sb
$t2, 0($t3)
beq
$t2, $zero, L2
addi $s0, $s0, 1
j
L1
L2: lw $s0, 0($sp)
addi $sp, $sp, 4
jr
$ra
14
String Copy Example
• MIPS code:
strcpy:
addi
sw
add
L1: add
lbu
add
sb
beq
addi
j
L2: lw
addi
jr
$sp,
$s0,
$s0,
$t1,
$t2,
$t3,
$t2,
$t2,
$s0,
L1
$s0,
$sp,
$ra
$sp, -4
0($sp)
$zero, $zero
$s0, $a1
0($t1)
$s0, $a0
0($t3)
$zero, L2
$s0, 1
0($sp)
$sp, 4
#
#
#
#
#
#
#
#
#
#
#
#
#
adjust stack for 1 item
save $s0
i = 0
addr of y[i] in $t1
$t2 = y[i]
addr of x[i] in $t3
x[i] = y[i]
exit loop if y[i] == 0
i = i + 1
next iteration of loop
restore saved $s0
pop 1 item from stack
and return
15
32-bit Constants
• Most constants are small
– 16-bit immediate is sufficient
• For the occasional 32-bit constant
lui rt, constant
– Copies 16-bit constant to left 16 bits of rt
– Clears right 16 bits of rt to 0
lui $s0, 61
0000 0000 0111 1101 0000 0000 0000 0000
ori $s0, $s0, 2304 0000 0000 0111 1101 0000 1001 0000 0000
16
Branch Addressing
• Branch instructions specify
– Opcode, two registers, target address
• Most branch targets are near branch
– Forward or backward
op
rs
rt
constant or address
6 bits
5 bits
5 bits
16 bits
PC-relative addressing
Target address = PC + offset × 4
PC already incremented by 4 by this time
17
Jump Addressing
• Jump (j and jal) targets could be
anywhere in text segment
– Encode full address in instruction
op
address
6 bits
26 bits
18
Branching Far Away
• If branch target is too far to encode with
16-bit offset, assembler rewrites the
code
• Example
beq $s0,$s1, L1
↓
bne $s0,$s1, L2
j L1
L2: …
19
Addressing Mode Summary
20
Large Constants
• Immediate instructions can only specify 16-bit constants
• The lui instruction is used to store a 16-bit constant into
the upper 16 bits of a register… thus, two immediate
instructions are used to specify a 32-bit constant
• The destination PC-address in a conditional branch is
specified as a 16-bit constant, relative to the current PC
• A jump (j) instruction can specify a 26-bit constant; if more
bits are required, the jump-register (jr) instruction is used
21