Practice

Two kinds of exercise: a compiler that misbehaves, where you name the stage before the fix; and a transformation you apply by hand, where the trap is the answer that looks right.

Diagnose the stage

A compiler produces the wrong thing. Commit to which phase is at fault before you open the evidence — that is the skill.

intermediate4
Nothing errors and every number is wrong

The rule `total = base + qty * unit` computes `(base + qty) * unit`. There is no error, no warning, no crash — the program runs and produces a number, and the number is plausible. Small inputs happen to agree, which is why the tests passed: the fixtures use `qty = 1` and `unit = 1`.

A type error that only the runtime notices

`let flag: bool = 3;` compiles without a diagnostic. So does `let n: int = true;`. The generated bytecode stores the integer into a slot typed `bool`, and the VM faults on the first branch that reads it, several hundred instructions later, with `expected bool, found int` — pointing at the branch, not at the assignment.

The build broke on code that was never going to run

error: division by zero in constant expression. The build fails. Nothing is wrong at run time and nothing ever was: the guard is correct and the entry is unreachable. Reverting the compiler upgrade makes the error disappear and the binary behave identically.

Every stack frame points one line too high

Every frame in every production stack trace points at the line immediately above the real one. Off by exactly one, everywhere, in every file. The mapped column is correct. Traces from the un-minified build are correct.

advanced5
The inner `let` overwrote the outer one

The program `let x = 1; if (true) { let x = 2; print(x); } print(x);` printed `2` and then `2`. The inner block is supposed to introduce a new binding that dies at the closing brace, so the second print must see `1`. No diagnostic was produced. The interpreter, which walks the AST and never goes near the IR, printed `2` then `1` — correctly.

The counter stopped counting at -O2

`record("requests");` as a statement produces no counter increment in the optimized build. `let n = record("requests"); print(n);` works. The generated IR for the first form contains no call at all — the instruction is simply absent between the two neighbouring instructions.

A phi with three sources in a block with two predecessors

The verifier reports `phi in b7 has 3 sources but b7 has 2 predecessors`. When the verifier is disabled — which someone tried — the program runs and produces a value read from a block that no longer exists on any path into b7.

The right function was called, from the wrong library

Every call to `malloc` from application code goes to the vendored allocator. Every call from the SDK goes to the system allocator. Both were compiled against the same header, both resolve at run time, neither reports an error. Under `LD_PRELOAD` of a third allocator, all of it moves again.

The incremental build produced a binary the sources cannot explain

One consumer module reads fields at the wrong offsets; every other consumer is correct. A clean build produces a correct binary. Deleting the build cache fixes it, so the reflex is to call it a cache bug and move on.

expert4
A value that was still needed, in a register that was reused

A checksum function returns a value that is wrong by exactly the contribution of one term. The IR is correct, the SSA is correct, and the optimized IR is correct. Only the assembly is wrong, and only above about forty live values.

The two arguments both arrived as the second one

`divide(a, b)` where `a` currently lives in the second argument register and `b` in the first — a natural outcome of the previous call — returns `b / b`, which is 1 for every non-zero input. Swapping the two parameters at the call site makes the bug disappear and reappear elsewhere.

The copy executed on a path that did not need it

A loop that accumulates into `sum` when a condition holds produces a value that is too large. The extra contribution comes from an iteration on which the condition was false. Disabling the optimizer does not change it, and the bug survives at every optimization level.

Correct for nine minutes, then wrong

The wrong output begins at the point where the input starts containing a subclass that overrides the method. The interpreter and the first-tier compiler both handle it correctly. Only the optimizing tier is wrong, and only after the method has been recompiled at that tier.

Do the transformation

Apply the optimization, insert the phi nodes, allocate the registers, solve the constraints — by hand, then check.

Optimize four instructions away by handbeginnerOptimize

The program is x = 2 * 3; y = x + 0; if false: expensive(); return y, written in AtlasLang with print(999) standing in for the expensive call and print(y) for the return. It is a real example in this build: open /compilers/passes, select "Constant folding", and you can toggle each pass and watch the IR change. Do it on paper first.

1let x = 2 * 3;
2let y = x + 0;
3if (false) { print(999); }
4print(y);
5
Your task

Write out the unoptimized three-address IR, then apply, in order, constant folding, the additive identity, constant propagation, branch simplification, unreachable-block elimination and dead-code elimination. Produce the final IR — blocks, labels and all — and state, for each pass, the precondition that made it legal on THIS program. Then say how many passes over the whole pipeline are needed before nothing changes.

Work through it
  1. Lower to three-address code with named slots. You should get seven instructions across three blocks: the two arithmetic instructions with their stores, a branch on the literal false, a then-block containing print 999, and a join block that loads y and prints it.
  2. Promote the slots to SSA. store @x followed by load @x collapses, so %0 = int 2 * 3 and %2 = int %0 + 0 remain with no memory traffic. There is no phi: nothing is assigned on two paths.
  3. Constant folding: %0 = int 2 * 3 becomes the literal 6. Legal because both operands are literals and integer multiplication of 2 and 3 cannot trap. Note what would stop you if this were 1 / 0.
  4. Additive identity: %2 = int %0 + 0 becomes a copy of %0. Legal because x + 0 = x for every value of AtlasLang's int. Write down why you could not do this for an IEEE-754 float, and what negative zero has to do with it.
  5. Constant propagation: the single definition of %2 is now the literal 6, so every use of %2 becomes 6. SSA is what makes "the single definition" a phrase you are allowed to use without an analysis.
  6. Branch simplification: branch false ? b1 : b2 becomes jump b2. Now b1 has no predecessors, so unreachable-block elimination deletes it and the print 999 inside it. Say precisely why deleting print 999 here is legal when deleting a print is normally not.
  7. Dead-code elimination: anything with no remaining uses and no effects goes. Count what is left, and count how many times the pipeline has to run before a full pass makes no change.
