Similar to how the PC is used to keep track of where in memory the CPU is executing, we need a Stack Pointer (SP) to tell us where in the 16-levels of stack our most recent value was placed (i.e, the top).
We only need 8 bits for our stack pointer because the stack will be represented as an array, so our stack pointer can just be an index into that array. We only need sixteen indices then, which a single byte can manage.
When we pop a value off the stack, we won’t actually delete it from the array but instead just copy the value and decrement the SP so it “points” to the previous value.
Let’s go through an example of how the stack works. Here is the example program we’re running, with the address of the instruction on the left and the actual instruction on the right. Don’t worry about the LD instructions, just focus on the CALLs and the RETs. A JMP is like a CALL, but it doesn’t put anything onto the stack.
$200: CALL $208
$202: JMP $20E
$204: LD V1, $1
$206: RET
$208: LD V3, $3
$20A: CALL $204
$20C: RET
$20E: LD V4, $4Initially the stack pointer starts at 0, indicating the top of the stack, and the stack itself is just an array filled with zeroes. As we execute CALLs and RETs, we’ll see what the stack does.
PC: $202 PC: $20A PC: $20C PC: $206 PC: $208 PC: $20E PC: $204 PC: $210
$200: CALL $208 $208: LD V3, $3 $20A: CALL $204 $204: LD V1, $1 $206: RET $20C: RET $202: JMP $20E $20E: JMP
-------- -------- -------- -------- -------- -------- -------- -------- --------
|00|0x000| <- SP |00|0x000| <- SP |00|0x202| |00|0x202| |00|0x202| |00|0x202| |00|0x202| |00|0x202| <- SP |00|0x202| <- SP
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|01|0x000| |01|0x000| |01|0x000| <- SP |01|0x000| <- SP |01|0x20C| |01|0x20C| |01|0x20C| <- SP |01|0x20C| |01|0x20C|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|02|0x000| |02|0x000| |02|0x000| |02|0x000| |02|0x000| <- SP |02|0x000| <- SP |02|0x000| |02|0x000| |02|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|03|0x000| |03|0x000| |03|0x000| |03|0x000| |03|0x000| |03|0x000| |03|0x000| |03|0x000| |03|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|04|0x000| |04|0x000| |04|0x000| |04|0x000| |04|0x000| |04|0x000| |04|0x000| |04|0x000| |04|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|05|0x000| |05|0x000| |05|0x000| |05|0x000| |05|0x000| |05|0x000| |05|0x000| |05|0x000| |05|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|06|0x000| |06|0x000| |06|0x000| |06|0x000| |06|0x000| |06|0x000| |06|0x000| |06|0x000| |06|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|07|0x000| |07|0x000| |07|0x000| |07|0x000| |07|0x000| |07|0x000| |07|0x000| |07|0x000| |07|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|08|0x000| |08|0x000| |08|0x000| |08|0x000| |08|0x000| |08|0x000| |08|0x000| |08|0x000| |08|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|09|0x000| |09|0x000| |09|0x000| |09|0x000| |09|0x000| |09|0x000| |09|0x000| |09|0x000| |09|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|10|0x000| |10|0x000| |10|0x000| |10|0x000| |10|0x000| |10|0x000| |10|0x000| |10|0x000| |10|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|11|0x000| |11|0x000| |11|0x000| |11|0x000| |11|0x000| |11|0x000| |11|0x000| |11|0x000| |11|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|12|0x000| |12|0x000| |12|0x000| |12|0x000| |12|0x000| |12|0x000| |12|0x000| |12|0x000| |12|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|13|0x000| |13|0x000| |13|0x000| |13|0x000| |13|0x000| |13|0x000| |13|0x000| |13|0x000| |13|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|14|0x000| |14|0x000| |14|0x000| |14|0x000| |14|0x000| |14|0x000| |14|0x000| |14|0x000| |14|0x000|
|--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------| |--------|
|15|0x000| |15|0x000| |15|0x000| |15|0x000| |15|0x000| |15|0x000| |15|0x000| |15|0x000| |15|0x000|
-------- -------- -------- -------- -------- -------- -------- -------- --------With each CALL, the current PC (which was previously incremented to point to the next instruction) is placed where the SP was pointing, and the SP is incremented.
With each RET, the stack pointer is decremented by one and the address that it’s pointing to is put into the PC for execution.
The actual order of execution looks like this:
$200: CALL $208 -> PC += 2 = $202 | SP = 0 | Put $202 in stack[0] and ++SP = 1 | PC = $208 | Next cycle at PC = $208
$208: LD V3, $3 -> PC += 2 = $20A | SP = 1 | Do not modify stack or SP | PC = $20A | Next cycle at PC = $20A
$20A: CALL $204 -> PC += 2 = $20C | SP = 1 | Put $20C on stack[1] and ++SP = 2 | PC = $204 | Next cycle at PC = $204
$204: LD V1, $1 -> PC += 2 = $206 | SP = 2 | Do not modify stack or SP | PC = $206 | Next cycle at PC = $206
$206: RET -> PC += 2 = $208 | SP = 2 | --SP = 1 and Pull $20C from stack[1] | PC = $20C | Next cycle at PC = $20C
$20C: RET -> PC += 2 = $20E | SP = 0 | --SP = 0 and Pull $202 from stack[0] | PC = $202 | Next cycle at PC = $202
$202: JMP $20E -> PC += 2 = $204 | SP = 0 | Do not modify stack or SP | PC = $204 | Next cycle at PC = $204
$20E: LD V4, $4 -> PC += 2 = $210 | SP = 0 | Do not modify stack or SP | PC = $210 | Next cycle at PC = $210