Compilers and Runtimes

Lexing and parsing

The two-stage front end of a compiler: lexing splits text into tokens, parsing builds a tree from those tokens.

A finite state machine recognizes tokens. A recursive descent or generated parser consumes them, using a stack to track nested structure.

Character-level patterns are regular; nesting requires a stack. Separating the jobs lets a fast machine handle the first and a more powerful one handle the second.

The big idea

Any formal language: source code, configuration, query syntax, structured model output.

When source reaches a compiler, the first problem is not what it means but where its pieces begin and end. A stream of characters has to become identifiers, numbers, operators, and nested constructs before any later stage can reason about it. Lexing and parsing split that work: the lexer turns characters into tokens, and the parser organizes those tokens into structure. The consequence is a front end that uses simple machinery for character patterns and stronger machinery only where nesting demands it.

Why two stages

The split between lexing and parsing exists because the two jobs sit at different levels of the language hierarchy.

Stage	What it does	Machinery	Key limitation
Lexer	Recognizes tokens (identifiers, numbers, operators)	Finite state machine, one pass	Cannot count nested delimiters
Parser	Recognizes nested structure	Stack (explicit or via recursion), context-free grammar	Cannot express regular patterns efficiently

Separating the two keeps the fast, character-level work in a simple machine and leaves the parser dealing with a short stream of typed tokens rather than raw text.

Recursive descent versus generated parsers

Most production compilers hand-write a recursive descent parser despite the existence of parser generators. A generated parser is compact and provably faithful to a grammar, but when it rejects input it can report little beyond the position and the legal tokens.

A recursive descent parser is ordinary code (one function per grammar construct), allowing:

• Context-specific error messages
• Targeted lookahead for ambiguities
• Stepping through in a debugger

Features that resist grammars

Several patterns force the front end to break its clean two-stage split. A contextual keyword is an ordinary identifier in one position and a keyword in another, so the lexer cannot label it without knowing where the parser is. C is the sharp case: whether a * b; declares a pointer or multiplies two values depends on whether a was already introduced as a type name, a fact only the symbol table holds, so the classic C front end feeds that information back into the lexer. Python takes block structure from indentation, which a character-level scanner cannot express, so its tokenizer keeps an indentation stack and emits explicit INDENT and DEDENT tokens for the parser to read. Older C++ compilers parsed the >> that closes two nested template arguments as the right-shift operator, and the standard had to add a rule to disambiguate it.

Error recovery

Error recovery separates a usable compiler from a merely correct one. A parser that stops at the first error forces a compile-fix-compile cycle per mistake.

Technique	How it works
Panic mode	Discards tokens until reaching a synchronizing token (semicolon, closing brace)
Targeted insertion	Assumes a specific missing token and proceeds as if it were present

Cascading errors occur when one real mistake generates a page of consequences. Good recovery suppresses diagnostics that are likely downstream of an earlier one.

Beyond programming languages

The same machinery parses configuration formats, query languages, log formats, template syntaxes, and structured output from a model.

Parsing structured model output has exactly the failure modes a compiler engineer would predict: output that is nearly valid but truncated, or valid syntax carrying semantically wrong content. Constrained decoding makes invalid output unrepresentable rather than merely unlikely.

Abstract syntax trees

A tree encoding what a program means rather than how it was punctuated.

The parser produces it by discarding syntactic noise such as parentheses and separators; equivalent source forms yield the same tree.

Later stages need meaning, not typography. Encoding precedence in tree shape removes it from every subsequent pass.

The big idea

Compilers, linters, formatters, codemods, and any tool that must understand code rather than match strings.

After parsing, the compiler still has evidence of how the grammar recognized the program: separators, parentheses, and intermediate rules that helped parse it. Later stages need a cleaner object, one that says what operation contains what operands without preserving every bit of punctuation. An abstract syntax tree is that object. It gives optimizers, linters, formatters, and codemods a stable structure to traverse, so they work on the program rather than on its surface spelling.

Parse tree versus abstract tree

A parse tree records how the input matched the grammar. An abstract syntax tree records what the program means.

Parse tree	Abstract tree
Contains nodes for every grammar rule traversed	Keeps only semantic structure
Includes precedence rules, parentheses, separators	Precedence encoded by tree shape
Two equivalent source forms produce different trees	Equivalent source forms produce the same tree

The compiler stops caring how the programmer wrote it as soon as this tree exists.

Tree-based tooling

Tool	What it does	Why trees matter
Linter	Walks tree looking for probable mistakes	Unaffected by spacing or spelling
Formatter	Discards original whitespace, prints tree to fixed layout	Output stable regardless of input
Codemod	Matches subtree, replaces with new subtree	Mechanical migration across API changes

Source locations

Source locations carried through every stage are what make diagnostics possible. Each node records where in the original file it came from (usually as a byte range), and every transformation must propagate that information.

Without source locations, a compiler can prove a program wrong and be unable to say where. This gets harder as the program is transformed, since a node in an optimized representation may correspond to several source locations or to code inlined from elsewhere.

Why regex-based tooling fails

