What makes the stack concept useful in embedded programming?

Question

Below is an illustration of the stack concept:

I have read many times about the stack pointer and how some variables are stored in SRAM on a stack.

Many tutorials explain how it works, but not why this concept exist at all.

Imagine I am the program and I want to store my cup, my watch and my hat in my room. Why would I store them on top of each other instead of putting them in random places in my room?

Program can reach the data as long as it has its address. But if the stack pointer puts x on the top y. How will it reach y without removing x then? So to me a stack must make things (data access) even harder.

Can you give a very simple example with registers or assembly code or C code to illustrate the benefit of this stacking concept, namely "Last in, first out" (LIFO)?

Answer 1

Conclusion

Yes, you want stacks in embedded programming. It's a good idea that has emerged from long experience.

Short History

I'm old enough to have worked on computers that didn't possess hardware stack support. (You can always manufacture your own stacks in software, obviously, if you have the necessary instructions for some kind of indirect memory references, anyway.) So perhaps I have a few things to say about the topic.

The HP 21xx series processor family is a good example. Back in the day this processor family was commonly used in dual-processor configurations by school systems as a time-sharing system for administrative and/or student use. The last software edition using the HP 21xx processor family was the HP 2000F Timesharing System. (They switched to the HP 21MX going from "F" to "G".)

The instruction set did not support stacks for making a subroutine call. Instead, it poked the first memory location with the return address and started execution of the routine at the next address. At the end of the subroutine, there would be an indirect jump instruction that would reference that first memory location and jump back to the caller, just after the call, in that fashion.

Here's some actual code from the BASIC operating system (note the UPPER CASE being used -- lower case wasn't always available):

STACH NOP
      STB LTEMP+8      SAVE B-REG.
      AND B177         CLEAR TOP BITS.
      LDB STABF        GET BUFFER POINTER.
      CLE,ERB
      SEZ,RSS
      ALF,SLA,ALF      CHARACTER ON LEFT.
      IOR 1,I          CHARACTER ON RIGHT.
      STA 1,I
      ISZ STABF        BUMP POINTER.
      LDA LTEMP+8      RESTORE OLD B-REG.INTO A.
      JMP STACH,I

The last line is the return from subroutine instruction. Note that a NOP is always used as the first instruction of a subroutine. That's because it is always "blown away" and replaced by the caller's return address when the subroutine is called.

The RSS instruction is a modifier that "reverses the skip sense" of whatever it modifies. In this case, a "Skip next instruction if Z=0" instruction (SEZ.) So RSS reverses that sense and changes it to a "Skip next instruction if Z!=0" instruction.

Here's a nearby example that actually has to play with the return address because it wants a different routine to directly return to this routine's caller:

STAPR NOP
      LDA STAPR        SAVE RETURN ADDRESS.
      STA T35SP
      LDA T35B2        COMPUTE # OF CHARS.
      CMA,INA
      ADA STABF
      LDB T35B2        RESET BUFFER
      STB STABF         POINTER.
      LDB T35B1
      JMP T35SP+1      OUTPUT.

Note that the last instruction jumps to T35SP+1. That's one instruction after T35SP. (T35SP is yet another function.) Note also that this routine had to first copy its own return address and stuff it into that first address of this routine they will at the end be jumping to. This allows the routine they jump to (which uses a JMP,I instruction to return) to return to its caller, directly. There's no stack, so this is kind of how it was done back then.

(The CMA,INA is the same thing as NEG A. It just means complement A and then increment A. You could do one, the other, or both in a single instruction.)

Note also that the assembler did NOT support local labels. All labels were completely global. This means those HP 21xx programmers were continually having to come up with new, slightly modified names for things to avoid conflicts. And no lower-case!

Yup. You got it. Times were hard back then.

Of course, an entire BASIC interpreter code providing time-sharing capabilities for 32 simultaneous users and as well as all the usual transcendental functions, matrices, the usual matrix operations that included matrix inversion and matrix determinant operators would fit completely inside of 6k-word (16-bit words.) Yes -- The whole thing.

Now ask yourself, "What could I do with only 12k-byte of code space to work with?"

Moving on,

