Runtime environments and memory management

A compiled program does not run in a vacuum. It needs a runtime environment: conventions for how functions call one another and pass arguments, where local variables live, how the stack and heap are organized, how nested functions find variables of enclosing ones, and, in many languages, a garbage collector that reclaims memory automatically. The compiler must generate code that creates and respects this environment, and some of its parts, such as the calling convention, must be agreed among all compilers that produce code for a platform so that separately compiled code can be linked together. This lesson looks at the runtime environment from the compiler writer's side. CMPUT-229 (lessons 7 and 8) showed the RISC-V calling convention and stack frames from the machine's side, and CMPUT-325 (lesson 10) covered memory management and garbage collection algorithms; we build on both and focus on what the compiler must generate and record.

The memory layout of a running program

A typical process divides its address space into regions: the code (text) segment holding instructions; static data for global variables and constants; the heap for dynamically allocated objects, growing upward; and the stack for function activations, growing downward on most architectures, including RISC-V and x86-64. Each thread has its own stack. The compiler decides which region each kind of storage belongs to: globals go in static data with fixed addresses resolved by the linker; locals whose lifetime ends with their function go on the stack; objects that outlive the function creating them, or whose size is not known at compile time, go on the heap. Escape analysis, which determines whether an object can be referenced after its creating function returns, lets compilers for Java and Go allocate some objects on the stack even when the source asks for the heap.

Activation records and calling conventions

Each call creates an activation record, or stack frame, holding the information that call needs: arguments that do not fit in registers, the return address, saved registers, local variables, temporaries the register allocator spills (lesson 10), and space for outgoing arguments to calls it makes. A calling convention, part of a platform's application binary interface (ABI), specifies which registers carry arguments and results, which registers the callee must preserve (callee-saved) and which the caller must save if it needs them (caller-saved), how the stack is aligned, and who allocates and frees which parts of the frame. The RISC-V LP64 convention passes up to eight integer arguments in a0 to a7 and returns results in a0 and a1; s0 to s11 are callee-saved; t0 to t6 and the argument registers are caller-saved; ra holds the return address; and sp must stay 16-byte aligned at calls.

The code at the start of a function, the prologue, allocates the frame by decrementing sp, saves ra and any callee-saved registers it will use, and sets up a frame pointer if one is used. The epilogue restores them, frees the frame and returns. The compiler lays out the frame after register allocation, when it knows which callee-saved registers are used and how many spill slots are needed. Each object needs a slot aligned to its natural boundary, and the frame as a whole must keep sp aligned. The program below computes such layouts.

# Laying out a stack frame under the RISC-V LP64 calling convention:
# arguments in a0-a7, return address in ra, frame pointer s0, callee-saved
# s1-s11, stack pointer kept 16-byte aligned. Offsets are from the frame
# pointer s0, which points just above the frame (the old sp).
def layout(name, saved, locals_, outgoing_stack_args=0):
    slots, off = [], 0
    def place(what, size, align):
        nonlocal off
        off += size
        off = (off + align - 1) // align * align       # round the distance up to the alignment
        slots.append((-off, size, what))
    for r in ["ra", "s0"] + saved: place(f"saved {r}", 8, 8)
    for var, size in locals_: place(f"local {var}", size, min(size, 8) if size <= 8 else 8)
    out = 8 * outgoing_stack_args
    frame = (off + out + 15) // 16 * 16                 # whole frame stays 16-byte aligned
    print(f"{name}: frame size {frame} bytes  (addi sp, sp, -{frame})")
    for o, size, what in slots: print(f"   {o:5}(s0)  {size:3} bytes  {what}")
    if out: print(f"   {-frame:5}(s0)  {out:3} bytes  outgoing arguments 9.. at 0(sp)")
    return frame
layout("fact", [], [("r", 8), ("n.spill", 8)])
layout("sort", ["s1", "s2", "s3"], [("i", 4), ("j", 4), ("buf", 40), ("flag", 1)], outgoing_stack_args=2)

fact: frame size 32 bytes  (addi sp, sp, -32)
      -8(s0)    8 bytes  saved ra
     -16(s0)    8 bytes  saved s0
     -24(s0)    8 bytes  local r
     -32(s0)    8 bytes  local n.spill
