Why push first decreases the stack pointer?

3
votes

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?

2
assemblystackcpu-architecturecallstackinstruction-set
There are implementations for both kinds and some architectures support both. The notion of "first position" depends on the stack type. You can't write to the address of the initial stack pointer, but then you won't call it "first position". Or to put it differently: given an intended first position, set up the stack pointer to point directly after it and then it will work. - Jester
Primarily opinion-based/too broad. That said, consider the non-x86 approach of store-then-decrement: the first useful data element will be at offset 1 or larger from SP. Doing decrement-then-store, indexes into the valid stack values start at 0, just like conventional access for any type of array/pointer-based storage. IMHO that's a useful consistency. It also means you're not "wasting" offsets, i.e. the offset of 0 actually is meaningful instead of never useful. - Peter Duniho
First modifying the SP is a protection. What may happen if you have an interrupt between the copy of your data in the stack and the SP update? If you first change SP, no problem may arise. - Alain Merigot
@AlainMerigot: that makes sense for ISAs without a push instruction, where you have to manually decrement the stack. But if you do have a push instruction, the store-and-decrement would be atomic WRT. interrupts. (Interrupts always logically happen at instruction boundaries; partial progress is discarded or the interrupt waits for the instruction to complete.) I've never heard of an ISA where simple instructions like push were interruptible with half the instruction completed. So full vs. empty stack is mostly an arbitrary design choice, but having SP pointing at data can be useful. - Peter Cordes
Of course, instructions are never interrupted. But even on a machine with a push instruction, one can use a sp--/store pair of instructions to push on the stack and this needs to be protected from interrupts by first decrementing sp. And, while it is not strictly required technically, it makes sense to have exactly the same mechanism with a push or a pair of instructions. - Alain Merigot

2 Answers

6
votes

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.)

2
votes

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.