MIPS Functions

The Stack

Suppose you have a program as follows:

int f(int);
int g(int);
int h(int);

int main(void) {
	int n,m;
	n = 5;
	m = f(n);
	return 0;
}

int f(int x) {
	return g(x);
}

int g(int y) {
	int r = 4 * h(y);
	return r;
}

int h(int z) {
	int i;
	int p = 1;
	for (i = 1; i < z; i++) {
		p = p * i;
	}
	
	return p;
}

Since this program performs no dynamic allocation with functions such as malloc, it makes no explicit use of the heap. Instead, much of the transient state associated with each active function call can be represented on the stack. Each invocation is associated with a region of stack memory known as a stack frame.

Stack frames

A stack frame contains the information required for a particular invocation of a function. Depending on the architecture and compiler, this can include local variables, function parameters and other information required to return to the calling function.

As we progress from main() to h(), the state of the stack can be roughly represented as follows:

flowchart LR

    subgraph S1["1. main"]
        direction BT
        M1["Stack frame for main()<br/>contains n, m"]
    end

    subgraph S2["2. main calls f"]
        direction BT
        M2["Stack frame for main()<br/>contains n, m"] --> F2["Stack frame for f()<br/>contains x"]
    end

    subgraph S3["3. f calls g"]
        direction BT
        M3["Stack frame for main()<br/>contains n, m"] --> F3["Stack frame for f()<br/>contains x"] --> G3["Stack frame for g()<br/>contains y, r"]
    end

    subgraph S4["4. g calls h"]
        direction BT
        M4["Stack frame for main()<br/>contains n, m"] --> F4["Stack frame for f()<br/>contains x"] --> G4["Stack frame for g()<br/>contains y, r"] --> H4["Stack frame for h()<br/>contains i, p, z"]
    end

    S1 --> S2 --> S3 --> S4

Once a function completes and returns to its caller, its stack frame is no longer required and its space can be reclaimed. The frames are therefore removed in the reverse order from which they were created:

flowchart LR

    subgraph S1["1. h is active"]
        direction BT
        M1["Stack frame for main()<br/>contains n, m"] --> F1["Stack frame for f()<br/>contains x"] --> G1["Stack frame for g()<br/>contains y, r"] --> H1["Stack frame for h()<br/>contains i, p, z"]
    end

    subgraph S2["2. h returns"]
        direction BT
        M2["Stack frame for main()<br/>contains n, m"] --> F2["Stack frame for f()<br/>contains x"] --> G2["Stack frame for g()<br/>contains y, r"]
    end

    subgraph S3["3. g returns"]
        direction BT
        M3["Stack frame for main()<br/>contains n, m"] --> F3["Stack frame for f()<br/>contains x"]
    end

    subgraph S4["4. f returns"]
        direction BT
        M4["Stack frame for main()<br/>contains n, m"]
    end

    S1 --> S2 --> S3 --> S4

Infinite Recursion

Since the stack is finite, it is obvious that we can only accumulate so many function calls before exhausting the available stack space, and end up with a stack overflow. One straightforward way this can occur is through unbounded recursion. Recursion is when a function directly (or indirectly) calls itself;

void f(int x) {
	printf("%d\n", x);
	f(x + 1);
}

Here, every invocation of f() creates another invocation before the previous one has returned:

flowchart BT

    F0["Stack frame for f(0)"]
    F1["Stack frame for f(1)"]
    F2["Stack frame for f(2)"]
    F3["Stack frame for f(3)"]
    FN["Stack frame for f(...)"]
    SO["Stack Overflow"]

    F0 --> F1 --> F2 --> F3 --> FN --> SO