Module 0304: Calling and returning from subroutines

Tak Auyeung, Ph.D.

November 9, 2021

Contents

 1 About this module
 2 C program example
 3 A quick digression to stack
 4 Calling and returning
 5 Will this work with recursion?

1 About this module

2 C program example

Let us example the code from the following program:

 
001void f() 
002{ 
003} 
004 
005int main() 
006{ 
007  f(); 
008  f(); 
009  return 0; 
010}

Calling a subroutine does not seem difficult at all, as we can use an unconditional branch to continue execution from the caller to the called subroutine (callee). The difficult part is how we return to the caller at the end of the execution of a callee.

At the end of executing a called subroutine, the processor needs to figure out where to continue execution in the caller. Given the instruction set of TTP, this means that location must be remembered somewhere in memory.

3 A quick digression to stack

A “stack” is a data structure that enforces the LIFO (last-in-first-out) order. As a data structure in C++, a stack is often implemented as a linked list of nodes. However, this is rather inefficient from the perspective of low-level code that is written in assembly.

In assembly language, a stack is implemented by a stack pointer (SP) and an area reserved for the stack. The stack pointer always points to “the last item stored on stack”. This automatically makes the location pointed by the SP also the first item to retrieve due to the LIFO nature of a stack.

Let us assume the stack area is reserved as a static global array called “stack” as follows:

 
001#define STACKSIZE 32 
002uint8_t stack[STACKSIZE]; 
003uint8_t *SP;

Note how the stack point is declared as a pointer to an element in the stack array.

In TTP, we assume the stack is from location 255 to the last byte available after the program takes up space. We also have to designate a register to be the stack pointer. For the rest of this discussion, we assume register D is the stack pointer.

To facilitate efficient use of instructions, a stack grows “down” instead of up. This means that as more items are added to the stack, the stack pointer moves down instead of up.

Because the SP is assumed to be pointing to the last item stored (also called pushed), the code to store something new is as follows:

 
001  SP--; // reserve space on stack 
002  *(SP)=x; // now store x to the newly reserved location

To retrieve (also referred to as pop) the most recently stored item that is still on stack and “remove” it at the same time, we can use the following code:

 
001  x=*(SP); // retrieve the most recently stored item 
002  SP++;    // deallocate (free) the space

Due to this methods, the proper way to initialize the SP is to make point to the byte that is just one past the end of the stack area:

 
001  SP=stack+STACKSIZE;

This seems to cause a problem because it is pointing past the allocated area. However, remember that when we push items on a stack, we first decrement the SP, and as a result, the initial value of SP is never used for dereferencing.

4 Calling and returning

The code to a subroutine has two distinct parts. The first part is to set for the return address. This allows the called subroutine to continue execution in the caller. The second part is to continue execution in the subroutine.

Let us examine the TTP assembly code to do this:

 
001  dec  d      // allocate a byte on stack 
002  ldi  c,L1   // this is the return address 
003  st   (d),c  // now store it on stack 
004  jmpi f      // continue execution in subroutine 
005L1: // continuation point of caller

Assuming the return address is stored on the stack, at the end of a subroutine, the following code can be used to return to the caller:

 
001  ld   a,(d)  // retrieve return address 
002  inc  d      // deallocate location from stack 
003  jmp  a      // continue execution in caller

5 Will this work with recursion?

Yes, it will.

The important part is that there is a return address stored on stack for each invocation of a subroutine.