A regular expression cannot match balanced delimiters, so it cannot reliably find the end of a function, a nested call, or a block.

Problems with regex transformations:

• No notion of scope (renaming a variable renames the string inside unrelated scopes, string literals, and comments)
• No notion of type (cannot distinguish two methods with the same name on different objects)
• Failures are silent and produce code that still compiles
• They cluster in large or unusual files where manual review is least likely

Tree-based transformation

A tree-based transformation gets all of this correct once the tree carries binding information. A parse alone does not: the shape of the syntax says nothing about which declaration a name refers to, so a rename driven by the bare tree still walks into shadowing and imports. What makes the transformation safe is resolved names and known types hanging off the nodes.

A transformation that runs on the tree works in terms of binding rather than characters. Renaming a declaration reaches only the uses that resolve to it and leaves the same name alone where it sits in a string literal or an unrelated scope. Matching on subtree shape lets it rewrite a call to one method without touching another method of the same name on a different type, and delimiter balance is guaranteed because a subtree is balanced by construction. The price is that the tree has to be printed back to source, and a minimal syntax tree drops the comments and spacing a person wants kept, so tools that rewrite source in place carry a fuller tree that preserves them. A rename in an IDE and a mechanical migration across an API change are both tree rewrites underneath.

Intermediate representations

A language between source and machine code used as the shared representation inside a compiler.

Front ends lower source to the IR; optimizers transform it; back ends lower it to machine code.

Writing one optimizer against the IR covers every source language and every target, turning a multiplication problem into an addition problem.

The big idea

Any toolchain serving multiple languages or multiple targets. Breaks down when domain structure the IR cannot express is needed for optimization.

A toolchain that accepts several source languages and emits code for several processors can easily turn into a grid of one-off translators. Each new language would need every target, and each new target would need every language. Intermediate representations put a shared language in the middle. Front ends lower into it, optimizers rewrite it, and back ends lower it to machines. The consequence is that support grows by adding edges to the middle instead of filling the whole grid.

Multiplication problem

The common middle solves a multiplication problem. Supporting many source languages on many target architectures by writing a direct translator for each pair costs the product of the two counts.

Approach	Cost	What optimizations can use
Direct translation	languages × targets	Must be duplicated for each pair
Common IR	languages + targets	Written once against the IR

A new language gets every existing target for the price of one front end, and a new processor gets every existing language for the price of one back end.

Multiple IR levels

Real compilers use several levels rather than one:

Level	What it retains	What uses it
High-level	Loops, array accesses, type information	Loop transformations, vectorization
Middle	Basic blocks connected by branches	Data-flow analysis
Low-level	Explicit registers, addressing modes	Instruction selection, scheduling

Each lowering step discards information deliberately. A transformation that needs loop structure has to rebuild it once the loops are branches, recovering natural loops from the control-flow graph by way of dominators, and what does not survive that round trip is what the source said rather than what the graph implies.

LLVM IR and MLIR

LLVM IR is a typed, low-level, single-assignment representation resembling a portable assembly language. Its uniformity is its strength for scalar and pointer-heavy code and its limitation for anything with domain structure, since a tensor operation lowered into loops and pointer arithmetic has lost the information a tensor optimizer would use.

MLIR responds by making the representation extensible: instead of one instruction set it provides a framework in which many coexist, organized into dialects. A program can begin in a dialect that knows about tensors and convolutions, and be progressively lowered through dialects that know about loops, then vectors, then hardware intrinsics.

Deep learning compilers

Deep learning compilers adopted this structure because they face the same multiplication problem. Lowering a model graph through progressively more specific representations lets the high stages fuse operations while the tensor structure is still present, and lets the low stages handle tiling and vendor intrinsics.

The gain that justifies the machinery is fusion: a chain of elementwise operations executed separately writes each intermediate result to memory and reads it back, while a fused kernel keeps the value in registers. On hardware where memory bandwidth is the binding constraint, that difference sets the achievable throughput.

SSA form

An IR discipline where every variable is assigned exactly once and phi nodes select among values at control-flow joins.

Give each assignment a distinct name, so every use identifies its defining assignment directly.

Finding which definition reaches a use becomes a lookup instead of a search, so every data-flow analysis gets cheaper.

The big idea

Nearly every optimizing compiler since the early 1990s. Memory locations are exempt because aliasing reintroduces the search.

Once a program has branches and loops, even a plain question can get expensive: which assignment produced the value being used here? In a usual representation, the answer may require walking back through possible paths. SSA form makes each assignment create a new versioned name, with special join names only where control paths meet. That turns many data-flow questions into direct name relationships, so optimization passes can use facts without recomputing them from the control-flow graph.

Why single assignment

Single assignment turns a search problem into a lookup. In an ordinary representation a variable can be assigned in many places, so answering which value reaches a given use requires walking backward through the control flow graph.

Under single assignment:

• Each name is written exactly once
• A use names its definition directly
• Reassignment in the source becomes a new version of the name
• Def-use chains are present in the representation rather than computed by each pass

Phi nodes

Phi nodes handle the one case where a value genuinely depends on which path was taken. If two branches each assign a variable and control rejoins, a phi node sits at the top of the merge block and defines a new name whose value is selected according to which predecessor block control arrived from.

