I've read that stack frames contain return addresses, function arguments, and local variables for a function. Since functions don't know where their stack frame is in memory at compile time, how do they know the memory address of their local variables? Do they offset and dereference the stack pointer for every read or write of a local? In particular, how does this work on embedded devices without efficient support for pointer accesses, where load and store addresses have to be hardcoded into the firmware and pointer accesses go through reserved registers?
3 Answers
The anser is, it depends on the architecture. You will have a register that contains the address of the current stack frame, EBP for x86 for instance, once you know this, individual variables are identified by their offsets into the stack frame, calculated by object size at compile time (hence the need for size to be know at compile time for local variables).
Even if a stack frame appears in different places in memory, the variables will have the same relative offset, so you can always calculate the address.
The size of the stack frame for each function is calculated at compile and included in the code so that each call can set up and clean its own frame.
The way objects work is that the compiler or assembly programmer determines the layout of an object — the offset of each field relative to the start of the object (as well as the size of the object as a whole). Then, objects are passed and stored as references, which are generally pointers in C and machine code. In struct xy { int x; int y; }, we can reason that x is at offset 0 and y at offset 4 from an object reference to a struct xy.
The stack frame is like an object that contains a function's memory-based local variables (instead of struct members), and being accessed not by an object reference but by the stack or frame pointer. (And being allocated/deallocated by stack pointer decrement/increment, instead of malloc and free.)
Both share the issue that we don't know the actual location/address of a given field (x or y) of a dynamically allocated object or stack frame position of a memory-based local variable until runtime, but when a function runs, it can compute the complete absolute address (of object fields or memory-based local variables) quite simply by adding together the base (object reference or stack/frame pointer) to relative position of the desired item, knowing its predetermined layout.
Processors offer addressing modes that help to support this kind of access, usually something like base + displacement.
Let's also note that many local variables are assigned directly to CPU registers so have no memory address at all. Other local variables move between memory and CPU registers, and such might be considered optimization that means we don't have to access memory if the value of a variable is needed when that has recently already been loaded into a CPU register.
In many ways, processors for embedded devices are like other processors, offering addressing modes to help with memory accesses, and with optimizing compilers that can make good decisions about where a variable lives. As you can tell from the above, not all variables need live in memory, and some live in both in memory and in CPU registers to help reduce memory access costs.
You could just try it and see for yourself.
unsigned int fun1 ( unsigned int );
unsigned int fun ( unsigned int a )
{
unsigned int x;
x=fun1(a);
return(x);
}
unoptimized to save time (developing a function that does not optimize out stack use)
0: e92d4800 push {fp, lr}
4: e28db004 add fp, sp, #4
8: e24dd010 sub sp, sp, #16
c: e50b0010 str r0, [fp, #-16]
10: e51b0010 ldr r0, [fp, #-16]
14: ebfffffe bl 0 <fun1>
18: e50b0008 str r0, [fp, #-8]
1c: e51b3008 ldr r3, [fp, #-8]
20: e1a00003 mov r0, r3
24: e24bd004 sub sp, fp, #4
28: e8bd4800 pop {fp, lr}
2c: e12fff1e bx lr
You should have already read about a stack frame. Stacks are dynamic as you know, so access is going to be relative not fixed addresses. There are basically two approaches, one is the obvious one, you move the stack pointer deeper into the stack an amount. For ease of development and debug of the compiler you move it to cover all the local storage you need for the duration of the function. And then all the items you need to access are relative to the stack pointer in a backward from the growth direction of the stack. The other option is to burn another register and have a stack frame where one pointer is at/near the address of the stack pointer entering the function then the stack pointer moves, again to ease development, the amount needed for the duration of the function. And use the accesses from the frame pointer in the direction of the growth of the stack.
0: e92d4800 push {fp, lr}
save the frame pointer so you do not trash the value for the caller. And save the link register so the nested call does not cause it to be lost. This moves the stack pointer obviously.
4: e28db004 add fp, sp, #4
8: e24dd010 sub sp, sp, #16
set the frame pointer and move the stack pointer forward.
sp = base
4: e28db004 add fp, sp, #4
fp = base + 4
8: e24dd010 sub sp, sp, #16
sp = base + 16
str r0, [fp, #-16]
base +4 -16 = base-12
1c: e51b3008 ldr r3, [fp, #-8]
base +4 - 8 = base - 4
Yes this seems strange and excessive amount of storage. This is unoptimized though.
save the frame pointer and return address
0: e92d4800 push {fp, lr}
set up the stack frame
4: e28db004 add fp, sp, #4
allocate space on the stack for this function
8: e24dd010 sub sp, sp, #16
save a on the stack (unoptimized)
c: e50b0010 str r0, [fp, #-16]
get a from the stack
10: e51b0010 ldr r0, [fp, #-16]
call the nested function (lr and assume r0,r1,r2,r3 are changed)
14: ebfffffe bl 0 <fun1>
save the return value on the stack (x)
18: e50b0008 str r0, [fp, #-8]
get x from the stack
1c: e51b3008 ldr r3, [fp, #-8]
put x in the return address register
20: e1a00003 mov r0, r3
free the allocated stack for this function
24: e24bd004 sub sp, fp, #4
restore the frame pointer and return address
28: e8bd4800 pop {fp, lr}
return
2c: e12fff1e bx lr
Now if I tell the compiler to omit the frame pointer.
00000000 <fun>:
0: e52de004 push {lr} ; (str lr, [sp, #-4]!)
4: e24dd014 sub sp, sp, #20
8: e58d0004 str r0, [sp, #4]
c: e59d0004 ldr r0, [sp, #4]
10: ebfffffe bl 0 <fun1>
14: e58d000c str r0, [sp, #12]
18: e59d300c ldr r3, [sp, #12]
1c: e1a00003 mov r0, r3
20: e28dd014 add sp, sp, #20
24: e49de004 pop {lr} ; (ldr lr, [sp], #4)
28: e12fff1e bx lr
The frame pointer is often not needed, instruction set matters though.
save the return address
0: e52de004 push {lr} ; (str lr, [sp, #-4]!)
allocate stack space for this function
4: e24dd014 sub sp, sp, #20
save a on the stack
8: e58d0004 str r0, [sp, #4]
get a from the stack to call the function
c: e59d0004 ldr r0, [sp, #4]
call the nested function
10: ebfffffe bl 0 <fun1>
save the return value on the stack (x)
14: e58d000c str r0, [sp, #12]
get x from the stack
18: e59d300c ldr r3, [sp, #12]
put x in the return register
1c: e1a00003 mov r0, r3
free up the space on the stack
20: e28dd014 add sp, sp, #20
get the return address from the stack
24: e49de004 pop {lr} ; (ldr lr, [sp], #4)
return
28: e12fff1e bx lr
an embedded microcontroller
0: 04 12 push r4
2: 04 41 mov r1, r4
4: 24 53 incd r4
6: 21 82 sub #4, r1 ;r2 As==10
8: 84 4f fc ff mov r15, -4(r4) ;0xfffc(r4)
c: 1f 44 fc ff mov -4(r4), r15 ;0xfffc(r4)
10: b0 12 00 00 call #0x0000
14: 84 4f fa ff mov r15, -6(r4) ;0xfffa(r4)
18: 1f 44 fa ff mov -6(r4), r15 ;0xfffa(r4)
1c: 21 52 add #4, r1 ;r2 As==10
1e: 34 41 pop r4
20: 30 41 ret
without the frame pointer
0: 21 82 sub #4, r1 ;r2 As==10
2: 81 4f 02 00 mov r15, 2(r1) ;0x0002(r1)
6: 1f 41 02 00 mov 2(r1), r15 ;0x0002(r1)
a: b0 12 00 00 call #0x0000
e: 81 4f 00 00 mov r15, 0(r1) ;0x0000(r1)
12: 2f 41 mov @r1, r15
14: 21 52 add #4, r1 ;r2 As==10
16: 30 41 ret
So so this one does not have the same rules for stack alignment as the other, so it allocates the space for just the two variables needed (a and x). Like before we can see the stack pointer allocates space, a is stored and then loaded from the stack to make the nested call. The return value is saved on the stack as x then read back to use as a return value.
Another instruction set.
0: 1166 mov r5, -(sp)
2: 1185 mov sp, r5
4: 65c6 fffe add $-2, sp
8: 1d66 0004 mov 4(r5), -(sp)
c: 09f7 fff0 jsr pc, 0 <_fun>
10: 65c6 0002 add $2, sp
14: 1035 fffe mov r0, -2(r5)
18: 1d40 fffe mov -2(r5), r0
1c: 1146 mov r5, sp
1e: 1585 mov (sp)+, r5
20: 0087 rts pc
without frame pointer
0: 65c6 fffe add $-2, sp
4: 1da6 0004 mov 4(sp), -(sp)
8: 09f7 fff4 jsr pc, 0 <_fun>
c: 65c6 0002 add $2, sp
10: 100e mov r0, (sp)
12: 1380 mov (sp), r0
14: 65c6 0002 add $2, sp
18: 0087 rts pc
same story, except the calling convention has the passed parameters on the stack so we do not see a written then read back. After the call though we see the return value saved to x then x read from the stack to perform the return.
another instruction set
0: 91 1c dec $sp, 0x1c
2: 0d 02 00 0c sto.l 0xc($fp), $r0
6: 0c 20 00 0c ldo.l $r0, 0xc($fp)
a: 03 00 00 00 jsra 0 <fun>
e: 00 00
10: 0d 02 ff fc sto.l 0xfffc($fp), $r0
14: 0c 20 ff fc ldo.l $r0, 0xfffc($fp)
18: 04 00 ret
another
0: 7179 addi x2,x2,-48
2: d606 sw x1,44(x2)
4: d422 sw x8,40(x2)
6: 1800 addi x8,x2,48
8: fca42e23 sw x10,-36(x8)
c: fdc42503 lw x10,-36(x8)
10: 00000097 auipc x1,0x0
14: 000080e7 jalr x1 # 10 <fun+0x10>
18: fea42623 sw x10,-20(x8)
1c: fec42783 lw x15,-20(x8)
20: 853e mv x10,x15
22: 50b2 lw x1,44(x2)
24: 5422 lw x8,40(x2)
26: 6145 addi x2,x2,48
28: 8082 ret
without a stack frame.
0: 7179 addi x2,x2,-48
2: d606 sw x1,44(x2)
4: c62a sw x10,12(x2)
6: 4532 lw x10,12(x2)
8: 00000097 auipc x1,0x0
c: 000080e7 jalr x1 # 8 <fun+0x8>
10: ce2a sw x10,28(x2)
12: 47f2 lw x15,28(x2)
14: 853e mv x10,x15
16: 50b2 lw x1,44(x2)
18: 6145 addi x2,x2,48
1a: 8082 ret
Why are some of these allocating more memory than needed? A number of SO questions already cover that topic.
Can keep going, and you can try godbolt if you wish, but you can see that as described above.
With a frame pointer
- save the frame pointer to not mess up the prior function
- point the frame pointer to the stack pointer to mark one end of the allocated
- allocate memory from the stack for the whole function (move the stack pointer).
Now the frame pointer points to one end of the allocated space and the stack pointer the other end. With a frame pointer the local variables and passed parameters are generally addressed relative to the frame pointer.
With out the frame pointer you just move the stack pointer to allocate the space and access all the local stuff and the passed parameters relative to the stack pointer.
It is all relative addressing no fixed addressing needed. As it should be with a memory space you do not know the physical address for (at compile/link time). Just like any other pointer (an array or pointer in C code for example).
You will not see this with compilers, but where the compiler produces
00000000 <fun>:
0: e52de004 push {lr} ; (str lr, [sp, #-4]!)
4: e24dd014 sub sp, sp, #20
8: e58d0004 str r0, [sp, #4]
c: e59d0004 ldr r0, [sp, #4]
10: ebfffffe bl 0 <fun1>
14: e58d000c str r0, [sp, #12]
18: e59d300c ldr r3, [sp, #12]
1c: e1a00003 mov r0, r3
20: e28dd014 add sp, sp, #20
24: e49de004 pop {lr} ; (ldr lr, [sp], #4)
28: e12fff1e bx lr
if we were doing this by hand, still being unoptimized, and consuming stack only as needed runtime rather than allocate a bunch up front for the whole function.
push {r0}
pop {r0}
push {lr}
bl fun1
pop {lr}
push {r0}
pop {r0}
bx lr
save a on the stack, pull it back off. save the return address just before and restore just after a nested call rather than up front and at the end. The push and pop x as needed. A compiler could certainly produce code similar to this, think for example something like this instead not related to the C code shown above.
push {r0}
...
ldr r3,[sp,#4]
...
push {r4}
...
ldr r3,[sp,#8]
push {lr}
bl fun1
pop {lr}
...
pop {r4}
...
pop {r0}
bx lr
The loads to r3 are of the same address on the stack, the same item. But the offset to the pointer moves because the pointer is moving relative to that item, dynamically through the function. And again saving the return address right before and restoring right after the place it will be lost. Some calling conventions have stack alignment rules so the above would fail that and need more instructions. It is easier to read the code and debug if the item on the stack is at the same relative address for the duration. Unwinding the stack if your tools support it, you want something more fixed not dynamic. And yes you are saving the stack consumption but by how much really?
If the instruction set has enough support for relative addressing you can build without a stack frame and make your program faster and save instruction space and a wee bit of stack space. Some instruction sets only support one direction of relative addressing, for example a stack pointer that grows downward in address space (from higher addresses to lower) but the only direction of relative addressing is a positive offset, giving twice as much range on the offset, but limited to the one direction. Which is really all a compiler needs.
Some compilers are not going to default to a stack frame and some might not even have stack frame support.
Since functions don't know where their stack frame is in memory at compile time, how do they know the memory address of their local variables?
The compiler working on the function knows how many local resources are needed, at compile time. The stack is not fixed addressing you have to use relative addressing. The compiler, at compile time, allocates the stack space, knows where in that allocated space each resource is, and generates the relative addressing instructions to access each individual resource. All done at compile time.
Static locals are not on the stack so they are addressed like a global variable, link time and fixed addresses are involved.
Related