CD Notes

Stack Allocation: Automatic Memory Management

Guide to stack-based memory allocation for automatic variables and function calls

Introduction to Stack Memory

Imagine a stack of plates in a cafeteria. You can only place a new plate on top, and you can only remove the plate that is currently on top. This Last-In-First-Out (LIFO) principle is exactly how stack memory works in your programs. Every time a function is called, a new "plate" (called a stack frame) is placed on top containing all the function's local variables. When the function returns, that plate is removed, and all its variables vanish instantly.

Stack allocation is the workhorse of memory management in compiled programs. It is incredibly fast — allocating memory is as simple as moving a single pointer — and completely automatic, requiring no explicit cleanup from the programmer. The compiler generates all the necessary instructions to manage the stack, making it invisible to the programmer in most situations.

Why the Stack is Fast

To allocate memory on the stack, the CPU simply decrements the stack pointer (SP) by the required number of bytes. To deallocate, it increments SP back. There is no searching for free blocks, no metadata to update, no fragmentation to worry about. The entire operation takes a single instruction:

Example

Allocation: SUB SP, SP, #32 ; Reserve 32 bytes (one instruction!) Deallocation: ADD SP, SP, #32 ; Release 32 bytes (one instruction!)

Compare this to heap allocation, which involves calling malloc(), searching free lists, splitting blocks, and updating metadata — potentially hundreds of instructions for a single allocation. The stack achieves O(1) allocation in practice, not just in theory.

How the Compiler Uses the Stack

When the compiler processes a function, it calculates the total size needed for all local variables and allocates them as a single block by adjusting the stack pointer. Consider this C function:

Example