It is a notational device rather than a machine instruction, removed during register allocation by inserting copies at the end of each predecessor.

Optimizations enabled

Optimization	Under SSA	Without SSA
Constant propagation	One lookup (is the single definition a constant?)	Path analysis
Dead code elimination	Reference count (any uses?)	Data-flow analysis over CFG
Common subexpression elimination	Syntactic comparison of operator and operand names	Full data-flow analysis

The adoption is explained by the compounding effect rather than any single optimization. The representation makes each analysis cheaper, and cheaper analyses mean a pipeline can afford more passes.

Adoption and limitations

Nearly every serious compiler built since the early 1990s uses SSA: production compilers for systems languages, managed-runtime just-in-time compilers, and JavaScript engines all converged on it independently.

Limitations:

• Cost of construction and destruction around phi nodes
• Memory analyses do not benefit (memory locations are not names, and aliasing reintroduces the search problem)

Optimization passes

Individual transformations applied in sequence to an IR, each preserving the meaning of the program.

Each pass rewrites the IR according to a local rule. The pipeline runs many passes, often repeating some at different points.

Earlier passes expose opportunities for later ones: inlining reveals constants, constants enable dead code elimination.

The big idea

Ahead-of-time and just-in-time compilers. The gain compounds on generated code more than on hand-written source.

Compiled speed usually comes from many small rewrites compounding. One rewrite exposes a constant, another removes the branch made pointless by that constant, and a later one cleans up the now-unused work. Optimization passes are those meaning-preserving rewrites, run over the intermediate representation in a deliberate order. The consequence is that generated and inlined code, which often contains opportunities a person would never write by hand, can collapse into much simpler machine work.

Pass ordering matters

A pass pipeline is an ordered sequence, and the order changes the result because passes are not commutative. Inlining a function exposes constants that constant propagation can then fold, which may make a branch condition constant, which lets dead code elimination delete a whole block.

Run in the other order, none of that happens. Production pipelines contain the same pass several times at different points, tuned empirically against benchmark suites.

Core passes

Pass	What it does
Constant folding	Evaluates at compile time any expression whose operands are known
Dead code elimination	Removes computations whose results are never used
Loop-invariant code motion	Hoists computations that do not change across iterations out of the loop, when the expression cannot trap or the loop is known to run at least once
Strength reduction	Replaces expensive operations with cheaper equivalents (multiply by power of two → shift)

Individually these look almost too simple to matter. Their value comes from running on code that earlier passes generated, since human-written source rarely contains an obviously foldable constant while inlined and specialized code contains them everywhere.

Phase ordering problem

No pass order is best for all programs, and finding the best order for a given program is intractable. The pipeline is a fixed sequence chosen to work well on average.

Approaches that attack it:

• Iterative compilation: searches a restricted space for a specific program (used when compile budget is large relative to run budget)
• Learned heuristics: predict a good ordering from program features

No general solution

Neither yields a general solution. Iterative compilation searches the space for one program and pays for it in compile time, so its result does not transfer to the next program and it is affordable only when the same binary will run far more often than it is built. A learned heuristic predicts an ordering from program features but generalizes only over code that resembles its training set, and it degrades on inputs outside that distribution. Each improves on a fixed pipeline for the cases it targets while leaving the core problem untouched, so a production compiler ships a default order such as -O2, chosen empirically to work well on average and to behave predictably. The phase-ordering problem is open in general, and a good default is the working answer rather than a solution to it.

Semantic preservation

Semantic preservation is the contract every pass must honor, defined against the language specification rather than observed behavior. A miscompilation is a transformation that violates this contract.

Miscompilations are rare in mature compilers and cluster at:

• Undefined behavior
• Floating point under relaxed modes
• Concurrency (reordering safe for one thread is visible to another)

Inlining

Replacing a function call with the body of the callee at the call site.

The compiler copies the callee into the caller, renaming variables to avoid collision, and deletes the call.

The call boundary hides information: the compiler must assume the callee could do anything. Removing it exposes constants and enables further optimization.

The big idea

Hot call sites with small callees. Stops paying when code duplication pushes the working set out of instruction cache.

A function call is a boundary where the compiler often has to stop assuming what it knows. Arguments go in, a result comes back, and the body may hide constants or branches that would be obvious if it were nearby. Inlining replaces the call with the callee body at the call site. Saving the call mechanics helps, but the larger consequence is that later optimizations can see through the former boundary.

Real benefit

The direct saving from inlining is the call overhead (setting up arguments, saving registers, jumping, returning), which amounts to a few cycles on a modern processor with a well-predicted branch.

The larger effect is that inlining removes an optimization barrier:

Before inlining	After inlining
Compiler must assume call could do anything	Callee’s body is ordinary code in caller’s context
Cannot track constants across boundary	Constant argument becomes constant inside body
Must treat return value as unknown	Branch conditions may become determinate

Trade-off

Code size against speed is the trade, and instruction cache pressure rather than binary size is the real limit. Each inlined copy is duplicated code, and beyond a point the working set no longer fits in the instruction cache.