Check your answer
What you should have
  • The unoptimized IR is 7 instructions. The optimized IR is 3, and the pipeline reaches a fixed point after 2 full iterations.
  • Each of the six passes reports exactly one change: constant-folding 1, strength-reduction 1, constant-propagation 1, branch-simplification 1, unreachable-block-elimination 1, dead-code-elimination 1.
  • The final IR is: fn main(): void { b0: ; entry jump b2 b2: ; if.join preds=b0 print 6 ret }
  • The program prints 6, before and after — which is the only acceptance criterion that matters. An optimization that changes the output is not an optimization.
  • b0 and b2 are still two blocks joined by a jump. Nothing in this pipeline merges a block into its single successor.
The trap

Writing the answer as one block containing print 6; ret. It is the tidy answer, it is what the program means, and it is not what this pipeline produces: there is no block-merging pass, so the jump from b0 to b2 survives. The second half of the trap is the explanation people give for print 999 disappearing — "dead-code elimination removed it because its value is unused". print has no value and DCE may never remove it; it disappeared because its block became unreachable, which is a completely different licence. Get that wrong and you will confidently delete an effectful call on a live path.

Constant Folding →Strength Reduction and Algebraic Identities →Constant Propagation →Dead Code Elimination →Optimization Legality →The As-If Rule →Observable Behavior →Pass Pipelines →Phase Ordering →Three-Address Code →Static Single Assignment →AtlasLang: Eight Passes and Two Guards →
Insert the phi nodes, then take them out againintermediateSSA

A function assigns to one variable on both arms of a conditional and reads it after the merge. Converting it to SSA is the standard exercise; the part people skip is what happens when you leave SSA again, which is where the copies come from.

1fn classify(n: int): int {
2  let x = 0;
3  if (n > 3) { x = 1; } else { x = 2; }
4  let y = x + n;
5  return y;
6}
7print(classify(9));
8
Your task

Draw the CFG with four blocks. Compute the dominator tree and the dominance frontier of each block. Place phi nodes using the frontier, rename every definition and use, and state how many phis the function needs. Then convert back out of SSA and say exactly which blocks receive copies and how many.

Work through it
  1. Build the CFG: b0 (entry, evaluates the condition and branches), b1 (then), b2 (else), b3 (join). Edges: b0->b1, b0->b2, b1->b3, b2->b3.
  2. Immediate dominators: idom(b1) = idom(b2) = idom(b3) = b0. b3 is dominated by b0 and by neither arm, which is the fact the frontier is about to encode.
  3. Dominance frontier: DF(b1) = DF(b2) = {b3}; DF(b0) = {}. A block is in the frontier of b when b dominates a predecessor of it but not the block itself.
  4. Place phis by iterated frontier over the blocks that define each variable. x is defined in b0, b1 and b2, so a phi for x is needed in b3. n is defined once, in b0, and b0 dominates every use, so no phi. y is defined once. Count: one phi.
  5. Rename. The initial x = 0 in b0 is dead once the phi exists, because b3's value comes from b1 or b2 and no other path reaches b3. Write the phi as %7 = phi x [1 from b1, 2 from b2] and check that every source is listed against the correct predecessor, in the same order as b3's predecessor list.
  6. Now go the other way. Replace the phi with a copy on each incoming edge, placed at the end of the corresponding predecessor. Ask, before you do it, whether either edge is critical — a source with several successors feeding a target with several predecessors — because if one is, the copy has nowhere legal to go until you split it.
  7. Count the copies and check them against the phi: one copy per phi source, so two.
Check your answer
What you should have
  • Exactly one phi, in b3, with two sources: %7 = phi x [1 from b1, 2 from b2].
  • The store of 0 into x in b0 does not survive SSA construction. Nothing reads it.
  • The addition after the merge becomes %5 = int %7 + %0, where %0 is the parameter — the parameter needs no phi because its single definition dominates every use.
  • Leaving SSA inserts 2 copies: %7 = copy 1 at the end of b1 and %7 = copy 2 at the end of b2. The critical-edge list for this function is empty, because b1 and b2 each have exactly one successor.
  • The optimizer changes nothing here: the condition depends on a parameter, so branch simplification has nothing to fold and the phi survives to codegen. The function returns 10 for an argument of 9.
The trap

Placing a phi for n as well, on the reasoning that b3 has two predecessors and n is live across the merge. Liveness at the merge is not the criterion — a phi is needed only where two DIFFERENT definitions reach the same point, which is exactly what the iterated dominance frontier of the definition blocks computes. n has one definition that dominates b3, so every path carries the same value and a phi would be a copy of itself. The same mistake in reverse is placing phis for every live variable at every join, which is correct, enormously wasteful, and the reason minimal SSA is worth computing properly.

Phi Functions →Constructing SSA →Static Single Assignment →Leaving SSA →Why SSA Helps →The Dominance Frontier →Dominators →The Dominator Tree →The Control-Flow Graph →Basic Blocks →Liveness Analysis →
Six live values, three registersadvancedRegisters

Live ranges are given as half-open intervals over instruction numbers. The machine has three allocatable registers. Colour the interference graph, and where you cannot, choose what to spill and defend the choice — the choice is the exercise, not the colouring.

1value   live range     uses          note
2  a     [ 1 .. 14 ]    1, 6, 14      loop-carried
3  b     [ 2 ..  5 ]    2, 5
4  c     [ 3 .. 12 ]    3, 9, 12
5  d     [ 4 ..  7 ]    4, 7
6  e     [ 8 .. 13 ]    8, 13
7  f     [10 .. 11 ]    10, 11        inside the loop body
8 
9Instructions 6..11 are a loop body executed 1000 times per call.
10Registers: r0, r1, r2.  A spill costs one store at the definition and
11one load before each use.
12
Your task

Build the interference graph from the ranges. Try to 3-colour it with the simplify-and-select algorithm: repeatedly remove a node of degree less than 3, push it on a stack, and colour on the way back. When you get stuck, pick a spill candidate, justify it with a cost model, and finish the allocation. Report the assignment, the spilled value, and the dynamic cost of the spill.

