Why push first decreases the stack pointer?

Question

I'm trying to understand how the stack works when something is pushed and pulled from it, sorry if the question sounds very simple.

I want to start with something super basic, like an 8 bit memory (I know it will be an oversimplification, but let's start simple)

The way I would design a stack is the following:

SP will initially point to the highest position in memory: 0xFF

0xFF:   <- SP

When a push command is issued, I would save val in the position pointed by SP and then decrease SP.

0xFE:         <- SP
0xFF:  val

A pop command will first increment SP and then move the value pointed by SP into a register.

Basically my SP points to the first available position in the stack.

However it appears that this is not how it's implemented in real systems.

Looking at the assembly manual for the push instruction:

Decrements the stack pointer and then stores the source operand on the top of the stack.

So basically SP points to the latest stored value.

My question is: By first decreasing the stack pointer, isn't the very top of the stack unusable? How can we store data to the first position of the stack if we first decrease the pointer before saving the data?

Is there a reason to design the stack pointer this way?

Answer 1

Decrements the stack pointer and then stores the source operand on the top of the stack.

There are some design considerations (but rest assured, I agree that it is relatively arbitrary as either could be made to work):

First, let's take your example, and see what happens if, from the beginning, a 2-byte word is pushed onto the stack.

        0xFF:   <- SP

push.w val2

        0xFD:         <- SP
        0xFE:  val2(hi 8-bits)   # order depends on big/little endian
        0xFF:  val2(lo 8-bits)

8 bits of the value went to where SP is pointing (the first available byte) and the other 8 bits had to go below that address (because they can't go above it, eh?).  The stack pointer is left referring to a free byte, so the value just pushed is accessible at SP + 1.

While this can be made to work, the alternative seems more reasonable:

The item just pushed is at location SP + 0.

Keep in mind that loading is more common than storing, so loading the top item of the stack may happen more often than storing it.  Accessing the top of stack at SP + 0 favors loading, in an architecture that supports load without displacement.  (It also favors claimed space over unclaimed space.)

---

If we think of SP + ? as a demarcation between claimed and unclaimed, it seems more practical and natural to include 0 in the claimed space.  This is because (in computers, unlike math) zero is more like one of the positive numbers than like a negative number — for example, consider unsigned numbers, which always support zero (as well as positive values).

---

Let's also note that due to micro-architectural reasons, memory reads are slower than memory writes (reads are usually on the critical path, which bounds the maximum possible clock frequency, whereas writes are not).  Therefore, a post-increment pop (a load) is preferred to a pre-increment pop, because the post-increment can do the addition in parallel hardware (to the data memory access) whereas the pre-increment pop puts an adder in the way of the address bus & data memory read operation.  (To favor a post-increment pop, of course, we need a pre-decrement push.)

Answer 2

Why push first decreases the stack pointer?

First of all: It depends on the CPU type how the stack pointer works.

On the 6800, the value is written first and then the stack pointer is decremented.

And on the TMS320F28, the value is written and then the stack pointer is incremented.

... isn't the very top of the stack unusable?

Please forget the word "unusable". The correct word would be "in use".

Think about the following C or Java program:

int a, b;
a = someFunction();
someOtherFunction();
thirdFunction(a);

You want to store the return value of someOtherFunction() in a variable, like this:

int a, b;
a = someFunction();
a = someOtherFunction();
thirdFunction(a);

Not a good idea, because the variable a is already "in use". The variable b however is still "useable".

However, this does not prevent you from overwriting the variable a.

Now let's go back to the stack pointer and look at local variables. Looking at local variables (instead of push) we can see much clearer what the stack pointer actually does:

When entering a function like this:

void someFunction(void)
{
    int x, y, z;
    ...
    y = 5;
}

... the resulting assembler code will first decrease the stack pointer by 3 (assuming one int requires one memory location).

Let's say the stack pointer has the value 0x73 before entering the function. This means that memory locations 0...72 are "not in use" and memory locations 73...FF are "in use".

The assembler code will change the value of the stack pointer to 0x70 and store the variable x at address 0x70, y at address 0x71 and z at 0x72.

The stack pointer has the value 0x70, which means that memory locations 70...FF are "in use" now.

It should be clear that memory locations 70...72 are "in use" because the variables x, y and z are stored there.

However, this does not mean that it is not possible to access (read or write) these memory locations: The instruction y=5; will write to the memory location 0x71.