sort: frame size 112 bytes  (addi sp, sp, -112)
      -8(s0)    8 bytes  saved ra
     -16(s0)    8 bytes  saved s0
     -24(s0)    8 bytes  saved s1
     -32(s0)    8 bytes  saved s2
     -40(s0)    8 bytes  saved s3
     -44(s0)    4 bytes  local i
     -48(s0)    4 bytes  local j
     -88(s0)   40 bytes  local buf
     -89(s0)    1 bytes  local flag
    -112(s0)   16 bytes  outgoing arguments 9.. at 0(sp)

Clang's real output for a small function shows the same structure. At -O0 the compiler keeps a frame pointer and stores every variable in the frame; at -O2, the frame shrinks or disappears and values stay in registers.

cat frame.c
clang --target=riscv64 -O0 -S frame.c -o - | sed -n "/^scaled:/,/ret/p" | grep -v "^\s*\." | grep -v "^\.L"
clang --target=riscv64 -O2 -S frame.c -o - | sed -n "/^scaled:/,/ret/p" | grep -v "^\s*\." | grep -v "^\.L"

$ cat frame.c
long helper(long v);
long scaled(long a, long b) {
    long t = a * 3;
    return helper(t) + b;
}
$ clang --target=riscv64 -O0 -S frame.c -o - | sed -n "/^scaled:/,/ret/p" | grep -v "^\s*\." | grep -v "^\.L"
scaled:                                 # @scaled
# %bb.0:
	addi	sp, sp, -48
	sd	ra, 40(sp)                      # 8-byte Folded Spill
	sd	s0, 32(sp)                      # 8-byte Folded Spill
	addi	s0, sp, 48
	sd	a0, -24(s0)
	sd	a1, -32(s0)
	ld	a1, -24(s0)
	slli	a0, a1, 1
	add	a0, a0, a1
	sd	a0, -40(s0)
	ld	a0, -40(s0)
	call	helper
	ld	a1, -32(s0)
	add	a0, a0, a1
	ld	ra, 40(sp)                      # 8-byte Folded Reload
	ld	s0, 32(sp)                      # 8-byte Folded Reload
	addi	sp, sp, 48
	ret
$ clang --target=riscv64 -O2 -S frame.c -o - | sed -n "/^scaled:/,/ret/p" | grep -v "^\s*\." | grep -v "^\.L"
scaled:                                 # @scaled
# %bb.0:
	addi	sp, sp, -16
	sd	ra, 8(sp)                       # 8-byte Folded Spill
	sd	s0, 0(sp)                       # 8-byte Folded Spill
	mv	s0, a1
	slli	a1, a0, 1
	add	a0, a0, a1
	call	helper
	add	a0, a0, s0
	ld	ra, 8(sp)                       # 8-byte Folded Reload
	ld	s0, 0(sp)                       # 8-byte Folded Reload
	addi	sp, sp, 16
	ret

At -O0 the prologue allocates a 48-byte frame (a multiple of 16), saves ra and s0, and points s0 at the frame's top, then stores the arguments into slots at negative offsets from s0, reloading them for every use. At -O2, the frame shrinks to 16 bytes and holds only the saved ra and the old value of s0. The compiler keeps b, which must survive the call to helper, in the callee-saved register s0 rather than in a caller-saved register that the call could destroy, and so it must save and restore s0 itself. This is exactly the reasoning the register allocator automates: values live across calls belong in callee-saved registers, or must be spilled.

Access to non-local variables

Tern, like C, has no nested functions, so every variable a function can name is either local or global. Languages with nested functions, such as Pascal, Ada, Python, JavaScript, Scala and every functional language, let an inner function refer to variables of the functions enclosing it, and the compiler must provide a way to find them at run time. The classic technique, for languages where nested functions do not outlive their enclosing call, is the static link, sometimes called the access link: each frame stores a pointer to the most recent frame of its lexically enclosing function. Because nesting is static, the compiler knows, for each variable use, how many levels out the variable is declared; at run time the code follows that many static links and then uses the variable's offset. This differs from the dynamic link, which points to the caller's frame and is what a debugger walks to print a backtrace.