Work through it
  1. Two values interfere when their ranges overlap. Write the edges: a-b, a-c, a-d, a-e, a-f, c-d, c-e, c-f, e-f, b-c, b-d. Check each one against the intervals rather than against your memory of the picture.
  2. Compute degrees. a has degree 5, c has degree 5, and everything else is 2 or 3. With three registers available, any node of degree less than 3 is trivially colourable and can be removed.
  3. Simplify: remove b (degree 3? recount after each removal — degrees change as neighbours leave). Keep removing until either the graph is empty, in which case colouring succeeds, or every remaining node has degree 3 or more, in which case you must spill.
  4. When you get stuck, rank the candidates by a cost model, not by convenience. The standard one is (spill cost) / (degree), where spill cost is the sum of use frequencies weighted by loop depth — a use inside a body executed 1000 times counts 1000, not 1.
  5. Apply it: a has high degree but a use at instruction 6, inside the loop. f is entirely inside the loop. c has high degree and only one use in the loop range. Compute the ratio for each and pick the largest degree per unit of cost.
  6. Spill your choice, rewrite the code with a store at the definition and a load before each use, and note that each load creates a new tiny live range that must itself be coloured. Re-run simplify on the rewritten graph.
  7. Report: which physical register each surviving value gets, what was spilled, and how many dynamic memory accesses the spill costs per call.
Check your answer
What you should have
  • The graph is not 3-colourable as given: a, c, e and f form a subgraph in which a, c and e are mutually interfering and f interferes with all three, so four values are simultaneously live at instruction 10.
  • The right spill is c. Its live range is long, its degree is high, and only one of its three uses (instruction 9) falls inside the loop, so its cost-per-degree is the lowest of the high-degree candidates. Spilling a is worse: it is used at 6, inside the loop, and reloading it there costs 1000 loads per call.
  • After spilling c, one valid assignment is a=r0, b=r1, d=r2, e=r1, f=r2, with c living in a stack slot and being reloaded into whichever register is free at 9 and 12.
  • The spill costs one store plus three loads statically. Dynamically it costs 1 store, 1000 loads for the use at instruction 9 inside the loop, and 1 load for the use at 12.
  • Spilling f colours the graph too and is the wrong answer: f lives entirely inside the loop, so every one of its accesses is multiplied by 1000. It is the cheapest node to spill by static count and the most expensive by dynamic count.
The trap

Choosing the spill by live-range length alone — "spill the longest range, it interferes with the most things". Length correlates with degree and says nothing about cost, and the two diverge exactly where it matters: a long range with all its uses outside loops is nearly free to spill, and a short range inside a hot loop is ruinous. The second half of the trap is forgetting that a spill is not free of register pressure: every reload needs a register at the point of use, so spilling one value does not simply remove a node from the graph, it replaces it with several short ones.

Register Allocation →Live Ranges →The Interference Graph →Graph Colouring Allocation →Spilling →Linear Scan Allocation →Coalescing and Rematerialization →Liveness Analysis →Natural Loops →Profile-Guided Optimization →
Two ambiguities, two different fixesintermediateGrammar

The grammar below is ambiguous in two independent ways, and the two need different repairs. One is fixed by stratifying the grammar; the other cannot be fixed by stratification at all and needs either a rule outside the grammar or a change to the language.

1expr  ::= expr "+" expr
2        | expr "*" expr
3        | expr "^" expr
4        | NUMBER
5        | IDENT
6 
7stmt  ::= "if" expr "then" stmt
8        | "if" expr "then" stmt "else" stmt
9        | IDENT "=" expr ";"
10        | "{" stmt* "}"
11
Your task

For each ambiguity: give one input with two distinct parse trees, draw both, and say what each one means. Then rewrite the grammar so that * binds tighter than +, ^ binds tighter than * and associates to the RIGHT while the other two associate to the left. Finally, deal with the second ambiguity and say why the same technique does not work on it.

Work through it
  1. Find the first ambiguity by looking for a nonterminal that appears on both sides of its own production with no ordering between the alternatives. a + b * c has two leftmost derivations; write both trees and evaluate each with a=1, b=2, c=3 so the difference is a number, not a shape.
  2. Stratify. Introduce one nonterminal per precedence level, lowest binding at the top: expr for +, term for *, power for ^, factor for atoms and parentheses. Each level refers to the next tighter one.
  3. Encode associativity by which side recurses. expr ::= expr "+" term | term is left-associative; power ::= factor "^" power | factor is right-associative. Check 2 ^ 3 ^ 2 gives 512 and not 64, and 8 - 3 - 2 gives 3 and not 7.
  4. Note what you have just done to the parser: expr ::= expr "+" term is left-recursive, which a recursive-descent parser cannot use directly. Either transform it to iteration — parse a term, then loop while the next token is + — or use an LR parser, which handles left recursion natively. Say which you would choose and why.
  5. Now the second ambiguity: if a then if b then x = 1; else y = 2; — which if owns the else? Write both trees and describe the two behaviors when a is true and b is false.
  6. Try to stratify it. You will find you can write a grammar that forces the else to attach to the nearest if (matched and unmatched statement nonterminals), but you cannot write one that leaves the choice to the programmer, because the ambiguity is in the language, not in the notation.
  7. List the three real fixes and name a language that took each: attach to the nearest if by rule outside the grammar; require braces so the question cannot be asked; require an explicit terminator such as end or fi.
Check your answer
What you should have
  • The stratified grammar is: expr ::= expr "+" term | term ; term ::= term "*" power | power ; power ::= factor "^" power | factor ; factor ::= NUMBER | IDENT | "(" expr ")".
  • 1 + 2 * 3 has exactly one tree in the new grammar and evaluates to 7. 2 ^ 3 ^ 2 is 512, because ^ recurses on the right.
  • The matched/unmatched formulation for the dangling else is: stmt ::= matched | unmatched ; matched ::= "if" expr "then" matched "else" matched | other ; unmatched ::= "if" expr "then" stmt | "if" expr "then" matched "else" unmatched.
  • That formulation removes the ambiguity by legislating nearest-if attachment. It does not give the programmer a way to attach the else to the outer if — only braces or a terminator can do that.
  • A parser generator reports the first ambiguity as shift/reduce conflicts on +, * and ^, and the second as a single shift/reduce conflict on else. Both default to shift, which happens to produce the conventional answer for the dangling else and the WRONG answer for left-associative operators.
The trap

