When you get and go into your room you allocate three boxes. You stack them on their sides so that you can see the open end of each box. You put your hat, watch and cup in the boxes, one item each. That is the key to having the stack be useful for general purpose computing. You can have random access to your allocated stack for the duration of the time you are in your room. When you move out you free up those boxes and return them to the pile of empty stack boxes.
You get your room, you go allocate a box, set it such that the open side faces you (is not up or down but to the side). Put your cup in it. You go off and allocate another box, set it on top of the first stack box, also open end facing you, put your hat in it. Repeat until you have the desired items stored in stack boxes. For the duration of your stay you can randomly access (any item in any order) any of the times from your stack. When you move out you empty and return one box at a time from the owner of the stack boxes.
True, stacking them such that the open end is covered by the next box on the stack and you can only access the item on the top of the stack does not work nor make sense for general purpose computing (with high level, compiled, programming languages). There is a use case that you will find in some processors. Return addresses for function calls. You nest your function calls and you cant cheat, you have to return from one before you can return from the next higher one. So you can use a stack in that way such that you can only at any time see the contents of the item on the top of the stack and all the others are blocked from view.
So why not just try it?
unsigned int fun ( unsigned int a, unsigned int b )
{
unsigned int x;
x=b;
return a+x;
}
Unoptimized:
Disassembly of section .text:
00000000 <fun>:
0: e24dd010 sub sp, sp, #16
4: e58d0004 str r0, [sp, #4]
8: e58d1000 str r1, [sp]
c: e59d3000 ldr r3, [sp]
10: e58d300c str r3, [sp, #12]
14: e59d2004 ldr r2, [sp, #4]
18: e59d300c ldr r3, [sp, #12]
1c: e0823003 add r3, r2, r3
20: e1a00003 mov r0, r3
24: e28dd010 add sp, sp, #16
28: e12fff1e bx lr
We have ideally three things on the stack, copy of a, copy of b, and x. That is 12 bytes. The calling convention for this tool and target says the stack must be aligned on a 64 bit boundary, so the compiler instead allocate 16 bytes.
0: e24dd010 sub sp, sp, #16
Adjust the stack pointer, similar to doing four pushes on the stack. The stack grows down (quite common) in address space. Heap grows up up from lower addresses go higher.
At this point we do not know nor care what is in those for stack locations. We assume garbage.
4: e58d0004 str r0, [sp, #4]
This is the key to your understanding. The stack pointer can be used with an offset (was not and is not always the case). So you 1) do not have to push to allocate and 2) do not have to pop to uncover and discover items that were pushed.
r0 is where the a variable is passed in so:
[sp+12]
[sp+8]
[sp+4] write variable a (r0) here
[sp+0]
8: e58d1000 str r1, [sp]
r1 contains the b variable per the convention
[sp+12]
[sp+8]
[sp+4] a
[sp+0] write b here
c: e59d3000 ldr r3, [sp]
[sp+12]
[sp+8]
[sp+4] a
[sp+0] b
read the b value from the stack into r3
10: e58d300c str r3, [sp, #12]
[sp+12] this is x, write r3 (the b value) here
[sp+8]
[sp+4] a
[sp+0] b
14: e59d2004 ldr r2, [sp, #4]
read a into r2
[sp+12] x
[sp+8]
[sp+4] a
[sp+0] b
18: e59d300c ldr r3, [sp, #12]
read x into r3
[sp+12] x
[sp+8]
[sp+4] a
[sp+0] b
1c: e0823003 add r3, r2, r3
add r2 (a) and r3 (x) and save in r3
20: e1a00003 mov r0, r3
make r3 (a+x)(which is a+b) the return value (r0)
yep, absolutely they could have done an add r0,r3,r2 but this is unoptimized and for the moment r3 holds x
24: e28dd010 add sp, sp, #16
always put the stack (pointer) back the way you found it
28: e12fff1e bx lr
Now to be fair this is what optimization does for you:
00000000 <fun>:
0: e0810000 add r0, r1, r0
4: e12fff1e bx lr
Here is another one and this is technically connected to the early days of the stack concept.
unsigned int more_fun ( unsigned int );
unsigned int fun ( unsigned int a, unsigned int b )
{
return(a+more_fun(b));
}
Optimized:
00000000 <fun>:
0: e92d4010 push {r4, lr}
4: e1a04000 mov r4, r0
8: e1a00001 mov r0, r1
c: ebfffffe bl 0 <more_fun>
10: e0800004 add r0, r0, r4
14: e8bd4010 pop {r4, lr}
18: e12fff1e bx lr
If it helps to understand, this is the functional equivalent of the above:
push {lr}
push {r4}
mov r4, r0
mov r0, r1
bl <more_fun>
add r0, r0, r4
pop {r4}
pop {lr}
bx lr
So there are a few things going on here. We are pushing two things on the stack. r4 and lr. Per the calling convention we cannot destroy r4 (r0-r3 yes, not r4). So if we want to use r4 we have to save it and restore it (perfect use of the stack). lr holds the return address for the function. bl modifies lr, so we have to save lr for this function so that the call to more_fun does not lose our place in the world. r0 is the first parameter, a, for the call to fun, it is also the first parameter to the call to more_fun as well as the return value from more_fun, so we need to save a somewhere, and the compiler chose to use r4, which we will see why later. Instead of saving r0 on the stack it saves some other register on the stack (that more_fun and all nested function calls will put back/leave untouched) and saves r0 (a) in that register (r4).
I crafted this function so that the a variable is used after the call to more_fun which means we have to remember the a variable through a call. And the compiler chose to push r4 and save a in r4.
0: e92d4010 push {r4, lr}
save the return address and preserve the contents of r4 so we can use it in the function
4: e1a04000 mov r4, r0
save the value a in r4
8: e1a00001 mov r0, r1
the value b (r1) is the first parameter (r0) to the call to more_fun, prep the call to more_fun by putting b in r0
c: ebfffffe bl 0 <more_fun>
call more_fun
10: e0800004 add r0, r0, r4
add the return value from more_fun and the variable in r4 (a) together and save in r0 (the return value for fun())
14: e8bd4010 pop {r4, lr}
restore the contents of r4 to the value found when the function started. restore the return address from fun()
18: e12fff1e bx lr
return from the function call.
You may be asking why not do it this way:
push {r0}
mov r0, r1
push {lr}
bl 0 <more_fun>
pop {lr}
pop {r1}
add r0, r0, r1
bx lr
push {r0}
save the variable a on the stack we need it later
mov r0, r1
prepare the call to more_fun by putting b as the first parameter
push {lr}
bl modifies lr, lr is the address we need to return from fun() so we need to save it temporarily on the stack.
bl 0 <more_fun>
call more fun (note this is unlinked the linker would fill in the relative address later)
pop {lr}
restore the return address to lr
pop {r1}
recover the variable a value into r1
add r0, r0, r1
add the return value from more_fun plus the a variable. r0 is the return value for the function fun()
bx lr
return from fun();
If the calling convention did not have a stack alignment rule there is nothing wrong with the compiler generating code like that. It uses far less stack space when you start nesting functions (which we do normally). We tend to go so far as to burn a second register as a frame pointer, add more instructions per function to prep the frame and restore it at the end. Why? so we can unroll stacks with debugger tools, I have no use for debuggers and have less use for unrolling stacks in some automatic fashion. I personally have no need to permanently burn code and memory space for something I will never use.
Pre-allocating everything we need for the duration of the function makes it easier for humans to read (a specific variable on the stack will or can always be at a fixed offset from the stack or frame pointer (both)). This makes it easier to generate code from the compiler and easier to debug the generated code which makes the compiler more reliable and less buggy. At the cost of memory to the user. The compiler authors themselves are more than capable of writing code to keep track of items on the stack during the function
[sp+0] variable a
push b
[sp+4] variable a
[sp+0] variable b
You can easily generate code to know that at this point in the function a is at [sp+4]
pop b
[sp+0] variable a
and at this point in the function a is at [sp+0].
Good luck getting compiler folks to do that. It is what it is, if you are using a high level language you automatically accept more code and data consumption and a performance hit. True, you get more, quality, debugged, code written that is easier to maintain and reuse.
But from a traditional, elementary concept, of writing things on a note card and stacking the note cards to save stuff temporarily . This demonstrates that
push {r0}
mov r0, r1
push {lr}
bl 0 <more_fun>
pop {lr}
pop {r1}
add r0, r0, r1
bx lr
Now why push r4 and not r0?
push {r4, lr} push {r0,lr}
mov r4, r0
mov r0, r1 mov r0,r1
bl 0 <more_fun> bl more_fun
ldr r1,[sp]
add r0, r0, r4 add r0,r0,r1
pop {r4, lr} pop {r1,lr}
bx lr bx lr
same number of instructions. But you trade a register operation to a memory operation which is slower/worse. So doing the r4 thing is already better here. Add more variables (not too many) and there is a sweet spot where using more registers in the function (r4,r5,r6...) by pushing them up front and popping them at the end, is much more efficient than doing stack accesses during the function, not just a one slower instruction traded for another.
You can do without stacks if you can do without (relatively modern) programming languages (if you write in assembly language for example). Compiled languages lead to calling conventions, and local and global variables. Local variables, return addresses, etc lead to a stack and stack pointer and stack pointer relative addressing. Without the stack pointer (or stack frame pointer) relative addressing instructions, compiled languages become much less attractive for that processor.