To provide a concrete example of how a compiler manages the stack and how values on the stack are accessed, we can look at visual depictions, plus code generated by GCC
in a Linux environment with i386 as the target architecture.
1. Stack frames
As you know, the stack is a location in the address space of a running process that is used by functions, or procedures, in the sense that space is allocated on the stack for variables declared locally, as well as arguments passed to the function (space for variables declared outside any function (i.e. global variables) is allocated in a different region in virtual memory). Space allocated for all of a function's data is referred to a stack frame. Here is a visual depiction of multiple stack frames (from Computer Systems: A Programmer's Perspective):
2. Stack frame management and variable location
In order for values written to the stack within a particular stack frame to be managed by the compiler and read by the program, there must be some method for calculating the positions of these values and retrieving their memory address. The registers in the CPU referred to as the stack pointer and the base pointer help with this.
The base pointer, ebp
by convention, contains the memory address of the bottom, or base, of the stack. The positions of all of the values within the stack frame can be calculated using the address in the base pointer as a reference. This is depicted in the picture above: %ebp + 4
is the memory address stored in the base pointer plus 4, for example.
3. Compiler-generated code
But what I don't get is how variables on the stack are then read by an application- if I declare and assign x as an integer, say x = 3, and storage is reserved on the stack and then its value of 3 is stored there, and then in the same function I declare and assign y as, say 4, and then following that I then use x in another expression, (say z = 5 + x) how can the program read x in order to evaluate z when it is below y on the stack?
Let us use a simple example program written in C to see how this works:
int main(void)
{
int x = 3;
int y = 4;
int z = 5 + x;
return 0;
}
Let us examine the assembly text produced by GCC for this C source text (I cleaned it up a bit for the sake of clarity):
main:
pushl %ebp # save previous frame's base address on stack
movl %esp, %ebp # use current address of stack pointer as new frame base address
subl $16, %esp # allocate 16 bytes of space on stack for function data
movl $3, -12(%ebp) # variable x at address %ebp - 12
movl $4, -8(%ebp) # variable y at address %ebp - 8
movl -12(%ebp), %eax # write x to register %eax
addl $5, %eax # x + 5 = 9
movl %eax, -4(%ebp) # write 9 to address %ebp - 4 - this is z
movl $0, %eax
leave
What we observe is that variables x, y and z are located at addresses %ebp - 12
, %ebp -8
and %ebp - 4
, respectively. In other words, the locations of the variables within the stack frame for main()
are calculated using the memory address saved in the CPU register %ebp
.
4. Data in memory beyond the stack pointer is out of scope
I am clearly missing something. Is it that the location on the stack is only about the lifetime/ scope of the variable, and that the whole stack is actually accessible to the program all the time? If so, does that imply there is some other index that holds the addresses only of the variables on the stack to allow the values to be retrieved? But then I thought the whole point of the stack was that values were stored in the same place as the variable address?
The stack is a region in virtual memory, whose use is managed by the compiler. The compiler generates code in such a way that values beyond the stack pointer (values beyond the top of the stack) are never referenced. When a function is called, the position of the stack pointer changes to create space on the stack deemed to be not "out of bounds", so to speak.
As functions are called and return, the stack pointer is decremented and incremented. Data written to the stack does not disappear after it is out of scope, but the compiler does not generate instructions referencing this data because there is no way for the compiler to calculate the addresses of these data using %ebp
or %esp
.
5. Summary
Code that can be directly executed by the CPU is generated by the compiler. The compiler manages the stack, stack frames for functions and CPU registers. One strategy used by GCC to track the locations of variables in stack frames in code intended to execute on i386 architecture is to use the memory address in the stack frame base pointer, %ebp
, as a reference and write values of variables to locations in the stack frames at offsets to the address in %ebp
.