Review of the Fetch Execute Cycle
Before the compiled version of any subroutine starts to run, it must be loaded into the RAM, in its entirety. Each instruction of the machine code program will occupy a location in the memory, and each of these memory locations has an address. As per the fetch-execute cycle, the instructions of a program are fetched from memory into the CPU, decoded and executed, one at a time. With a regular sequence of instructions, a register inside the CPU known as the program counter contains the memory address of the next instruction to fetch. Each time another instruction is fetched, the program counter is incremented so that it is always pointing to the location of the next instruction to fetch. When one subroutine calls another, the caller must relinquish control of the CPU to the subroutine that it called. That means there needs to be a mechanism for the caller to pick up from where it left off once it gets control back.
Stacks
A stack is dynamic data structure. Stacks are employed by software and hardware engineers in several areas of computing including the evaluation of complex expressions, backtracking algorithms and memory management. A stack is a Last In First Out (LIFO) data structure. Take a look at this pile of dirty plates. The ones at the bottom were put there first, but you have to wash the ones at the top before you can get to them (by which time they will be very crusty).
When something is placed onto a stack, this is known as a push operation. When something is taken off a stack, this is known as a pop operation.
The Call Stack
The call stack is sometimes referred to as the execution stack, the machine stack and even the activation stack. More often than not, it is simply known as ‘the stack’. Understanding the call stack is important if you want to be able to work with parameters efficiently, and to understand advanced programming techniques such as recursion.
Each task (or each thread), which is usually comprised of many subroutines (sub procedures and functions), has its own call stack. Call stacks are maintained in the RAM by the operating system. The call stack is a dynamic data structure; it grows and shrinks while a task is running.
When one subroutine calls another, the call stack enables execution to return to the correct instruction of the caller once the subroutine that was called comes to an end. The call stack does this by storing the return address of the caller, that is the memory address in the program counter just before control was relinquished. The call stack also provides a mechanism for passing parameters between subroutines, and is a convenient place to store a subroutine’s local variables since these need only exist while the subroutine is running.
Examine the two programs below. ProcedureA calls ProcedureB and passes it two parameters. ProcedureB also has two local variables.
Sub ProcedureA()
Call ProcedureB(10, 20)
‘more code here
End Sub
Sub ProcedureB(BParameter1 As Integer, BParameter2 As Integer)
Dim BVariable1 As Integer
Dim BVariable2 As Integer
BVariable1 = 1
BVariable2 = 2
‘more code here
End Sub
When subroutine A calls subroutine B:
1.Parameters being passed are pushed onto the stack first (in reverse order)
2.The return address is then pushed onto stack (i.e. where to return to in ProcedureA when ProcedureB finishes)
3.ProcedureB starts to run
4.ProcedureB’s local variables are pushed onto stack
5.ProcedureB continues to run
So ProcedureB’s stack frame now looks like this:
Top of stack
————————–
BVariable2
BVariable1
ProcedureA’s Return Address
BParameter1
BParameter2
————————–
Bottom of stack
That stack is an abstract data type. It actually grows in memory from high addresses towards low addresses (the top of the stack is at lower numbered address locations), but it is useful to visualise the stack growing from the bottom up. The caller’s return address comes from the program counter; this is also sometimes called the Instruction Pointer (IP). While a subroutine is running, it can traverse up and down its own stack frame to get a hold of the parameter values and local variables it needs.
Now let’s consider what is going on when there are several procedures in a calling chain.
When ProcedureB then calls ProcedureC, which then calls ProcedureD
Sub ProcedureA()
Call ProcedureB(10, 20)
‘more code here
End Sub
Sub ProcedureB(BParameter1 As Integer, BParameter2 As Integer)
Dim BVariable1 As Integer
Dim BVariable2 As Integer
BVariable1 = 1
BVariable2 = 2
Call ProcedureC(30, 40)
‘more code here
End Sub
Sub ProcedureC(CParameter1 As Integer, CParameter2 As Integer)
Dim CVariable1 As Integer
Dim CVariable2 As Integer
CVariable1 = 3
CVariable2 = 4
Call ProcedureD(50, 60)
‘more code here
End Sub
Sub ProcedureD(DParameter1 As Integer, DParameter2 As Integer)
Dim DVariable1 As Integer
Dim DVariable2 As Integer
DVariable1 = 5
DVariable2 = 6
‘more code here
End Sub
Once ProcedureD is running, the stack now looks like this:
Top of stack
————————–
DVariable2
DVariable1
ProcedureC’s Return Address ProcedureD’s Stack Frame
DParameter1
DParameter2
————————–
CVariable2
CVariable1
ProcedureB’s Return Address ProcedureC’s Stack Frame
CParameter1
CParameter2
————————–
BVariable2
BVariable1
ProcedureA’s Return Address ProcedureB’s Stack Frame
BParameter1
BParameter2
————————–
Bottom of stack
Returning control to the caller
As each subroutine in the calling chain finishes, the stack is torn down (Last In First Out). When a subroutine is ready to return control its caller, items are popped of the stack one at a time in order to obtain the return address of its caller which is then used to update the program counter. The caller can then pick up from where it left off.
Note that although it is not shown on the diagrams above, the very first subroutine in the calling chain (in this case ProcedureA) has also got its own stack frame (below that of the procedure it called) with the same structure. ProcedureA was originally called by the operating system.
Architectural variations
The exact structure of a stack frame depends on the machine architecture and the OS. Parameters, return address and local variables may be placed in a different order (this example reflects the x86 architecture).
With the x86 architecture, other processor registers are also placed onto the stack when a call is made. For example, the current contents of the accumulator.
With the x86 architecture, when a called function (as opposed to a called sub procedure) wants to return a value to its caller, this value is put into the accumulator. With other architectures, the return value may be passed back via the stack.