MIPS: Why do we need the stack?

Question

What is the purpose of the stack in MIPS and why do we need it? Can someone give also an example code where it would be relevant?

To implement what C calls automatic storage (local variables) efficiently when you run out of registers, or across function calls. — Peter Cordes, May 23 '18 at 11:01
you don't *need* stack. But it is often most simple/efficient way of using computer memory for storage in LIFO (last in, first out) way. — Ped7g, May 23 '18 at 11:01
[Why is memory split up into stack and heap?](https://stackoverflow.com/q/8173353/995714), [What is the purpose of a stack? Why do we need it?](https://stackoverflow.com/q/7875253/995714) — phuclv, May 23 '18 at 11:16
Why you stress MIPS? Stack is used similarly by most processors. — Uprooted, May 23 '18 at 14:34
@LưuVĩnhPhúc: The third link (second link in the second comment) seems not to be related to the "normal" stack but to some special "stack" used in .NET calculations. — Martin Rosenau, May 23 '18 at 15:01

score 1 · Answer 1 · answered May 23 '18 at 14:59

Think of the following recursively defined C function:

int f(int n)
{
    if(n<3)
    {
        return n+4;
    }
    else
    {
        return f(n-1)+f(n-2);
    }
}

You are calling f(20).

The following will happen:

Initially the return address is located in the register $ra.

The function calls itself with the function argument f(19) and f(19) returns. So far so good. Some register will now contain the value returned by f(19).

Now the function calls itself with the argument f(18).

The value returned by f(19) had been stored in some register. Either f(19) was writing the value there; in this case f(18) is overwriting this register because f(19) and f(18) are the same function. Or f(20) was writing the value there ... well f(20) and f(18) are the same function.

The register will be overwritten in any case.

So storing the value returned in a register will not work. How about storing in a global variable?

int intermediate;

int f(int n)
{
    ...
    intermediate = f(n-1);
    return f(n-2) + intermediate;
}

We will have the same problem: Calling f(18) will overwrite the variable intermediate so we cannot do the addition any more ...

... and when we want to return from the function we have the next problem: By calling f(19) we have overwritten $ra ...

Using local variables will only move the problem:

int f(int n)
{
    int local;
    ...
}

=> Where shall we store the variable local? In a fixed memory address (= global variable) or in a register? In both cases we have the same problem as described above.

Now we could think of the following solution:

int intermediate[100];

int f(int n, int level)
{
    ...
    intermediate[level] = f(n-1, level+1);
    intermediate[level] += f(n-2, level+1);
    ...
}

So f(20) will use intermediate[0], the functions being called from f(20) use intermediate[1] and the functions being called from that functions use intermediate[2] and so on...

Exactly this is the concept of a "stack"!

However you don't have to implement this yourself but it is already pre-defined that the register $sp points to the memory you can use (level in the example).

MIPS: Why do we need the stack?

1 Answers1