Procedure

Dense

This article is probably the longest on the repo, but it is very important with respect to 213. You are expected to know how to manage a stack and implement both calling a function, and a function being called.

A procedure, or function is a reusable piece of software logic with a name, arguments, and a local scope. In some languages, the distinction is made in between logic that has a return value, in which case it is a function, and ones that don’t, in which case it’s a routine. Most modern languages will just call it a function, and many object oriented programming languages will call them methods when they’re inside classes, but they’re effectively the same thing.

Procedure calls cause the procedure to run with values bound to the arguments, and a possible result bound to the invocation.

Implementing Procedure return

To accurately implement a return from a procedure, we must implement dynamic control flow. To do so, there are a few steps involved.

First, the procedure we call must know where to come back to. For that to happen, the caller of a procedure must save the address for the procedure to return to, and must pass it to the callee somehow.

In CPSC 213, by convention, the caller will save the return address in r[6]. We also need a new instruction to read the PC, which is called gpc. Therefore all we have to do is get the current program counter, and store it into r6.

The callee will then assume the caller is implemented correctly and that the saved address is in r[6].

To jump to that address, we also need a new instruction in SM213 that jumps to a dynamic address, which is an indirect jump with assembly.

j o(rt) # where o is offset as an integer an t is a register

You will usually have something like this:

foo: gpc $6, r6
j bar # go to bar
... # do stuff after bar

bar: ...  # do stuff
	j (r6) # return

Note the offset of 6 with gpc corresponds to the size of the following jump instruction, otherwise the return would jump to foo’s jump, causing an infinite loop.

Activation of Procedures

Procedures start when called, ends when the procedure returns. There can be many activations of the same procedure alive at once. The memory needed for that call is in the context of CPSC 213, an activation frame. In general computer science, it is generally called a stack frame.

Activation Frame

Memory that stores the activation’s state. More plainly, it stores the information necessary for the currently executing procedure to execute correctly. This includes local variables, the return address, and arguments. The organization of the activation frame is outlined below.

Note that with respect to CPSC 213 and SM213, the stack of activation frames grows downwards in the order of addresses, so the more call frames you have, the lower the address.

The stack pointer, i.e. the pointer that points to the top of the stack at all times is by convention stored in r[5].

Special Registers

In dynamically controlled procedures in SM213, the following registers are now optionally reserved to help with the implementation of procedures:

• r0 for return values
• r5 for the pointer to the stack
• r6 for the return address

Stack Frame Layout

The stack frame is laid out as follows top to bottom:

• saved registers
• local variables
• return address
• arguments

Arguments are in the same order as declared, and so are the local variables. The return address is in between both. The return address only needs to be saved to the stack if that procedure calls another procedure. As an example, if we have the following procedure:

void doSmth(int a, int b){
	int x;
	int y;
	
	foo();
}

The activation frame for this procedure would look like this:

r[5] -> x                 x1000
        y                 x1004
	    return address    x1008
	    a                 x1012
	    b                 x1016

Division of Labor

When calling a function, the different components required to make it work are split in between the code calling the function, i.e. the caller, and the function being called, i.e. the callee. Both of these are further divided into the work they need to do at the beginning and at the end of the procedure, which is called prologue and epilogue respectively. They have effectively the same meaning as the literary terms if you’re familiar with those.

Caller Prologue

The callee prologue runs before the procedure is even called. If a procedure expects parameters, we have to pass it to the procedure being called. In order to do so, we save the arguments of that procedure to the stack. For each argument, increment the stack by the space they occupy (in SM213 it will always be 4 bytes) and increment the stack pointer accordingly. Remember that the order read left to right of the arguments is the order from top to bottom on the stack.

We then save the return address of the current procedure to the register reserved for this purpose, r[6].

The procedure is then called, and control is passed onto the callee.

Callee Prologue

The callee must then set itself up to be able to execute properly. First, if the callee calls another procedure, it must save the return address of the procedure that called it, otherwise when it finishes executing it wouldn’t know where to return.

As an example, let A be a procedure that calls the procedure we’re currently in, B. B calls another procedure C. If B doesn’t save the return address of A, when B calls C and saves its own return address to r[6], when B finishes executing and attempts to jump to r[6], it will jump… to itself, as the register has been clobbered by B. For this reason, we must save the return address to the stack if procedure B calls another procedure.

The other setup the callee needs to do before starting the actual procedure is allocating space for local variables. This is pretty straightforward and effectively follows exactly the same logic as allocating for arguments, simply increment the stack pointer by the size needed for local variables and use that space as needed during the procedure.

Callee Epilogue

Once the procedure is done, the procedure must clean up and free memory on the stack that it used during its runtime. The first step in doing so, is to simply decrement the stack pointer by the size of your local variables.

It must them give up control to the caller procedure, and to do so it will retrieve the return address stored in the stack if it called another procedure, or simply use the value already in r[6] if it does not call another procedure. Load that value into r[6], then deallocate the stack pointer if the return address was saved on the stack, and then jump to that address.

Caller Epilogue

The caller epilogue then has the very simple job of deallocating the space that was used to store arguments on the stack. Same as before, it’s simply a matter of decrementing the stack pointer by the total size of the arguments.

Creating the Stack

Before any procedure starts, including the main procedure that exists in every C and C++ program, every program thread will start with a hidden procedure. The name varies, usually start or entry point, sometimes crt0. This procedure initializes the stack.

Possible Optimizations

Some local variables don’t need to be on the stack. In CPSC 213 specifically, you do not need to allocate on the stack for loop variables.