Aggressive inlining sometimes regresses performance in ways invisible in a microbenchmark, where the entire loop fits in cache regardless. This is why larger programs often see different inlining effects than small tests.

How decisions are made

The inliner estimates the size of the callee after inlining (a function full of constant-foldable code may shrink) and weighs it against an estimate of call frequency.

A source-level inline hint is advisory in most languages, and the compiler is usually right. The reliable way to influence the decision is a profile, since profile-guided compilation replaces the static frequency guess with a measurement.

Connection to kernel fusion

The same idea appears on tensors under the name kernel fusion. In scalar code the barrier is the function call. In tensor code the barrier is the boundary between two operations, each of which reads from memory and writes back.

Fusing them into one kernel keeps the intermediate value in registers or on-chip memory. The costs rhyme: a fused kernel uses more registers, and past a point the pressure forces spilling or reduces concurrent threads.

Register allocation

Assigning an unbounded number of program values to a fixed set of hardware registers.

Build an interference graph where edges connect values live at the same time, then color the graph so no edge has matching endpoints.

A value in a register is accessed in a cycle; a spilled value costs a load. Graph-coloring heuristics look for an assignment with few spills; finding the minimum is NP-hard.

The big idea

Any compiler targeting hardware with a finite register file. JITs use faster, less optimal algorithms because compile time matters.

Near the end of compilation, the program may have more live values than the processor has fast storage for. Values whose lifetimes do not overlap can share a register; values needed at the same time cannot. Register allocation is the assignment of those program values to the fixed hardware register file. The consequence is immediate at runtime: values kept in registers are cheap to use, while spilled values have to be loaded from memory when needed.

Live ranges and interference

A value is live from its definition until its last use. Two values interfere if their live ranges overlap (both must exist simultaneously and cannot share a register).

Building a graph with one vertex per value and an edge for each interference turns allocation into graph coloring: assign a color to every vertex such that adjacent vertices differ, where the colors are the physical registers.

Allocation algorithms

Algorithm	How it works	Use case
Classic (Chaitin-Briggs)	Repeatedly remove vertices with fewer neighbors than registers, push to stack, pop, and color	Ahead-of-time compilers
Linear scan	Treats live ranges as simple intervals over a linearized order	JIT compilers (faster, less optimal)

The chosen spill candidate matters more than the coloring order. Chaitin’s classic metric divides an estimate of access cost (weighted heavily by loop nesting depth) by the value’s degree in the interference graph; some allocators divide by the size of the live range instead.

Spilling

Spilling means keeping a value in memory and loading it when needed.

A spill inside an inner loop is expensive in a way that is easy to underestimate. Each access becomes a load; if modified, a store as well. What looks like one extra instruction is millions of extra memory operations in a numerical kernel.

Cost of a stack slot

A spilled value’s stack slot will usually be in L1 cache (a few cycles, not a memory round trip), but it consumes load and store issue slots. Allocators try hard to place spills outside loops.

Register pressure

Register pressure limits how aggressively earlier passes may transform code:

• Unrolling a loop by 4× quadruples simultaneously live temporaries
• Inlining makes callee’s values compete with caller’s
• Vectorization increases pressure on the vector register file

This is why optimizers model register pressure while making decisions rather than optimizing greedily and discovering the problem afterward.

Accelerator constraint

On accelerators the constraint is sharper: the register file is divided among concurrently resident threads, so a kernel using more registers per thread reduces how many threads can be in flight.

A GPU hides memory latency by keeping many threads resident and switching among them whenever one stalls, so the count of resident threads (its occupancy) sets how much latency the hardware can cover. Registers are frequently the binding resource: the file on each streaming multiprocessor is fixed, and registers per thread multiplied by resident threads cannot exceed it, so a register-hungry kernel runs at low occupancy and gives up the latency hiding that makes the device fast. Spilling is worse here than on a CPU. A spilled value goes to memory that, on current hardware, sits in the same off-chip DRAM as the rest of the working set, cached but far costlier to reach than the L1 stack slot a CPU spill usually lands in. The allocator and the passes above it are therefore balancing register use against occupancy rather than against a few extra loads.

Bytecode and interpreters

A compact instruction set executed by software rather than by hardware, plus the loop that dispatches it.

Source compiles to bytecode once. An interpreter loop reads each instruction, decodes it, and calls a handler.

Bytecode is portable across machines and can be inspected or instrumented at runtime, at the cost of dispatch overhead per instruction.

The big idea

Scripting languages, managed runtimes, configuration VMs. Dispatch dominates for tight loops; array libraries avoid it by moving loops into compiled code.

A runtime that wants the same compiled program to run on different machines can avoid targeting each processor directly. It can instead compile to a small instruction set for a software machine and execute that with a loop. Bytecode and interpreters are that arrangement: bytecode is the portable instruction stream, and the interpreter dispatches each operation. The consequence is easier portability and runtime inspection, paid for by dispatch overhead in tight loops.

Stack versus register machines

