ASTs & Intermediate Representations: Design, Lowering & SSA

ASTs & Intermediate Representations

A parser hands you a tree; everything after that is transforming trees into other trees, and eventually into something flat enough to execute. The abstract syntax tree models the program's structure with the syntax noise removed — no parentheses, no semicolons, no commas, just the nesting they implied. The intermediate representation is what you get after flattening that tree into a linear sequence of simple operations, and it's where essentially all optimization happens.

The distinction matters because trees and linear IR are good at different things. A tree is natural for type checking, name resolution, and anything that follows the shape the programmer wrote. Data flow analysis on a tree is miserable — you want to ask "what is the value of x at this point?", and answering that requires a representation where control flow is explicit and each value has one definition. That's what SSA form provides, and its adoption is one of the genuinely large ideas in compiler engineering.

Between the two sits lowering: a series of passes each replacing a high-level construct with a simpler one. A for loop becomes a while; a while becomes conditional branches; string interpolation becomes concatenation calls. Each pass is small, testable, and reduces the number of constructs the next stage has to know about.

TL;DR

An AST drops syntax noise and keeps structure. Parentheses vanish; nesting remains.
Design nodes as a sum type (enum, sealed class, tagged union) so exhaustive matching is checkable.
Every node carries a source span. Diagnostics, IDE features, and stack traces all depend on it.
Desugaring rewrites convenience constructs into a smaller core language — fewer cases downstream.
Lowering progressively flattens the tree toward linear IR.
Three-address code breaks expressions into single operations with explicit temporaries.
SSA form gives each variable exactly one assignment, with φ (phi) nodes at control-flow merges.
SSA makes data flow analysis nearly trivial — which is why LLVM, HotSpot, V8, and GCC all use it.

Quick Example

An AST as a sum type, a visitor over it, and a desugaring pass:

After that pass, no later stage needs to know for exists. Every desugaring you do shrinks the surface area of everything downstream — which is the entire argument for a small core language.

Core Concepts

AST vs. parse tree

A concrete syntax tree keeps every token including whitespace and comments, which formatters and refactoring tools need. An AST keeps only what affects meaning, which is what a compiler wants. Tools needing both (rust-analyzer, Roslyn) keep a lossless CST and project an AST from it.

Designing the node type

The sum-type point is the one that pays off repeatedly. When you add a node kind, a language with exhaustive matching tells you every pass that needs updating. Without it, you find out at runtime, in the pass you forgot.

Lowering

Each step reduces the number of distinct constructs. By the time you reach the control flow graph there are no loops, no conditionals, and no expressions — only basic blocks, simple instructions, and branches. That uniformity is what makes optimization tractable.

Three-address code

This is the classic linear IR shape. It's easy to generate from a tree with a post-order walk, easy to analyze, and close enough to machine instructions that code generation is mostly selection and register allocation.

SSA form

Static Single Assignment: every variable is assigned exactly once. Reassignment creates a new version.

The φ (phi) node is the only new concept: at a control-flow merge, it selects the value from whichever predecessor block was actually taken. It isn't a real instruction — it's resolved during register allocation, usually by inserting copies at the ends of predecessor blocks.

Why it's worth the trouble:

Every serious modern compiler uses it: LLVM, GCC (GIMPLE), HotSpot's C2, V8's TurboFan, and Go's SSA backend.

Control flow graphs

Loops and conditionals disappear into edges between blocks. Dominance relationships in this graph are what determine where φ nodes go, and loop detection for optimization is graph analysis on it. See Graph Algorithms.

Working With Trees

Visitor vs. pattern matching

The visitor pattern exists mostly to work around the absence of pattern matching. In a language that has it, an explicit Visitor interface adds ceremony for no benefit — though a walk helper that handles recursion is still useful so each pass only writes the cases it cares about.

Immutable vs. mutable trees

Immutable trees (each pass produces a new tree) are easier to reason about, trivially parallelizable, and make it possible to keep earlier stages for diagnostics. They cost allocations. Mutable trees are faster and make it easy to introduce bugs where one pass invalidates another's assumptions.

