Compiler Design
Runtime Environment & Activation Records
Runtime Memory Organization
The **Runtime Environment** manages program memory during execution. When a program starts, the operating system allocates a large virtual address space partitioned into distinct logical segments:
| Region | Location | Contents | Allocation Time |
|---|---|---|---|
| Code / Text Segment | Low addresses (Fixed size) | Compiled machine instructions, read-only constants. | Compile / Load Time |
| Static Data Segment | Above code (Fixed size) | Global variables, static variables. | Compile / Load Time |
| Heap | Grows upward | Dynamically allocated variables (via malloc / new). | Runtime (Explicit request) |
| Stack | Grows downward (from high addresses) | Activation records representing active procedure calls. | Runtime (Automatic) |
Activation Records (Stack Frames)
Whenever a procedure (function) is called, the compiler allocates a block of stack memory called an **Activation Record** (or Stack Frame). This frame is popped and discarded when the function returns.
Space allocated for depositing the returned value before returning control to the caller.
Note: On modern architectures, small values (like integers or pointers) are returned directly via CPU registers (e.g., EAX / RAX) rather than stack slots.
The arguments passed from the caller. Copies of values are stored for call-by-value, while memory addresses are stored for call-by-reference.
A pointer referencing the activation record of the **caller**. When the callee returns, this dynamic link is used to restore the caller's frame pointer (FP).
A pointer referencing the activation record of the **lexical parent**. Used to access non-local variables in nested procedures (common in Pascal, but absent in C since C doesn't support nested functions).
Saves PC (return address) and registers that the callee might overwrite, ensuring the caller can resume execution seamlessly.
Local Variables: Variables declared locally within the procedure. Access is compiled to fixed offsets relative to the frame pointer (e.g., [FP - 8]).
Temporaries: Temporary slots for intermediate expression evaluations that do not fit within registers.
[Caller's frame] +------------------------------------+ | Actual parameters (passed to P) | <- pushed by CALLER +------------------------------------+ | Return value (space for result) | <- read by CALLER +------------------------------------+ [P's activation record begins here] +------------------------------------+ | Return address (saved PC) | <- pushed by CALL instruction +------------------------------------+ | Control link (caller's FP) | <- FP points here on entry +------------------------------------+ | Access link (static parent's FP) | +------------------------------------+ | Saved registers | +------------------------------------+ | Local variables | e.g., [FP - 4] +------------------------------------+ | Temporaries | e.g., t1, t2 +------------------------------------+ <- SP points here during P's run
Memory Allocation Strategies
| Strategy | Allocation Time | Deallocation | Supports Recursion? | Overhead |
|---|---|---|---|---|
| Static | Compile / Load Time | Never (Program End) | No | Zero |
| Stack | Runtime (Call) | Automatic (Return) | Yes | Very Low (O(1)) |
| Heap | Runtime (Explicit) | Manual / GC | Yes | High (Manager/GC) |
Heap Allocator Strategies
- First Fit: Scans the free list from the beginning and returns the first free block large enough. Fast, but causes fragmentation at the beginning of the list.
- Best Fit: Scans the entire list to return the smallest block that fits. Minimizes wasted space, but lookup is slow.
- Worst Fit: Returns the largest available block. Leaves large remaining fragments, but quickly exhausts large blocks.
- Buddy System: Block sizes are powers of 2. Split/merge adjacent blocks (buddies) dynamically. Quick coalescing, but introduces internal fragmentation.