Understanding Activation Records and Variable Resolution in Compiler Design

Verified Sources

May 18, 2026

An activation record, also widely known as a stack frame, is the fundamental memory management unit utilized by compilers and runtime environments . Whenever a program calls a function, a new activation record is allocated on the program's runtime stack to store vital execution context, including local variables, formal parameters, return addresses, and register states .

The exact layout of an activation record is determined at compile-time, though its instantiation occurs dynamically during program execution . The diagram below illustrates the typical layout of a stack frame within the runtime environment:

When a function finishes execution, its activation record is popped off the runtime stack, returning control and restoring the program counter to the calling function. This stack-based allocation natively supports recursive function calls, as each recursive invocation allocates its own isolated activation record .

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley. - Explains runtime environments, activation record structure, and scoping links. ↩ ↩²
Cooper, K. D., & Torczon, L. (2011). Engineering a Compiler. Morgan Kaufmann. - Details stack layout, dynamic links, and the mechanics of procedure calls. ↩ ↩²

Activation Records and Stacks - MIT 6.004

Frame Pointer vs. Stack Pointer

Do not confuse the Stack Pointer (SP) with the Frame Pointer (FP). The SP moves dynamically as temporaries are pushed and popped. The FP remains constant throughout a function's execution lifetime, providing a stable baseline for addressing variables.

Local Variable Access via Offset Arithmetic

In runtime environments, local variables are not accessed by name; instead, they are accessed using a constant offset relative to the frame pointer ( $FP$ ).

Because the compiler knows the size of each variable type, it computes the exact displacement (offset) of every local variable during the code generation phase. For instance, if the frame pointer points to the middle of the activation record, local variables are typically located at negative offsets (e.g., $FP - 8$ ), while arguments are located at positive offsets (e.g., $FP + 8$ ).

$Variable\_Address = FP + Offset$

This ensures that variable retrieval is an $O(1)$ operation, completely bypassing any symbol lookup during runtime execution .

Accessing Non-Local Variables

In languages that support nested function declarations (such as Pascal, Go, or Python), an inner function may need to access variables declared in outer, enclosing scopes . Resolving these non-local variables requires tracking lexical relationships:

Static Link (Access Link): Used for languages with lexical scope . It points directly to the activation record of the structurally enclosing block or function.
Dynamic Link (Control Link): Points to the activation record of the caller function, regardless of static structure .

If Inner attempts to access a variable declared in Outer, the runtime starts at the current activation record ( $FP_{Inner}$ ), follows its static link to locate the activation record of Outer ( $FP_{Outer}$ ), and then applies the variable's compile-time offset within Outer's frame .

Muchnick, S. S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. - Focuses on local variable addressing, non-local access paths, and compilation optimizations like display registers. ↩ ↩²
Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley. - Explains runtime environments, activation record structure, and scoping links. ↩ ↩²
Cooper, K. D., & Torczon, L. (2011). Engineering a Compiler. Morgan Kaufmann. - Details stack layout, dynamic links, and the mechanics of procedure calls. ↩

The Runtime Function Call Lifecycle

1
Step 1
The calling function evaluates the actual arguments and pushes them onto the runtime stack in preparation for the function invocation.
2
Step 2
The program counter (PC) or return address is saved to the stack, allowing the processor to return to the calling location after execution completes.
3
Step 3
The current Frame Pointer ( $FP$ ) is pushed onto the stack as the Dynamic Link. The $FP$ is then updated to point to the current top of the stack, setting the new frame baseline.
4
Step 4
The Stack Pointer ( $SP$ ) is decremented (or incremented, depending on stack growth direction) to allocate space for local variables and compiler-generated temporaries.
5
Step 5
The function body executes. Variables are resolved dynamically using constant offsets from the active $FP$ , or via Static Links if accessing outer nested scopes.
6
Step 6
Upon return, the $SP$ is adjusted back to the $FP$ position. The old $FP$ is restored from the dynamic link, and the return instruction pops the return address back into the program counter.

1// Code Structure
2procedure Outer;
3  var x: integer;
4  procedure Inner;
5    begin
6      x := 10; // Accessed via Static Link
7    end;
8
9// Assembly Concept:
10mov r1, [fp - 4]       // Load the Static Link (Parent AR)
11mov [r1 - 8], 10       // Store value 10 in variable 'x'

Optimization: Display Registers

Traversing a long static chain (nested functions within nested functions) can be slow. High-performance compilers construct an array of active pointers called a Display. This allows $O(1)$ access to any outer scope without walking multiple static links.

Deep Dive into Variables and Scopes

Knowledge Check

Question 1 of 3

Q1Single choice

Which pointer inside an activation record is used to resolve non-local variables in a lexically-scoped nested language?

Dynamic Link

Static Link (Access Link)

Stack Pointer

Return Address

Explore Related Topics

Introduction to Compiler Design and Architecture

The course introduces the fundamental structure and operation of modern compilers, describing how source code is transformed through front‑end analysis, intermediate representation, and back‑end generation.

Front‑end performs lexical, syntax, and semantic analysis, building a symbol table and an AST independent of the target.
An intermediate representation (IR) like three‑address code lets language‑independent optimizations run before back‑end register and instruction selection.
Optimization passes (e.g., dead‑code elimination, loop unrolling) on the IR consume about 50 % of compilation CPU time.
Top‑down parsers fail on left‑recursive grammars; they are fixed by rewriting A → Aα | β as A → β A' and A' → α A' | ε.

Fixed Partition vs Variable Partition in Operating Systems, and the Need for Compaction

Fixed and variable partitioning are contiguous memory allocation schemes that differ in when partitions are created and the type of fragmentation they produce, prompting the use of compaction.

Fixed partitioning: static predefined partitions, simple implementation, limited multiprogramming, suffers internal fragmentation (e.g., a $20\text{ KB}$ process in a $32\text{ KB}$ partition).
Variable partitioning: dynamic partitions sized to each process, higher memory utilization, but creates external fragmentation requiring placement algorithms.
Compaction moves processes to coalesce free holes, turning scattered space such as $10\text{ KB}+12\text{ KB}+18\text{ KB}=40\text{ KB}$ into a single $40\text{ KB}$ block for a $30\text{ KB}$ request.
Compaction is expensive because it involves process relocation and address updates.

Compare Between Compile-Time, Load-Time, and Execution-Time Address Binding

Address binding maps a program’s symbolic or relocatable addresses to actual physical memory, and it can be performed at compile‑time, load‑time, or execution‑time.

Compile‑time binding: the compiler produces absolute code; final addresses are fixed before loading and require recompilation if the start location changes.
Load‑time binding: the loader relocates code using a base register (e.g.,  $Physical = Base + Logical$ ); addresses are fixed after loading but no recompilation is needed.
Execution‑time binding: the CPU generates logical addresses that the MMU translates on each reference, allowing the process to move while running and supporting paging, segmentation, and virtual memory.

Research more with Coursify