CMPEN
Lecture
7
331
•
Procedure Calling
Steps required
1. Place parameters in registers
2. Transfer control to procedure
3. Acquire storage for procedure
4. Perform procedure’s operations
5. Place result in register for caller
6. Return to place of call
Chapter 2 — Instructions: Language of the Computer — 2
§2.8 Supporting Procedures in Computer Hardware
Register Usage
• $a0–$a3:arguments(reg’s4–7)
• $v0,$v1:resultvalues(reg’s2and3)
• $t0–$t9:temporaries
• Can be overwritten by callee (calling program)
• $s0–$s7:saved
• Must be saved/restored by callee
• $gp:globalpointerforstaticdata(reg28) • $sp:stackpointer(reg29)
• $fp:framepointer(reg30)
• $ra:returnaddress(reg31)
Chapter 2 — Instructions: Language of the Computer — 3
Register Specifications
• $t0 – $t9: temporary register that are not preserved by the callee (called procedure) on a procedure call
• $s0 – $s7: saved registers that must be preserved on a procedure call (if used, the callee saves and restore them)
Chapter 2 — Instructions: Language of the Computer — 4
Procedure Call Instructions
• Procedure call: jump and link
jal ProcedureLabel
• Addressoffollowinginstructionputin$ra • Jumpstotargetaddress
• Procedure return: jump register
jr $ra
• Copies$ratoprogramcounter
• Canalsobeusedforcomputedjumps • e.g., for case/switch statements
Chapter 2 — Instructions: Language of the Computer — 5
Leaf Procedure Example
• C code: (Leaf procedure: procedures that don’t call others)
int leaf_example (int g, h, i, j)
{ int f;
f = (g + h) – (i + j);
return f; }
• Argumentsg,h,i,jin$a0-$a3
• fin$s0(hence,needtosave$s0onstack)
• Resultin$v0
Chapter 2 — Instructions: Language of the Computer — 6
• MIPS code:
Leaf Procedure Example
leaf_example:
addi $sp, $sp, -4
sw $s0, 0($sp)
add $t0, $a0, $a1
add $t1, $a2, $a3
sub $s0, $t0, $t1
add $v0, $s0, $zero
lw $s0, 0($sp)
addi $sp, $sp, 4
jr $ra
Save $s0 on stack
Procedure body
Result Restore $s0
Return back to calling routine
Chapter 2 — Instructions: Language of the Computer — 7
Non
• Procedures that call other procedures
• For nested call, caller needs to save on the stack:
• Itsreturnaddress
• Anyargumentsandtemporariesneededafterthecall
• Restore from the stack after the call
Chapter 2 — Instructions: Language of the Computer — 8
–
Leaf Procedures
Non
• C code:
int fact (int n)
{
if (n < 1) return 1;
else return n * fact(n - 1);
}
• Argumentnin$a0 • Resultin$v0
Chapter 2 — Instructions: Language of the Computer — 9
-
Leaf Procedure Example
Steps for Calling a Procedure
• Save necessary values onto stack
• Assign arguments if any
• jal call
• Restore values from stack
Chapter 2 — Instructions: Language of the Computer — 10
Non
• MIPScode:
-
Leaf Procedure Example
fact:
addi $sp, $sp, -8
sw $ra, 4($sp)
sw $a0, 0($sp)
# adjust stack for 2 items
# save return address
# save argument
slti $t0, $a0, 1 # test for n < 1
beq $t0, $zero, L1
addi $v0, $zero, 1
addi $sp, $sp, 8
jr $ra
# if so, result is 1
# pop 2 items from stack
# and return
L1: addi $a0, $a0, -1 # else decrement n
jal fact # recursive call
lw $a0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
# restore original n
# and return address
# pop 2 items from stack
mul $v0, $a0, $v0 # multiply to get result
jr $ra # and return
Chapter 2 — Instructions: Language of the Computer — 11
CMPEN
Lecture
8
331
Local Data on the Stack
• Localdataallocatedbycallee • e.g., C automatic variables
• Procedureframe(activationrecord)
• Used by some compilers to manage stack storage
Chapter 2 — Instructions: Language of the Computer — 13
Memory Layout
• Text:programcode
• Staticdata:global variables
• e.g., static variables in C, constant arrays and strings
• $gp initialized to address allowing ±offsets into this segment
• Dynamicdata:heap
• E.g., malloc in C, new in Java
• Stack:automaticstorage Chapter 2 — Instructions: Language of the Computer — 14
Character Data
• Byte-encoded character sets
• ASCII:128characters • 95 graphic, 33 control
• Unicode: 32-bit character set
• UsedinJava,C++widecharacters,...
• Mostoftheworld’salphabets,plussymbols • UTF-8,UTF-16:variable-lengthencodings
Chapter 2 — Instructions: Language of the Computer — 15
§2.9 Communicating with People
Byte Operations
• Could use bitwise operations
• MIPS byte load/store
• lb:load a byte from memory, placing it in the rightmost 8 bits of a register
lb rt, offset(rs) # read byte from source
lbu rt, offset(rs)
sb rt, offset(rs)
Chapter 2 — Instructions: Language of the Computer — 16
String Copy Example
• C code:
• Null-terminatedstring
void strcpy (char x[], char y[])
{ int i;
i = 0;
while ((x[i]=y[i])!='\0')
i += 1; }
• Addressesofx,yin$a0,$a1 • iin$s0
Chapter 2 — Instructions: Language of the Computer — 17
String Copy Example
• MIPScode:
strcpy:
addi $sp, $sp, -4 # adjust stack for 1 item
sw $s0, 0($sp) # save $s0
add $s0, $zero, $zero # i = 0
L1: add $t1, $s0, $a1 # addr of y[i] in $t1
lbu $t2, 0($t1) # $t2 = y[i]
add $t3, $s0, $a0 # addr of x[i] in $t3
sb $t2, 0($t3) # x[i] = y[i]
beq $t2, $zero, L2 # exit loop if y[i] == 0
addi $s0, $s0, 1 # i = i + 1
j L1 # next iteration of loop
L2: lw $s0, 0($sp) # restore saved $s0
addi $sp, $sp, 4 # pop 1 item from stack
jr $ra # and return
Chapter 2 — Instructions: Language of the Computer — 18
32
• Most constants are small
• 16-bitimmediateissufficient
• For the occasional 32-bit constant
• lui: load upper immediate
lui rt, constant
• Copies16-bitconstanttoleft16bitsofrt • Clearsright16bitsofrtto0
• Load 32 bit constant into register $s0
-
bit Constants
0000 0000 0011 1101
0000 1001 0000 0000
61 in decimal
2304 in decimal
0000 0000 0011 1101
0000 0000 0000 0000
lui $s0, 61
ori $s0, $s0, 2304
0000 0000 0111 1101
0000 1001 0000 0000
Chapter 2 — Instructions: Language of the Computer — 19
§2.10 MIPS Addressing for 32-Bit Immediates and Addresses
Jump Addressing
• Jump (j and jal) targets could be anywhere in text segment
• Encodefulladdressininstruction
op
address
6 bits
26 bits
Chapter 2 — Instructions: Language of the Computer — 20
Branch Addressing
• Branch instructions specify
• Opcode,tworegisters,targetaddress
• Most branch targets are near branch • Forwardorbackward
op
rs
rt
constant or address
6 bits 5 bits 5 bits 16 bits
n PC (program counter)-relative addressing n Target address = PC + branch address
Chapter 2 — Instructions: Language of the Computer — 21
Target Addressing Example
• Loop code from earlier example • AssumeLoopatlocation80000
Loop: sll $t1, $s3, 2
80000
0
0
19
9
2
0
add $t1, $t1, $s6
80004
0
9
22
9
0
32
lw $t0, 0($t1)
80008
35
9
8
0
bne $t0, $s5, Exit
80012
5
8
21
2
addi $s3, $s3, 1
80016
8
19
19
1
j Loop
80020
2
20000
Exit: ...
80024
Chapter 2 — Instructions: Language of the Computer — 22
Branching Far Away
• If branch target is too far to encode with 16-bit offset, assembler rewrites the code
• Example
j L1 L2: ...
Chapter 2 — Instructions: Language of the Computer — 23
beq $s0,$s1, L1
↓
bne $s0,$s1, L2