What is the idea behind using a stack for local variables?

Question

In C as many of you know, the stack is where all local variables reside. The stack being a first in last out data structure means you can only access what has been most recently pushed onto it. So given the following code:

int k = 5;
int j = 3;
short int i;

if (k > j) i = 1;

Obviously this is useless code which has no real meaning but I'm trying to wrap my head around something.

For the short int i declaration I'm assuming 2 bytes get allocated on the stack. For int k and int j for both 4 bytes get allocated with the values 5 and 3. So the stack would look as follows

----------   <- stack pointer
int i
----------
int k = 5
----------
int j = 3
----------

so for the if statement you would have to pop the int i to get to the conditions k and j, and if so where does int i go? This all seems very time consuming and tedious if this is the way that C does local variables.

So is this actually how C does it or am I mucking it all up?

Answer 1

You're ever-so-slightly mucking it up.

Yes, local (auto) variables are typically stored on a stack. However, they're not popped off the stack when read; they're referenced by an offset from the stack pointer.

Take the following code:

x = y + z;

where each of x, y, and z are allocated on the stack. When the compiler generates the equivalent machine code, it will refer to each variable by an offset from a given register, sort of like:

mov -8(%ebp), %eax   
add -12(%ebp), %eax
mov %eax, -4(%ebp)

On x86 architectures, %ebp is the frame pointer; the stack is broken up into frames, where each frame contains function parameters (if any), the return address (that is, the address of the instruction following the function call), and local variables (if any). On the systems I'm familiar with, the stack grows "downwards" towards 0, and local variables are stored "below" the frame pointer (lower addresses), hence the negative offset. The code above assumes that x is at -4(%ebp), y is at -8(%ebp), and z is at -12(%ebp).

Everything will be popped off the stack¹ when the function returns, but not before.

EDIT

Please note that none of this is mandated by the C language definition. The language does not require the use of a runtime stack at all (although a compiler would be a bitch to implement without one). It merely defines the lifetime of auto variables as being from the end of their declaration to the end of their enclosing scope. A stack makes that easy, but it's not required.

---

^{1. Well, the stack and frame pointers will be set to new values; the data will remain where it was, but that memory is now available for something else to use.}

Answer 2

The stack is not a stack. It's still random access memory, meaning you can access any location in constant time. The only purpose of the stack discipline is to give every function call its own, private memory area that the function can be sure is not used by anyone else.

Answer 3

The top of the stack, on an Intel processor, and many others, is referenced by an address stored in a cpu register, call it SP which is copied to the Base Pointer, call it BP; many machine instructions allow an address expression composed of the current BP combined with a byte offset. so, in your example i would be offset 0, j would be offset -2 and k would be offset -6.

the if would simply resolve to a compare of the contents of addresses -6(BP) and -4(BP). the actual offset values may differ from implementation to implementation; but, that's the general idea...

Answer 4

The call stack is a stack, but it's not used as you're imagining. Each time a call is made from a function, the return address (the program counter) is pushed onto the stack, along with the local variables. When each function returns, the stack is popped by what's called one "stack frame", which includes the variables. Within each function, the memory is treated as random access. The compiler, having generated the code that ordered the local variables on the stack, knows exactly what distance they are from stack frame pointer, and so doesn't have to push and pop the individual local variables.