Fixing the operators with a precedence declaration in the parser generator (%left "+", %right "^") and calling the grammar unambiguous. The generator now produces the right parser, and the grammar in the language reference is still ambiguous — which means the reference no longer defines the language, the generator directives do. That is a real cost: the specification and the implementation have separated, and the next person to write a second parser, a formatter or a syntax highlighter will read the reference and get it wrong. Precedence declarations are a conflict-resolution convenience, not a disambiguation of the grammar.

Ambiguous Grammars →Operator Precedence →Associativity →Context-Free Grammars →Productions & Derivations →BNF & EBNF →Left Recursion →Shift and Reduce, Step by Step →LR Parsing →Parser Generators →Recursive Descent →
Solve the constraints, including the one that must failadvancedTypes

Hindley-Milner inference in three moves: walk the term generating constraints, solve them by unification, then generalize. The last of the three programs below has no type, and knowing exactly which step rejects it is the point of the exercise.

1let twice = fn (f, x) => f(f(x));
2 
3let apply  = fn (g, y) => g(y);
4let result = apply(fn (n) => n + 1, 41);
5 
6let omega  = fn (s) => s(s);
7
Your task

For each of the three definitions, assign fresh type variables to every binder and every application, write down the constraint set, and solve it by unification, showing the substitution after each step. Give the final generalized type scheme where one exists. For omega, run the unifier until it fails and name the check that rejects it.

Work through it
  1. Assign variables: for twice, let f : t1, x : t2, and let the two applications produce t3 and t4. The body is f(f(x)), so the inner application constrains t1 = t2 -> t3 and the outer constrains t1 = t3 -> t4.
  2. Unify the two constraints on t1. From t2 -> t3 = t3 -> t4 you get t2 = t3 and t3 = t4, so all three collapse to one variable. Apply the substitution everywhere before continuing — a solver that forgets to apply a substitution to the remaining constraints produces answers that are locally right and globally inconsistent.
  3. Read off the type of twice, then generalize over the variables that are free in the type and not free in the environment. That last clause is the whole of let-polymorphism, and it is why a lambda-bound variable is not generalized.
  4. For apply, generate the constraints for g(y) and then for the call site. The argument fn (n) => n + 1 gives n : int from the +, so the instantiation of apply's scheme at this call site substitutes int for both variables. Show the instantiation as a separate step from the unification; conflating them is where inference bugs live.
  5. For omega, let s : t1. The body applies s to s, so the application requires t1 = t1 -> t2. Attempt to unify t1 with t1 -> t2.
  6. The unifier binds a variable to a term. Before doing so it must check that the variable does not occur inside that term — here t1 occurs on the right of t1 -> t2 — and reject if it does. Say what would happen without that check.
  7. Write down the error a real compiler produces for this program, and note that the message is almost always about an infinite type rather than about the check by name.
Check your answer
What you should have
  • twice : forall a. (a -> a, a) -> a. The function argument must have the same domain and codomain, which falls out of unification rather than being assumed.
  • apply : forall a b. (a -> b, a) -> b, instantiated at this call site to (int -> int, int) -> int, so result : int and evaluates to 42.
  • omega has no type. Unification reaches t1 = t1 -> t2 and the occurs check fails.
  • Without the occurs check, unification would build the infinite type t1 = (((... -> t2) -> t2) -> t2) and either loop forever or, with a cyclic representation, succeed and accept a program the runtime cannot execute. The check is what makes unification terminate.
  • Real messages: OCaml says "This expression has type 'a -> 'b but an expression was expected of type 'a. The type variable 'a occurs inside 'a -> 'b." Haskell says "Occurs check: cannot construct the infinite type". Both are naming this exact step.
The trap

Concluding that twice : forall a b. (a -> b, a) -> b because the two applications "could" have different types. They cannot: the result of the inner application is fed to the same f, so its output type must equal its input type, and unification discovers that whether or not you expected it. The other common trap is generalizing at the wrong moment — generalizing a lambda-bound parameter gives you a type that is more general than the term, and the program then type-checks and goes wrong at run time. Generalization happens at let, over variables not free in the environment, and nowhere else.

Hindley–Milner: Inference Without a Single Annotation →Unification, and Why `T = List<T>` Must Fail →Type Inference: Leaving the Type Off →Parametric Polymorphism and the Theorems You Get Free →Typing Rules: Reading the Notation With the Line Through It →The Type Environment: What Γ Is, and Where the Compiler Keeps It →Type Checking: Is This Operation Defined for These Operands? →Type Soundness →What a Type System Actually Proves →
Design a configuration language and defend every choiceexpertDSL

A deployment tool needs configuration files written by service teams. Today they are YAML with a templating layer bolted on top, and the failures are the familiar ones: whitespace errors, a value that is a boolean when it should be a string, a template that produces syntactically valid nonsense, and no way to tell which of forty files set a field. Design the replacement.

1Requirements, in the order the team ranked them:
2  1. A wrong config must fail at validation time, never at deploy time.
3  2. Common values must be shareable across services without copy-paste.
4  3. A non-specialist must be able to read a file and predict what it does.
5  4. It must be diffable and reviewable in a pull request.
6  5. Editor support: completion and inline errors, within one engineer-quarter.
7 
8Current scale: 340 files, 40 teams, 6 environments, ~200 lines each.
9
Your task

Produce a design covering six decisions: surface syntax, grammar, type system, error strategy, execution model, and tooling. For each, state the choice, the alternative you rejected, and what your choice costs. Then answer the question that comes before all of them — whether a new language is warranted at all, given that the honest answer is often no.

