The stack and stack frames in a low level language

assembly, stack

Solution

Yes...

Assume you have a language like C that allows recursion. For that to work each instance of a function must be self contained from other instances of that function. The stack is the perfect place as code can "allocate" and reference items in the allocation without knowing the physical address, it is all accessed by reference. All you care about is keeping track of that reference within the context of the function and restoring the stack pointer to where it was when you entered the function.

Now you have to have a calling convention, one that fits recursion, etc. Two popular choices (using a simplified model) are register passing and stack passing. You can have and actually will have hybrids in reality (register based you will run out of registers and have to revert to the stack for the remaining parameters).

Assume for a moment that the fictional hardware I am talking about magically handles the return address without messing with registers or the stack.

register passing. Define a specific set of hardware/processor registers that will hold the parameters, lets say r0 is always the first parameter, r1 the second, r2 the third. and lets say the return value is r0 (this is simplified).

stack passing. lets define the first thing you push on the stack is the last parameter, then next to last up to the first parameter. When you return lets say the return value is the first thing on the stack.

Why declare a calling convention? So that both the caller and the callee know exactly what the rules are and where to find parameters. Register passing looks great on the surface, but when you run out of registers you have to save stuff on the stack. When you want to go from being a callee to a caller of another function, you might have to preserve items in the calling registers so you dont lose those values. And you are on the stack.

int myfun ( int a, int b, int c)
{
    a = a + b;
    b+=more_fun(a,c)
    return(a+b+c);
}

a, b, and c are used after the call to more_fun, more_fun at a minimum needs r0 and r1 to pass the parameters a and c and so you need to save r0 and r1 somewhere so that you can 1) use them to call more_fun() and 2) so that you dont lose the values a and b which you will need after you return from more_fun(). you could save them in other registers but how do you protect those registers from being modified by called functions. Ultimately stuff is saved on the stack, which is dynamic and accessed by reference instead of physical addresses. so

someone wants to call myfun and we are using register pasing.

r0 = a
r1 = b
r2 = c
call myfun
;return value in r0

myfun:
r0 = r0 + r1 (a = a + b)
;save a and b so we dont lose them
push r0 (a)
push r1 (b)
r0 = r0 (a) (dead code, can be optimized out)
r1 = r2 (c)
call more_fun
;morefun returns something in r0
pop r1 (recover b)
r1 = r1 + r0 (b = b+return value)
pop r0 (recover a)
;r0 is used for returning a value from a function
r0 = r0 + r1 (= a+b)
r0 = r0 + r2 (=(a+b)+c)
return

The calling function (caller) knows to prepare three parameters in r0, r1, r2 and take a return value in r0. The callee knows to accept r0,r1,r2 as incoming parameters and return in r0 AND it knows it has to preserve some things when it becomes the caller to some other function.

And if we use the stack to pass parameters using our calling convention

int myfun ( int a, int b, int c)
{
    a = a + b;
    b+=more_fun(a,c)
    return(a+b+c);
}

Now we have to make some register rules, do we define the calling rules to say that 1) you can destroy any register (but the sp and pc and psr), 2) that you have to preserve every register such that when you return the calling function never sees its registers changed or do you define 3) that some registers are scratch and can be modified at will and some have to be preserved if used. I am going to say that you can destroy registers except sp, pc, and spr for simplicity.

We have one more problem to solve. Who cleans up the stack? When I call morefun I have two items on the stack going in, and only the return value on the way out, who cleans up the stack. Two choices, caller cleans, callee cleans, I go with caller cleans. Which means the callee has to return from the function with the stack the way it was found, it leave anything on the stack and it doesnt take too many things off the stack.

caller:

push c
push b
push a
call myfun
pop result
pop and discard
pop and discard

assume with this hardware the stack pointer sp points at the current item on the stack

myfun:
;sp points at a
load r0,[sp+0] (get a)
load r1,[sp+1] (get b)
add r0,r1 (a = a+b)
store [sp+0],r0 (the new a is saved)
;prepare call to more_fun
load r0,[sp+2] (get c)
load r1,[sp+0] (get a)
push r0 (c)
push r1 (a)
call more_fun
;two items on stack have to be cleaned, top is return value
pop r0 (return value)
pop r1 (discarded)
;we have cleaned the stack after calling more_fun, our offsets are as
   ;they were when we were called
