Section 2.8 Calling Functions
As soon as programs get larger there is a danger of producing spaghetti code, i.e. writing very large chunks of code that does not have a clear focus but does multiple things all at once. Such code is hard to understand and almost never correct. Therefore, we want to break up programs into smaller modules with clear responsibilities. Each module consists of a set of functions and is grouped in one sometimes a few translation units. The benefit of writing a subroutine for each single task is that we can develop, debug, test, and reuse such subroutines individually. In this section, we look at the mechanics of defining subroutines in machine code and making them interact using function calls.
Consider the following piece of code that calls a function
bar: .text
foo:
addu $t0 $a0 $a1
jal bar
addu $v0 $v0 $t0
jr $ra
First of all,
jal jumps to the function bar and bar, being a function, will ultimately return to its caller, which is our function foo by executing the instruction jr $ra. Remember that jal puts the address of the instruction behind jal into register $ra before jumping. This allows bar to return to from where it was called.Let us assume that
bar is defined in a different translation unit that we do not make any assumption about. So, how can we know that the value we stored into $t0 with the first addu is still intact? Now you might say that we have to look inside the code of bar to be sure that it doesn't overwrite $t0. This is a bad idea for several reasons: First, if the project is bigger this may mean that you have to look at way more code than your own. Above a certain code size, this is no longer feasible. Second, the implementation of bar may change in the future and so might its usage of $t0. So it is a good idea to make as few assumptions as possible about the inner workings of bar. Pessimistically, we have to assume that bar uses $t0 for its own purposes.One way to “transport” a value over a function call might be to store the value at some memory address specifically chosen for this purpose. This however does not work for recursive functions. A function \(f\) is called recursively if, during execution there is a call to \(f\) before all previous calls have returned. In this case, we would need multiple such memory cells. The following execution trace illustrates the problem:
f g f
...
sw $t0 p
jal g
...
jal f
...
sw $t0 p
jal g
lw $t0 p
...
jr $ra
...
jr $ra
lw $t0 p
...
jr $ra
f is called a second time before the first call returned. Hence, the second store sw $t0 p would overwrite the saved value of $t0 at p.So, we need to allocate space in memory for every call to save the registers of this particular instance. Because each function returns before its caller, we can organize this memory using a stack. A stack is a data structure (a way to organize data) with the policy that data can only be removed from the data structure in the reverse order of their insertion which means that the last in is first out (LIFO). To this end, each function that wants to save register contents allocates a stack frame (certain amount of bytes) on the stack where the register contents can be saved. Allocation is simple because it is a stack: One register that holds the current height of the stack is sufficient. In practice this register, called the stack pointer, points to the last byte that is currently on the stack. Since the stack grows downwards decreasing the stack pointer by \(n\) allocates \(n\) bytes on the stack. On MIPS systems register 29 is assigned the role of the stack pointer and therefore bears the short name
$sp. The following listing extends the example program above with the allocation and de-allocation of a stack frame and loads and stores to save and restore the values of $t0 and $ra. .text
foo:
addiu $sp $sp -8 # decrease $sp, allocate frame
addu $t0 $a0 $a1
sw $t0 0($sp) # save $t0
sw $ra 4($sp) # save $ra
jal bar
lw $ra 4($sp) # restore $ra
lw $t0 0($sp) # restore $t0
addu $v0 $v0 $t0
addiu $sp $sp 8 # deallocate frame
jr $ra
Typically, the size of the stack frame is constant (i.e. the same for all program executions). In some situations, one wants to allocate more memory on the stack, maybe also dependent on some input. In such a case, it may not be statically known how deep the stack pointer will move throughout the execution of a procedure's code. This makes using constant offsets in the form of immediates like in the example above impossible. In such a situation, one uses an additional register that is called the frame pointer. In MIPS, frame pointers reside in register 30 and are called
$fp. It is common to set the frame pointer right at the entrance of the procedure by saving the old frame pointer and setting the frame pointer to the current stack pointer value.The stack frame (see Figure 2.8.1) typically contains the following elements:
- Arguments, i.e. values that are passed to the procedure. (The convention in MIPS is that the first four arguments are passed in registers
$a0to$a3, hence their name. Remaining arguments are passed on the stack.) - Space to store the contents of registers that …
- the procedure wants to overwrite but the caller expects to be unchanged. These are so-called callee-save registers because the callee has to make sure the values of these registers are preserved from entering the procedure to its return.
- might be overwritten by procedures that are called by the procedure. These are so-called caller-save registers because the caller needs to preserve their value across a procedure call.
- space for further data local to the procedure that don't fit into a register because there is either no free register available or the data is too big to fit into a 32-bit register.
The stack frame is constructed by the caller and the callee together. The caller puts additional arguments on the stack while the callee allocates space to save registers as discussed above. The code of the procedure that builds and tears down the stack frame is called the prologue and the epilogue.
Subsection 2.8.1 Recursion
Let us reconsider our initial example, the computation of the factorial function. The standard way of defining the factorial function mathematically is by recursion:
\begin{equation*}
f_r(n)\defeq\begin{cases}
n\cdot f_r(n-1) \amp n \ge 1 \\
1 \amp n \lt 1
\end{cases}
\end{equation*}
The implementation in Listing 2.3.4 is not recursive: It does not contain any procedure calls especially not to itself. This implementation is based on a different but equivalent definition of the factorial function which is tail recursive
\begin{equation*}
f_e(n, r)\defeq\begin{cases}
f_e(n-1, n\cdot r) \amp n \ge 1 \\
r \amp n \lt 1
\end{cases}
\end{equation*}
Tail recursive means that the result of the recursive function application is the result of the function and does not appear in a larger expression.
Let us look at the implementations of both variants in MIPS assembly shown in Figure 2.8.2
.text
.globl fac
fac:
li $v0 1
blez $a0 end
loop:
mul $v0 $v0 $a0
addiu $a0 $a0 -1
bgtz $a0 loop
end:
jr $ra
.text
.globl fac_rec
fac_rec:
li $v0 1
blez $a0 end
addiu $sp $sp -8
sw $ra 0($sp)
sw $a0 4($sp)
addiu $a0 $a0 -1
jal fac_rec
lw $a0 4($sp)
mul $v0 $v0 $a0
lw $ra 0($sp)
addiu $sp $sp 8
end:
jr $ra
The recursive implementation incurs a significant amount of overhead to create and deallocate the stack frame and to save and restore the arguments that need to be saved across the recursive procedure call. Observing the evolution of the stack during an execution of the recursive implementation, one can see that the first \(n\) calls only allocate frames and store the respective argument on the stack. implicitly, it builds a list of all numbers from \(1\) to \(n\) and ever the same return address. Only when returning from the recursive calls the computation is performed.
Subsection 2.8.2 The Calling Convention
Calling conventions regulate who has to save register contents when. Registers that the callee may change at its own discretion are called caller-save because the caller is responsible to save their contents before calling a function. Registers that the caller can assume to be unchanged by a call are called callee-save because the callee has to guarantee that when the function returns, these registers have the same contents as when the function was entered.
For efficiency reasons, callers pass the arguments to called functions in registers. In MIPS registers
$a0 to $a3 are used for this purpose. The result of a function call (i.e. a value that the called function wants to return to the caller) is passed in $v0. The following table shows all MIPS registers and their role in the calling convention.| Number | Name | save | Comment |
| 0 | $zero |
-- | Always reads zero |
| 1 | $at |
-- | Reserved. Used by linker. |
| 2 –3 |
$v0–$v1
|
caller | Return values |
| 4 –7 |
$a0–$a3
|
caller | First four arguments |
| 8 –15 |
$t0–$t7
|
caller | Temporaries |
| 16–23 |
$s0–$s7
|
callee | Temporaries |
| 24–25 |
$t8–$t9
|
caller | Temporaries |
| 26–27 |
$k0–$k1
|
-- | Reserved. Used by operating system |
| 28 | $gp |
-- | Global data pointer. Used to address elements in the global data segment. |
| 29 | $sp |
callee | Stack pointer |
| 30 | $fp |
callee | Frame pointer |
| 31 | $ra |
caller | Return address |