Work through it
  1. Start with the null hypothesis: a library, a schema over the existing format, or a subset of an existing language. Say what each would fail to deliver against the five requirements. If none of them fails, the exercise ends here and that is a legitimate outcome.
  2. Surface syntax. Choose, and justify against requirement 3: significant whitespace is compact and produces a class of error your users already hate; braces are noisier and unambiguous; an S-expression syntax is trivial to parse and unfamiliar. Say which failure you are choosing to accept.
  3. Grammar. Write it in EBNF, keep it unambiguous, and check it for the two classic hazards — a nonterminal on both sides of its own production without stratification, and any construct that needs unbounded lookahead. Aim for something an LL(1) recursive-descent parser can handle, and say what you gave up to get there.
  4. Type system. Decide what is checkable before deployment: field names against a schema, value types, enum membership, cross-field constraints, references to other services. Decide whether types are declared in the config or in a separate schema, and whether unknown fields are an error. Requirement 1 is a type-system requirement in disguise.
  5. Error strategy. Decide whether the parser stops at the first error, and what a diagnostic contains: span, expected set, a suggestion. Decide what happens to a file with three errors and whether validation continues past a parse failure. Write the exact text of one diagnostic; a language is judged on its errors more than on its syntax.
  6. Execution model. Sharing values across files (requirement 2) is where configuration languages become programming languages. Choose: plain includes, includes with override, named functions, or full evaluation. State the halting question honestly — if the language can loop, a config can hang the deploy tool — and say what you forbid to prevent it.
  7. Tooling. One engineer-quarter buys roughly: a parser with spans, a validator, a formatter, and a language server exposing diagnostics and completion. It does not buy a debugger, a package manager or a REPL. Decide what you are not building and say how users will live without it.
  8. Finally, write the migration: 340 files cannot move at once. Decide whether the new tool reads both formats, whether there is a mechanical converter, and how long the two coexist.
Check your answer
What you should have
  • The design says no to at least one requirement, explicitly. A design that satisfies all five at no cost has not been thought through — most commonly, requirement 2 and requirement 3 are in direct tension, because every sharing mechanism is an indirection a reader has to follow.
  • The grammar is written down and is unambiguous. If it uses a parser generator, the conflict count is stated and is zero.
  • The execution model has an explicit answer to termination. "No user-defined recursion and no unbounded loops, so evaluation is structurally terminating" is an answer; "we would not write a config that loops" is not.
  • The tooling budget is spent on the language server rather than on language features, or the design says why not. Requirement 5 is the one most often written into a plan and least often delivered.
  • The migration story exists and has a date on which the old format stops being read. Two formats forever is the actual outcome of most of these projects, and it costs more than either format alone.
The trap

Making the language Turing-complete "so it can express anything". It is the choice that feels generous and it defeats requirements 1, 3 and 5 simultaneously: you can no longer validate a config without running it, a reader can no longer predict what a file does by reading it, and completion becomes a whole-program analysis rather than a lookup. Every configuration language that grew conditionals and loops arrived here, and the ones that are pleasant to use — dhall's guaranteed termination, starlark's absence of unbounded recursion — bought that by deciding early what they would refuse to express.

Should I Build a DSL? →Domain-Specific Languages →Internal versus External DSLs →Configuration Languages →Implementing a DSL →The Tooling Cost of a DSL →The Questions a Language Definition Must Answer →Who Is the Language For? →The Trade Nobody Escapes →Syntax versus Semantics →Diagnostic Quality →The Language Server →
The password buffer that was never clearedexpertCorrectness

A function reads a passphrase, uses it, and wipes the buffer before returning. A security review of the release binary finds the passphrase still in stack memory after the function returns. The compiler is behaving correctly and the code is wrong — work out why, without appealing to a compiler bug.

1int authenticate(const char *user) {
2    char pass[64];
3    read_passphrase(pass, sizeof pass);
4    int ok = verify(user, pass);
5    memset(pass, 0, sizeof pass);   /* wipe the secret */
6    return ok;
7}
8
Your task

Explain, as a sequence of compiler decisions, why the memset is absent from the optimized output. State the exact language rule the compiler is relying on, name the transformation, and give three fixes ranked by how much they rely on the compiler cooperating. Then generalise: state the property this code assumed and the language does not guarantee.

Work through it
  1. Ask what the abstract machine can observe. Write down every effect of the function that a conforming program could detect: the return value, the calls to read_passphrase and verify, and anything they do. Note whether the contents of pass after the function returns is on that list.
  2. It is not. pass has automatic storage duration and its lifetime ends when the function returns, so the abstract machine cannot observe its contents afterwards — reading it would be undefined behavior, which means no defined program can tell whether the write happened.
  3. Name the transformation: dead store elimination. Its legality condition is that the stored value cannot be read before it is overwritten or its storage ends. Check that condition against this code and confirm the compiler is right.
  4. Note what makes this dangerous rather than merely surprising: the attacker's read of that stack memory is not a defined program operation, so the compiler is not obliged to preserve anything about it. Your threat model includes an observer the language's model does not.
  5. Fix one: explicit_bzero, memset_s or SecureZeroMemory — functions the implementation promises not to elide. This works because the guarantee is in the library contract, not because the code looks different.
  6. Fix two: make the store observable. Declaring the buffer volatile, or writing through a volatile pointer, moves the accesses into the set of things the abstract machine must perform. Say what this costs: volatile also blocks every other optimization on that object and is easy to apply to the wrong pointer.
  7. Fix three: a compiler barrier — an empty inline asm with a memory clobber, or passing the pointer to an opaque function the compiler cannot see into. Say why this is the most fragile: it relies on the compiler's current inability to prove something, and link-time optimization can remove that inability.
  8. Generalise. State the assumption in one sentence, in the form "this code assumed the compiler would preserve ___, and the language only guarantees ___".
