Explain about stack organization used in processors. What do you understand by register stack?

Two operations work on a stack. PUSH inserts a new item on the top, and POP removes the top item. The stack can be built inside the CPU as a set of registers, or as a part of main memory.

Uses of stack in processors

• Evaluation of arithmetic expressions in reverse Polish notation, using zero-address instructions.
• Saving the return address and the local data when a subroutine is called, so that nested and recursive calls work.
• Saving the state of the processor when an interrupt occurs.

For example, to compute $(A+B)*C$ the stack machine runs PUSH A, PUSH B, ADD, PUSH C, MUL. Each operator takes the top two items and leaves the result on the top. No address is given for the operators.

Register stack

A register stack is a small group of registers organized as a stack. Take a stack of 64 words. The stack pointer SP has 6 bits and holds the address of the top. Two flip-flops, FULL and EMPTY, show whether the stack is full or empty. DR is the data register that holds the word to be pushed or the word that is popped.

At the start, $SP = 0$, $EMPTY = 1$ and $FULL = 0$. A push is done by

$$SP \leftarrow SP + 1$$

$$M[SP] \leftarrow DR$$

$$\text{if } SP = 0 \text{ then } FULL \leftarrow 1,\ EMPTY \leftarrow 0$$

After the push of the 63rd item, SP is 63. One more push makes SP wrap round to 0, which sets FULL. A pop is done by

$$DR \leftarrow M[SP]$$

$$SP \leftarrow SP - 1$$

$$\text{if } SP = 0 \text{ then } EMPTY \leftarrow 1,\ FULL \leftarrow 0$$

A push when FULL is set, or a pop when EMPTY is set, is an error and is not allowed. Register stacks are very fast, as no memory access is needed, but they are small.

Memory stack

The same idea works with part of main memory. Then SP points to a memory word. The stack grows toward lower addresses. A push does $SP \leftarrow SP - 1$ and $M[SP] \leftarrow DR$. A pop does $DR \leftarrow M[SP]$ and $SP \leftarrow SP + 1$. This stack can be large, but each access is slower.

In short, a register stack is a fast hardware stack made of registers, with FULL and EMPTY flags to guard its limits.