Design	How it works	Trade-off
Stack machine	Operands from implicit stack, single-byte instructions	Compact, easy to generate; more instructions and stack traffic
Register machine	Operands named from virtual register file	Fewer dispatches; larger instructions, needs allocation

Register designs generally win on interpretation speed because dispatch dominates.

WebAssembly’s memory boundary

WebAssembly (Wasm) uses a stack machine for its instructions. A module’s linear memory is a contiguous byte array that can grow in pages of 64 KiB, the unit fixed by the WebAssembly specification. A load or store outside the current memory size causes a trap, which stops execution and reports the failure to the host environment.

Bounds checks isolate linear memory from the engine’s memory. They do not check the boundaries of objects stored inside it: a bad pointer can overwrite a neighboring object without trapping. Haas and colleagues make this distinction explicit in their 2017 WebAssembly design paper. Memory-unsafe code compiled to Wasm can retain its memory-corruption bugs inside the sandbox.

Dispatch overhead

Dispatch overhead is the dominant cost in a simple interpreter.

Dispatch style	Mechanism	Branch prediction behavior
Switch loop	Read opcode, enter switch, return to top	One branch site with varying targets; predicts poorly
Threaded	Each opcode jumps directly to next handler	One branch site per opcode; much better prediction

A mispredicted indirect branch costs 10-20 cycles on a deeply pipelined processor, often more than the work the instruction performed.

Python GIL

The global interpreter lock is a mutex ensuring only one thread executes bytecode at a time. Threads do not give parallel speedup for computation in pure Python.

Alternatives for parallelism:

• Separate processes (pay for inter-process data transfer)
• Extension code that releases the lock while running compiled work
• Free-threaded build (extensions with exclusive-execution assumptions must be revised)

Interpreted versus compiled numerical work

Operation	Interpreted loop	Compiled vectorized kernel
Cost per element	~100 nanoseconds (dispatch + unboxing + allocation)	~few hundred picoseconds
Difference	2-3 orders of magnitude

The idiom in array libraries is to express computation as whole-array operations rather than loops: the loop then runs inside compiled code and the interpreter executes a handful of instructions to launch it.

Per-element callbacks in the interpreted language are the standard performance trap.

JIT compilation

Compiling code at runtime using information gathered while the program runs.

Counters identify hot methods. The JIT compiles them with speculative assumptions (observed types, call targets), guarded by cheap checks that deoptimize on violation.

Runtime profiles reveal which paths are hot and what types appear; the compiler specializes for those rather than for all possibilities.

The big idea

Dynamic languages where types are unknown at load time. Warm-up cost makes short-lived processes slower than ahead-of-time.

An interpreter sees facts that a build-time compiler cannot: which functions run often, which branches are common, and which types actually appear. Leaving all of that information unused keeps hot code paying interpreter overhead forever. JIT compilation uses runtime profiles to compile the paths that matter, guarded by checks for the assumptions it made. The consequence is fast steady-state execution when behavior is stable enough to specialize.

Tiering and deoptimization

Code starts in an interpreter or baseline compiler, and counters track how often each function and loop executes. When a counter crosses a threshold, the method is queued for an optimizing compiler.

The optimizing compiler speculates on facts observed so far (e.g., a call site always reaching one implementation) and emits a cheap guard. When a guard fails, the runtime deoptimizes: reconstructs the interpreter state and resumes in the slower tier.

Type feedback and specialization

What JIT learns	What it enables
A site has only ever seen one type	Specialized code with a guard confirming the type
An object always has a certain shape	Property access at fixed offset instead of hash probe

A well-warmed dynamic language can approach statically compiled performance on type-stable code paths. A site that sees many types stays slow.

Warm-up cost

A program spends its early execution interpreting, profiling, and compiling.

Measurement approach	When honest
Steady-state numbers only	Long-running service
Warm-up curve reported	Command-line tool or short-lived function

Deployment shapes that penalize warm-up (per-request isolation, frequent restarts) are why ahead-of-time compilation regained ground.

Tracing JIT

Tracing compilers optimize hot paths instead of hot methods: record the actual sequence of operations through a hot loop, produce a straight-line trace with guards at each divergence point.

Works well when the loop follows the same path most times. Works badly when control flow varies (each divergence adds a guard whose failure exits the trace).

Tensor languages

In tensor languages, the traced sequence is a chain of tensor operations with stable shapes, and the trace becomes a graph that can be fused and compiled for an accelerator. Data-dependent control flow forces a break in the trace.

AOT compilation

Compiling a program to native code before it runs, producing a directly executable artifact.

The compiler sees the whole program at build time, optimizes across modules, and emits machine code for the target.

No warm-up, no compilation spikes, and the artifact can ship without a runtime. The cost is that runtime values are unavailable for specialization.

The big idea

Latency-sensitive services, short-lived processes, and environments where code generation at runtime is prohibited.

Some deployments cannot afford a period of interpreting, profiling, and compiling before performance settles. Others need to ship a binary that runs without generating code at runtime. AOT compilation moves code generation to build time and produces native code before the program starts. The consequence is predictable startup and no compilation spikes during service, while specialization based on actual runtime values is no longer available.

Predictable latency

