How are variables accessed in the correct order from the stack?

Question

I'm learning about the stack but one thing I am unable to understand is how variables can be accessed in the correct order.

So if I had a basic program calculating the sum of some user entered values (pseudocode)

Input value1
Input value2
Input value3
Input value4
Input value5
result = value1 + value2 + value3 + value4 + value5

Am I correct in thinking the variables value1 through to 5 would be stored in the stack? If so this means that value 5 would be the first out for the next section but since my program needs value1 first how does it get this value? (assuming a simplistic computer with minimal registers).

Answer 1

That depends on how your program is written, its language, and how exactly your compiler implements variables. Some languages just don't place variables on any stack (everything is global). This is how FORTRAN and early versions of BASIC used to work. "Normal" languages (like C, Pascal and such) allocate a structure (often called activation record) on the stack, containing space for the local variables, and use architecture-dependent (and compiler-dependent) code to get at the variables. Many scripting languages will have the variables handled by allocating space elsewhere and just linking to the values from an activation record-like place in the stack. Even other languages, particularly LISP-derived ones, don't enforce the last call done -- first call finished rule, and thus can't use a stack for activation records. As @YuvalFilmus comments, there are languages like FORTH around, where it is your responsibility to manage such details.

Answer 2

This stack here is different from the data structure: you can access every element (typically). The stack is just a piece of memory the compiler uses with a certain structure; it's a stack of frames, one for each (nested) method call. Inside each frame, we don't have a stack.

The compiler knows, at compile-time, the offset for every variable from the top-of-the-stack pointer (i.e. its position in the stack frame) -- because it defines it. So the compiler has no trouble at all writing code to access whichever variable is needed.

The details depend, of course, on the compiler (and thus, indirectly, on source and target language/platform). There also are (virtual) stack machines on which you have to work differently, e.g. the JVM.

Answer 3

When performing reverse engineering on a software created by a compiler such as C or C++, we can see how the stack is manipulated.

Before calling a function, each parameter value is pushed on the stack. The function is then called with the instruction "CALL" which perform two operations : it push the current instruction pointer on the stack, then perform a "JUMP" by over-writing the instruction pointer with the address of the function.

The first operation performed when entering a function is to add a specific constant to the stack pointer. The constant is equal to the number of bytes needed by all the local variables. Adding a constant is like performing a number of pushes all at once. This is a very efficient way to reserve a frame on the stack. However, it does mean that local variables are not initialized before they are first used.

Every part of the function which needs to access a local variable will use an indexed instruction. In other words, it can read/write any variable without first pop-ing any value from the stack.

In the case of x86 processor, since it lacks instructions to access the stack pointer, the convention is to copy the value of the stack pointer to another register, EBP, which does have indexing address mode. The register EBP is copied before reserving the space for the local variables. The beauty of this convention is that all parameters are using positive index values and all local variables are using negatives values.

Final remark: when a compiler uses aggressive optimization techniques, the reverse engineered code may be very hard to understand. For example, if a local variable is used only near the top of a function, the compiler may pop it out. After executing that line, the index value used is adjusted to take account of the updated stack pointer. Another optimization which makes lots of sense is for the compiler to use a register for some local variable instead of reserving space on the stack. The reverse engineered code would show that the index used on the stack would effectively have values not assigned to some local variables.