07. Call frame and macros
Convention on multi-argument (>4) subroutine:
- more registers (bad)
- memory block and pointer (good, but needs dynamic memory heap alloc/dealloc)
- on stack
- Convention on extra memory variables in subroutine
- stack
Frame pointer
(Very slightly) complex example:
1 # ... some code, now calling subr
2
3 # preamble: passing arguments
4 addiu $sp $sp -4
5 sw $t0 ($sp) # variable A0 +16
6 addiu $sp $sp -4
7 sw $t1 ($sp) # variable B0 +12
8 addiu $sp $sp -4
9 sw $t2 ($sp) # variable A1 +8
10 addiu $sp $sp -4
11 sw $t3 ($sp) # variable B1 +4
12 addiu $sp $sp -4
13 sw $t4 ($sp) # variable x
14
15 jal subr
16
17 # now restoring $sp dropping 5 cells
18 addiu $sp $sp 20
19
20 # ... some other code
21 break 0
22
23 subr: # Prologue: keep $ra and all used $s*; allocate local vars
24 addiu $sp $sp -4 # storing $ra
25 sw $ra ($sp)
26
27 # we will use $s0 as non-volatile register, keep it
28 addiu $sp $sp -4
29 sw $s0 ($sp) # variable x
30
31 # we want to use local variable Y at stack, allocate it
32 addiu $sp $sp -4
33 sw $zero ($sp)
34
35 # Prologue end
36 # Now Y is ($sp), x is 12($sp), B1 is 16($sp) … a is 28($sp)
37
38 # … do something
39
40 # Epilogue:
41 # drop local variables
42 addiu $sp $sp 4
43
44 # restore $s* and $ra
45 lw $s0 ($sp)
46 lw $ra 4($sp)
47 addiu $sp $sp 8
48
49 jr $ra
We need to:
track all arguments' stack offset
- …and it's changed every new local variable is added
track all variables' stack offset
- …same thing
- Drop all the local variables in epilogue
Offset recalculating is hell. Let's evade this sacrificing a register — $fp, frame pointer.
$fp:
Keeps $sp state before preamble
Useful when calculating argument/local variable offset (which never changes)
To be kept along with $ra and $s*
Simplified calling convention with frame
As always, there's 4 parts: preamble, prologue, epilogue and stack restore
(preamble) Up to 4 arguments are stored in $a0 … $a3
- (preamble) More than 4 arguments are stored in stack
jal to call
- No stack modification above current ($sp)
(prologue) Store current $fp (outer subroutine frame) on -4($sp), no $sp change here
(prologue) Store current $sp to $fp
(prologue) Allocate stack space for $ra, $s* and local variables
(prologue) Store $ra, $s* and local variables to allocated memory (using fixed $fp offset is possible)
Return value(s) in $v0($v1)
(epilogue) Restore $ra and $s*
(epilogue) Drop the whole frame by restoring $sp from $fp,
Return with jr $ra
- (stack restore) If there was more than 4 arguments, drop them from stack
Notes:
This is not universal convention.
- One can imagine «more useful» conventions
- Using Offsets instead of names is still a bit uneasy
.eqv directive and .text/.data mixing
Compile this:
.eqv string value is simple macro: assembler will replace every string with value
There's only one .data or .text, section, every next .data or .text continues filling corresponded section with data or code
Do not use «b» name, it confuses with b command; this is bug in Mars
Frame usage example
1 .data
2 .eqv SZ 20 # «constant»
3 Arr: .space SZ
4 EndArr: .align 2 # just to mark array end
5 .text
6
7 main: la $t1 Arr # input integers
8 la $t2 EndArr
9 input: li $v0 5
10 syscall
11 sw $v0 ($t1)
12 addiu $t1 $t1 4
13 bne $t2 $t1 input
14
15 li $a0 SZ # call sort
16 la $a1 Arr
17 jal sort
18
19 move $t1 $v1 # Address
20 move $t2 $v0 # size in bites
21 sra $t2 $t2 2 # sise in words
22
23 li $v0 11
24 li $a0 '\n'
25 syscall
26
27 output: li $v0 1
28 lw $a0 ($t1)
29 syscall
30 li $a0 '\n'
31 li $v0 11
32 syscall
33 sw $v0 ($t1)
34 addiu $t1 $t1 4
35 addiu $t2 $t2 -1
36 bgtz $t2 output
37
38 li $v0 10
39 syscall
40
41 sort: # a0 — array size
42 # a1 — array address
43 # v0 — output array size (same as input :)
44 # v1 — aoutput array address (same as input :)
45 .eqv .RA -8($fp) # Offest of $ra storage
46 .eqv .S0 -12($fp) # Offset of $s0 storage
47 .eqv .S1 -16($fp) # Offest of $s1 storage
48 .eqv .ARR -20($fp) # Local variable
49 .eqv .SIZE -24($fp) # Local variable
50 .eqv FSIZE -24 # Frame size
51 sw $fp -4($sp) # Store old frame
52 move $fp $sp # Allocate new frame
53 addiu $sp $sp FSIZE # …on stack
54 sw $ra .RA # Store registers
55 sw $s0 .S0
56 sw $s1 .S1
57
58 sw $a0 .SIZE # Store arguments: size
59 sw $a1 .ARR # …and array address
60
61 move $s0 $a0 # We can use $s* non-volatile registers
62 move $s1 $a1 # when calling any subroutine
63 fnext: move $a0 $s0
64 move $a1 $s1
65 jal getmin
66 lw $t0 ($v0)
67 lw $t1 ($s1)
68 sw $t0 ($s1)
69 sw $t1 ($v0)
70 addiu $s1 $s1 4
71 addiu $s0 $s0 -4
72 bleu $a0 4 fnext
73
74 lw $v0 .SIZE # local variables
75 lw $v1 .ARR
76
77 lw $ra .RA # Restore registers
78 lw $s0 .S0
79 lw $s1 .S1
80 move $sp $fp # Restore stack
81 lw $fp -4($sp) # Restore old frame
82 jr $ra
83
84 getmin: # terminal subroutine, we can relax a bit :)
85 # a0 — array size
86 # a1 — array address
87 # v0 — return minimal element address
88 lw $t0 ($a1)
89 move $v0 $a1
90 gmnext: addiu $a0 $a0 -4
91 addiu $a1 $a1 4
92 blez $a0 gmfin
93 lw $t1 ($a1)
94 bge $t1 $t0 gmnext
95 move $t0 $t1
96 move $v0 $a1
97 j gmnext
98 gmfin: jr $ra
Notes
Dots in names like .S0 etc. have not any sense except aesthetical
We use $s0 and $s1 as non-volatile register, so we ought to keep them
- We also use (solely in educational purpose) two local variables on stack
We need to recalculate FZISE if we add another variable/register keep, bu it is just equals to last used stack cell offset
Industrial conventions
What we need to add to convention to make in «universal»?
- C1 (mathematical coprocessor) calling conventions (arguments, return values, volatility)
- Huge argument passing (e. g. arrays). Evidently address + size, but memory allocation/deallocation?
- No convention about «side-effect» (modifying non-stack memory)
- In particular no convention about returning large/huge data
- …
Full ABI documentation (the more universal is ABI, the more complex it became):
MIPSpro™ N32 ABI Handbook — more than one ABI
Пояснительный текст относительно этих ABI, including remarks like «nodoy use this part IRL» ☺
SYSTEM V APPLICATION BINARY INTERFACE Full ABI (250 pages!)
Industrial ABI is not intended for use manually, in mostly describes what code higher-language compilers (e. g. C compiler) shall generate.
- Fixed frame size
- ⇒ simplified debugging/tracing
- All registers are kept/restored
Standard fixed code for preamble, prologue and epilogue
Plus:
All generated labels must be local (no name clash)
- Multi-file compilation requires function and global variables metadata
- Typed languages require metadata (size and structure) for complex types
- …
Strings
String is just byte sequence in memory with undefined size. String operations (s. a. input/output) process all the non-zero bytes until. Zero byte is string terminator (aka EOL).
Strings are just conventions and has no hardware support in MIPS.
1 .data
2 Ex1: .asciiz "This is example"
3 Ex2: .asciiz "This is\nanother example\n"
4 Ex3: .ascii "This is example without zero."
5 Ex4: .ascii "Nobody khows when it terminates"
6 .byte 33
7 .byte 0
8 .text
9 li $v0 4
10 la $a0 Ex1
11 syscall
12 li $v0 4
13 la $a0 Ex2
14 syscall
15 li $v0 4
16 la $a0 Ex3
17 syscall
18 li $v0 4
19 la $a0 Ex4
20 syscall
Macros
Macro:
- write once, use often
- substitution expands code
Simple form:
.macro name
...
any code
...
.end_macroE. g.
Parametric macro:
.macro name %parameter1 %parameter2 … # ... code using %parameter1 %parameter2 etc. .end_macro
E. g.
Note:
- There is no type check, just substitution
- Although one can write several macro with same name, but different number of parameters
Local labels:
- All labels inside macro are translated like this: 'label' → 'label_M№'
- → Label clash avoid
⇒ Using .data/.text mix for local data labels:
.macro printS %message
.data
msg: .asciiz %message
.text li $v0 4
la $a0 msg
syscall
.end_macro
# ....
printS "Hello!"Macro explosion: when expanding macros within macros within macros etc, te size of resulting code can be abruptly™ huge.
H/W
EJudge: ASCIIGrid 'Character grid'
Input:Wrirte a program that inputs ordinals M an N, and outputs MxN grid made with «+» and «-». You should write a macro that accepts three parameters: a number of cells and two characters, and outputs a line like this:
printline 4, '+', '-'
- →
+-+-+-+-+
Output:3 4
+-+-+-+ | | | | +-+-+-+ | | | | +-+-+-+ | | | | +-+-+-+ | | | | +-+-+-+
EJudge: CrtDraw 'ASCII art'
Input:Write a program, that input an odd number of integers. Each odd input is x coordinate, and each even input is y coordinate of a certain dot. If x is negative, input ends immediately and the program outputs 16×16 character matrix, containing '*' at places of the dots and '.' at empty places. The 0:0 coordinate is at upper-left corner (OX points right, OY points down).
Output:1 1 2 2 13 2 12 3 11 11 12 12 1 14 0 15 -1
................ .*.............. ..*..........*.. ............*... ................ ................ ................ ................ ................ ................ ................ ...........*.... ............*... ................ .*.............. *...............
EJudge: KeySort 'Key sorting'
Input:Write a program of key sorting. You should write a subroutine that accepts three arguments: array size (in words, not in bytes), array address, and comparison subroutine. You subroutine sorts an array and return array size in $v0 and array address in $v1. You subroutine should use comparing subroutine to determine if two elements is in order. Comparing subroutine accepts integers in $a0 and $a1 and returns 1 in $v0 if they're in proper order, and 0 otherwise. Write two comparing subroutines: first for $a0 < $a1, second for $a0%10 > $a1%10. Please use bubble sort algorithm (ar any other stable). Your program reads an ordinal N, then an integer T, then N integers. If T is 0, use first comparison subroutine, if T != 0, use second one. Then output an array.
Output:9 0 34 456 2 5 567 2 2 0 42
0 2 2 2 5 34 42 456 567
EJudge: ReverseString 'Reverse string'
Input:Write a program which accepts a sequence of non-empty strings (each not longer than 200 characters) and outputs every string backwards. Sequence ends with a string started from '.'; this final string is not printed. You should write a subroutine which accepts string address in $a0 and prints it backwards. Caution: if you want to use syscall 8, read carefully the documentation about '\n' at the end of the input string (it either can evolve or not, you should omit it).
Output:Write a program which accepts a sequence of strings and outputs every string backwards. Empty strings are treated as normal. .that's all
sgnirts fo ecneuqes a stpecca hcihw margorp a etirW .sdrawkcab gnirts yreve stuptuo dna .lamron sa detaert era sgnirts ytpmE