Agner`s CPU blog

Now I wonder if it is better to have two stacks: a call stack for return addresses and a data stack for the local variables of functions. The call stack will be quite small in most cases because the nesting level of function calls is limited in most programs. We can have a small rolling stack on the chip which is used most of the time. If the on-chip stack overflows then it must be spilled to memory. Let's take an example: we have a rolling stack on the chip with 16 entries. We are running a program where function calls are nested 20 deep. The on-chip stack will be copied to memory at call level 17. The on-chip stack entries are overwritten one by one (oldest first) on each deeper call. After call number 20 there will be 4 entries that are overwritten. The first 16 returns after the deepest call can take the return addresses from the on-chip stack. We don't have to reload the on-chip stack from memory until we come down to level 4. We will never have to spill the on-chip stack to memory inside a loop more than on the first iteration unless there are very deep function nesting or recursive functions inside the loop. In other words, the costs of spilling the on-chip stack to memory are minimal because it will not occur repeatedly in a loop except in recursive functions.

In fact, modern microprocessors already have such a rolling call stack on the chip. It is used for predicting return addresses. We might as well use this structure as the genuine call stack rather than just a shadow stack used for prediction. The prediction of return addresses will then be simple and perfect, of course.

There is also a security advantage to having a separate call stack. The return address of a function cannot be overwritten by software bugs or malicious buffer overflow attacks. Legitimate attempts to change the return address of a function will also be prevented, of course, but this is bad programming anyway because it wrecks the prediction mechanism.

The mechanism of the on-chip stack can be hidden in special registers. The application does not need to access the stack pointer of the call stack, except for stack unwinding in the exception handler.

The cost of having two stacks is the complexity of saving the on-chip stack to memory when it overflows. This can be implemented in hardware or software. Memory management will also be a little more complex because there are two stacks that can overflow. The size of both stacks can be predicted by using the method explained in my document, except for recursive functions.

I will propose, tentatively, to allow both principles - one stack or two stacks - in the CRISC1 architecture. It does not matter to the software whether there is one or two stacks except when function parameters are saved on the stack. A function needs to know the addresses of its parameters relative to the stack pointer, and this depends on whether there is a return address in between. It is rare that we will have parameters on the stack because the first 16 general purpose registers and the first 16 vector registers can be used for function parameters.

If we want the same software to be compatible with both one-stack and two-stack systems then we need to solve the problem of the address of parameters on the stack, however rare it may be. The simplest solution is to put an empty space on the data stack where the return address would be if we have a separate call stack. But I want to suggest a smarter solution: don't put parameters on the stack. If there are more parameters than registers then put the extra parameters in a list and use one register to point to this list. This solution is simple and efficient. We are getting rid of the old discussion of which order of parameters on the stack is better, and whether the stack should be cleaned up by caller or callee.

So this is my proposal. Small simple systems can have one unified stack, and large systems where performance or security is important can have two stacks. The size of the on-chip call stack is implementation dependent. The calling convention is changed so that parameters are never saved on the stack. Application programs don't need to care whether there is one or two stacks, but the stack unwinding mechanism in the exception handler needs to know, of course.