Check your answer
What you should have
  • The transformation is dead store elimination, and it is legal here: the object's lifetime ends at the return, so no defined program can read the value the memset wrote.
  • This is not a miscompilation. The program's defined observable behavior is unchanged; what changed is a property the source relied on and the language never promised.
  • Ranked by reliance on cooperation: explicit_bzero/memset_s (a contract), volatile (a rule of the abstract machine), inline-asm barrier (a bet on the optimizer's current reach). Only the first two are guarantees.
  • The same reasoning applies to any "clear the secret" idiom — zeroing a key, a token or a decrypted plaintext — and to any code that assumes an unobservable write happens.
  • Compiler Explorer with -O2 shows the memset call absent from the emitted function; with explicit_bzero it remains. That is a two-minute experiment and it is more convincing than any argument.
The trap

Concluding that the compiler has a security bug and filing it. It has not: it applied a transformation whose precondition holds, and the precondition holds because the language defines observability in terms of the abstract machine rather than in terms of memory. The tidy wrong fix follows from the tidy wrong diagnosis — turning off optimization for the file, which "works" until someone re-enables it, hides the reasoning, and leaves every other secret-wiping site in the codebase exposed.

Compilers and Security →Undefined Behavior →How Undefined Behavior Becomes Faster Code →Observable Behavior →The As-If Rule →Optimization Legality →Dead Code Elimination →Miscompilation →Semantics Decide, Not Cleverness →Link-Time Optimization →
The check the compiler was entitled to deleteadvancedLegality

A driver function dereferences a pointer, then checks it for null. The check disappears at -O2 and the function faults on a null argument instead of returning an error. This is the shape of CVE-2009-1897 in the Linux kernel, and the reasoning is worth reconstructing exactly.

1static void handle(struct req *r) {
2    unsigned int flags = r->flags;      /* dereference */
3 
4    if (r == NULL)                      /* check, after the fact */
5        return;
6 
7    if (flags & F_URGENT)
8        dispatch_now(r);
9    else
10        queue(r);
11}
12
Your task

Derive, step by step, the inference that lets the optimizer delete the null check. Say which pass performs the deletion and which analysis supplies the fact it uses. Then state what the compiler is NOT claiming, because the common objection misstates it. Finally, give the fix and the two diagnostics that would have caught this at build time.

Work through it
  1. Write down what r->flags means when r is null: it is undefined behavior. The standard does not say it traps, it says the behavior of the whole program is undefined, which places no obligation on the implementation at all.
  2. Turn that into an assumption. Because a program with defined behavior cannot reach the dereference with r == NULL, the compiler may assume r != NULL at every point dominated by the dereference. This is the licence-to-assume reading of undefined behavior, and it is the only reading that explains the code that comes out.
  3. Propagate the fact forward. The value-range or predicate analysis records r != NULL after the load; the branch condition r == NULL is then provably false at that point.
  4. Apply the transformation: branch simplification folds the always-false condition, and the unreachable return is deleted. Name both passes; "the optimizer removed it" is not a diagnosis you can act on.
  5. State what the compiler is not claiming. It is not claiming r is never null at run time. It is claiming that IF r is null, the program has already invoked undefined behavior one line earlier, so no behavior at all is required afterwards.
  6. Fix it by ordering: check first, then dereference. Note that this is not a workaround for a compiler quirk — it is the only order in which the code ever meant what it looked like it meant.
  7. Name the build-time diagnostics: -Wnull-dereference on GCC and Clang flags exactly this pattern, and -fno-delete-null-pointer-checks disables the inference for codebases that cannot be audited at once. Say why the second is a mitigation and not a fix.
Check your answer
What you should have
  • The reasoning chain is: dereference implies r != NULL may be assumed; the assumption makes the check's condition constant-false; branch simplification folds it; unreachable-code elimination removes the return.
  • The passes are conditional constant propagation (or value-range propagation) supplying the fact, and branch simplification plus dead-code elimination applying it.
  • The compiler makes no claim about run-time values. Every statement it makes is conditional on the program having defined behavior, which is the premise the source violated.
  • The fix is to move the null test above the dereference. No compiler flag is needed once the order is right.
  • -fno-delete-null-pointer-checks restores the check on this compiler at this version, and does nothing about the undefined behavior itself, which other passes may still exploit. The kernel adopted it as a fleet-wide mitigation while the individual sites were fixed.
The trap

Arguing that "the compiler should just emit the check — it costs one instruction". It is the reasonable-sounding position and it misidentifies what happened: the compiler did not weigh the cost of a check, it concluded the check was unreachable under an assumption the source handed it. The same inference that deletes this check is the one that removes redundant bounds checks and hoists loads out of loops, and it cannot be selectively disabled by good intentions. The other trap is treating this as a null-pointer problem specifically; the mechanism is general to every undefined operation, and signed overflow, invalid shifts and strict aliasing all produce identically surprising deletions.

Undefined Behavior →How Undefined Behavior Becomes Faster Code →Optimization Legality →The As-If Rule →Observable Behavior →Semantics Decide, Not Cleverness →Constant Propagation →Dead Code Elimination →Control-Flow Analysis →Compilers and Security →Optimization Levels →
Desugar `for..in` to the core languagebeginnerLowering

A for..in loop is not a primitive. It is a while loop over an iterator protocol, plus scoping rules that are easy to state and easy to get wrong. Write the desugaring, then find the two places where the obvious version is subtly wrong.

1for item in collection {
2    if item.skip { continue; }
3    total = total + item.value;
4}
5 
6// The core language has: let, assignment, while, if, break, continue,
7// function calls, and a `try/finally` construct. It has no for..in.
8
Your task

Write the desugared form using only core constructs. Then answer four questions the naive desugaring gets wrong: when is collection evaluated, is item one binding or one per iteration, what does continue have to do before jumping, and what happens if the body throws. Give the corrected desugaring.

Work through it
  1. Start with the protocol. Assume iter(x) returns an iterator and next(it) returns either a value or a sentinel meaning exhausted. Write the loop as: obtain the iterator once, then while on the result of next.
  2. Evaluate the subject exactly once. for item in f() must call f once, not once per iteration, so the iterator expression is bound to a fresh temporary before the loop.
  3. Decide the binding. Write both versions: one where item is a single variable assigned each iteration, and one where each iteration creates a fresh binding. Then write a closure inside the loop body that captures item and say what each version prints when the closures are called after the loop. This is the difference that made JavaScript change var to let semantics in for loops.
  4. Handle continue. In the desugared while, continue jumps to the condition — which is the call to next — so it must not skip the advance. If your desugaring puts the advance at the bottom of the body, continue becomes an infinite loop. Say which of the two placements you chose and why.
  5. Handle early exit. If the body throws or breaks, an iterator that holds a resource must still be closed, so the loop body belongs inside a try/finally that closes the iterator. Python spells this in the language; a hand desugaring that omits it leaks.
  6. Write the final desugaring with all four corrections and check it against the original for a collection of length 0, 1 and 3, with and without a continue on the first element.
Check your answer
What you should have
  • The subject is evaluated once, into a temporary that is not visible to the body.
  • The advance is part of the loop condition (or the first thing in the body), so continue cannot skip it. The version with the advance at the bottom of the body is an infinite loop on continue and is the single most common error here.
  • Per-iteration binding: a closure created in iteration k captures the value from iteration k. With a single shared binding every closure sees the final value, which is the classic loop-capture bug.
  • The iterator is closed on every exit path — normal exhaustion, break, return and an exception — which requires the body to be inside a try/finally.
  • Behavior for an empty collection: the body never runs and the iterator is still closed. That is the case a hand-written desugaring most often gets wrong by placing the close inside the loop.
The trap

The tidy desugaring that reads let it = iter(collection); while (hasNext(it)) { let item = next(it); ...body... }. It looks correct and it changes behavior in two ways: hasNext plus next is a two-call protocol where the language specifies one, so an iterator that can only be advanced (a stream, a generator, a network cursor) cannot implement it; and for iterators where hasNext is not idempotent, the loop consumes elements it never yields. Desugaring is a claim about equivalence, and an equivalence that holds for arrays and fails for generators is not one.

Desugaring →Syntactic Sugar →Closures →Closure Conversion →Lowering →Changing the Tree →Exception Handling →Stack Unwinding →Lexical Scope →Shadowing →
Lower an async function to a state machineexpertLowering

An async function is not a thread and not a callback chain. It is a state machine whose states are the suspension points, and whose locals live in a heap object rather than on the stack — because the stack frame is gone while it is suspended. Perform the transformation by hand.

1async function loadProfile(id) {
2  const user = await fetchUser(id);
3  let posts = [];
4  if (user.active) {
5    posts = await fetchPosts(user.id);
6  }
7  const summary = summarize(user, posts);
8  return summary;
9}
10
Your task

Identify the suspension points and number the states. Determine which locals must be stored in the state object and which may stay in registers. Write the resume function as a switch over the state, including the entry state and the completion state. Then answer three questions: what happens to the if when it straddles no suspension, where the exception handling goes, and why the state object must be heap-allocated.

Work through it
  1. Number the states by cutting the function at each await. State 0 is entry, state 1 resumes after fetchUser, state 2 resumes after fetchPosts, and a final state marks completion. Two awaits give three live states plus done.
  2. Classify each local by whether its live range crosses a suspension point. id is used after the first await, so it must be stored. user is defined before the second await and used after it, so it must be stored. posts is written before the second await and read after it, so it must be stored. summary is created and consumed with no await between, so it need not be.
  3. This classification is a liveness analysis across suspension points, and it is exactly the analysis that decides an async frame's size. Write down the state object: { state, id, user, posts, promise }.
  4. Write the resume function as switch (frame.state), with each case picking up where the await left off. Each await becomes: start the operation, store the state number, register this resume function as the continuation, and return. The return is what releases the stack frame.
  5. Handle the branch. The if does not straddle a suspension on the false path, so the false path goes straight to the code after the join; on the true path it enters state 2. Draw the resulting control flow and note that the state machine is a CFG with the suspension points as extra entry edges.
  6. Handle failure. A rejected promise must resume the state machine in a way that throws at the await point, so the switch needs an error entry as well as a value entry, and any try/finally in the source becomes explicit bookkeeping in the state object. Say what would go wrong if a finally block itself contained an await.
  7. Explain the heap allocation. The state object outlives the stack frame by construction — the frame is gone between suspension and resumption — so it cannot live on the stack. Name the optimization that can undo this when the compiler can prove the async call never actually suspends or never escapes.
Check your answer
What you should have
  • Three resume states plus a completed state. Two awaits, three entry points into the body.
  • Stored in the frame: id, user, posts. Not stored: summary, and any temporary whose live range does not cross an await.
  • Each await compiles to: begin the operation, record the next state, install the continuation, return to the caller. Nothing on the machine stack survives that return.
  • The rejected path re-enters the same switch with an error flag, so a try in the source becomes a state-indexed handler rather than a stack-unwinding target. An await inside a finally requires the finally block to be its own set of states, which is why some early implementations forbade it.
  • The frame must be heap-allocated because its lifetime is not the stack frame's. Escape analysis can stack-allocate or elide it when the compiler proves the state machine never suspends or never escapes, which is what makes an already-resolved await cheap.
The trap

Storing every local in the state object because it is simpler. It is correct and it is a real cost — the frame is allocated on every call, its size is the sum of everything you stored, and async-heavy code is measured in exactly this. The opposite trap is worse: keeping a local in a register because the code between two awaits looks straight-line, when a value defined before an await and used after it must be in the frame no matter how it looks. The criterion is liveness across the suspension point, and neither intuition nor the source layout substitutes for computing it.

Lowering Async and Await →Lowering Coroutines →Lowering →Closures →Closure Conversion →Liveness Analysis →The Control-Flow Graph →Escape Analysis →Exception Handling →Stack Unwinding →Desugaring →
Compile a match expression to a decision treeadvancedLowering

A match expression is not a chain of if-else tests, or it should not be. Compiling it well means building a decision tree that tests each scrutinee position at most once, and proving exhaustiveness while you are at it — the same algorithm answers both questions.

1enum Shape {
2    Circle(f64),
3    Rect(f64, f64),
4    Point,
5}
6 
7match (a, b) {
8    (Shape::Point,      _)                 => 0,
9    (Shape::Circle(r),  Shape::Point)      => 1,
10    (Shape::Circle(r),  Shape::Circle(s))  => 2,
11    (Shape::Rect(w, h), Shape::Point)      => 3,
12    (_,                 Shape::Rect(_, _)) => 4,
13}
14
Your task

Build the pattern matrix, choose a column to test, and construct the decision tree by specialising the matrix on each constructor and computing the default matrix for the rest. Report the tree, the number of tag tests on the worst path, and whether the match is exhaustive. If it is not, produce a witness — a concrete pair of values that no arm covers.

Work through it
  1. Write the pattern matrix: five rows, two columns, each cell a constructor pattern or a wildcard. Keep the arm bodies as row labels; the algorithm never looks at them.
  2. Choose a column. A good heuristic prefers a column with no wildcards, since a wildcard in a column means every branch of a test on it must also carry that row. Column 0 has one wildcard (the last row); column 1 has one (the first row). Either works here — pick column 0 and note what changes if you pick column 1.
  3. Specialise. For each constructor of Shape, build the submatrix of rows whose column-0 pattern is that constructor or a wildcard, with the constructor's arguments spliced in as new columns. Do this for Point, Circle and Rect.
  4. Recurse on each submatrix, choosing a column and specialising again, until a matrix has a row of all wildcards — that row's body is the leaf — or has no rows at all, which means this combination of constructors is unmatched.
  5. Compute the default matrix for column 0: the rows whose column-0 pattern is a wildcard, with that column removed. This is the branch taken when the tag matches no constructor listed, and here it is what makes the last row reachable from a Rect scrutinee.
  6. Check exhaustiveness with the same machinery: the match is exhaustive if and only if no path through the tree reaches an empty matrix. Enumerate the paths and find any that do.
  7. Count tag tests on the longest path and compare with the naive lowering — testing each arm in order, re-testing the same scrutinee position once per arm — for a case that falls through to the last arm.
Check your answer
What you should have
  • The match is NOT exhaustive. (Shape::Rect(w, h), Shape::Circle(s)) matches no arm: row 4 requires column 0 to be Point, row 5 requires column 1 to be Rect, and no other row admits a Rect paired with a Circle.
  • The witness the algorithm produces is exactly that pair, and a real compiler reports it in that form — rustc says "patterns (Rect(_, _), Circle(_)) not covered", which is this witness printed.
  • The decision tree tests the tag of a once, and then the tag of b once on the Circle and Rect branches only. Worst path: two tag tests. The Point branch tests once and is done, because row 1 has a wildcard in column 1.
  • The naive lowering tests up to five times against column 0 and up to four times against column 1 for a value that reaches the last arm, re-loading and re-testing the same tags.
  • Choosing column 1 first produces a different tree with the same worst-case depth here. Column choice affects tree size in general and is NP-hard to optimize, so real compilers use heuristics — prefer columns without wildcards, prefer small constructor sets.
The trap

Adding a final _ => 5 arm to silence the exhaustiveness error. It compiles, and it converts a compile-time proof into a run-time behavior: the next constructor added to Shape will silently fall into the catch-all instead of producing an error at every site that needs updating. Exhaustiveness checking is worth most precisely when the enum changes, and a wildcard arm on a closed enum is a decision to give that up. The other trap is assuming a wildcard row can be dropped from a specialised submatrix; it cannot — a wildcard matches every constructor, so it appears in every branch, which is why specialisation copies it rather than moving it.

Compiling Pattern Matching →Pattern Matching →Exhaustiveness Checking →Algebraic Data Types →Lowering →Desugaring →Union Types →The Control-Flow Graph →Type Checking: Is This Operation Defined for These Operands? →
Iterate liveness to a fixed point, by handintermediateData Flow

Liveness is the backward data-flow analysis every backend depends on, and iterating it by hand once is worth more than reading the equations three times. The loop is what makes it interesting: the fact you need at the top of the body depends on the fact at the bottom.

1b0:  a = 1
2     b = 2
3     jump b1
4 
5b1:  c = a + b
6     branch c > 0 ? b2 : b3
7 
8b2:  a = c + 1
9     d = a * 2
10     jump b1            ; back edge
11 
12b3:  e = b + c
13     print e
14     ret
15
Your task

Write use and def for each block. Then iterate the backward equations — out[B] is the union of in[S] over successors S, and in[B] is use[B] union (out[B] minus def[B]) — starting from empty sets, in reverse postorder, until nothing changes. Report the in and out sets per block, the number of iterations, and which value is dead.

Work through it
  1. Compute use and def per block, being careful about order within a block: a variable used before it is defined in the same block is in use; one defined before any use is in def only. In b2, a = c + 1 defines a and uses c; the next line uses the NEW a, so a is not in use[b2].
  2. Pick a traversal order. Liveness is a backward analysis, so reverse postorder on the reverse CFG — roughly, process blocks in reverse — converges fastest. Note the order you chose; it changes the iteration count and not the answer.
  3. Initialise every in and out to the empty set. Do the first sweep and record every set. Nothing about the back edge is known yet, so out[b2] will be empty on this pass and in[b1] will be incomplete.
  4. Do the second sweep. Now in[b1] from the first pass flows back through the b2 -> b1 edge into out[b2], which adds facts to in[b2], which flows into out[b1]. This is the loop-carried part, and it is why one sweep is never enough on a cyclic CFG.
  5. Keep sweeping until a full pass changes nothing. Record how many passes it took and confirm the sets only ever grew — the transfer functions are monotone and the lattice is finite, which is what guarantees termination.
  6. Read off the answer: a variable is dead at its definition if it is not in the out set of the instruction that defines it. Find the one in this program.
  7. Finally, state the maximum number of simultaneously live values and what that implies for register allocation on a three-register machine.
Check your answer
What you should have
  • use/def: b0 use {} def {a, b}; b1 use {a, b} def {c}; b2 use {c} def {a, d}; b3 use {b, c} def {e}.
  • Final sets: in[b0] = {}; out[b0] = {a, b}. in[b1] = {a, b}; out[b1] = {b, c}. in[b2] = {b, c}; out[b2] = {a, b}. in[b3] = {b, c}; out[b3] = {}.
  • d is dead: it is defined in b2 and appears in no out set, because nothing reads it. Dead-code elimination can remove d = a * 2 — and only because multiplication is pure and cannot trap.
  • Three sweeps in reverse postorder: one to propagate the straight-line facts, one to carry the back-edge facts, one to confirm nothing changed. Forward order takes more.
  • The maximum simultaneous liveness is three ({a, b, c} at the end of b1 and start of b2 once a is redefined), so this function fits in three registers with no spill.
The trap

Stopping after the first sweep because every set "looks right". On an acyclic CFG one backward sweep in the right order is enough, and that is exactly why the habit forms — but the back edge from b2 to b1 means out[b2] depends on in[b1], which depends on out[b1], which depends on in[b2]. One sweep reports b as dead in b2 and an allocator acting on that reuses its register inside the loop, corrupting the value on the second iteration. The fixed point is not a formality; it is the only thing that makes the answer true on a cyclic graph.

Liveness Analysis →The Data-Flow Framework →Iterating to a Fixed Point →Forward and Backward Analysis →Reaching Definitions →Dead Code Elimination →The Control-Flow Graph →Basic Blocks →Natural Loops →Live Ranges →Register Allocation →