An ahead-of-time compiled binary executes optimized code from its first instruction. The latency distribution has no compilation spikes, which is a narrower claim than a flat first request: cold page faults, lazy relocation and whatever the program initializes on first use are all still there to be paid.

Situation	Better approach
Service measured at high percentile	AOT
Short-lived instances (steady state never reached)	AOT
Generating code at run time is prohibited	AOT

Recovering run-time information statically

A build can gather information that improves its output without observing the program in production.

Technique	What it does	Limitation
Link-time optimization	Defers code generation until whole program available; inlining works across modules	Still cannot specialize on runtime values
Profile-guided compilation	Runs instrumented build, feeds back branch frequencies and call counts	Profile may not match deployment workload

Shape specialization for tensors

A tensor compiler produces much better code when it knows exact dimensions (tiling, unrolling, vector widths, memory layout all depend on them).

Each distinct shape may trigger a fresh compilation, which takes hundreds of milliseconds to tens of seconds. A serving system that receives varied input lengths spends much of its time compiling.

Controlling shapes in inference

Strategy	How it works	Trade-off
Padding	Round every input up to a fixed size	Wasted compute on padding
Bucketing	Define a small set of sizes, pad to nearest	Bounded compilations; some waste
Dynamic shapes	Leave dimensions symbolic	Avoids recompilation; gives up some optimization

Warming the cache at start-up by running one request per bucket before accepting traffic is standard practice.

Type systems

A static discipline that classifies expressions by the kind of value they produce and rejects programs that violate those classifications.

The compiler assigns a type to each expression and checks that every use is consistent with the type at the definition site.

A type error caught at compile time cannot occur at runtime. The discipline rules out a class of bugs by construction.

The big idea

Any language with a static checker. Soundness is nearly always kept; completeness is always sacrificed.

In ordinary programming, many bugs are mismatches between what a value is and what a piece of code assumes it can do. Tests catch only the paths they execute. Type systems make the compiler classify expressions and reject uses inconsistent with those classifications before the program runs. The consequence is that a broad family of mistakes becomes impossible in accepted programs, though the checker must reject some programs that would have happened to run correctly.

Soundness versus completeness

Property	Meaning	Practical choice
Sound	Never accepts a program that will commit the errors it claims to prevent	Nearly all systems keep this
Complete	Never rejects a program that would have run correctly	All practical systems give this up

Rice’s theorem rules out deciding any non-trivial semantic property of general programs, so no checker can be both sound and complete.

Some widely used systems deliberately introduce unsoundness at specific points (covariant array assignment, escape hatches that suppress checking).

Static versus dynamic

Checking	Coverage	Cost
Static	Every path, including those tests never reach	Annotation effort, compile time, cannot express runtime-dependent properties
Dynamic	Examines actual values; handles anything the program can represent	Finds errors only on paths that execute

Gradual typing

Gradual typing allows typed and untyped regions to coexist so an existing codebase can be annotated incrementally.

What happens at the boundary matters. Systems that erase types (the widely deployed ones) give no run-time guarantee at all: an untyped caller can pass a value that the typed code assumed impossible.

Performance benefits

What types enable	Why it matters
Known size and layout	Structure laid out contiguously with fields at known offsets (better cache behavior)
Concrete type at call site	Direct call or inlined body instead of dynamic dispatch
Known numeric type	Arithmetic on raw value rather than heap-allocated tagged object

This is the same information a JIT discovers through profiling, obtained for free from the declaration.

Types as documentation

A comment describing what a function accepts becomes wrong the moment someone changes the function and forgets it. A signature is checked on every build, so it is either accurate or the build fails.

This is what makes a large codebase navigable by someone who did not write it, and what makes editor tooling (completion, jump-to-definition, safe renaming) possible.

Type inference

Deducing types the programmer did not write from the structure of the program.

Hindley-Milner assigns a fresh type variable to each expression, collects constraints from how they combine, and solves by unification.

The type system remains static and sound while the programmer writes almost no annotations, so the language feels dynamic.

The big idea

Functional languages with parametric polymorphism. Subtyping and overloading break full inference; most OO languages require annotations at boundaries.

Static checking is useful, but writing every type can make code feel heavier than the information in the program requires. Often the surrounding expressions already determine the missing classifications. Type inference is the compiler’s reconstruction of those omitted types from constraints in the code. The consequence is a language that keeps compile-time checking while letting the programmer omit annotations where the structure already pins the answer down.

Hindley-Milner algorithm

The algorithm infers types by generating constraints and solving them with unification:

• Assign each expression a fresh type variable
• Collect equations among those variables from the program’s structure
• Solve the system by unification, matching type expressions and binding variables

The result is the most general type that works. A function that could be used at many types is given a polymorphic type covering all of them; the programmer writes no annotations at all.

Where full inference breaks

Feature	Why it breaks inference
Subtyping	Replaces equalities with inequalities; many solutions with no clear best one
Overloading	Type of expression depends on which function is selected; selection depends on types (circular)

Mainstream object-oriented languages have both features, and none of them offers whole-program inference. Type inference for the full polymorphic lambda calculus is undecidable.