An immediately obvious problem with this arrangement is that you cannot call any other routines that might need to call the routine you are currently in because, if that were to happen, you'd lose the original caller's return address. And you certainly cannot recursively call yourself!

So if that's a requirement, you have to write a bunch of code in the routine to copy the address to some "software stack" that you create. And you have to do that everywhere it may be an issue.

It can become a serious pain. Been there, done that.

During the '60's, there was a learning process going on about useful mechanisms.

There's a step-wise process of learning that's sometimes called 2nd system syndrome. Or, at least, among my peers at the time. This is where the 1st system just fails to meet the necessary targets in a variety of ways and there's a strong push to use what's been learned in order to create a brighter 2nd system. But the 2nd system goes over-board with features and, as a result, consumers complain that they can't find the main things they really need as they are buried among so many different options. So, after some feature-trimming, right about on the 3rd system attempt then the design is "about right." (I suppose this could also be the story of Goldilocks and the three bears, where the last bed tried was "just right.")

When the PDP-11 was designed, it was a "2nd system" approach. They provided every possible way of having hardware support stacks. There is nothing like it, today. Nothing quite that good. You should get a chance to see the instruction set. It's a marvel in ways to call other routines. You can call code and have your return address placed in a register. This is great for fast co-routines. You can call code and use almost any other register as a stack pointer for the return address. Not stuck with just one. You want two hardware stacks? No problem. Three? That's okay, too. Every register can be used for: Register, Register Indirect, Auto-increment Pointer, Auto-decrement Pointer, Auto-increment Pointer Indirect, Auto-decrement Pointer Indirect, Indexed Pointer, and Indexed Pointer Indirect.

The PDP-11 was stack-heaven. Life seemed good.

But then... the 3rd system syndrome hit. Now, we are stuck with a more "balanced" view of instruction sets.

Oh, well.

The Stack Frame aka Activation Frame

A stack isn't just a stack for holding return addresses. It's also an important tool for compiling code from source languages and for assembly programmers who want an easier life than having to keep track of stuff strewn about the room, in random locations.

I drew this up a long time ago:

The above, shown in the whiter region, is a typical activation frame.

The above diagram does not define all possible variations. Only one of the simpler ones. For example, Pascal requires support for nested functions and these nested routines must have access to local variables in their enclosing code bodies, so the activation frames for compiled Pascal code may be a little more complicated than what's above.

The caller pushes parameters onto "a [thread] stack" and then makes a call, which automatically pushes the return address. Note that in the above case there is an "optional" return value parameter. This is because sometimes the return value might be a vector instead of something that can easily fit in a register. (Registers are often used as return values, when the data result readily fits -- such as integers.) So the called routine can use this slot to stuff the vector return value, if that's appropriate. But it is optional in the sense that each circumstance determines if it is needed, or not.

Once the called routine starts, the first thing it does (using prologue code) is save special registers that must be preserved across calls. These registers are ones that the calling routine rightly assumes won't be destroyed when it calls the subroutine. They were sometimes called "preserve registers," but I've no idea what today's computer scientists call them. The point is if the called subroutine needs to play with those registers, then it must save them so that it can return them, unmolested, to the caller.

Separately, a different register called the "frame pointer" or "activation frame pointer" must also be preserved. This is just one added register that is reserved for this special activation frame purpose by a compiler (or assembly coder.) The activation frame pointer always points at the "current frame" on the stack and it provides the currently executing subroutine with access to everything it needs to get its job done.

