The Stack

What is a stack?

A stack is a concept that's not linked to GB programming. But the CPU implements a stack, so let's talk about it. A stack is a way to store data, in a LIFO manner (last in first out). It's just like a stack of books: the last one put on top of the pile is the first one you take out.

A stack is interfaced with in two ways: either you push data onto it, or you pop data off of it. In the second case, data is retrieved and removed from the stack. (Again, picture a pile of books.)

The point of a stack is that it allows to "save" values temporarily. Push a value on top, get it back later.

Now introducing the sp

sp is the CPU's implementation of the stack concept. It's a 16-bit register that points to the top of the stack. Here's what you can do with sp, before we talk about how the CPU's stack works.

    ld sp, $DEAD ; Set sp to something

    ; Point hl to the stack, with a signed 8-bit offset
    ld hl, sp+4
    ; Set sp to hl, although this one doesn't have an offset
    ld sp, hl

    ; Edit sp directly (signed 8-bit offset)
    add sp, -4

    ; Save SP to RAM
    ld [$BEEF], sp

    ; Doesn't affect flags
    inc sp
    dec sp

Now, let's get to the Real Stuff™: the CPU's stack. The first instruction is push, which pushes a 16-bit register's contents to the stack. Here's a breakdown of what occurs:

    push hl

    ; is equivalent to
    ; NB: some of these instructions are NOT valid, just here to give an example

    dec sp
    ld [sp], h
    dec sp
    ld [sp], l

Notice how hl ends up being stored in little-endian format? (Little-endian was evoked in the section.) Notice also that sp is decremented after each push, which essentially means that the stack is placed at the end of RAM, rather than at the beginning (this is called an "descending" stack). And finally, notice that sp always points to the topmost entry, instead of pointing to the free space before it (this is called a "full" stack).

Also, the same way that we have push, we have pop:

    pop de

    ; is equivalent to

    ld e, [sp]
    inc sp
    ld d, [sp]
    inc sp

Its uses

A mentioned previously, the stack allows "saving" values.

    ld hl, 42
    ; hl contains an important value that we must not lose
    ; But we need to use hl for a calculation!

    push hl ; Save important value

    ; Perform calculation that uses hl
    ld hl, 1337
    ld de, 9001
    add hl, de
    ld d, h
    ld e, l

    pop hl ; Get back important value

So the stack is dandy and all, but you should be careful not to overuse it. Why? Because it's slow. push hl isn't as slow as

    ld a, l
    ld [$C000], a
    ld a, h
    ld [$C001], a

-- but if you can avoid it, do so. (Otherwise you're a bad programmer who shouldn't complain when their OS or any other program takes ages to launch and/or runs like ass on a quad-core CPU and 8GB RAM.)

But the most important use of the stack has yet to come... in the next lesson...