A common compromise is an arena with indices: nodes live in a Vec, children are u32 indices rather than pointers. This gives cache locality, cheap copying, trivial serialization, and no borrow-checker fights — which is why rust-analyzer, many game engines, and several production compilers use it.

Best Practices

Keep the core language small

Every construct you don't desugar is a construct every downstream pass must handle. A language with 60 surface forms and a 15-form core is far easier to work on than one where all 60 reach the code generator.

Preserve spans through every transformation

A desugared node should point at the original source, not at nothing. Users get errors about code they wrote, and a for loop that reports errors at a synthesized while is confusing and hard to debug.

Separate the typed AST from the untyped one

After type checking, produce a distinct tree type where the type is a required field rather than an Option. Downstream passes then can't accidentally read a type that was never computed, and the type system enforces pass ordering for you.

Make passes small and single-purpose

One pass per concern — resolve names, then check types, then desugar loops, then lower to IR. Small passes are testable in isolation, reorderable, and much easier to debug than a single traversal doing five things.

Provide a pretty-printer early

Being able to print any tree back as source is the single most useful debugging tool in a compiler. It makes golden-file testing possible, lets you diff before and after a pass, and catches malformed trees immediately.

Move to SSA before optimizing

Almost every classical optimization is dramatically simpler on SSA. Building it (via dominance frontiers, or the Braun et al. algorithm for a simpler construction) is real work and pays for itself the moment you write a second optimization pass.

Use an arena when performance matters

Index-based nodes in a flat array give better cache behavior than pointer-chasing, make the tree trivially copyable and serializable, and sidestep ownership complexity in languages that care about it.

Verify the IR

A verifier pass that checks structural invariants — every block ends in a terminator, every use is dominated by its definition, φ nodes have one operand per predecessor — catches optimizer bugs immediately rather than as mysterious wrong code. LLVM's verifier is a major reason its passes are debuggable.

Common Mistakes

A single node type with optional fields

Losing source spans in desugaring

Optimizing on the AST

One giant pass

Mutating a shared tree

Forgetting φ nodes at merges

FAQ

AST or IR — do I need both?

For a simple interpreter, an AST alone is fine — walk it and execute. Once you want optimization, you want a linear IR: control flow becomes explicit, data flow becomes analyzable, and the same optimizations stop needing to be rewritten per node shape. Most real compilers have several IRs at decreasing levels of abstraction (Rust has HIR, MIR, and then LLVM IR).

Is SSA hard to build?

The classical algorithm (Cytron et al., using dominance frontiers) is genuinely involved. The Braun et al. "Simple and Efficient Construction of SSA Form" algorithm is much easier to implement and produces good results — build SSA directly during IR construction rather than converting afterward. Most people implementing SSA today use it.

What are φ nodes, physically?

Nothing, at runtime. They're a notational device saying "the value here depends on which predecessor block we came from." During register allocation they're eliminated by inserting copy instructions at the end of each predecessor. Getting this "out of SSA" step right in the presence of overlapping live ranges — the lost-copy and swap problems — is a known subtlety.

Should the AST be immutable?

Immutable is easier to reason about and enables keeping earlier stages around for diagnostics, at the cost of allocations. Mutable is faster and invites pass-ordering bugs. An arena of indexed nodes gives most of the benefits of both, and it's what several production compilers and IDE backends have converged on.

How do IDEs use these structures?

Heavily and continuously. Syntax highlighting and folding come from the tree, "go to definition" from name resolution over it, refactoring from tree transformations, and inline errors from spans. The requirements are different from a compiler's: the tree must survive syntax errors, must be built incrementally on every keystroke, and must retain whitespace and comments — which is why IDE backends keep a lossless CST.

Can I skip the IR and generate code from the AST?

Yes, and it's a reasonable choice for a simple compiler or a bytecode-emitting interpreter — a post-order walk emits stack-machine bytecode naturally. What you give up is optimization: without a representation where control and data flow are explicit, even constant propagation across a branch is painful. Start there, add an IR when you want the compiler to be fast rather than just correct.