Designing an IR: The Four Decisions

In SSA form, every value is assigned exactly once, and a merge of two definitions is written explicitly as a phi node. The benefit is that a use points at exactly one definition, so def-use chains are free and most dataflow analyses become substantially cheaper — constant propagation, for instance, no longer needs a separate reaching-definitions analysis because the answer is in the name.

The cost is real. Construction is a nontrivial algorithm requiring dominance and the dominance frontier; leaving SSA again requires resolving phi nodes into copies, and doing that correctly requires handling parallel-copy cycles and critical edges. AtlasLang implements all of it, and the sharp edges — the swap problem, the critical edge — are visible in outOfSSA because they are unavoidable, not because the implementation is naive.

GCC's GIMPLE has both: it is used in a non-SSA form early and converted to SSA for the main optimization pipeline. That is the honest middle answer, and it costs a conversion in each direction.

A typed IR carries a type on every value and rejects an instruction whose operand types do not match its signature. LLVM IR is typed: add i32 %a, %b will not verify if %a is an i64, and a getelementptr must be given a type to index into. The benefit is that a whole class of pass bug becomes unrepresentable rather than merely detectable — a pass that builds an ill-typed instruction fails immediately, at the pass that built it, rather than three passes later in a code generator that assumed otherwise.

The cost is that every transformation must maintain the types, and any transformation that would be natural to express without them becomes more work. LLVM famously spent years moving from typed pointers (i32*) to opaque pointers (ptr) precisely because the pointee type was carrying no information the optimizer could trust and a great deal of complexity every pass had to maintain. That is a real, documented example of a typing decision being partly reversed after the costs were measured.

An untyped IR — or a weakly typed one, where everything is a machine word — is simpler to build and simpler to transform, and pushes the checking to the frontend and the human. Cranelift takes a middle path: values have machine types (i32, i64, f64, vector types) rather than source types, which is enough to catch operand mismatches without carrying any source-language type system.

An IR that knows nothing about the target is maximally portable and maximally unable to make target-sensitive decisions. An IR that knows the register file can schedule for it, and can no longer be shared. Every real design picks a point on that line and then leaks a little.

LLVM IR is nominally target-independent, and in practice is not quite: pointer size, endianness, alignment rules and the availability of vector widths all reach it through the data layout string and target features. Anyone who has moved LLVM IR from a 64-bit to a 32-bit target has discovered that "target-independent" means "parameterised by the data layout", not "identical everywhere".

Cranelift admits more, on purpose. It was built to compile WebAssembly quickly inside a running process, where compile time is a latency budget rather than a build-time cost, so it accepts target awareness earlier in exchange for a shorter path to machine code. That is not a worse design; it is a design for a different constraint — and it is the same reasoning that makes a [[jit-compilation]] tier-one compiler look nothing like an ahead-of-time one.

A linear IR is a list of instructions per block. Order is explicit, printing is trivial, and every pass knows exactly where an instruction sits. A tree IR keeps the nesting and is what an AST-based compiler uses. A graph IR — sea-of-nodes, as in V8 TurboFan and historically in HotSpot C2 — records only *dependencies*: value edges, effect edges and control edges, with no instruction order at all until a scheduling pass invents one at the end.

The sea-of-nodes argument is that most reordering optimizations are free, because there was never an order to preserve. Global value numbering falls out of node identity, and code motion is a matter of where the scheduler eventually places a node rather than a transformation that has to move anything. That is genuinely powerful for a JIT doing aggressive speculation.

The cost is legibility and debuggability, and it is not a small cost. There is no natural textual form, so tooling is a graph viewer rather than a diff. Reasoning about *when* something happens requires reasoning about the scheduler. And a bug in the effect-edge chain produces a reordering that is very hard to see. V8 has publicly moved away from sea-of-nodes for its newer Maglev and Turboshaft tiers, citing exactly these costs — which is the strongest available evidence that this is a genuine tradeoff and not a settled question.