Low Level Stack and Stack Frames

Question

I'm trying to circle my head around the concept of function calls, as they relate to the stack. This question is asked in the context of a low level language, not a high level language.

From what I understand so far, when a function is called, local variables and parameters are stored on the stack stack in the stack. Each stack frame is associated with one function call. The part I don’t quite understand about is who is responsible for creating the frame? Is my program supposed to consider declaring a function in a program and manually copy local variables onto a new frame onto the stack?

Answer 1

Yes...

Suppose you have a language, such as C, that allows recursion. To do this, each instance of the function must be autonomous from other instances of this function. The stack is an ideal place, because the code can "allocate" and refer to elements in the distribution without knowing the physical address; everyone accesses it by reference. All you care about is keeping track of this link in the context of the function and restoring the stack pointer to where it was when you introduced this function.

You should now have a calling convention that is suitable for recursion, etc. Two popular options (using a simplified model) are register transfer and stack transfer. In fact, you can have and actually have hybrids (based on the registers, you will end the registers and should go back to the stack for the rest of the parameters).

Suppose for a moment that the fictional hardware that I'm talking about magically processes the return address without messing around with registers or the stack.

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

stack. allows you to determine the first thing you click on the stack is the last parameter, and then next to the last to the first parameter. When you return, let's say that the return value is the first thing on the stack.

Why announce a calling agreement? Thus, both the caller and the callee know exactly what the rules are and where to find the parameters. Registering a passage looks great on the surface, but when you run out of registers, you need to keep things on the stack. If you want to move from the caller to another function, you may need to store items in the calling registers so that you do not lose these 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 calling more_fun, more_fun with the minimum requirements r0 and r1 pass the parameters a and c, 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 do not lose the values ​​of a and b that you will need after returning from more_fun (). you can save them in other registers, but how to protect these registers from modifying the called functions. Ultimately, the material is stored on the stack, which is dynamic and accessible by reference instead of physical addresses. So

Someone wants to call myfun, and we use registration.

 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 (the calling party) knows to prepare the three parameters in r0, r1, r2 and take the return value in r0. The caller knows what to take r0, r1, r2 as input parameters and return to r0 And he knows that he needs to save some things when he becomes the caller for 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 create some registration rules, we define call rules to say that 1) you can destroy any register (but sp and pc and psr), 2) that you must save each register so that when you return the calling function, never seeing that its registers are changed or you determine 3) that some registers are scratches and can be changed at will, and some should be saved if they are used. I'm going to say that you can destroy registers besides sp, pc and spr for simplicity.

We have one more problem. Who clears the stack? When I call more, I have two elements on the stack, and only a return value on the output that clears the stack. Two choices, caller cleaning, cleaning, I go with a cleaner. This means that the caller must return from the function with the stack as it was found, it leaves something on the stack, and it does not take up too many things from the stack.

subscriber:

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

Assume with this equipment, the stack pointer sp points to the current item in 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 this on the fly, there may be a mistake. The key to all this is to define a calling convention, and if everyone (the caller and the callee) follows the calling convention, it makes compilation easier. The trick is to create a working call agreement, as you can see above, we needed to change the agreement and add rules to make it work even for such a simple program.

How about a stack frame?

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

using stack

subscriber

 push b push a call myfun pop result pop and discard 

called

 ;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 

A call, if it uses the stack and moves the stack pointer, it must return it to where it was when it was called. You create a stack frame by adding the right amount of stuff to the local storage stack. You may have local variables, and during the compilation process you may know in advance that you also need to save a certain number of registers. The easiest way is to simply add all this and move the stack pointer once for the whole function and return it one time before returning. You can become smarter and keep moving the stack pointer around adjusting offsets along the way, making it much harder to code and error-prone. Compilers like gcc tend to move the stack pointer only to a function and return it before leaving.

Some set commands add things to the stack when called and delete them when they return, and you need to adjust the offsets accordingly. Similarly, your creation and cleanup around calling another function may require processing involving the use of stack hardware, if any.

Suppose that hardware, when you make a call, pops the return value at 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 store the return value when the function is called, sometimes the hardware dictates which register, sometimes the compiler chooses one and uses it as a convention. If your function does not call any other function, you can either not use the return address register, but use it to return, or you can push it on the stack at some point, and then use it to return before returning it If your function calls another function, you must save this return address so that the call to the next function does not destroy it, and you cannot find your way home. so you either save it in a different register if you can or push it on the stack

Using the aforementioned register calling convention that we have defined, plus we have a register named rx, which when you call the hardware puts the return address for you in rx.

 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 

Answer 2

As a rule, either the processor manufacturer or the first company developing compilers of popular languages ​​for the processor will determine what the calling function should do before the function call (what should be on the stack, what different registers should contain, etc.) and what the called function must be called before it returns (including restoring the values ​​of certain registers, if they have been changed, etc.). For some processors, several conventions have become popular, and as a rule, it is very important to make sure that the code for any given function will use the convention that awaits the calling code.

In 8088/8086, which had a slightly small number of registers, two main conventions appeared: the C convention, which states that the caller must push arguments onto the stack before calling the function and then call them (which means the only thing that the called function should pop out of stack, this is the return address) and the Pascal convention, which indicates that the called function should jump out of all the arguments passed to it, in addition to popping up the return address. On 8086, the Pascal convention often allows slightly smaller code (since stack cleanup should only be done once for each function call, not once for each function call, but because 8086 contains a version of RET that adds the specified value to the stack pointer after , which placed the return address. One of the drawbacks of the Pascal convention was that it required the called function to know how many bytes the parameters would cost. If the called function didn't exactly pop the correct number of bytes, stack corruption is almost ernyaka happen.

In many new processors, routines that have a small fixed number of parameters usually do not have their parameters pushed onto the stack. Instead, compiler providers will indicate that the first few parameters will be placed in registers before the function is called. This often allows for greater performance than using stack parameters. However, procedures with many parameters or variable argument lists must still use the stack.

Answer 3

To deploy a bit in a supercar response, setting the stack frame is the common responsibility of the calling and called functions. A stack frame usually refers to all data that is local to a particular program call. Then, the calling procedure creates an external stack of frames, first pushing any stack parameters onto the stack, and then the return address, calling the procedure. The called procedure then creates the rest of the stack frame (the inner stack of the stack) by (usually) pushing (saving) the current frame pointer on the stack and creating a new one that points to the next free stack slot. It then reserves the stack for local variables in the stack and, depending on the language used, can also initialize them at this point. Then, the frame pointer can be used to access parameters based on the stack and local variables, one with a negative and the other with a positive offset. When you exit the subroutine, the old stack stack is restored, and local data and parameters are unloaded, as described by supercat.