# Nested functions need access to variables of enclosing functions. Each frame
# stores a static link (to the frame of the lexically enclosing function) as
# well as a dynamic link (to the caller). A variable is addressed by
# (nesting distance, offset): follow that many static links, then index.
class Frame:
    def __init__(f, fn, depth, static, dynamic, values):
        f.fn, f.depth, f.static, f.dynamic, f.slots = fn, depth, static, dynamic, values
stack = []
def call(fn, depth, caller, values):
    # The caller passes the static link: the frame of fn's enclosing function,
    # found by following (caller.depth - depth + 1) static links from the caller.
    link = caller
    if caller is not None:
        for _ in range(caller.depth - depth + 1): link = link.static
    fr = Frame(fn, depth, link, caller, values); stack.append(fr); return fr
def load(frame, distance, slot):
    hops, f = 0, frame
    for _ in range(distance): f = f.static; hops += 1
    return f.slots[slot], hops
# program outer(x) { fn middle(y) { fn inner(z) { return x + y + z; } ... } ... }
# with recursion: outer calls middle(1), middle calls middle(2), which calls inner(3)
o  = call("outer",  1, None, {"x": 100})
m1 = call("middle", 2, o,    {"y": 1})
m2 = call("middle", 2, m1,   {"y": 2})              # recursive call: same static link as m1
i  = call("inner",  3, m2,   {"z": 3})
for fr in stack:
    print(f"{fr.fn:7} depth {fr.depth}  dynamic link -> {fr.dynamic.fn + '/' + str(fr.dynamic.slots) if fr.dynamic else '-':16}"
          f"  static link -> {fr.static.fn + '/' + str(fr.static.slots) if fr.static else '-'}")
total, hops_used = 0, []
for name, dist in (("z", 0), ("y", 1), ("x", 2)):     # distances known at compile time
    v, h = load(i, dist, name); total += v; hops_used.append(f"{name}={v} ({h} hop{'s' * (h != 1)})")
print("inner sees", ", ".join(hops_used), "-> x + y + z =", total)

outer   depth 1  dynamic link -> -                 static link -> -
middle  depth 2  dynamic link -> outer/{'x': 100}  static link -> outer/{'x': 100}
middle  depth 2  dynamic link -> middle/{'y': 1}   static link -> outer/{'x': 100}
inner   depth 3  dynamic link -> middle/{'y': 2}   static link -> middle/{'y': 2}
inner sees z=3 (0 hops), y=2 (1 hop), x=100 (2 hops) -> x + y + z = 105

The recursive call is the instructive case. The second middle frame's caller is the first middle frame, so its dynamic link points there, but its static link points to outer, because middle is nested in outer, not in itself. The inner function finds y in the most recent middle frame by one hop and x by two, distances fixed at compile time. An alternative, the display, keeps an array whose element k points to the current frame at nesting depth k, giving constant-time access at the cost of maintaining the array on every call.

When functions are values that can outlive the call that created them, frames cannot be freed on return. The standard solution is closure conversion. A closure is a pair of a code pointer and an environment record holding the free variables the function uses; the compiler rewrites each nested function to take its environment as an extra parameter and allocates the environment on the heap if it may escape. Variables captured by a closure and also modified need care: they are moved to a heap-allocated box shared by all who use them. Lambda lifting is the related transformation that turns a nested function into a top-level one by adding its free variables as parameters, avoiding allocation when all call sites are known. JavaScript engines, the JVM (for lambdas and inner classes), Swift and OCaml all perform variants of closure conversion; Rust makes the choice explicit by distinguishing closures that borrow their environment from those that move it.

The heap and its management

Heap memory is managed either manually, as in C with malloc and free, or automatically by a garbage collector, as in Java, Go, Python, JavaScript, C# and most functional languages, or by ownership rules checked at compile time, as in Rust. CMPUT-325 lesson 10 explained the collection algorithms: reference counting, mark and sweep, copying collection and generational collection. Each requires the compiler's cooperation, and that is our concern here. A collector must find every pointer into the heap held by the running program, the roots, which live in global variables, in registers and in stack frames; it may need to know the layout of every object to find pointers inside it; and, if it moves objects, it must update every pointer to them.