void calculate(int a, int b) { int sum = a + b; // 4 bytes double average = sum / 2.0; // 8 bytes char buffer[20]; // 20 bytes // Total local storage: 32 bytes (with alignment padding) }

The compiler generates a prologue (entry code) and epilogue (exit code) for every function:

Example

calculate: ; Prologue — set up stack frame PUSH RBP ; Save caller's frame pointer MOV RBP, RSP ; Set new frame pointer SUB RSP, 32 ; Allocate 32 bytes for locals ; Function body — use local variables via RBP offsets ; sum is at [RBP - 4] ; average is at [RBP - 12] ; buffer starts at [RBP - 32] ; Epilogue — tear down stack frame MOV RSP, RBP ; Deallocate all locals at once POP RBP ; Restore caller's frame pointer RET ; Return to caller

Notice how deallocation is instantaneous — just restore the old stack pointer. All local variables are destroyed simultaneously regardless of how many there were.

Stack Frame Layout

Each function call creates a stack frame (also called activation record) with a well-defined structure:

High Address ┌─────────────────────┐ │ Argument n │ (passed by caller) │ Argument 2 │ │ Argument 1 │ ├─────────────────────┤ │ Return Address │ (where to jump back after RET) ├─────────────────────┤ │ Saved Frame Pointer │ (previous RBP value) ├─────────────────────┤ ← Current RBP points here │ Local variable 1 │ [RBP - 4] │ Local variable 2 │ [RBP - 8] │ Local variable 3 │ [RBP - 12] ├─────────────────────┤ │ Temporary values │ (intermediate calculations) ├─────────────────────┤ │ Saved registers │ (callee-saved registers) └─────────────────────┘ ← Current RSP points here Low Address

The frame pointer (RBP) provides a stable reference for accessing local variables. Even as the stack pointer changes during the function (due to pushing temporary values), all local variables remain at fixed offsets from RBP.

Scope and Variable Lifetime

Stack allocation perfectly aligns with lexical scoping rules. Variables are alive exactly as long as their enclosing scope exists:

c example

void example() {
    int x = 10;              // x alive from here
    {
        int y = 20;          // y alive from here
        int z = x + y;       // z alive from here
    }                        // y and z dead here (scope ends)
    
    printf("%d\n", x);       // x still alive
    // printf("%d\n", y);    // ERROR: y no longer exists
}                            // x dead here

In nested scopes, the compiler can reuse the same stack space for variables in non-overlapping scopes:

Example

void efficient() { { int a[100]; // Uses bytes 0-399 of stack frame process(a); } { int b[100]; // Can REUSE bytes 0-399 (a no longer exists) fill(b); } } // Total stack usage: 400 bytes (not 800)

The Call Stack: Nested Function Calls

When functions call other functions, stack frames pile up. Consider this recursive example:

c example

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

int main() {
    int result = factorial(4);
}

The call stack grows with each recursive call:

│ factorial(1)	n=1 │ ← Top (most recent call)
│ factorial(2)	n=2 │
│ factorial(3)	n=3 │
│ factorial(4)	n=4 │

Each recursive call gets its own independent copy of n because each has its own stack frame. This is why recursion works — there is no confusion between the different instances of the same variable.

Stack Overflow

The stack has a fixed maximum size (typically 1-8 MB on modern systems). If your program exceeds this limit, you get a stack overflow — one of the most common runtime errors. The usual causes are:

Deep recursion without a base case, or with input too large:

c example

int infinite_recursion(int n) {
    return infinite_recursion(n + 1);  // Never stops → stack overflow
}

Large local arrays consuming excessive stack space:

Example

void dangerous() { double matrix[10000][10000]; // 800 MB on stack → overflow! // Should use heap: double *matrix = malloc(...) }

Stack vs Heap: When to Use Each

Criterion	Stack	Heap
Size known at compile time?	Yes → Stack	No → Heap
Needs to outlive function?	No → Stack	Yes → Heap
Very large allocation?	Risky → Heap	Safe → Heap
Performance critical?	Stack (faster)	Heap (slower)
Shared between threads?	Not easily	Yes (with sync)

The Compiler's Optimization Opportunities

Modern compilers perform several stack-related optimizations. Stack slot reuse allows variables with non-overlapping lifetimes to share the same memory location. Register promotion moves frequently accessed stack variables into CPU registers entirely, eliminating memory access. Tail call optimization reuses the current stack frame for a recursive call in tail position, converting recursion into iteration and preventing stack overflow.

Key Takeaways

Stack allocation is the foundation of function-based programming. Its LIFO discipline perfectly matches the nested nature of function calls — last called, first returned. The compiler handles all stack management automatically, generating prologue and epilogue code for each function. The key limitations are fixed size (determined at compile time) and limited lifetime (tied to function scope). Understanding stack allocation helps you write efficient code, avoid stack overflows, and appreciate why certain programming patterns (like returning pointers to local variables) lead to bugs.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Stack Allocation: Automatic Memory Management.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, runtime, environment, stack, allocation

Continue learning this concept

Runtime EnvironmentHeap Allocation: Dynamic Memory ManagementGuide to dynamic memory allocation, garbage collection, and memory leaks Runtime EnvironmentActivation Records: Function Call ManagementComplete guide to activation records, stack frames, and function call mechanics Runtime EnvironmentMemory Management: Strategies and OptimizationComprehensive guide to memory management strategies, caching, and optimization Runtime EnvironmentParameter Passing: Communication Between FunctionsGuide to parameter passing mechanisms: pass-by-value, pass-by-reference, etc.Runtime EnvironmentRuntime Environment: Program Execution ContextOverview of runtime environments, memory management, and execution support Runtime EnvironmentStorage Organization: Memory Sections and LayoutGuide to program memory sections, layout organization, and storage classes

PreviousRuntime Environment: Program Execution Context NextStorage Organization: Memory Sections and Layout

CD Notes

Stack Allocation: Automatic Memory Management

Guide to stack-based memory allocation for automatic variables and function calls

Introduction to Stack Memory

Why the Stack is Fast

Example

Allocation: SUB SP, SP, #32 ; Reserve 32 bytes (one instruction!) Deallocation: ADD SP, SP, #32 ; Release 32 bytes (one instruction!)

How the Compiler Uses the Stack

When the compiler processes a function, it calculates the total size needed for all local variables and allocates them as a single block by adjusting the stack pointer. Consider this C function:

Example

void calculate(int a, int b) { int sum = a + b; // 4 bytes double average = sum / 2.0; // 8 bytes char buffer[20]; // 20 bytes // Total local storage: 32 bytes (with alignment padding) }

The compiler generates a prologue (entry code) and epilogue (exit code) for every function:

Example

Notice how deallocation is instantaneous — just restore the old stack pointer. All local variables are destroyed simultaneously regardless of how many there were.

Stack Frame Layout

Each function call creates a stack frame (also called activation record) with a well-defined structure:

Scope and Variable Lifetime

Stack allocation perfectly aligns with lexical scoping rules. Variables are alive exactly as long as their enclosing scope exists:

c example

void example() {
    int x = 10;              // x alive from here
    {
        int y = 20;          // y alive from here
        int z = x + y;       // z alive from here
    }                        // y and z dead here (scope ends)
    
    printf("%d\n", x);       // x still alive
    // printf("%d\n", y);    // ERROR: y no longer exists
}                            // x dead here

In nested scopes, the compiler can reuse the same stack space for variables in non-overlapping scopes:

Example

void efficient() { { int a[100]; // Uses bytes 0-399 of stack frame process(a); } { int b[100]; // Can REUSE bytes 0-399 (a no longer exists) fill(b); } } // Total stack usage: 400 bytes (not 800)

The Call Stack: Nested Function Calls

When functions call other functions, stack frames pile up. Consider this recursive example:

c example

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

int main() {
    int result = factorial(4);
}

The call stack grows with each recursive call:

│ factorial(1)	n=1 │ ← Top (most recent call)
│ factorial(2)	n=2 │
│ factorial(3)	n=3 │
│ factorial(4)	n=4 │

Stack Overflow

Deep recursion without a base case, or with input too large:

c example

int infinite_recursion(int n) {
    return infinite_recursion(n + 1);  // Never stops → stack overflow
}

Large local arrays consuming excessive stack space:

Example

void dangerous() { double matrix[10000][10000]; // 800 MB on stack → overflow! // Should use heap: double *matrix = malloc(...) }

Stack vs Heap: When to Use Each

Criterion	Stack	Heap
Size known at compile time?	Yes → Stack	No → Heap
Needs to outlive function?	No → Stack	Yes → Heap
Very large allocation?	Risky → Heap	Safe → Heap
Performance critical?	Stack (faster)	Heap (slower)
Shared between threads?	Not easily	Yes (with sync)

The Compiler's Optimization Opportunities

Key Takeaways

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Stack Allocation: Automatic Memory Management.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, runtime, environment, stack, allocation

Continue learning this concept

PreviousRuntime Environment: Program Execution Context NextStorage Organization: Memory Sections and Layout