load r1,[sp+1] (get b)
add r1,r0 (b = b + return value)
store [sp+1],r1
load r0,[sp+0] (get a)
load r1,[sp+1] (get b)
load r2,[sp+2] (get c)
add r0,r1 (=a+b)
add r0,r2 (=(a+b)+c)
store [sp+0],r0 (return value)
return 

So I wrote all of this on the fly there might be a bug. The key to all of this is you have to define a calling convention and if everyone (caller and callee) follow the calling convention it makes compiling easy. The trick is making a working calling convention, as you can see above we had to modify the convention and add rules to make it work even for such a simple program.

What about a stack frame?

int myfun ( int a, int b)
{
    int c;
    c = a + b;
    c+=more_fun(a,b)
    return(c);
}

using stack based

caller

push b
push a
call myfun
pop result
pop and discard

callee

;at this point sp+0 = a, sp+1 = b, but we need room for c, so
sp=sp-1 (provide space on stack for local variable c)
;sp+0 = c
;sp+1 = a
;sp+2 = b
load r0,[sp+1] (get a)
load r1,[sp+2] (get b)
add r0,r1
store [sp+0],r0 (store c)
load r0,[sp+1] (get a)
;r1 already has b in it
push r1 (b)
push r0 (a)
call more_fun
pop r0 (return value)
pop r1 (discarded to clean up stack)
;stack pointer has been cleaned, as was before the call
load r1,[sp+0] (get c)
add r1,r0 (c = c+return value)
store [sp+0],r1 (store c)(dead code)
sp = sp + 1 (we have to put the stack pointer back to where 
   ;it was when we were called
;r1 still holds c, the return value
store [sp+0],r1 (place the return value in proper place 
   ;relative to callers stack)
return

The callee, if it uses the stack and moves the stack pointer, it has to put it back where it was when it was called. You create a stack frame by adding the right number of things on the stack for local storage. You might have local variables and through the process of compiling you may know ahead of time that you have to also preserve a certain number of registers. The simplest way is to just add all of that up and move the stack pointer one time for the whole function and put it back one time before return. You can get more clever and keep moving the stack pointer around adjusting offsets as you go, a lot harder to code and more prone to error. Compilers like gcc tend to move the stack pointer just into the function and return it just before leaving.

Some instructions sets add stuff to the stack on a call and remove it on return and you have to adjust your offsets accordingly. Likewise your creation and cleanup around a call to another function might require handling related to the hardwares use of the stack if any.

Lets say the hardware when you make a call pushes the return value on the top of the stack.

int onefun ( int a, int b )
{
    return(a+b)
}

onefun:
;because of the hardware
;sp+0 return address
;sp+1 a
;sp+2 b
load r0,[sp+1] (get a)
load r1,[sp+2] (get b)
add r1,r2
;skipping over the hardware use of the stack we return on what will be the
;top of stack after the hardware pops the return address
store [sp+1],r1 (store a+b as return value)
return (pops return address off of stack, calling function pops the other two 
   ;to clean up)

Some processors use a register to hold a return value when a function is called, sometimes the hardware dictates which register, sometimes the compiler chooses one and uses it as the convention. If your function does not call any other function, you can either not use the return address register and use it for the return, or you can push it on the stack at some point, and then before returning pop it off then use it to return. If your function does call another function you have to preserve that return address so the call to the next function does not destroy it and you cant find your way home. so you either save it in another register if you can or put it on the stack

Using the above register calling convention we defined, plus have a register named rx that when a call is made the hardware places the return address in rx for you.

int myfun ( int a, int b)
{ 
   return(some_fun(a+b));
}

myfun:
;rx = return address
;r0 = a, first parameter
;r1 = b, second parameter
push rx ; we are going to make another call we have to save the return
        ; from myfun
;since we dont need a or b after the call to some_fun we can destroy them.
add r0,r1 (r0 = a+b) 
;we are all ready to call some_fun first parameter is set, rx is saved
;so the call can destroy it
call some_fun
;r0 is the return from some_fun and is going to be the return from myfun, 
;so we dont have to do anything it is ready
pop rx ; get our return address back, stack is now where we found it 
       ; one push, one pop
mov pc,rx ; return

Problem

Original source