Topic domain
Compilers
From source text to machine code, stage by stage.
- Articles
- 80
- Clusters
- 8
- Foundational
- 24
- Intermediate
- 32
- Advanced
- 24
Tokenization, grammars, and parser construction.
- Maximal Munch and the Boundary Between Tokens
- From Regular Expression to DFA Table: Inside a Lexer Generator
- Recursive Descent and the Cost of One Token of Lookahead
- Precedence Climbing for Binary Expressions
- LALR Table Construction and What the Conflicts Mean
- Error Recovery in Recursive Descent Parsers
Scopes, symbol tables, and type checking passes.
- Resolving Identifier Uses Against a Stack of Lexical Scopes
- Symbol Table Layouts and the Cost of Leaving a Scope
- Separate Namespaces and Overload Sets in a Symbol Table
- Collecting Declarations Before Resolving Any Body
- Bottom-Up Expression Typing with Inference Variables
- Definite Assignment as a Flow-Sensitive Dataflow Problem
SSA, control-flow graphs, and IR design.
- Three-Address Code as the Contract Between Front End and Back End
- Building Basic Blocks and Control-Flow Graphs from Linear Code
- Minimal SSA Construction from Dominance Frontiers
- Phi Functions: Parallel Semantics and the Out-of-SSA Problem
- Sparse Conditional Constant Propagation Across the SSA Graph
- Memory SSA: Giving Loads and Stores Def-Use Chains
Optimization
10Dataflow analysis, inlining, and loop transformations.
- Reaching Definitions and the Monotone Dataflow Framework
- Live-Variable Analysis and the Backward Direction of Dataflow
- SSA Construction and the Cost of Phi Placement
- Constant Propagation over a Flat Lattice
- Inlining Decisions and the Cost Model Behind Them
- Escape Analysis and Scalar Replacement of Aggregates
Graph coloring, spilling, and calling conventions.
- Live Ranges as the Input to Register Allocation
- Building the Interference Graph from Live Sets
- The Simplify and Select Loop of Chaitin-Style Coloring
- Spill Cost Heuristics and the Choice of Victim
- Conservative Coalescing and the Conditions That Make It Safe
- Linear Scan Allocation over Sorted Live Intervals
Instruction selection, scheduling, and peepholes.
- Instruction Selection as Tree Tiling
- Maximal Munch and Dynamic-Programming Tiling
- Folding Address Computation into Memory Operands
- Two-Address Instructions and Destructive Operands
- Peephole Optimization and the Sliding Window
- List Scheduling and the Critical Path
Object formats, relocation, and dynamic linking.
- Sections, Symbols, and Relocations in an ELF Object File
- Static Archives and Link Order: Why a Library Must Come After Its User
- Relocation Arithmetic: Patching Machine Code at Link Time
- Position-Independent Code and the Global Offset Table
- From execve to _start: How the Kernel Maps an ELF Executable
- SONAME, DT_NEEDED, and Symbol Versioning in Shared Libraries
Build systems, cross compilation, and diagnostics.
- How a Compiler Driver Dispatches Work to Preprocessor, Compiler, Assembler, and Linker
- Header Dependency Discovery: Why the Compiler Records Includes, Not the Build Tool
- Target Triples, Sysroots, and What Actually Changes When Cross-Compiling
- Sources of Nondeterminism in Compiled Artifacts and How They Are Removed
- Scheduling a Parallel Build from a Dependency Graph
- Content-Addressed Build Cache Keys: What Must Go Into the Hash
All Compilers articles
- Oct 23, 2026 Precedence Climbing for Binary Expressions How a loop with a minimum-binding-power parameter parses operator precedence and associativity in one function, and how its behaviour maps onto the grammar it replaces.
- Oct 20, 2026 Sections, Symbols, and Relocations in an ELF Object File Why a compiled object file is more than machine code: the section header table, the symbol table and its string table, and the relocation records a linker consumes.
- Sep 26, 2026 Symbol Interposition and the Global Namespace The search order that decides which definition of a name wins, why a shared library cannot rely on its own globals, and how preloading and interposition actually take effect.
- Sep 16, 2026 Target Triples, Sysroots, and What Actually Changes When Cross-Compiling A triple names an architecture, vendor, operating system, and ABI. The hard part of cross-compilation is not instruction selection but the header tree, startup objects, and libraries that the triple implies.
- Sep 14, 2026 Instruction Scheduling and Its Dependence on the Graph How list scheduling trades register pressure against parallelism, what latency and resource tables must contain, and why the scheduler sees a different graph from the one the optimiser built.
- Sep 10, 2026 From execve to _start: How the Kernel Maps an ELF Executable Program headers rather than section headers drive loading, PT_LOAD segments carry permissions, PT_INTERP names the dynamic linker, and the kernel hands over a stack with argc, argv, and auxv.
- Sep 9, 2026 Scheduling Before Allocation and the Pressure Trade Why an aggressive instruction schedule can force spills that erase its own benefit, how pressure-aware scheduling caps live values, and what iterative repair actually converges on.
- Aug 21, 2026 Profile-Guided Optimization and Hot-Cold Code Splitting Profile data turns optimization decisions from static guesses into frequency estimates, and splitting cold paths out of hot functions is what converts that knowledge into layout, register, and inlining wins.
- Jul 28, 2026 STT_GNU_IFUNC: Choosing an Implementation at Load Time How a symbol can name a function that returns the address to call, the constraints the resolver runs under, and why the technique trades startup determinism for dispatch without indirection.
- Jun 14, 2026 Incremental Reparsing After an Edit How an editor reuses the parse tree around a changed range, why error recovery nodes make reuse unsafe, and what the invalidation rules must guarantee.
- Jun 11, 2026 Static Archives and Link Order: Why a Library Must Come After Its User How an ar archive is laid out and searched, why a single left-to-right pass over libraries resolves some references and not others, and what group and repeated search do about it.
- Jun 8, 2026 Chordal Interference Graphs and Optimal Coloring in SSA Form Why the interference graph of an SSA program has no induced cycles longer than three, how a perfect elimination ordering yields a minimum coloring in linear time, and what destroying SSA costs.
- Jun 3, 2026 Collecting Declarations Before Resolving Any Body How a hoisting pass makes forward and mutual references resolvable, what it must record about ordering and initialization, and which language rules it cannot express.
- May 29, 2026 Content-Addressed Build Cache Keys: What Must Go Into the Hash A cache hit is only sound if the key covers every input that can change the output. The compiler binary, its flags, the header contents, and the transitive environment all belong in it; the clock and the path usually do not.
- May 27, 2026 Reaching Definitions and the Monotone Dataflow Framework How a compiler computes which assignments can reach each program point, why the answer is a least fixpoint over a lattice, and where the bitvector approximation stops being exact.
- May 15, 2026 Bidirectional Checking: When a Type Is Synthesized and When It Is Checked How splitting the typing judgment into synthesis and checking makes annotated lambdas and empty literals typable without a global constraint solver, and where the split loses completeness.
- May 15, 2026 SSA Construction and the Cost of Phi Placement Dominance frontiers decide where phi nodes belong, minimal SSA places too many of them, and pruning by liveness is what keeps the form small enough to optimize.
- Apr 27, 2026 LALR Table Construction and What the Conflicts Mean How LR(1) item sets become LALR states, what shift-reduce and reduce-reduce conflicts actually report about a grammar, and when a precedence declaration is the correct repair.
- Apr 2, 2026 Reading a Preprocessor Diagnostic Through Macro Expansion Preprocessor errors cite a line that may contain no error at all. Tracking the expansion stack, the difference between a file and a macro origin, and where note lines come from turns the output into a usable trace.
- Mar 21, 2026 Building the Interference Graph from SSA Live Ranges Why SSA live ranges interfere only at phi-connected join points, how that makes the graph chordal, and what the colouring and spilling decisions cost once the graph is built.
- Mar 18, 2026 Loop Unrolling, Trip Counts, and the Cost of Code Growth Unrolling by a known factor removes loop overhead and enables scheduling across iterations, but it needs trip-count knowledge, a remainder loop, and a register-pressure check to pay off.
- Mar 1, 2026 Dependence Analysis and Polyhedral Loop Transformations Deciding whether two iterations touch the same memory requires a dependence test, and the polyhedral model turns those tests into an integer linear program whose solution drives tiling, skewing, and fusion.
- Feb 27, 2026 Memory SSA: Giving Loads and Stores Def-Use Chains How aliasing prevents ordinary SSA from naming memory locations, what the memory-phi construction buys for store-to-load forwarding, and why the result must be abandoned rather than verified.
- Feb 17, 2026 Peephole Optimization and the Sliding Window How local rewrites over a small instruction window remove redundant loads, collapse moves, and turn compare-and-branch pairs into single instructions, and where the window size stops helping.
- Feb 5, 2026 Building Basic Blocks and Control-Flow Graphs from Linear Code How leaders split a linear instruction stream into basic blocks, how edges are derived from branches, and which irregularities in real control flow break the simple model.
- Feb 5, 2026 Loop-Invariant Code Motion and the Conditions It Needs Hoisting an expression out of a loop requires proving it computes the same value on every iteration, and each of the conditions that license it fails in a way that costs correctness rather than speed.
- Jan 17, 2026 Hermetic Build Actions: Enforcing That Compilation Reads Only Declared Inputs A declared input list is a promise. Making the promise enforceable means restricting the file system, the clock, and the network, and choosing which of those restrictions is worth its cost.
- Jan 8, 2026 Error Recovery in Recursive Descent Parsers How a hand-written parser detects a syntax error, chooses a synchronisation point, and limits cascading diagnostics, including why panic-mode recovery beats local correction.
- Dec 31, 2025 Recursive Descent and the Cost of One Token of Lookahead How a hand-written parser decides which production to take from a single token, how FIRST and FOLLOW sets make that decision safe, and why the method fails on left-recursive and prefix-sharing grammars.
- Nov 16, 2025 Maximal Munch and the Boundary Between Tokens How a lexer decides where one token ends, why the longest-match rule is separate from the grammar, and which token sequences it produces that the source text does not appear to contain.
- Nov 10, 2025 Relocation Arithmetic: Patching Machine Code at Link Time The formulas behind absolute, PC-relative, and GOT-relative relocations, the range limits that make them fail, and why the addend must be stored separately on some architectures.
- Oct 30, 2025 Inlining Decisions and the Cost Model Behind Them Inlining is chosen by a profitability estimate over caller and callee size, call frequency, and constant-argument opportunities, and every model trades code size against a set of downstream optimizations.
- Oct 21, 2025 List Scheduling and the Critical Path How a basic-block scheduler orders instructions to hide latency, why the critical path bounds the result, and how register pressure forces it to give that bound up.
- Sep 25, 2025 Escape Analysis and Scalar Replacement of Aggregates Escape analysis decides which allocations never leave a thread or a method, and scalar replacement turns those objects into SSA values so the allocation and its fields disappear entirely.
- Sep 6, 2025 Definite Assignment as a Flow-Sensitive Dataflow Problem How a checker proves every variable is written before it is read, why the answer depends on control flow rather than scope, and how the lattice and transfer functions are chosen.
- Sep 3, 2025 Spill Cost Heuristics and the Choice of Victim How allocators price a virtual register in loads and stores, why the cost-to-degree ratio is the wrong objective in loops, and what the reload placement problem looks like after spilling.
- Aug 26, 2025 Building the Interference Graph from Live Sets The exact rules that turn per-instruction liveness into graph edges, why move instructions are treated differently, and how the graph representation affects the cost of coloring.
- Aug 26, 2025 Folding Address Computation into Memory Operands How base, index, scale, and displacement get absorbed into load and store encodings, which arithmetic survives the fold, and why the selector must sometimes refuse.
- Aug 13, 2025 Lazy Binding and the Procedure Linkage Table How the first call to an external function lands in the dynamic linker, what the resolver writes into the GOT, and why eager binding and full RELRO remove the writable page.
- Aug 1, 2025 Closure Capture, Lexical Scope, and Storage Duration Why capturing a variable is a decision about storage rather than about names, how an escaping frame is moved to the heap, and what breaks when a loop body shares one binding.
- Jul 29, 2025 Partitioned Boolean Quadratic Programming for Register Allocation How encoding allocation as per-node costs plus per-edge cost matrices lets a solver trade spills against copies with a single objective, and why reduction rules beat coloring heuristics on hard graphs.
- Jul 16, 2025 Live-Variable Analysis and the Backward Direction of Dataflow Liveness runs the dataflow equations against the edges, from uses back to definitions, and the difference between may-liveness and must-liveness decides which optimizations are legal.
- Jun 29, 2025 Linear Scan Allocation over Sorted Live Intervals How a single pass over intervals ordered by start point assigns registers, why active-list eviction beats spilling the current interval, and what the interval approximation gives up.
- Jun 17, 2025 Constant Propagation over a Flat Lattice Propagating constants requires a lattice with an explicit top element for "not constant", a meet that never guesses, and an SSA-based solver that avoids the quadratic worklist.
- May 27, 2025 Packrat Parsing and the Linear-Time Guarantee How memoising PEG results buys guaranteed linear parse time, what the memo table costs in memory, and why ordered choice removes ambiguity by fiat rather than by analysis.
- May 23, 2025 SONAME, DT_NEEDED, and Symbol Versioning in Shared Libraries How a shared object records the name it wants to be found under, why DT_NEEDED names a soname rather than a file, and how version definitions keep old binaries working.
- Apr 1, 2025 Phi Functions: Parallel Semantics and the Out-of-SSA Problem Why phi inputs are read simultaneously rather than in sequence, how that forces the lost-copy and swap problems on elimination, and how edge splitting and register coalescing resolve them.
- Mar 26, 2025 Bottom-Up Expression Typing with Inference Variables How a checker types an expression from its children, when it must defer a decision to a metavariable, and how unification and the occurs check close those holes.
- Mar 22, 2025 Debug Information for Optimized Code: Line Tables, Location Lists, and Lost Variables At -O2 the compiler moves, merges, and deletes variables. DWARF describes the result with location lists and inline scopes, and the debugger reconstructs values that no longer live anywhere.
- Mar 8, 2025 Separate Namespaces and Overload Sets in a Symbol Table How languages keep types, values, tags, and labels in distinct tables, and what changes when one spelling must resolve to a set of candidate declarations instead of a single one.
- Mar 4, 2025 Symbol Table Layouts and the Cost of Leaving a Scope Why a compiler symbol table is not just a hash map, how scope exit is made cheap, and what the per-scope-frame and shadow-stack designs each cost in lookup and memory.
- Feb 10, 2025 Error Types and Recovery in a Type Checker How a checker keeps going after the first type error without accepting nonsense, what an error type must absorb, and why the count of reported errors is a design decision.
- Jan 24, 2025 Three-Address Code as the Contract Between Front End and Back End Why compilers flatten expression trees into single-operator instructions with named temporaries, what optimization gains from that shape, and which machine constructs the form cannot express directly.
- Jan 22, 2025 Bundling Instructions for VLIW Issue Slots How a compiler packs independent operations into fixed-width bundles, why empty slots become explicit no-ops, and how slot assignment and stop bits constrain the scheduler.
- Dec 19, 2024 Maximal Munch and Dynamic-Programming Tiling Two ways to choose which instruction patterns cover an expression tree, why greedy top-down matching can be arbitrarily bad, and what the optimal algorithm costs to run.
- Dec 12, 2024 Minimal SSA Construction from Dominance Frontiers How the Cytron placement algorithm decides where phi functions belong using dominance frontiers, and why placing them minimally changes what later passes can assume.
- Aug 5, 2024 Header Dependency Discovery: Why the Compiler Records Includes, Not the Build Tool Reconstructing a translation unit's header list by scanning source text fails on conditional and computed includes. The front end already knows which files it opened, and it can write that list as a makefile fragment.
- Jul 30, 2024 If-Conversion, Predication, and the Limits of Speculation How conditional branches become data dependences on a predicate, when that is profitable, and why the transformation must respect faults, exceptions, and the register file.
- Jul 9, 2024 Bootstrapping a Self-Hosted Compiler and Why the Build Is Compared Against Itself A compiler written in its own language cannot be built from nothing. Three-stage bootstrapping solves the chicken-and-egg problem and turns the second and third stages into a self-check of the whole toolchain.
- Jun 23, 2024 Let-Polymorphism and Where Generalization Happens Why a let-bound definition can be used at several types while a lambda parameter cannot, how the level of a metavariable decides what gets generalized, and what the value restriction protects.
- Apr 8, 2024 Modulo Scheduling and Software Pipelining How a loop is transformed so that successive iterations overlap in the pipeline, what the initiation interval bounds are, and why prologue and epilogue code appears at the edges.
- Jan 25, 2024 Sources of Nondeterminism in Compiled Artifacts and How They Are Removed Two builds of the same source can differ in embedded timestamps, temporary paths, hash-map iteration order, and archive member metadata. Each leak has a specific mechanism and a specific suppression.
- Oct 23, 2023 Live-Range Splitting at Region Boundaries Why a value that is live in two distant regions is better allocated as two values, how splitting interacts with spilling, and what the extra moves cost at the join.
- Sep 17, 2023 From Regular Expression to DFA Table: Inside a Lexer Generator Thompson construction, subset construction, and table compression, and why a generated lexer scans in time linear in the input no matter how many patterns were declared.
- Sep 12, 2023 Calling Conventions as Precolored Constraints on the Graph How the ABI fixes which registers hold arguments, returns, and preserved values, and how those obligations enter the interference graph as edges to nodes that already have a color.
- Jul 11, 2023 Thread-Local Storage Access Models The four TLS access sequences the compiler can emit, what each costs per access, and why a module loaded after startup cannot use the cheapest ones.
- May 19, 2023 Context-Dependent Lexing: Typedef Names, Layout, and Lexer Modes How the C typedef ambiguity forces the lexer to consult the parser, how indentation-sensitive layout is implemented, and what string interpolation does to the token model.
- Apr 7, 2023 Instruction Selection as Tree Tiling How a back end maps an intermediate representation onto machine instructions by covering expression trees with patterns, and why legality and cost are separate questions.
- Feb 15, 2023 Scheduling a Parallel Build from a Dependency Graph A build is a DAG of commands with known costs and unknown costs alike. Choosing what to run next determines both wall-clock time and how badly a late-discovered dependency hurts.
- Jan 13, 2023 Position-Independent Code and the Global Offset Table Why shared code cannot contain absolute addresses, how the GOT turns one pointer indirection into position independence, and what the PLT adds for functions.
- Nov 16, 2022 GLR Parsing and the Graph-Structured Stack How a generalized LR parser follows every viable parse at once by replacing the stack with a DAG, how ambiguity is packaged into a shared forest, and what the merging costs.
- Aug 3, 2022 Conservative Coalescing and the Conditions That Make It Safe Why merging the source and destination of a move can make a colorable graph uncolorable, and how the Briggs and George tests decide when the merge is guaranteed not to hurt.
- Jul 25, 2022 The Simplify and Select Loop of Chaitin-Style Coloring Why coloring a register interference graph is done by repeatedly removing low-degree nodes and pushing them back on a stack, what the degree test really guarantees, and when the greedy result is optimal.
- Jul 4, 2022 Sparse Conditional Constant Propagation Across the SSA Graph How SCCP combines constant propagation with reachability so that unreachable branches stop contributing values, and why the sparse formulation converges faster than a dense lattice iteration.
- Mar 4, 2022 Two-Address Instructions and Destructive Operands Why many instruction sets overwrite an input register to produce a result, how that constraint turns selection into a copy-insertion problem, and what the copies cost.
- Feb 23, 2022 Poison, Undef, and What an IR Must Say About Speculation How deferred undefined behaviour lets an IR move and duplicate operations that might trap, why poison propagates through flags like nsw, and what a freeze instruction buys in exchange for lost optimisation.
- Feb 18, 2022 Sea of Nodes: Scheduling Without a Fixed Instruction Order How a graph-based IR represents data, control, and memory dependences as edges with no block order, what scheduling then becomes, and which analyses become harder when nothing is sequential.
- Dec 22, 2021 How a Compiler Driver Dispatches Work to Preprocessor, Compiler, Assembler, and Linker The program named cc compiles nothing itself. It parses one command line, routes each option to the stage that understands it, and chains four subprocesses through temporary files.
- Dec 8, 2021 Live Ranges as the Input to Register Allocation How backward liveness analysis turns a control-flow graph into the per-value program points that every allocator reasons over, and where that abstraction stops being exact.
- Nov 14, 2021 Resolving Identifier Uses Against a Stack of Lexical Scopes How a semantic pass turns each identifier token into a reference to exactly one declaration, what the scope stack must record, and where a single pass over the tree is not enough.