(The order in which the above preservation takes place isn't terribly important. There are pluses and minuses, regardless of the choice.)

After the necessary prologue is over, the subroutine gets about its business. Once it is over, the subroutine is now required to restore the preserved registers, restore the activation frame pointer and then return to its caller. (The epilogue code.)

This allows a subroutine to have its own local variables that are local to it, even in the face of recursion (calling itself.)

Let's take two un-optimized C routines and the old 16-bit x86 instruction set to make some examples for clarity.

Suppose:

int f1( int a ) {
    if ( a > 2 ) return a * f1( a-1 );
  return a;
}

int f2( int a ) {
  int r= a;
    if ( a > 2 ) r= a * f2( a-1 );
  return r;
}

I've used recursive forms of computing a factorial from a supplied value. I don't want to focus on the quality or clarity of the above code. That's not relevant. I just want to focus on how this might be compiled, and why. Also, since it has been so long since I regularly coded x86 routines, forgive any "pigeonness" of my coding. It's possible I will have forgotten a syntax detail.

       ; Caller expects the function result in AX.
f1:    push si               ; save SI because caller assumes it is preserved.
       push bp               ; save caller's activation frame pointer.
       mov  bp, sp           ; set up our own activation frame pointer.
       mov  ax, [bp+6]       ; fetch parameter value into AX.
                             ;    the +6 part is there to skip the saved BP, SI,
                             ;    and the caller's return address.
       cmp  ax, #2           ; compare it against 2.
       ble  t1               ; exit the routine if <= 2, AX is already set.
       mov  si, ax           ; save parameter value in SI where it is safe.
       dec  ax               ; subtract 1 from the given parameter value.
       push ax               ; push this value as a parameter to a call.
       call f1               ; now call ourselves to compute its factorial.
       imul si               ; multiply this result (in AX) by the saved parameter.
                             ;    the result will be in DX:AX, but we ignore DX.
t1:    pop  bp               ; restore caller's activation frame pointer.           
       pop  si               ; restore SI.
       ret                   ; result is already in AX so just return.


       ; Caller expects the function result in AX.
f2:    push bp               ; save caller's activation frame pointer.
       mov  bp, sp           ; set up our own activation frame pointer.
       sub  sp, #2           ; reserve 2 bytes for local variable 'r'.
       mov  ax, [bp+4]       ; fetch parameter value into AX.
                             ;    the +4 part is there to skip the saved BP
                             ;    and the caller's return address.
       mov  [bp-2], ax       ; set local variable 'r' to parameter 'a'.
       cmp  ax, #2           ; compare 'a' against 2.
       ble  t2               ; exit the routine if <= 2, result 'r' is already set.
       dec  ax               ; subtract 1 from the given parameter value.
       push ax               ; push this value as a parameter to a call.
       call f2               ; now call ourselves to compute its factorial.
       imul [bp-2]           ; multiply this result (in AX) by 'r'.
       mov  [bp-2], ax       ; save result in 'r' (ignore DX.)
t2:    mov  ax, [bp-2]       ; put 'r' into the function result register.
       pop  bp               ; restore caller's activation frame pointer.           
       ret                   ; just return.

These are intentionally left unoptimized in order to maintain coherency with the source code. A good optimizer would have a field day with the above code.

I wanted to provide two different cases: the first highlights preserving a register that a caller expects not to be changed across the call and the second highlights how local variables are allocated using the stack. In the second case, note how easy it is to allocate -- just subtract a number from the stack pointer. You can subtract a much larger number, still with a single instruction, to allocate vast amounts of local variable storage. It's truly 'that easy.' (Note also that these local variables are not initialized!)

If you work through a few examples like this, you'll see many benefits to the concept of a stack.

I've not described something in the picture. There's an optional exception handler pointer. This is quite useful when handling exceptions. Normally, this can be NULL when this routine doesn't include a Try-block handler. But if it does, then this value is set to the code that will handle the error. There is a process called a "stack unwind" (back in my day) where an exception that occurs in one routine that does not have a handler, will slowly unwind the stack backwards to prior callers until it finds one that has a handler installed. This action "blows away" the context of all called subroutines beneath the routine that carries a handler for errors. It's a convenient device. But beyond the context I wanted to add here.

A final note. The order and manner in which the preserved registers and the activation frame pointer are pushed onto the stack and restored from it isn't a vital issue. Different folks will choose different approaches here. It's just important to know what choice is actually made, because it impacts the offsets used relative to the activation frame pointer when accessing either parameter values or accessing local variables. The activation frame pointer is used, though, for all those accesses since the parameters and the local variables are all relative to the activation frame pointer. The exact positions relative to it are not important. But it is important that their relative positions are fixed and that the compiler or assembly coder knows the offsets to use and doesn't need to perform some run-time calculations to work them out.

Conclusion?

Yes, you want stacks in embedded programming. It's a good idea that has emerged from long experience.

(And you certainly do not want the HP 21xx instruction set implemented on your MCU if it doesn't implement FeRAM or magnetic core memory -- as it requires writable code space!)

Answer 2

The current place of execution is stored into stack when starting a subroutine, so that when the subroutine ends, it can be popped off the stack.

This enables a way to store context what the program was doing before changing context to another subroutine, and even makes it possible for subroutine to call itself recursively, so it goes only one level up on returning. That is useful if a subroutine is called multiple times, it does not make it forget where it is supposed to return. That's the problem of just storing the return address somewhere if it is not a stack.

So during the subroutine call, you don't need to access any context of subroutines that were executing prior to the subroutine that is called. This context includes both local variables of a subroutine, and the return address how to get back to previous subroutine.

Answer 3

You gave us one analogy, and now I will give you another one.

What if you were greeting people at the door of an establishment and collecting coat and hat from each person who entered to visit? If you knew for sure that the last person to visit would be the first to leave, you could store the hats and coats in a stack like structure. Then as each person left, you would hand them their coat and hat and go to the next hat and coat in the stack with minimum hassle and fuss. This is how function calls in a computer program work (to some extent).

Functions can call other functions in any order, but each time a function call occurs, the stacking increases one level. Each time a function call returns, the stacking gets reduced by one level.

Since functions use temporary memory and since the exact order they will be called in is not necessarily predetermined, the stack is a great way to handle this. The permanent memory address idea would work OK for programs with no function call mechanism, but it would make recursive function calls much more difficult.

The stack concept occurs often enough in data processing that even high-level programs sometimes use fancy stack data structures (last in, first out data structures).

Answer 4

Imagine I am the program and I want to store my cup, my watch and my hat in my room. Why would I store them on top of each other instead of putting them in random places in my room?

You're looking at this in the wrong way: imagine yourself not as the whole program, but as a subroutine that may be put in any of a variety of programs.

Programs of any significant size are generally built up in a modular way from small "components," or software routines. Small routines are more easily tested and offer more flexibility in how they can be combined to make a larger program and reused between programs. However, for this to work it is vital that these routines do not interfere with each other, even when one calls another one.

One way in which they can interfere is in their use of memory locations. If you have two different routines you're combining to use within a program, routine A uses memory location 6 to store some of its data, and calls routine B which also uses location 6 (even if just as a temporary thing until B is completed), routine B will overwrite routine A's data and routine A will break.

This can be avoided to some degree by keeping careful track of who uses what locations and who calls whom, but as the number of routines increases, the potential interactions between them increases exponentially. Thus it's useful to have a way of minimizing these interactions and a stack allows that by making reentrancy easier. When a routine needs to save something temporarily, it can always push on to the stack and later pull that value off that stack, while being completely unaffected by what's placed on the stack by any of the code leading up to the routine being called and also unaffected by stack use in any code it calls. (Of course, all routines must agree that they will always, before they exit, pull off the stack anything they had earlier pushed on to it.)

The simplest example is to imagine that you're a routine that needs to use the A register, but you're called with a (to you) random value in the A register that you must preserve. (For example, if you're called via an interrupt, the A register will contain whatever value another routine was in the middle of processing and that must not be changed when the other routine resumes or it will break.) In this case you can push the A register on the stack, go on to use it for your own purposes, and then pull the A register from the stack when you're done, restoring its original value and also leaving the stack exactly as you found it.

If you'd like a slightly more detailed example of stacks solving the reentrancy problem, you might also have a look at this answer from the Retrocomputing Stack Exchange.

Program can reach the data as long as it has its address. But if stack pointer puts x on the top y. How will it reach y without removing x then? So to me stack must make things(data access) even harder.

Well, it does make accesses "back up the stack" more difficult; generally when one needs to do this there will be a sequence of pointers on the stack that allow you to go back, routine by routine, finding the "stack frame" of each so you can access its data. (Thus, you could look up the hat you stored, the hat stored by the routine that called you, a different hat stored by the routine that called it, and so on.) This is not an unusual technique, but explaining it in detail is probably beyond the scope of the answer you're looking for.

Answer 5

But if stack pointer puts x on the top y. How will it reach y without removing x then? So to me stack must make things(data access) even harder.

It doesn't have to. These variables are temporarily stored on the stack in the exact order (push), then they are retrieved back in the reverse order.

At each function call, interrupt,... the processor pushes the registers on the stack, the most important among them is the PC - program counter, is the last position in the program before it jumps to another position in the program memory. When the function is called, then it jumps to another position, it processes the function and then in the reverse order it pops the registers, lastly the PC and it starts to execute where it was interrupted.

Answer 6

why this concept exist at all

The stack is a very simple temporary storage mechanism. To extend your analogy, it's the entry table of your room (that you pull out of the wall). It's already there, you know where it is and how to reference it. So you stack your item(s) there. When you are done, you take your stuff and put the table away, giving you your space back.

If you wanted to place them in random places, you'd first need to allocate that space (either in BCC or the heap), like building a table to put your hat on. Then (in the case of heap storage) when you remove your hat and leave the room, you need to deconstruct the table before you leave. Otherwise when you come into your room again and build a table for your hat you'll eventually run out of room for tables. That's called a memory leak!

If you want to use a permanent variable (from BCC) that would be like making one table per item, and they are always there taking up space, whether you used them or not.

How will it reach y without removing x then?

Not a problem! There are other registers (a shelf in the room?) that the stack pointer is copied to (SPc). Then the stack pointer is added to in order to create the temporary space on the stack. So SP+=1 to store X. Then SP+=1 again to store Y. The programmer can still access the memory pointed to by SPc+1. Of course the more efficient way is to do SPc+2 and then put X at SPc+1 and Y at SPc+2, but that's another story.

Answer 7

Imagine I am the program and I want to store my cup, my watch and my hat in my room. Why would I store them on top of each other instead of putting them in random places in my room?

You wouldn't.

But you could put your overcoat, hoodie and t-shirt in a stack, in that order, because you only ever need the top one of those, and to make use of the bottom one, you need to wear the others first.

Or, if you're a recursive function, and you only ever need the variables of the most recent instance of the function, putting them in a stack and just looking at the top one always gives the most recent instance. Usually, a general purpose programming environment would generalize that for all function calls, so it doesn't need to analyze the whole call tree to know which ones can be called from each other. That gives smaller memory footprint than allocating a distinct area for each function does.

None of this is probably specific to embedded programming, stacks come up in algorithms elsewhere too.

Answer 8

There are some very detailed answers already, but I think it might be helpful to focus on one of the most important.

A stack helps you write re-entrant code, that is, subroutines that can be called again before they finish. You need these for recursive algorithms, and sometimes for event handlers.

If you try to write one of these without a stack, one problem you have is how to return from the subroutine and resume execution. You need to save the original state of the program somewhere, and if the subroutine gets called again, it has to put the new information someplace else without overwriting the other information.

Another problem you get is when a subroutine needs local temporary data. If the same function gets called recursively, each call needs its own local data that won’t overwrite the data from earlier calls.

A stack is not the only way to do this, but it’s the solution everyone ended up using because it’s so simple: you allocate a new block of memory by subtracting the number of bytes you need from the stack pointer. Allocating memory from a heap is much slower and more complicated. And then, programs used the stack so often, most CPUs built support for it into their instruction sets.

Answer 9

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.

Answer 10

In many situations, you need to complete sub-steps before you can complete the larger steps. Think of the instructions for building legos. Every now and then they have to stop and say "Okay, put the big creation down. We need to put together a smaller piece that will be easier to build on its own."

If I may use your example:

Imagine I am the program and I want to store my cup, my watch and my hat in my room. Why would I store them on top of each other instead of putting them in random places in my room?

Now I'm sure you didn't mean "random." You meant "arbitrary." Random means that you'd have to go search for your watch every time -- something embedded code tries to avoid doing. You meant that you'd just put them individual spots, not on top of each other.

So let's write some instructions. Here's part of the "wakeup" routine. (ignore the emphasis for now, it will make sense later)

1. Pick up the cup that is on the bottom right corner of the bedside table in your room.
2. Drink orange juice from the cup
3. Put the cup in the bottom right corner of the bedside table in your room.
4. Pick up the watch from the middle of the bedside table in your room
5. Put watch on wrist
6. Pick up hat from top of the bedside table in your room
7. Put the hat on.

Now, let's go on a vacation. We're creatures of habit, so we want to follow the same wakeup routine. However, there's a problem. The instructions above specify "the bedside table in your room." That room is hundreds of miles away. You're in a hotel room. So we write another routine, "wakeupInHotel"

1. Pick up the cup that is on the bottom right corner of the bedside table in the hotel room.
2. Drink orange juice from the cup
3. Put the cup in the bottom right corner of the bedside table in the hotel room.
4. Pick up the watch from the middle of the bedside table in the hotel room
5. Put watch on wrist
6. Pick up hat from top of the bedside table in the hotel room
7. Put the hat on.

This works, we just replaced one bolded section with another. But obviously this is a tough way to write code. You have to write a different version for every room you are in. There are times you write this way (for speed), but usually we want to make more generic instructions like "wakeupIn(currentRoom)":

1. Pick up the cup that is on the bottom right corner of the bedside table in currentRoom.
2. Drink orange juice from the cup
3. Put the cup in the bottom right corner of the bedside table in currentRoom.
4. Pick up the watch from the middle of the bedside table in currentRoom
5. Put watch on wrist
6. Pick up hat from top of the bedside table in currentRoom
7. Put the hat on.

Now I can have "wakeupInRoom(myBedroom)" and "wakeupInRoom(hotel)" which execute the above instructions in the context of currentRoom=myBedroom or currentRoom=myHotel. Much more efficient, and more like the way we want to approach getting ready in the morning!

So what we need is a place to store this scoping information that describes the environment that the function is being executed in. These don't have to be a stack. You can put the information anywhere, and make the context just be a pointer to it.

However, going back to the lego assembly process, we find that quite often these contexts start nesting. You start building a large product. Then you switch to building a smaller sub-component until it is complete, and then you resume assembling the largr prodct. Then you switch to building another sub component. Think IKEA!

When this pattern of sub-steps occurs, we realize something useful. The context for the substep isn't needed until the moment you call the subprocess. And once the subprocess is completed, you don't need the context for it anymore. So you end up with this pattern where you have this big wide tree of contexts (perhaps you have 1 context for putting on each wheel of the lego contraption, using the same "putOnWheel" subroutine). Most of that tree is idle and unneeded most of the time. It's inefficient.

So what do we need to keep? We need to keep the current context, obviously. And we need to keep the contexts for the larger steps so that when we're done with our current step, we can go back to the larger process.

If you look at the structure, you realize that a stack is a very efficient way of keeping track of this data. You don't have to hold onto the whole tree, just the path from the root task to your current task.

A stack has a few particular benefits:

• The CPU only has to keep track of one pointer: top of stack. The rest isn't important until your current task returns. We store the "return pointer" on the stack too, so the CPU only sees the top of the stack, and we can use plain ol' memory to handle the rest of the chain. This means the CPU doesn't need any complicated functions to support this structure. Just a single pointer.
• This structure doesn't waste any memory. It has just the one extra "return pointer" that you need to support the idea of going back to the larger task, and nothing more.
• The program can reuse stack memory for calls with different contexts. As you get into higher order embedded programming (like C) you'll get used to the idea that every memory location has a "type," which is the kind of data you store in it. You can't change these types once chosen. Because we get to "throw away" the contexts after we're done with them, we can treat the space just above the "top of stack" as nothing more than "unallocated space" until you call something using that space. This makes book keeping tremendously simple.

So in the end, we use the stack because it is the perfect data structure for maintaining these hierarchical sub-task patterns. And, over the decades, programmers have found overwhelmingly that the things we want computers to do fit into this sub-task pattern. And that is why basically every computer out there has a stack.

The exception, of course, are the ultra-tiny embedded processors. They are small enough that they really cant' do much, so there's not much opportunity to do the kind of optimizations like we showed in the wakeup routine. On those processors, anything you want to do can be written out long-hand. This takes more effort (and sometimes more skill), but it avoids wasting the precious bytes for the "return pointer." It also means you don't need the CPU instructions required to manipulate a stack, so you can have a smaller instruction set. But outside of these extreme cases, we use stacks because they work.

Answer 11

The need for a LIFO queue (AKA stack) appears quite naturally as soon as you introduce function calls.

When calling a function, you temporarily leave the current context and enter that of the function. And if there is a function call in that function, you will also temporarily leave the function context and enter that of the newly called function.

The stack is there to let you know "where to return to" upon function completion, across the nesting levels, and this is where LIFO is required. At the same time, the stack frames allow to store the variables local to the function, and the stack is a convenient and efficient way of storing automatic variables.

Answer 12

I think this is a result of evolution of two factors:

1. Simplicitly of hardware;
2. Requirement to have abstract means to reason about programs.

In simple approximation processors can be seen as machines executing microcode. This way they can be described as:

• Set of registers, with one serving as instruction pointer;
• Arithmetic Logic Unit;
• Block to read data from, and write it to memory (both data and instructions);
• Block to decide what to do with specific instructions.

This is basically enough to execute arbitrary complex logic.

One can draw an execution graph, and see it can be arbitrary complex and beautiful in some sense.

Now we have a human being who should reason about programs. Graph representaion of code, or even a list of microcode instructions is not easiest way to think about program.

We use analysis and synthesis to reason about complex matters, which means we want to split this long list of microcode into sub sections that we call functions.

Once we do that we reach to a requirement of interface of a function that should address:

• how parameters are passed;
• how parameters are returned;
• what is entry point;
• what to do when function completes.

This way we arrive to idea of buffer (frame) to store data and instruction pointer to jump on complete.

So, when one calls a function, a buffer is set up, function is jumped to. After it completes execution is jumped to the next destination.

When you go back from analysis to synthesis you can see that program is functions calling other functions. Their frames form structures called stack.

So, why do we have stack?

Not because of hardware but due to humans!

Aliens might write programs differently.

Answer 13

These days we often think about how a thread’s stack helps it have ownership of data rather than sharing that with other threads, but in the OSless embedded world where you’re software architecture is a super loop a stack can seem or even be an unnecessary complication, but more often than not it helps more than it hurts.

The super loop of embedded programs often consists of a series of function calls inside of a forever loop. There may be some sort of event that each function gets to see at each call, the entire loop might block waiting on an event, or several other variations, but they follow a pattern. (In arduino the super loop calls the loop function once per cycle through the actual loop) A super loop can call multiple functions (which represents different modules, such as a communication interface, power source monitoring, measuring some system, storing data to non-volition storage, telling a robotic hand to slow down its grasping motion because its fingers are approaching the surface that it is grasping, …). Each of these functions may have some persistent state which could reside in global memory/be declared as global variables (or could be done in more of an object referenced way), but it’s very likely that at least sometimes a module function will need some temporary data that only needs to be used for the duration of a single call into that function. You could declare that data as global and tell everyone else not to use it, but if RAM space is tight then there might not be enough space for it. You could use heap allocation and free it when done, but that introduces complications (forgetting to free in all code paths, double freeing, heap fragmentation, handling memory allocation failures, …).

Using a stack each module gets to reuse the same memory space. It’s a dynamic overlay that works automatically for cases where the memory is only needed for the duration of a single call. This also makes the cases that need more persistent memory more obvious, and you can spend more effort designing and planning for those.

In an cpu with data cache you also benefit from the stack memory almost always being in the cache because it’s accessed so often.

I’ve programmed several systems in assembly, and one of those didn’t have a hardware stack. It has 16 registers, which was usually plenty, but it was also very common to need to store 1 more word for just a moment and have to either spend huge amounts of effort searching for a register that was free (for that part of the code) and then proving that it was in fact free. It would have been so much easier and safer to have been able to just push, do my stuff, pop.

Stacks are so useful that at least some 8051s have a separate memory space that is just the memory of the stack. Some compilers introduce second data stack when compiling for AVR. And Atmel (now part of Microchip) made the registers of some of its microcontrollers memory mapped so on some of their tiniest systems the registers could be used as a stack.

The pain of doing offsets from stack pointers is greatly eased by language compilers and language aware debuggers. It very much is a pain when you don’t have access to those, but even then I would usually rather have a stack than not.

I was recently designing a simple low lowered embedded program that slept 99.9999% of the time and responded to events in interrupts, and for that I did consider going (almost) stackless. ISRs couldn’t be interrupted themselves, each of the modules could have owned some registers and RAM, and no one besides the initialization code needed more than a few bytes of data.

Answer 14

A stack is used because it is faster to implement it in hardware than keeping track of variables in software