A hostel can give rooms to students in three ways. Some rooms are permanently assigned for the whole course (you always know where Ravi lives). Some are given for the duration of an exam week and taken back when the week ends, last-come-first-out. And some are handed out on request whenever someone needs one, and returned whenever they leave, in any order. Each scheme suits a different kind of guest.
A compiler has the same three choices for program data. In Runtime Environment & Activation Records we saw the memory areas of a running program. Now we look at the strategies used to allocate storage in those areas (static, stack and heap allocation), what each one can and cannot support, and then at the closely related question of how an argument reaches a procedure: parameter passing.
A storage-allocation strategy decides when and where memory for a data object is reserved and released. Static allocation fixes addresses at compile time; stack allocation creates storage when a procedure is called and releases it when the procedure returns; heap allocation creates and releases storage in any order, at the program's (or a garbage collector's) request.
The C programs in this chapter were compiled with GCC 15.2 on Linux and the outputs are real. The parameter-passing answers were computed by a small Python simulator that implements each passing mode, and checked by hand.
Static Allocation
In static allocation, the compiler decides the address of every data object at compile time. Names are bound to storage once, when the program is loaded, and the binding never changes.
This is how early Fortran worked: every procedure's locals had fixed addresses. It is also how C treats global variables and static local variables today:
#include <stdio.h>
int next_id(void) {
static int count = 0; /* static allocation: one copy, keeps its value */
int calls = 0; /* stack allocation: fresh copy every call */
count++;
calls++;
printf("count = %d, calls = %d\n", count, calls);
return count;
}
int main(void) {
next_id(); next_id(); next_id();
return 0;
}count = 1, calls = 1
count = 2, calls = 1
count = 3, calls = 1count lives in the static area and survives between calls; calls lives in the activation record and is created afresh each time.
Limitations of Static Allocation
No recursion. If every local has one fixed address, a second activation of the same procedure would overwrite the first one's locals. (This is exactly why Fortran 77 did not officially support recursion.)
Sizes must be known at compile time. No arrays whose size depends on input.
No dynamic data structures. Linked lists and trees whose size grows at run time cannot be built.
Its strengths are speed (addresses are constants, no allocation code at all) and the fact that values persist between calls.
Stack Allocation
In stack allocation, storage for locals is part of the activation record, pushed on the control stack when the procedure is called and popped when it returns. Each activation gets fresh storage, so recursion works. Locals are accessed at a fixed offset from the frame pointer, so access is still cheap, and allocation is just moving the stack pointer.
Limitation: Locals Die on Return
The values of locals are lost when the activation ends. If a pointer to a local survives the activation, it becomes a dangling reference: a reference to storage that has been deallocated and may be reused by the next call.
#include <stdio.h>
int *bad(void) {
int local = 42;
return &local;
}
int main(void) {
int *p = bad();
printf("%p\n", (void *)p);
return 0;
}dangle.c: In function 'bad':
dangle.c:4:12: warning: function returns address of local variable [-Wreturn-local-addr]
4 | return &local;
| ^~~~~~GCC warns, and at run time this build actually printed (nil): since using the returned address would be undefined behaviour anyway, GCC chose to return a null pointer instead. The lesson: data that must outlive the call that created it cannot live on the stack. It must go on the heap (or be static).
Stack allocation also has trouble with languages where a procedure can return a nested function that refers to its locals (closures, as in JavaScript or Python). Those locals must outlive the call, so such languages keep them on the heap.
Heap Allocation
Heap allocation hands out blocks of memory on request, in any order, and takes them back in any order. It is needed whenever:
data must outlive the procedure that created it (a node returned from a function that builds a tree),
the amount of data is unknown until run time (reading a file into memory),
the language returns closures or objects whose lifetime is not tied to calls.
The heap manager (for example malloc/free in the C library) keeps track of free blocks. Because blocks are freed in arbitrary order, the free space becomes a collection of scattered holes: fragmentation.
Choosing a Hole
When a request arrives, the manager must pick a free hole. The three classic policies:
First fit: the first hole (in address order) that is large enough.
Best fit: the smallest hole that is large enough.
Worst fit: the largest hole.
Example. Free holes in address order: H1 = 150, H2 = 400, H3 = 220, H4 = 90, H5 = 350 (bytes). Requests arrive: 200, 80, 300, 120.
Request | First fit | Best fit | Worst fit |
|---|---|---|---|
200 | H2 (400 → 200) | H3 (220 → 20) | H2 (400 → 200) |
80 | H1 (150 → 70) | H4 (90 → 10) | H5 (350 → 270) |
300 | H5 (350 → 50) | H5 (350 → 50) | Fails: largest hole is 270 |
120 | H2 (200 → 80) | H1 (150 → 30) | H5 (270 → 150) |
Holes left | 70, 80, 220, 90, 50 | 30, 400, 20, 10, 50 | 150, 200, 220, 90, 150 |
Best fit kept the 400-byte hole intact, which is valuable for a later large request, but left many tiny useless slivers (20, 10). Worst fit broke up the big holes early and could not serve the 300-byte request even though 930 bytes (150 + 200 + 220 + 90 + 270) were free in total. Which policy is best depends on the request pattern; real allocators (such as glibc's) use more elaborate schemes such as segregated free lists for different size classes. Adjacent free blocks are also coalesced into one bigger block when freed.
Who Frees Heap Memory?
With manual deallocation (C's free, C++'s delete), two errors are possible:
Memory leak: storage that is no longer reachable is never freed. The program slowly uses more and more memory.
Dangling pointer: storage is freed while a pointer to it is still used. Reading or writing through it corrupts whatever is allocated there next.
With automatic garbage collection (Java, Python, Go, C#), the runtime frees objects that can no longer be reached from the program's roots (globals, registers and stack variables). The main approaches:
Technique | Idea | Strength | Weakness |
|---|---|---|---|
Reference counting | Each object counts the pointers to it; free it when the count drops to 0. | Garbage freed immediately; work spread out evenly | Cannot free cycles (A points to B, B points to A, nothing else points to either: both counts stay 1); count updates on every pointer assignment |
Mark and sweep | Mark everything reachable from the roots, then sweep the heap and free every unmarked object. | Handles cycles | Pauses the program; leaves fragmentation |
Copying (e.g. semispace) | Copy reachable objects into a fresh half of the heap; the old half is then entirely free. | Compacts memory (no fragmentation); cost proportional to live data only | Uses only half the heap at a time; pointers must be updated |
Generational | Most objects die young, so collect the "young" area often and the "old" area rarely. | Short pauses for most collections | More complex bookkeeping |
CPython, for instance, uses reference counting plus a separate cycle detector, exactly to fix the cycle weakness in the table.
Comparing the Three Strategies
Point | Static | Stack | Heap |
|---|---|---|---|
When storage is bound | Compile/load time | At procedure call | On explicit request |
When it is released | Program end | At procedure return (LIFO) | Explicit free or garbage collection, any order |
Recursion | Not supported | Supported | Supported |
Sizes known at compile time? | Required | Fixed part yes; variable-length data possible | Not required |
Values kept between calls | Yes | No | Yes, until freed |
Speed | Fastest (constant addresses) | Fast (move stack pointer) | Slowest (search free list, possible GC) |
Typical problems | Inflexible | Dangling references to dead locals | Fragmentation, leaks, dangling pointers |
C example | Globals, | Ordinary locals, parameters |
|
Parameter Passing
First, two pieces of vocabulary:
Actual parameters (arguments) are the expressions written in the call: in
f(a, b + 1)they areaandb + 1. Formal parameters are the names in the procedure's definition: invoid f(int x, int y)they arexandy.The r-value of an expression is its value; the l-value is its location (address).
ahas both;b + 1has only an r-value. Ina = a + 1, theaon the left uses its l-value and the one on the right its r-value.
A parameter-passing mechanism decides what the formal receives: an r-value, an l-value, or something else.
Call by Value
The caller evaluates the actual parameter and copies its r-value into the formal, which then behaves like a local variable. Changes to the formal do not affect the caller. C and Java use only this mechanism (in Java, the value copied for an object is a reference, which is why methods can modify the object but cannot make the caller's variable point to a different object).
Call by Reference
The caller passes the l-value (address) of the actual parameter. Every use of the formal is an indirect access through that address, so assignments to the formal change the caller's variable. If the actual is an expression with no l-value, such as b + 1, its value is put in a temporary and the temporary's address is passed. C++ & parameters and Fortran use it; in C you simulate it by passing a pointer:
#include <stdio.h>
void by_value(int x) { x = x + 1; }
void by_pointer(int *x) { *x = *x + 1; }
int main(void) {
int a = 5;
by_value(a); printf("after by_value: a = %d\n", a);
by_pointer(&a); printf("after by_pointer: a = %d\n", a);
return 0;
}after by_value: a = 5
after by_pointer: a = 6Call by Value-Result (Copy-Restore)
The r-value of the actual is copied in at the call, the formal is used as a local during the call, and at the return its final value is copied out to the actual's l-value (computed at call time). Ada passes in out parameters of scalar (elementary) types this way, by copy-in/copy-out. Most of the time it behaves like call by reference; the difference shows up when the same variable is reachable in two ways (aliasing), as the examples below show.
Call by Name
Used in Algol 60. The procedure behaves as if the actual parameter's text were substituted for the formal everywhere in the body (renaming the callee's locals if necessary to avoid clashes). The actual is re-evaluated, in the caller's environment, every time the formal is used. It is implemented by passing a small parameterless function, called a thunk, that computes the actual's l-value or r-value on demand.
Modern relatives: call by need (lazy evaluation, as in Haskell) evaluates the actual at most once, the first time it is used, and remembers the result. C macros behave like call by name, which is why #define SQ(x) ((x)*(x)) evaluates x twice.
Summary Table
Mechanism | What is passed | Effect on caller's variable | Languages |
|---|---|---|---|
Call by value | r-value (a copy) | None | C, Java, Pascal (default) |
Call by reference | l-value (address) | Immediate, on every assignment | C++ &, Pascal var, Fortran |
Call by value-result | r-value in; result copied back to l-value | Only at return | Ada in out (scalar types), some Fortran implementations |
Call by name | A thunk (unevaluated expression) | Every use re-evaluates the actual in the caller's environment | Algol 60; C macros behave similarly |
Call by need | A thunk evaluated at most once | (Pure languages: no assignment) | Haskell |
Solved Problems
Problem 1: Aliasing
void f(int x, int y) { x = x + 1; y = y + 10; }
main: a = 5; f(a, a); print a;What is printed under each mechanism?
Value: x and y are copies;
ais untouched. Prints 5.Reference: x and y are both aliases of
a.x = x + 1makes a = 6;y = y + 10makes a = 16. Prints 16.Value-result: x = 5, y = 5 are copied in; they become x = 6, y = 15. At return both are copied out to
a. Copying left to right, x is copied first (a = 6) and y last (a = 15). Prints 15. (If the implementation copied out right to left, it would print 6. That ambiguity is exactly why aliasing with value-result is considered dangerous.)Name: both formals mean the text
a, so it behaves like reference here. Prints 16.
Problem 2: The Famous Call-by-Name Swap Failure
void swap(int x, int y) { int t; t = x; x = y; y = t; }
main: i = 1; a[1] = 3; a[3] = 7; swap(i, a[i]);By reference: the addresses of i and of a[1] are computed once, at the call. t = 1; i = a[1] = 3; a[1] = 1. Result: i = 3, a[1] = 1, a[3] = 7. A correct swap. (Value-result gives the same answer here.)
By name: replace x by i and y by a[i] textually:
t = i; // t = 1
i = a[i]; // i = a[1] = 3
a[i] = t; // i is now 3, so this sets a[3] = 1 !Result: i = 3, a[1] = 3 (unchanged), a[3] = 1. The subscript i was re-evaluated after i changed, so the wrong element was written. This is the classic demonstration that the obvious swap procedure is wrong under call by name; in fact it has been proved that no swap procedure working for all such arguments can be written in Algol 60 with call by name.
Problem 3: Globals and Parameters Together
int a = 2, b = 3; // globals
void f(int x, int y) {
x = x + y;
y = x * a;
a = a + 1;
}
main: f(a, b); print a, b;Mechanism | Working | Output a, b |
|---|---|---|
Value | x = 2 + 3 = 5; y = 5 × a = 5 × 2 = 10; a = 3. b untouched. | 3, 3 |
Reference | x is a, y is b. a = 2 + 3 = 5; b = 5 × a = 25; a = 6. | 6, 25 |
Value-result | x = 2, y = 3 copied in. x = 5; y = 5 × a = 10 (global a is still 2); a = 3. Copy out: a = x = 5, b = y = 10. The copy-out overwrites a's increment. | 5, 10 |
Name | Same as reference here (actuals are simple variables). | 6, 25 |
Note how value-result differs from reference: inside f, the assignment y = x * a reads the global a, which under value-result has not yet been updated by x.
Problem 4: Jensen's Device
Call by name lets an expression be "passed" and re-evaluated, which can be used cleverly:
int sum(int i, int lo, int hi, int term) { // all by name
int s = 0;
for (i = lo; i <= hi; i = i + 1) s = s + term;
return s;
}
a = {_, 2, 4, 6, 8}; // a[1..4]
sum(k, 1, 4, a[k] * k)Each use of term re-evaluates a[k] * k with the current k: 2·1 + 4·2 + 6·3 + 8·4 = 2 + 8 + 18 + 32 = 60. Under call by value, term would be evaluated once, before the loop, with whatever k was then.
Common Mistakes
Saying C has call by reference. C has only call by value; passing a pointer passes the pointer's value, which lets you simulate reference.
Treating value-result as identical to reference. They differ under aliasing and when the callee reads a global that is also passed as an argument.
Evaluating a call-by-name actual once. It is re-evaluated at every use of the formal, in the caller's environment.
Computing the reference/value-result address late. For reference and value-result, the address of
a[i]is computed at the call, with the value of i at that time.Returning a pointer to a local. The local dies when its activation record is popped; allocate the object on the heap instead.
Assuming reference counting collects all garbage. Cyclic structures are never freed by pure reference counting.
Interview and Exam Questions
Q1. Why does static allocation not support recursion?
Each local has exactly one fixed address. A recursive activation would use the same addresses and overwrite the locals of the activation that is still waiting.
Q2. What is a dangling reference? Give one way it arises with stack allocation and one with heap allocation.
A reference to storage that has been deallocated. Stack: a function returns the address of its own local variable. Heap: memory is freed with free() while another pointer to it is still used.
Q3. What is a thunk?
A small compiler-generated, parameterless procedure that evaluates an actual parameter (its l-value or r-value) in the caller's environment. Thunks implement call by name (and, with caching, call by need).
Q4. void p(int x) { x = x * 2; g = g + x; } with global g = 4, called as p(g). What is g afterwards under value, reference and value-result?
Value: x = 8, g = 4 + 8 = 12. Reference: x is g, so g = 8, then g = 8 + 8 = 16. Value-result: x = 8; g = 4 + 8 = 12; then x (8) is copied back to g, so g = 8.
Q5. Why can reference counting not reclaim cyclic garbage?
In a cycle, each object is pointed to by another object of the cycle, so no count ever drops to zero, even when nothing outside the cycle refers to it.
Q6. Which allocation is used for each: a global array, a function's local int, a node returned by a tree-building function?
Static, stack and heap respectively.
Q7. In which situation do call by reference and call by name give different results?
When the actual parameter's l-value can change during the call, e.g. an array element a[i] where the procedure changes i. Reference fixes the address at the call; name recomputes a[i] at each use.
Summary
Static allocation: addresses fixed at compile time; fastest; values persist; no recursion or dynamic sizes.
Stack allocation: storage in activation records; supports recursion; locals die on return, so pointers to them dangle.
Heap allocation: any lifetime and size; needs a manager (first, best, worst fit, coalescing) and either manual freeing (risk of leaks and dangling pointers) or garbage collection (reference counting, mark and sweep, copying, generational).
Parameter passing: value copies the r-value; reference passes the l-value; value-result copies in and copies back at return; name re-evaluates the actual via a thunk at every use; need evaluates it at most once.
The mechanisms differ under aliasing and when an actual's address depends on variables the callee changes.
This completes our look at the runtime side of compilation. We now return to the code itself: Basic Blocks & Flow Graphs shows how three-address code is split into straight-line pieces and connected into a graph, the starting point for optimization and code generation.