A subprogram is a sequence of instructions whose execution is invoked from one or more remote locations in a program, with the expectation that when the subprogram execution is complete, execution resumes at the instruction after the one that invoked the subprogram. In high-level languages, subprograms are also called subroutines, procedures, and functions. In object-oriented languages, they are usually called methods or constructors. In most modern high-level languages, subprograms can have parameters, local variables, and returned values.

Communication between a subprogram and its callers is governed by its subprogram linkage protocol. For subprograms that do not call other subprograms, a simple protocol based on register usage conventions can be used. For more complex subprograms a protocol based on a runtime stack is needed.

Much of the terminology concerning subprograms in MAL is the same for all assembly languages. MAL differs in the details of its register usage conventions and the particular instructions used for subprograms.

At the assembly language level, use of subprograms requires subprogram linkage protocols. These protocols involve designating registers for special purposes and the use of special instructions for subprogram calls and returns.

MIPS has two primary types of registers, integer registers and floating point registers. In addition, MIPS has a small number of special purpose control registers.

The protocol described here works well for subprogram linkage if the following conditions are satisfied:

• The caller does not expect to access values in $t0-$t9 after the subprogram call for values that were placed there before the call.
• the subprogram has no more than 4 parameters,
• the subprogram does not call other subprograms, and
• the subprogram does not need more than 10 registers for local variables.

The simple program linkage protocol is based on the register usage conventions. It requires the following behavior from the caller and the subprogram.

• The caller puts parameter values into $a0 - $a3 prior to calling the subprogram.
• The caller then calls the subprogram using jal subprogram-label.

• The subprogram gets parameter values from $a0 through $a3.
• The subprogram uses registers $t0 through $t9 for all local variables.
• The subprogram puts return values into registers $v0 and $v1 prior to returning.
• The subprogram returns using jr $ra.

• The caller takes values $v0 and/or $v1 after the call.

If the conditions for the simple subprogram linkage protocol are not met then a runtime stack-based protocol is needed. The runtime stack is a memory data structure that can hold any data needed by subprograms that cannot be held in registers. MAL register usage conventions designate the register $sp for use as a pointer for a runtime stack.

As in the simple protocol, the jal (or jalr) instruction is used for calling a subprogram. Returning from the subprogram is accomplished with the instruction jr $ra.

The difference is that each time the subprogram is invoked, it allocates a chunk of stack frame space for itself at the beginning of its code and deallocates it just before it returns. This chunk of runtime stack space is called a stack frame. It is also known as an activation record. In effect, a subprogram "pushes" a stack frame onto the runtime stack at the start of its execution and "pops" it at the end of its execution. Data in the stack frame is accessed using loads and stores with base-displacement addressing.

With base-displacement addressing, an item in memory is specified by operand with the form displacement(base register). The base register holds a memory address. The displacement specifies how far the memory item is from the memory location that is addressed by the base register. In other words, the operand displacement(base-register) specifies a memory location whose address is

contents of base register + displacement.

The displacement must be an integer constant, but it can be either positive or negative.

If you are writing code for a subprogram that needs to use a stack frame then take the time to figure out how big the stack frame needs to be. Also, you should carefully document the displacements that you will be using for each item in the stack frame.

In MAL, as in almost all machines, stack space starts at the the high end of memory with the stack top at the lowest address in the stack. The register designated as a stack pointer has alternate name $sp. Thus if you want to allocate a stack frame of size sz you should use the following code:

    sub	$sp, $sp, sz
      

The stack frame lies at and above the memory location addressed by $sp so all displacements should be non-negative.

Before each possible return, or exit if you are writing main subprogram code, you should use the following code to deallocate the stack frame:

    add	$sp, $sp, sz
      

Stack frame access in MAL, as in most machines, uses base-displacement addressing with $sp as the base register.

To save register reg on the stack with displacement disp, use the following code:

    sw      $reg, disp($sp)

The register value can be restored with the following code:

    lw      $reg, disp($sp)

A stack frame can be used for the following purposes.

• Normally, subprograms do not use "preserved across calls" registers. However they can be used if the subprogram saves the registers on the runtime stack at the beginning of the subprogram call and restores these registers just before returning.

• When a subprogram runs out of registers, it can assign space on the runtime stack to additional local variables. These additional variables are then accessed with load and store instructions.

• Saving "not preserved across calls" registers before the subprogram calls another subprogram and restoring the registers after the call returns. The register $ra should always be handled this way.

• Dealing with more than 4 parameters. This requires modifying the requirements for the caller to push additional parameters onto the runtime stack.

Always change $sp by multiples of 4. Otherwise, you will end up with unaligned memory references. Also take great care to ensure that no matter how the subprogram code is executed, it always deallocates the same amount of stack space that it allocates. Otherwise, it is likely that a subprogram call that returns later will have the wrong value restored into $ra. This is a very difficult error to debug.