A precise (exact) collector relies on the compiler to say exactly where pointers are. For objects, the compiler or runtime records a layout descriptor per type. For stack frames and registers, the compiler emits stack maps: for each point in the code where collection may happen, called a safepoint (typically calls, allocations and loop back edges), a table listing which frame slots and registers hold live pointers. LLVM provides the gc.statepoint mechanism and stack map sections for this purpose, and HotSpot, V8 and Go's compiler all generate such maps. A conservative collector, such as the Boehm–Demers–Weiser collector used with C and C++, receives no such help: it treats any word that holds a value which could be a heap address as a possible pointer. That is safe, but it may keep dead objects alive, and it cannot move objects, since a word it believes to be a pointer might really be an integer it must not change.

# Precise versus conservative root finding. The compiler emits a stack map
# for each safepoint saying which frame slots hold pointers; a conservative
# collector must instead treat any word that looks like a heap address as one.
import random
random.seed(7)
HEAP_BASE, CELL = 0x10000, 16
heap = {HEAP_BASE + CELL * k: {"refs": []} for k in range(40)}      # 40 objects
addrs = sorted(heap)
for a in addrs[:20]:                                                 # some objects point to others
    heap[a]["refs"] = random.sample(addrs, 2) if random.random() < 0.4 else []
# Three frames. Each slot is (value, is_pointer); the compiler knows which is which.
frames = [
    [(addrs[0], True), (42, False), (addrs[3], True)],
    [(addrs[5], True), (HEAP_BASE + CELL * 30, False), (7, False)],   # an int that equals an address!
    [(HEAP_BASE + CELL * 33, False), (addrs[8], True), (0, False)],  # another one
]
stack_maps = [[i for i, (_, p) in enumerate(f) if p] for f in frames]
def mark(roots):
    seen, work = set(), list(roots)
    while work:
        a = work.pop()
        if a in heap and a not in seen:
            seen.add(a); work.extend(heap[a]["refs"])
    return seen
precise = mark(f[i][0] for f, m in zip(frames, stack_maps) for i in m)
conservative = mark(v for f in frames for v, _ in f if v in heap)
print("stack maps (pointer slots per frame):", stack_maps)
print("live objects found precisely:    ", len(precise))
print("live objects found conservatively:", len(conservative))
print("falsely retained by conservatism: ", len(conservative - precise),
      "objects, reached from integers that happen to look like addresses")
print("garbage reclaimed (precise):      ", len(heap) - len(precise), "of", len(heap))

stack maps (pointer slots per frame): [[0, 2], [0], [1]]
live objects found precisely:     7
live objects found conservatively: 9
falsely retained by conservatism:  2 objects, reached from integers that happen to look like addresses
garbage reclaimed (precise):       33 of 40

Two integers in the frames happen to equal heap addresses, and the conservative scan retains the objects they appear to point to, along with anything reachable from them. In real programs such false retention is usually modest but unpredictable, and it is worse on 32-bit systems where integers and addresses overlap more often. The precise collector, guided by the stack maps, ignores the integers.

Moving and generational collectors place further demands on generated code. A generational collector must know about pointers from old objects to young ones, so every store of a pointer into a heap object is followed by a write barrier, a short code sequence the compiler inserts that records the store, for example by marking a card in a table. Concurrent collectors, which run alongside the program, need read barriers or load barriers as well, as in the Z Garbage Collector in Java and Go's collector. The compiler's optimizer must respect these barriers and must not, for instance, keep a derived pointer into the middle of an object in a register across a safepoint unless the stack map describes it. Reference counting, as in Swift and CPython, inserts increment and decrement operations around assignments, and optimizing compilers work hard to eliminate redundant pairs.

Exceptions, threads and other runtime services

Other language features also shape the runtime environment. Exceptions require a way to unwind the stack to the nearest handler, restoring callee-saved registers and running cleanup code; modern compilers use table-driven, zero-cost unwinding, emitting tables (DWARF call-frame information on Linux) that the runtime consults only when an exception is thrown, so the normal path pays nothing. Thread-local storage, dynamic linking with position-independent code and procedure linkage tables, stack protectors that place a canary value between buffers and the return address (lesson 12), and debugging information that maps machine code back to source variables are further responsibilities of the compiler and the runtime working together.

Worked examples