Local inference and bidirectional checking

The practical answer that explains the annotation style of modern languages:

• Local inference: Deduces types within a limited scope (function body), requires annotations at boundaries (parameters, return types)
• Bidirectional checking: Splits into synthesis (type computed from expression) and checking (expected type pushed down)

A lambda passed to a function whose parameter type is known can be checked against that type, so its own parameters need no annotation. The same lambda in isolation would need them.

Error message quality

Error messages pointing at the wrong line are a real cost of inference rather than an implementation defect. Because unification propagates constraints, an inconsistency is detected wherever two conflicting constraints finally meet, which may be far from the mistake.

The problem is worse with more inference and better with more annotations, which is a concrete argument for annotating boundaries even where the compiler does not require it. Compilers mitigate it by tracking the provenance of each constraint so a message can name the origin as well as the point of conflict, and by special-casing common patterns. The mitigation is partial in every implementation.

Calling conventions and the ABI

The binary-level contract for passing arguments, returning results, preserving registers, and laying out data.

The calling convention assigns arguments to registers or stack slots. The ABI extends this to structure layout, exception propagation, and symbol naming.

A binary boundary requires both sides to agree. The ABI provides that agreement, so code from different compilers can link and call each other.

The big idea

Any interface between separately compiled units. Breaking the ABI breaks every binary built against the old one.

A call across a binary boundary cannot rely on source-level intentions. Both sides must agree on where arguments are placed, where results appear, which registers survive, and how data is laid out. Calling conventions and the ABI are that agreement. They let separately compiled units, even from different languages, link and call each other, but they also make compatibility brittle: changing the agreement breaks binaries built for the old one.

Calling conventions

A calling convention specifies where arguments go, where the return value comes back, and who preserves what.

Component	How it works
Integer arguments	First several in designated registers, rest on stack
Floating point	Separate register set
Caller-saved registers	Caller must save before call if it wants the value
Callee-saved registers	Function must restore before returning

The exact registers and counts differ between platforms.

ABI

The application binary interface is the full contract, and it outlives any single compiler version. Beyond the calling convention it fixes:

• Structure layout and padding
• Size and alignment of every primitive type
• Representation of virtual dispatch tables
• How exceptions propagate
• Symbol naming scheme

Breaking the ABI is disruptive enough that ecosystems carry known suboptimal decisions indefinitely rather than change them. Mixing components built against different versions produces crashes rather than a clean error.

Name mangling

A language with overloading needs distinct linker symbols for functions sharing a source name, so it encodes scopes and parameter types into the symbol. Two compilers with different schemes cannot link against each other’s libraries.

C has no overloading, so its symbol names are the source names. This is why every language that wants to talk to another speaks C at the boundary.

Foreign function interface

The FFI is where an interpreted process reaches compiled code. It converts values between interpreter representation and machine representation, calls the function, and converts the result back.

Cost/hazard	Issue
Per-call overhead	Calling a tiny function in a loop is slower than staying in interpreter
Memory ownership	Two sides have different allocators and lifetime notions
Errors	Compiled function signaling failure through return code needs explicit checking

Linking and loading

Resolving symbol references across compiled units and producing an executable or loading one into memory.

The linker matches undefined symbols to definitions, patches addresses, and emits a final binary. The loader maps it and fixes up position-independent references.

Separate compilation requires a later stage to stitch modules together. Position-independent code requires fixup because ASLR varies placement.

The big idea

Any multi-file build, static or dynamic libraries. Version conflicts manifest here as missing or mismatched symbols.

A source file can compile cleanly while still referring to functions or data that live somewhere else. Those promises are settled only when compiled units are stitched together and placed into memory. Linking and loading name that work: resolving symbols, patching addresses, and mapping the resulting binary so it can run. The consequence is that missing libraries, version mismatches, and layout disagreements show up after the compiler has accepted the source.

Static versus dynamic linking

Type	When resolved	Advantages	Disadvantages
Static	Build time	Self-contained artifact, can optimize across boundary	Size; fixing vulnerability requires rebuilding everything
Dynamic	Load time	One copy serves all processes, fixes picked up immediately	Program depends on environment; environment can be wrong

Resolution, relocation, position-independence

Producing a runnable image takes several stages, and each handles references the compiler could not resolve on its own.

Stage	What happens
Resolution	Matches each undefined reference to a definition
Relocation	Patches addresses into code once final layout is known
Position-independent code	Refers to data through a table filled at load time (needed because ASLR varies placement)

The indirection costs an extra load on each access to a global.

Version conflicts

If two dependencies require incompatible versions of the same shared library under the same name, the loader typically maps only one, and the other dependency binds to the wrong version.

Containers sidestep rather than solve version conflicts: each image ships its own complete set of libraries. That converts the conflict problem into a patching problem, since a vulnerability in a common library must be fixed in every image that contains it.

Diagnosing failures

Symptom	Cause
Undefined symbol at build time	Missing library on link line; order issue; mangled name mismatch
Symbol lookup failure at run time	Library at run time differs from build time
Symbol found but behaving wrongly	Name matched but layout or semantics changed; produces corruption not diagnostic

