What building a compiler teaches you about modeling anything

Our engineers have built a compiler end to end: a typed source language, a hand-written scanner and recursive-descent parser, a type checker, an SSA-based intermediate representation, six optimizing passes and a graph-coloring register allocator, emitting machine code that runs. Roughly thirty-seven thousand lines. No client paid for it and none ever will.

It stays on the list of things we think an engineer should have done once, because a compiler is the purest available exercise in the skill that decides whether a business system ages well: choosing the representation that makes everything downstream cheap.

The front end is not the interesting part¶

Lexing and parsing get half the pages in most compiler books and roughly a tenth of the difficulty. A scanner is a state machine over a character window. A recursive-descent parser is one function per grammar rule with a constant-time membership check against each rule’s first set. Both are well-trodden, both are pleasant to write, and neither is where a compiler goes wrong.

This is worth saying because the same distortion shows up in business software. The part that is comfortable to build, the forms and the screens, absorbs attention that belongs to the part that decides whether the system can change: how the domain is represented.

public class Scanner implements Iterator<Token> {    private BufferedReader input;    private int lineNum, charPos;    private int nextChar, secondChar;   // 2-char lookahead     public Scanner(String name, Reader r) {        this.input = new BufferedReader(r);        this.nextChar   = readChar();        this.secondChar = readChar();    }    @Override public Token next() { /* DFA over the two-char window */ }}

One constraint that pays for everything¶

Static single assignment is a rule with one clause: every value is assigned exactly once. Where two control-flow paths merge and both define a value, you insert a merge node saying that the value here is whichever predecessor you arrived from. Cytron and colleagues published the efficient construction in 1991 and essentially every serious optimizing compiler since has used a descendant of it.

That single constraint collapses a pile of separately hard problems. Reaching definitions becomes a lookup rather than a fixed-point iteration. Use-def chains are implicit in the representation rather than a structure you maintain. Constant propagation becomes a graph traversal. Dead-code elimination becomes two passes over the use graph. None of those algorithms got smarter; the representation stopped fighting them.

Correct and unusable is a real category¶

The naive way to build SSA is to insert a merge node at every join for every variable. It is correct. It also produces an intermediate representation so large that the passes it was supposed to accelerate become slower than they were before. Cytron’s contribution is a criterion, the dominance frontier, that inserts only the merge nodes that can actually be needed, which in turn requires a working dominator tree, which requires implementing Lengauer-Tarjan first.

There is a further refinement worth naming because it is the cheapest one available: skip the merge node when the variable is not live at the join. Adding that liveness check turns minimal SSA into pruned SSA and stops every later pass from chasing definitions that can never be read. It is a two-line condition that measurably shrinks the work of everything after it.

// For each variable v with definition sites D(v),// place a phi at every block in DF+(D(v)).var worklist = new ArrayDeque<>(entry.getValue());var hasPhi   = new HashSet<BasicBlock>();while (!worklist.isEmpty()) {    BasicBlock b = worklist.poll();    for (BasicBlock y : df.getOrDefault(b, Set.of())) {        if (hasPhi.contains(y)) continue;        if (!liveIn.get(y).contains(s)) continue;   // pruned SSA        y.addPhi(new Phi(s, y.getPredecessors().size()));        hasPhi.add(y);        worklist.add(y);    }}

That liveness check is a dataflow analysis in its own right, and it is worth watching settle rather than reading about: it runs backwards over the control-flow graph and iterates until nothing changes, which takes more than one pass the moment the code contains a loop.

Construction is easy. Deconstruction is not.¶

SSA is a fiction that real machines do not implement. Before registers can be allocated, merge nodes have to be lowered back into ordinary copies. The obvious lowering, copy your value into the merge destination at the end of each predecessor block, is correct in isolation and wrong in two specific situations.

• The lost copy. If the value being copied is also read after the join, the copy can clobber something the join still needs.
• The swap. If a block has two merge nodes that exchange values, sequential copies destroy one before the other can read it.

The fix is to lower through a parallel-copy primitive that detects cycles in the copy graph and breaks them with a temporary. It is a small amount of code and, for us, two days of debugging, because every reference describes SSA construction at length and its deconstruction in a sentence. That asymmetry is not an accident of the literature. The pattern generalizes: the transformation that is elegant to apply is rarely elegant to undo, and systems get built on the assumption that they will never need to.

Both failures are easier to see than to describe. Step the naive lowering through either scenario and the register that gets clobbered is visible on the step it happens.

Register allocation, and knowing what to spill¶

The classical formulation builds an interference graph, joining two values with an edge when both are live at the same point, and colors it with as many colors as there are physical registers. Coloring is NP-hard in general, so real allocators use a heuristic: repeatedly remove any node with fewer neighbors than there are registers, since those are guaranteed colorable, and when none remain, choose something to spill to memory and continue.

The interesting engineering is entirely in that choice. An allocator that keeps per-value statistics can prefer to spill a short-lived value outside a loop over a long-lived one carried across it, and the difference between those two decisions is a memory access on every iteration. Coalescing, which merges values connected by a copy when they do not interfere, removes the copy entirely. Both are heuristics. Both are where the quality lives.

public class RIG {    record Edge(Variable a, Variable b) {}    private Set<Edge> edges = new HashSet<>();     private Stack<Variable> varStack = new Stack<>();    private Set<Variable> spilled    = new HashSet<>();     static class VarStats {        int usesDefs     = 0;        int maxLoopDepth = 0;    }    private Map<Variable, VarStats> varStats = new HashMap<>();    private Map<Variable, Variable> alias    = new HashMap<>();   // coalescing}

Where this lands in client work¶

We are not selling compilers. We are regularly asked to build the things that are compilers with the name filed off: pricing engines that evaluate versioned rule sets, underwriting appetite expressed as configuration a business user edits, eligibility logic that has to explain its own output, and integration layers that translate one domain’s vocabulary into another’s without letting either leak.

Every one of those is a question about representation before it is a question about logic. Can the model express the awkward case directly, or only as an exception? Can a rule change be reviewed, dated and reverted, or does it live in a WHERE clause? Can the system explain why it produced an answer, or only that it did? Teams that have thought hard about intermediate representations ask those questions in week one, which is the only week the answer is cheap.