MIPS ISA-II: Procedure Calls & Program Assembly
Module Outline
Review ISA and understand instruction encodings Arithmetic and Logical Instructions Review memory organization Memory (data movement) instructions
Control flow instructions
Procedure/Function calls Program assembly, linking, & encoding
(2)
Reading
Reading 2.8, 2.12 Appendix B: B1 - B.6
(3)
Procedure Calls
Basic functionality
Transfer of parameters & control to procedure Transfer of results & control back to the calling program Support for nested procedures
What is so hard about this?
Consider independently compiled code modules
o o o Where are the inputs? Where should I place the outputs? Recall: What do you need to know when you write procedures in C?
(4)
Specifics
Where do we pass data
Preferably registers make the common case fast Memory as an overflow area
Nested procedures
The stack, $fp, $sp and $ra Saving and restoring machine state
Set of rules that developers/compilers abide by
Which registers can am I permitted to use with no consequence? Caller and callee save conventions for MIPS
(5)
Basic Parameter Passing
arg1: arg2: .data .word 22, 20, 16, 4 .word 33,34,45,8 .text addi $t0, $0, 4 move $t3, $0 move $t1, $0 move $t2, $0 beq $t0, $0, exit addi $t0, $t0, -1 lw $a0, arg1($t1) lw $a1, arg2($t2) jal func add $t3, $t3, $v0 addi $t1, $t1, 4 addi $t2, $t2, 4 j loop sub $v0, $a0, $a1 jr $ra ---
Register usage What about nested calls? What about excess arguments?
loop:
PC + $31 4
PC $31
func: exit:
(6)
Leaf Procedure Example
C code:
int leaf_example (int g, h, i, j) { int f; f = (g + h) - (i + j); return f; }
Arguments g, , j are passed in $a0, , $a3 f in $s0 (we need to save $s0 on stack we will see why later) Results are returned in $v0, $v1
argument registers
$a0 $a1 $a2 $a3
procedure
$v0 result $v1 registers
(7)
Procedure Call Instructions
Procedure call: jump and link
jal ProcedureLabel
Address of following instruction put in $ra Jumps to target address
Procedure return: jump register
jr $ra
Copies $ra to program counter Can also be used for computed jumps
o e.g., for case/switch statements
Example:
(8)
Leaf Procedure Example
MIPS code:
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
(9)
Procedure Call Mechanics
High Address $fp
Old Stack Frame
System Wide Memory Map
$sp $sp
stack
$fp
arg registers return address dynamic data
$gp
static data text reserved
New Stack Frame
Saved registers
PC
$sp
local variables
compiler
compiler
ISA
Low Address
HW
addressing
(10)
Example of the Stack Frame
arg 1 arg 2 $fp
..
callee $s0-$s9 saved registers caller $a0-$a3 saved registers $t0-$t9 local variables
Call Sequence 1. place excess arguments 2. save caller save registers ($a0-$a3, $t0-$t9) 3. jal 4. allocate stack frame 5. save callee save registers ($s0-$s9, $fp, $ra) 6 set frame pointer Return 1. place function argument in $v0 2. restore callee save registers 3. restore $fp 4. pop frame 5. jr $31
(11)
..
$fp $sp $ra
Policy of Use Conventions
Name Register number $zero 0 $v0-$v1 2-3 $a0-$a3 4-7 $t0-$t7 8-15 $s0-$s7 16-23 $t8-$t9 24-25 $gp 28 $sp 29 $fp 30 $ra 31 Usage the constant value 0 values for results and expression evaluation arguments temporaries saved more temporaries global pointer stack pointer frame pointer return address
(12)
Summary: Register Usage
$a0 $a3: arguments (regs 4 7) $v0, $v1: result values (regs 2 and 3) $t0 $t9: temporaries
Can be overwritten by callee
$s0 $s7: saved
Must be saved/restored by callee
$gp: global pointer for static data (reg 28) $sp: stack pointer (reg 29) $fp: frame pointer (reg 30) $ra: return address (reg 31)
(13)
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
(14)
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
(15)
Template for a Procedure
1. Allocate stack frame (decrement stack pointer) 2. Save any registers (callee save registers) 3. Procedure body (remember some arguments may be on the stack!) 4. Restore registers (callee save registers) 5. Pop stack frame (increment stack pointer) 6. Return (jr $ra)
(16)
Non-Leaf Procedure Example
int fact (int n) { callee save if (n < 1) return f; else return n * fact(n - 1); restore
(17)
Non-Leaf Procedure Example
MIPS code:
fact: addi Callee save sw sw Termination slti Check beq addi Leaf Node addi jr L1: addi jal Recursive call lw lw Intermediate addi Node 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
(18)
Module Outline
Review ISA and understand instruction encodings Arithmetic and Logical Instructions Review memory organization Memory (data movement) instructions
Control flow instructions
Procedure/Function calls Program assembly, linking, & encoding
(19)
The Complete Picture
C program compiler Assembly assembler Object module Object libarary
Reading: 2.12, B2, B3, B4, B5
linker executable
loader memory
(20)
The Assembler
Create a binary encoding of all native instructions
Translation of all pseudo-instructions Computation of all branch offsets and jump addresses Symbol table for unresolved (library) references
Create an object file with all pertinent information Header (information)
Text segment Data segment Relocation information
Example:
Symbol table (21)
Assembly Process
One pass vs. two pass assembly Effect of fixed vs. variable length instructions
Time, space and one pass assembly
Local labels, global labels, external labels and the symbol table
What does mean when a symbol is unresolved?
Absolute addresses and re-location
(22)
Example
.data
L1: .word 0x44,22,33,55 # array .text .globl main main: la $t0, L1 li $t1, 4 add $t2, $t2, $zero lw $t3, 0($t0) add $t2, $t2, $t3 addi $t0, $t0, 4 addi $t1, $t1, -1 bne $t1, $zero, loop bgt $t2, $0, then move $s0, $t2 j exit move $s1, $t2 li $v0, 10 syscall
What changes when you relocate code?
00400000] 3c081001 [00400004] 34090004 [00400008] 01405020 [0040000c] 8d0b0000 [00400010] 014b5020 [00400014] 21080004 [00400018] 2129ffff [0040001c] 1520fffc [00400020] 000a082a [00400024] 14200003 [00400028] 000a8021 [0040002c] 0810000d [00400030] 000a8821 [00400034] 3402000a [00400038] 0000000c
Assembly Program
loop:
lui $8, 4097 [L1] ori $9, $0, 4 add $10, $10, $0 lw $11, 0($8) add $10, $10, $11 addi $8, $8, 4 addi $9, $9, -1 bne $9, $0, -16 [loop-0x0040001c] slt $1, $0, $10 bne $1, $0, 12 [then-0x00400024] addu $16, $0, $10 j 0x00400034 [exit] addu $17, $0, $10 ori $2, $0, 10 syscall
Assembled Binary
Native Instructions
then: exit:
(23)
Linker & Loader
Linker
Links independently compiled modules Determines real addresses Updates the executables with real addresses
Loader
As the name implies Specifics are operating system dependent
(24)
Linking
Program A Program B
header text
Assembly A
static data
Assembly B
cross reference labels
Why do we need independent compilation?
reloc symbol table debug
Study: Example on pg. 143
What are the issues with respect to independent compilation? references across files (can be to data or code!)
absolute addresses and relocation
(25)
Example:
# separate file .text addi $4, $0, 4 addi $5, $0, 5 jal func_add done 0x20040004 0x20050005 000011 0x0340200a 0x0000000c
0x00400000
0x00400004 0x00400008 0x0040000c 0x00400010 0x00400014 0x00400018 Ans: 0c100005
0x20040004
0x20050005 ? 0x3402000a 0x0000000c 0x008551020 0x03e00008
# separate file .text .globl func_add func_add: add $2, $4, $5 0x00851020 jr $31 0x03e00008
(26)
Loading a Program
Load from image file on disk into memory
1. Read header to determine segment sizes
2. Create virtual address space
3. Copy text and initialized data into memory
o Or set page table entries so they can be faulted in
4. Set up arguments on stack
5. Initialize registers (including $sp, $fp, $gp) 6. Jump to startup routine
o o Copies arguments to $a0, and calls main When main returns, do exit syscall
(27)
Dynamic Linking
Static Linking
All labels are resolved at link time Link all procedures that may be called by the program Size of executables?
Dynamic Linking: Only link/load library procedure when it is called
Requires procedure code to be relocatable Avoids image bloat caused by static linking of all (transitively) referenced libraries Automatically picks up new library versions
(28)
Lazy Linkage
Indirection table
Stub: Loads routine ID, Jump to linker/loader Linker/loader code
Dynamically mapped code
(29)
The Computing Model Revisited
Register File (Programmer Visible State) Memory Interface stack
0x00 0x01 0x02 0x03
0x1F
Processor Internal Buses Dynamic Data
Data segment (static) Text Segment Programmer Invisible State Program Counter Instruction register Kernel registers Arithmetic Logic Unit (ALU)
0xFFFFFFFF
Reserved
Memory Map
Program Execution and the von Neumann model
(30)
Summary
Instruction complexity is only one variable
lower instruction count vs. higher CPI / lower clock rate
Design Principles:
simplicity favors regularity smaller is faster good design demands compromise make the common case fast
Instruction set architecture
a very important abstraction indeed!
(31)
Study Guide
Compute number of bytes to encode a SPIM program What does it mean for a code segment to be relocatable? Identify addresses that need to be modified when a program is relocated.
Given the new start address modify the necessary addresses
Given the assembly of an independently compiled procedure, ensure that it follows the MIPS calling conventions, modifying it if necessary
(32)
Study Guide (cont.)
Given a SPIM program with nested procedures, ensure that you know what registers are stored in the stack as a consequence of a call Encode/disassemble jal and jr instructions Computation of jal encodings for independently compiled modules How can I make procedure calls faster?
Hint: What about a call is it that takes time?
How are independently compiled modules linked into a single executable? (assuming one calls a procedure located in another)
(33)
Glossary
Argument registers Caller save registers Callee save registers Disassembly Frame pointer Independent compilation Labels: local, global, external Linker/loader Linking: static vs. dynamic vs. lazy Native instructions Nested procedures Object file One/two pass assembly Procedure invocation Pseudo instructions Relocatable code Stack frame Stack pointer Symbol table Unresolved symbol
(34)