Garbage collection

Automatic reclamation of memory that is no longer reachable from program roots.

A tracing collector walks references from roots, marks live objects, and reclaims unmarked memory. Generational variants collect the young region often and the old region rarely.

Reachable objects cannot be freed without breaking the program; unreachable objects can. Automating the distinction removes use-after-free and double-free bugs.

The big idea

Managed runtimes. Pause time trades against throughput; heap headroom sets collection frequency.

Manual memory management asks programmers to decide exactly when an object can never be reached again. Free too early and a later use is broken; never free and the process grows. Garbage collection gives that decision to the runtime by tracing reachable objects from roots and reclaiming what is left. The consequence is fewer lifetime bugs, paid for with collection work that can affect pause time, throughput, and heap sizing.

Reachability versus usefulness

An object is live if a chain of references leads to it from the roots (registers, thread stacks, global variables). Everything else is unreachable and can be reclaimed.

The gap between reachable and useful is where memory leaks in managed languages live: a cache never evicted, a listener never removed, a collection that accumulates entries. The program’s memory grows without a single missing deallocation.

Heap dumps

Finding the cause requires a heap dump showing which reference chain retains the objects.

A heap dump is a snapshot of every live object and the references between them, taken from a running process. An analyzer builds the dominator tree over that graph, which gives each object a retained size (the memory that would come back if it became unreachable), and it finds the shortest path from a suspect object to a garbage-collection root. The retaining chain usually names the bug once it is laid out: a static registry that is only ever inserted into, or an observer that outlives the object it was watching. Comparing two dumps taken minutes apart isolates the class whose instance count keeps climbing, and that points at the allocation site faster than reading the code does. Tools such as the Eclipse Memory Analyzer for the JVM and the heap-snapshot panel in a browser’s developer tools present these views directly.

Tracing versus reference counting

Strategy	Advantage	Weakness
Tracing	Handles cycles; pays nothing on pointer operations	Collection pass timing program does not control
Reference counting	Prompt reclamation; predictable timing	Arithmetic on every pointer (expensive if atomic); cycles never freed

Systems built on reference counting either add a cycle collector or require the programmer to break cycles with weak references.

Generational collection

Most objects die young. A generational collector allocates into a small young region and collects it frequently (cheap because almost everything is dead). Objects surviving several young collections are promoted to an older region collected rarely.

The bookkeeping requires a write barrier: a small piece of code on every pointer store that records references from old objects to young ones.

Pause time versus throughput

Goal	Best choice	Why
Batch job	Throughput (stop-the-world)	Long pause costs nothing when nothing is waiting
Service measured at p99	Short pauses (concurrent/incremental)	Pauses appear directly in tail latency

The tuning knob that matters most is heap headroom: collection frequency falls as the heap grows relative to the live set. A heap sized too close to the live set produces continuous collection regardless of algorithm.

Undefined behavior

Program states the language specification declines to define, leaving the compiler free to assume they never happen.

The optimizer treats undefined operations as unreachable. Code that would execute only after such an operation may be deleted, including checks meant to prevent it.

Mandating one behavior would require extra instructions on hardware that handles the case differently. Leaving it undefined lets the compiler generate faster code.

The big idea

C and C++ primarily. Memory safety exploits often start at undefined behavior because the resulting state is attacker-controllable.

Some source operations are outside the behavior the language promises to define, even though the processor would still execute some instruction sequence. Undefined behavior is that gap between machine action and language meaning. The optimizer may assume such states never happen and simplify the program under that assumption. The consequence is that defensive-looking checks can vanish if they occur after an operation the specification already treated as impossible.

Why it exists

Reason	Mechanism
Portability	Different processors handle signed overflow, misaligned access, shift amounts differently; defining one behavior forces extra instructions on hardware that disagrees
Optimization	Declaring a case undefined lets the optimizer assume it never happens, which enables loop transformations, vectorization, and constant propagation

How assumptions delete your checks

Consider code that dereferences a pointer and then tests it against null:

• The dereference is undefined if the pointer is null
• The compiler may assume the pointer was not null
• The subsequent test is always false under that assumption
• Both the test and the error handling are deleted

The programmer’s defensive check is gone from the binary. Nothing here is a compiler bug: each step follows from the specification. The surprise comes from reading source as machine operations rather than as a program in a language with a formal contract.

Security consequences

A large share of memory-safety exploits begin at undefined behavior. A buffer overflow, use-after-free, or read past allocation end is undefined, so what follows is determined by memory layout an attacker can often influence.

Microsoft reported in 2019 that about 70 percent of the vulnerabilities it assigns a CVE each year are memory-safety issues, and the Chromium project reports the same share, around 70 percent, of its high-severity security bugs.

Mitigations

Approach	Cost	Coverage
Sanitizers	2-3× slowdown (ThreadSanitizer 5-15×); testing only	Detects violations on paths that execute
Memory-safe language	Rewrite plus runtime/expressiveness penalty	Removes class by construction

Government and industry guidance since 2022 pushes toward memory-safe languages for new development while accepting that existing systems will be hardened incrementally.