📘 Compilers and Program Execution

This page follows a program from source text to a running process. It explains what compilers, linkers, loaders, virtual machines, and garbage collectors do, which helps with performance tuning, reading stack traces, and answering "what happens when you run a program" questions.

Table of Contents

1. Compiled, Interpreted, and JIT
2. Compiler Phases
3. Common Optimizations
4. From Object Files to Executables
5. Static vs Dynamic Linking
6. Loading and Running
7. The Call Stack
8. Stack vs Heap
9. Garbage Collection
10. Virtual Machines and Runtimes
11. WebAssembly
12. Questions

1. Compiled, Interpreted, and JIT

A language is not inherently compiled or interpreted; implementations are. Python has CPython (interpreter, with an experimental JIT since 3.13), PyPy (JIT), and Cython (compiler).

Why JIT can beat AOT: it sees actual runtime types and hot paths, so it can inline virtual calls, specialize on common types, and deoptimize back to the interpreter if assumptions break. Why AOT wins at startup: no warm-up, lower memory, which matters for CLIs and serverless functions.

2. Compiler Phases

The front end (lexing through semantic analysis) is language specific; the back end (optimization and code generation) is target specific. LLVM made this split practical: Clang, Rust, Swift, Zig, and Julia front ends share one optimizer and many back ends.

Static single assignment (SSA): every variable is assigned exactly once in the IR, which makes data flow explicit and optimizations simpler.

Parsing families: LL (top-down, recursive descent, what most hand-written compilers use) and LR (bottom-up, parser generators like yacc and bison). Errors caught at each stage: lexical (bad character), syntax (missing semicolon), semantic (type mismatch, undefined variable).

3. Common Optimizations

Optimization levels: -O0 (debuggable), -O2 (standard release), -O3 (aggressive), -Os / -Oz (size). Link-time optimization (LTO) optimizes across files; profile-guided optimization (PGO) uses real run data to lay out hot code, typically worth 10 to 20 percent.

Undefined behavior in C and C++ lets compilers assume things never happen (signed overflow, null dereference), which enables optimizations but can delete checks you thought were there.

4. From Object Files to Executables

gcc -E main.c -o main.i     # preprocess only
gcc -S main.c               # compile to assembly (main.s)
gcc -c main.c               # assemble to object file (main.o)
gcc main.o util.o -o app    # link
nm main.o                   # list symbols (U = undefined, needs linking)
objdump -d app | less       # disassemble

An object file contains machine code and data in sections, plus a symbol table (what it defines and what it needs) and relocations (places to patch once final addresses are known).

The linker:

1. Symbol resolution: match every undefined symbol to exactly one definition; typical errors are "undefined reference to foo" (missing definition or library) and "multiple definition of foo".
2. Relocation: assign final addresses and patch references.

Key ELF sections: .text (code), .rodata (constants), .data (initialized globals), .bss (zeroed globals), .symtab, .debug_* (DWARF debug info, removed with strip).

5. Static vs Dynamic Linking

ldd ./app lists dynamic dependencies on Linux (otool -L on macOS).

Dynamic linking uses position-independent code (PIC): code that works at any address, reaching globals and functions through the GOT (global offset table) and PLT (procedure linkage table). Programs can also load libraries at run time with dlopen (plugins).

Static binaries are popular in containers: a Go binary in a scratch or distroless image has almost no attack surface.

6. Loading and Running

What happens when you type ./app in a shell:

1. The shell calls fork, and the child calls execve("./app", argv, envp).
2. The kernel reads the ELF header, checks permissions, and creates a new address space.
3. It maps the program's segments (text as read and execute, data as read and write), sets up the stack with argv, environment, and auxiliary vector, applying ASLR offsets.
4. For dynamic executables, it maps the dynamic loader (ld-linux.so) and jumps to it.
5. The loader maps shared libraries, performs relocations, and runs library initializers.
6. Control reaches _start, which sets up the C runtime and calls main(argc, argv).
7. main returns, exit runs atexit handlers and flushes buffers, and the kernel tears down the process and notifies the parent.

See Processes and Threads for the fork and exec side.

7. The Call Stack

Each function call pushes a stack frame.

Higher addresses
+------------------------------+
| caller's frame               |
+------------------------------+
| arguments beyond registers   |
| return address               |  pushed by CALL
| saved frame pointer          |  <- frame pointer (rbp)
| saved callee registers       |
| local variables              |
| temporaries / spills         |  <- stack pointer (rsp)
+------------------------------+
Lower addresses (stack grows down)

A calling convention is the agreement on how calls work at the machine level:

Windows x64 uses a different convention (rcx, rdx, r8, r9), which is one reason binaries are not portable across OSes on the same CPU. Calling conventions are part of the ABI (application binary interface), along with struct layout and name mangling.

Recursion uses one frame per level, so deep recursion hits the stack limit: stack overflow. Languages without guaranteed tail call optimization (Java, Python, JavaScript in most engines) need iteration for deep recursion.

Stack traces are produced by walking frames (using frame pointers or unwind tables) and mapping return addresses to function names via debug symbols. Many distributions re-enabled frame pointers by default (Fedora, Ubuntu 24.04) to make profiling reliable.

Buffer overflows on the stack overwrite the return address; defenses include stack canaries, NX (non-executable stack), ASLR, shadow stacks (Intel CET, ARM GCS), and memory-safe languages.

8. Stack vs Heap

In Java, objects live on the heap and references on the stack, though escape analysis may place non-escaping objects on the stack or remove them. In Go, the compiler decides via escape analysis (go build -gcflags=-m shows decisions). In C and C++, you choose; in Rust, ownership decides when heap memory is freed without a GC.

9. Garbage Collection

Automatic memory management frees objects that the program can no longer reach.

Roots are the starting points: stack variables, registers, globals, and static fields.

Real collectors:

Tri-color marking: white (not yet seen), gray (seen, children not scanned), black (done). Concurrent collectors use write barriers so the program cannot hide a white object behind a black one while marking runs.

Memory leaks still happen with GC: objects kept reachable by accident (growing caches, listeners never removed, static collections, closures capturing large objects).

10. Virtual Machines and Runtimes

Stack-based vs register-based VMs: the JVM and CPython push and pop operands on an operand stack (compact bytecode); Lua and Android's Dalvik use virtual registers (fewer instructions).

// javap -c output for: int add(int a, int b) { return a + b; }
iload_1
iload_2
iadd
ireturn

JIT warm-up is why JVM and Node.js benchmarks must run long enough, and why serverless cold starts favor AOT or snapshot techniques (CRaC, Lambda SnapStart).

11. WebAssembly

WebAssembly (Wasm) is a portable, sandboxed binary instruction format.

Uses: heavy computation in browsers (Figma, Photoshop web, video editing), plugin systems, edge functions, and portable sandboxes.

12. Questions

Next: Parallelism and Modern Hardware.