05. Stack and subroutines
Code reuse task
Program once, use often
- Subtasks (printing, sorting, function evaluation etc.)
- Subtask parameters (variable number, text, array size, function arguments etc.)
- Interface / implementation separation
- → Subroutine call conventions:
- Registers integrity (before end after call, incl. PC )
- Arguments passing
- Result gathering
Subroutines
Subroutine: continuous part of text section, that
- Can be executed more than once
- Can be reached by jumping to from any other address of text section
- Restores caller address (jumps «back») ti continue execution
⇒ Hardware solution:
jalr keeper_register, address_register
jal address_offset (type i, usually it's enough; use $ra as keeper)
jr keeper_register
1 # text section starts
2 # …
3 li $t1 5
4 li $t2 6
5 li $t3 7
6 # now calling subroutine
7 jal treug
8 # do something else
9 # …
10 # Exit from orpgram
11 li $v0 10
12 syscall
13 # …
14 # Subroutiine
15 treug: move $t0 $zero
16 add $t4 $t1 $t2
17 add $t5 $t2 $t3
18 add $t6 $t3 $t1
19 bgt $t3 $t4 not
20 bgt $t1 $t5 not
21 bgt $t2 $t6 not
22 li $t0 1
23 not: jr $ra
When calling $ra (rarely other) keeps the address of the next cell
Subroutine should keep $ra intact
To return, subroutine executes jr $ra (just normal indirect jump)
What it solves:
- Atomic call
- Arbitrary call and return
What it solves not:
- Transparency of reuse:
- Register integrity
- Arguments passing
- Return value gathering
Label names clash (when accidentally using the same name of label in both main code and subroutine)
Subsequent and recursive call (the only $ra)
⇒ All these are matter of convention, except /!\, which needs assembler to support «local» labels or namespaces
Terminal subroutine convention
Terminal subroutine must not call other subroutines.
- Subroutine S is terminal
S is called by $jal
Return from S is performed by $jr $ra
- Register usage:
$t0 - $t9 — temporary, can modify upon return
$s0 - $s7 — static, can not modify upon return
$a0 - $a3 — arguments
$v0 - $v1 — return values
No restriction of memory modification.
This subroutine uses terminal subroutine convention:
1 # …
2 li $a0 5
3 li $a1 6
4 li $a2 7
5 # …
6 jal treug
7 # keep the result in static register
8 move $s1 $v0
9 # …
10 li $v0 10
11 syscall
12 …
13 # Subroutine
14 treug: move $v0 $zero
15 add $t4 $a0 $a1
16 add $t5 $a1 $a2
17 add $t6 $a2 $a0
18 bgt $a2 $t4 not
19 bgt $a0 $t5 not
20 bgt $a1 $t6 not
21 li $v0 1
22 not: jr $ra
Stack
- Stack abstraction: operations, top access, LIFO, empty/overfull states
Requirements and restrictions:
- Object is constant-sized (preferably word)
- Stack memory is «actually half-infinite»
- Stack Pointer (preferably register)
Hardware implementation:
- Super fast small stack (just a lot of registers)
- Atomic push an pop (PDP11 ++/--)
- Indirect addressing (double Indirect addressing?)
MIPS:
Stack pointer: $sp
Stack settles in common memory, grows from 0x7ffffffc downwards
- Just under kernel space, so stack underflow is exception
Stack initial pointer is 0x7fffeffc (hence 0x7ffffffc-0x7fffeffc is buffer)
Stack lowest edge is 0x10040000 (this address is used for «heap», so it may be higher)
- No hardware check of stack/heap overlap
push/pop are not atomic:
push: first decrement $sp by 4, then store a value
pop: first load a value, then increment stack by 4
⇒ this convention leaves 0x7fffeffc unused
Commands example
1 li $t1, 123 # something
2 addi $sp, $sp, -4 # push.1
3 sw $t1, ($sp) # push.2
4 addi $t2, $t1, 100 # another something
5 addi $sp, $sp, -4 # push.1
6 sw $t2, ($sp) # push.2
7 lw $t3, ($sp) # read stack edge
8 lw $t4, 4($sp) # read second stack value
9 lw $t0, ($sp) # pop.1
10 addi $sp, $sp, 4 # pop.2
11 addi $sp, $sp, -4 # push.1
12 sw $zero, ($sp) # push.2
To read N-th item of stack we just provide N*4 offset from $sp
- (so positive offset is easier to read)
- There's no «automatic erasing» of popped stack items, they're still there, but no guarantee in that
- No single pseudoinstruction is used!
So using stack is:
more effective than direct lw/sw because of no pseudoinstructions
using relative addressing over $sp and $sp is changing, so beware!
- providing constant offsets instead of labels
- fragile on stack corruption / overflow / underflow
Universal subroutines
Subsequent and recursive calls ⇒ we need to keep every old $ra values somewhere.
If we need memory in addition to registers, it should be call-specific
If we modify $s-type registers, we need to keep/restore them
It can be done with stack.
1 .data
2 n: .word 7
3 res: .word 0
4
5 .text
6 # call fact:
7 lw $a0 n
8 jal fact
9 sw $v0 res
10
11 fact: addiu $sp $sp -4 # keep $ra
12 sw $ra ($sp)
13 addiu $sp $sp -4 # keep $s0
14 sw $s0 ($sp)
15
16 move $s0 $a0 # calculate n-1
17 subi $a0 $a0, 1
18 ble $a0 1 done # if n<2, done
19
20 jal fact # calculate fact(n-1)
21 mul $s0 $s0 $v0 # $s0 survives a call
22
23 done: move $v0, $s0 # return value
24 lw $s0 ($sp) # restore $s0
25 addiu $sp $sp 4
26 lw $ra ($sp) # restore $ra
27 addiu $sp $sp 4
28 jr $ra
Trace this program by Mars and observe how $sp and stack memory is changed.
Universal simple convention
$a registers for arguments
Call with jal or jalr
Do not write to the stack above the point it was set when the subroutine is called
$ra should be kept in stack
Return value is stored in $v0 (and $v1)
Used $s registers must be kept on stack
- All additional memory to use is taken from stack (at any time and actually unlimited)
Program restores $sp to its initial state (pointing to return address) before return (all memory above old $sp is considered free)
Program restores $ra and $s registers from stack
Return with jr $ra
- Prologue
- initial part of subroutine code, which stores program state (keeps registers etc.)
- Epilogue
- final part of subroutine code, which restores program state (loads registers etc.)
- Preamble
part of caller code just before jal subroutine preparing some subroutine-specific environment
Example with preamble, that narrows prologue and epilogue:
1 fact: addiu $sp $sp -4 # keep $ra
2 sw $ra ($sp)
3
4 move $t0 $a0
5 subi $a0 $a0, 1
6 ble $a0 1 done
7
8 addiu $sp $sp -4 # keep N
9 sw $t0 ($sp)
10 jal fact
11 lw $t1 ($sp) # keep N
12 addiu $sp $sp 4
13 mul $t0 $t1 $v0
14
15 done: move $v0, $t0 # return value
16 lw $ra ($sp) # restore $ra
17 addiu $sp $sp 4
18 jr $ra
H/W
TODO
EJudge: CheckTriangles 'Check triangles'
Write a subroutine check, which inputs 3 integers and checks if they can form a triangle (a=b+c is valid). Subroutine returns 1 if they can. 2 if not, and 0 if they were 0, 0, 0. Write a program that calls check and prints 'Y' on 1, or 'N'on 2, until check returns 0; then program must exit.
1 2 3 4 5 6 1 4 8 0 0 0
Y Y N
EJudge: LeftDigits 'Lefty digits'
Write a program that inputs a cardinal N, an then inputs N numbers (may be negative). After that it outputs only first digits of these numbers (in one line). You inclined to write a subroutine "first", that accepts a number (via $a0) and returns last digit (via $v0).
5 -2345 7345623 -4321 2 7543
27427
EJudge: FuncSort 'Just sort'
Write a program, that inputs N, then N numbers, and then outputs them sorted in one line. You may write a sort subroutine, but it is not mandatory here.
5 -123 34 546 0 -100500
-100500 -123 0 34 546
EJudge: RecursiveGCD 'Greatest common divisor'
Write a program that inputs two numbers and output its' Greatest_common_divisor. You must write a recursive subroutine gcd to complete this task.
2467080 49360080
9240