IRtypical

What an Intermediate Representation Is

Between the type checker and the code generator sits a third representation that belongs to neither: a flat sequence of simple instructions over an unlimited supply of virtual registers, grouped into blocks. It is not source, it is not machine code, and almost every interesting thing a compiler does happens there.

The question

What is an IR, and why is there a whole extra representation between my typed program and the machine code?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A linear sequence of instructions, each doing one thing, each naming its result, over an unbounded supply of virtual registers — grouped into basic blocks connected by explicit edges. It exists to answer a question the typed tree cannot phrase: in what order does this happen, and which value flows into which use. A tree says a + b * c is an addition whose right operand is a multiplication. It does not say that the multiplication happens first, and it gives the multiplication no name, so no analysis can say anything about it.

What this phase may assume or do

The IR builder is entitled to assume the program parsed, that every name resolves to a declaration, that every expression has a type and every operator is defined for its operand types — because a program that failed any of those never reaches this phase. It is entitled to assume nothing about the target: not the register count, not the word size, not whether an addition instruction exists. Any IR construction that consults a target detail has moved a backend decision into the middle-end and will need undoing when a second target arrives.

Key points

An IR is a linear sequence of one-operation instructions over unbounded virtual registers, grouped into basic blocks with explicit control-flow edges.
It exists because a tree cannot express evaluation order or refer to an intermediate value, and both are prerequisites for analysis.
The IR builder may assume the program type-checked and must assume nothing about the target.
Unoptimized IR is dominated by loads and stores against named slots, because that is what a frontend emits for local variables.
An IR is a data structure inside the compiler, not a format to ship — that difference is what separates it from bytecode.

The tree ran out of questions it could answer

A typed AST is a complete, checked description of what the program means. Ask it "is this program well-formed" and it answers immediately. Ask it "is this value ever used", "does this expression get computed twice", "what is live across this call" — and it has no way to even represent the question. Those are questions about *values over time*, and a tree has no time in it.

So the compiler builds one more representation. It flattens the tree into a sequence, which fixes an evaluation order. It gives every intermediate result a name, which gives analyses something to refer to. And it makes control flow explicit as edges between blocks rather than implicit in nesting, which is what turns "does this loop ever exit" into a graph question. Those three moves are the entire content of "IR".

The word *intermediate* is doing real work. This representation is not for humans and it is not for the machine. It exists so that a pass can be written once — against instructions and blocks — instead of once per source language and once per target. That argument is [[why-ir-exists]], and it is the reason the phase is paid for at all.

Where the IR sits, and what each handover coststypical

ASTbuild time
A tree of language constructs. Nesting expresses containment.
What is applied to what.
Punctuation, parentheses, and exact token positions unless spans are threaded deliberately.
Typed ASTbuild time
The same tree with a resolved symbol and a type on every node.
That the program is well-formed, and which declaration each name refers to.
IRbuild time
Three-address instructions over virtual registers, grouped into basic blocks with explicit edges.
An evaluation order, a name for every intermediate value, and control flow as a graph.
Expression nesting, and most of the source language. A for loop and a while loop with the same body are now indistinguishable.
Optimized IRbuild time
The same shape, fewer instructions or different ones.
Nothing representational — this stage only removes and rewrites.
Correspondence with the source. A statement the author wrote may no longer exist anywhere.
Machine IRbuild time
Target instructions, still over virtual registers.
A commitment to one instruction set.
Portability. From here the program is about a single machine.

Read it asThe IR row is the only one that adds *three* things at once, and that is why it is a separate representation rather than a decoration on the tree. It is also the row that loses the source language — which is exactly the point, and exactly why [[debugging-optimized-code]] is hard.

Three properties, and a listing

simplifiedAtlasLang instructions carry an opcode, operands and a type and nothing else. LLVM IR additionally carries alignment on every memory operation, address spaces, nsw/nuw overflow flags, fast-math flags, debug locations and arbitrary metadata — and several optimizations are legal only because of a flag we do not model. A reader who transfers "the IR is just opcode and operands" to LLVM will not understand why the same-looking add is optimized differently in two functions.

AtlasLang, the compiler that backs every interactive in this domain, lowers fn f(a: int, b: int, c: int): int { return a + b * c; } into the listing below. Read it against the three properties: every instruction does one thing, every result has a name, and the whole thing is inside a block called b0 that ends in a terminator.

Note what the frontend emits for a parameter: a param instruction that materialises the incoming value into a register, and then a store into a named slot. The slot is memory. That is not an accident or a naive choice — it is what a real frontend does, because it makes assignment to a parameter work without any special case. Promoting those slots back into registers is a later pass, and it is the pass that produces [[static-single-assignment]].

AtlasLang IR for return a + b * c; — verbatim engine output

fn f(a: int, b: int, c: int): int

▸b0: ; entry
▸  %0 = param 0 ; a: int
▸  store @a, %0
▸  %1 = param 1 ; b: int
▸  store @b, %1
▸  %2 = param 2 ; c: int
▸  store @c, %2
▸  %3 = load @a
▸  %4 = load @b
▸  %5 = load @c
▸  %6 = int %4 * %5
▸  %7 = int %3 + %6
▸  ret %7

Read it asEleven instructions for one expression, and nine of them are memory traffic the source never asked for. That is what unoptimized IR looks like everywhere, and it is why the first thing any middle-end does is promote local slots into registers. After that pass this function is four instructions: three params and the two arithmetic operations that survive.

What an IR is not

An IR is not assembly with nicer names. Assembly has a fixed, small register file, a specific instruction set and a calling convention baked in; the IR has an unbounded register supply and no target commitment at all. Confusing the two produces middle-end code that quietly assumes x86 semantics and breaks on the first cross-compile.

An IR is also not bytecode, though the two look similar on the page. Bytecode is a *format*: it is serialized, versioned, and executed by something. An IR is a data structure in a process that will exit before the program runs. The distinction matters the moment somebody proposes shipping it — see [[bytecode]] and [[wasm-model]] for representations that were designed to be shipped, and what that costs them.

And an IR is not one thing. Most production compilers have several, each at a different distance from the source. That is [[ir-levels]].

Which question each representation can answer about a + b * ctypical

Representation	Can answer	Cannot answer
Typed AST	Is this addition defined for these operand types	Whether the multiplication is computed more than once
IR	Which value flows into which use, and in what order	Which machine instruction can encode it
Machine IRtarget	Which target instruction implements it	Where the value physically lives
Machine codetarget	Exactly what executes	What the programmer called any of it

How it works

The steps, in the order the compiler takes them.

Walk the typed AST in evaluation order, one statement at a time, appending instructions to the current basic block.
For each expression node, lower the children first, then emit one instruction combining their results into a fresh virtual register.
Lower a local variable to a named slot, reading it with load and writing it with store, so that assignment needs no special case.
End a block whenever control can diverge or merge, and record the edge as part of the terminator rather than as a fallthrough convention.
Recompute predecessor and successor lists from the terminators once the function is complete, so the graph cannot drift out of sync with the code.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

Lowering fixes an evaluation order the language deliberately left unspecified, and a program whose operands have side effects prints its output in a different order under a different compiler — with no diagnostic from either.
Two variables that share a source name are lowered onto the same slot, and an inner declaration silently overwrites the outer one. The program compiles and returns wrong numbers. AtlasLang keys slots by the resolved symbol precisely to prevent this, and the shadowing test is what caught it.
A short-circuit operator is lowered as an ordinary binary instruction, and a != 0 && 10 / a > 1 divides by zero because the right operand was evaluated unconditionally.
A block is left without a terminator, and the code generator falls through into whatever block happens to be emitted next — producing a program that works until an unrelated change reorders the blocks.

When it helps

Reading an unfamiliar compiler: knowing which representation a pass runs on tells you immediately what it can and cannot be responsible for.
Debugging a wrong answer with no diagnostic. Dumping the IR before and after each pass localises the fault to one transformation faster than any amount of reasoning about the source.
Deciding where to implement a language feature: as sugar in the parser, as a lowering into existing IR, or as a new IR instruction with backend support. The three have wildly different costs and the IR is where the boundary sits.

When it hurts

Reasoning about performance from the IR. Instruction count in the IR correlates weakly with runtime: the backend will fold several IR instructions into one machine instruction, and the machine will reorder what it is given.
Very small or very simple compilers. A single-pass compiler that emits machine code directly from the parser needs no IR at all, and paying for one buys nothing if there is exactly one source language and exactly one target.

What it costs

Every one of these is paid by something.

An explicit IR buys analysability and retargetability, and costs compile time and memory proportional to program size — every instruction is an allocated object that the frontend did not previously need.
It costs implementation surface that is easy to underestimate: a printer, a parser for the printed form, a verifier, a serializer and a test suite, all of which must be maintained alongside the instructions themselves.
Flattening the tree buys an evaluation order, and pays for it by discarding the source structure — which is why line tables and [[debug-information]] must be threaded through explicitly rather than recovered later.

What else you could do

What a different compiler or language does instead, and when that is better.

A tree-walking interpreter skips IR entirely and executes the typed AST directly. Far simpler, considerably slower, and a completely legitimate implementation — see [[tree-walk-interpreter]].
A single-pass compiler emits target code as it parses, with no IR and effectively no optimization. Turbo Pascal was famously built this way and compiled at a speed nothing since has matched; the price is that no transformation needing two passes is possible at all.
Some compilers use the AST *as* the IR, annotating it in place and transforming it there. This keeps source structure available for diagnostics, and makes any analysis about values-over-time awkward enough that most such compilers eventually grow a second representation anyway.

See it for yourself

The flag, dump or tool that shows you this directly.

clang -S -emit-llvm -o - file.c prints LLVM IR for a C or C++ translation unit. Add -O0 and -O2 and diff the two listings — the difference is the entire middle-end.
rustc --emit=mir src/main.rs writes Rust MIR, the mid-level IR that borrow checking and most Rust-specific lowering run on.
gcc -fdump-tree-gimple writes GCC GIMPLE beside the object file; -fdump-tree-all writes every intermediate form the tree pipeline produces.
GOSSAFUNC=Fname go build writes ssa.html — an interactive dump of Go SSA at every pass, which is the friendliest IR dump any mainstream toolchain ships.
Our own pipeline explorer at /compilers/pipeline shows the AtlasLang IR panel for whatever you type, alongside the tokens, tree and typed tree it came from.

Plausible wrong readings

Stated the way a confident engineer states them.

"The IR is what the CPU runs." Nothing runs the IR. It is a data structure inside a compiler process that has usually exited before your program starts.
"The IR is just simplified assembly." Assembly commits to a register file, an instruction set and a calling convention. The IR commits to none of them, and a middle-end that assumes any of them is broken for the second target.
"There is one IR." Most production compilers have three or four at different levels, and a pass is written against exactly one of them — [[ir-levels]].
"Unoptimized IR shows what the machine will do." Unoptimized IR is mostly memory traffic the source never requested. It shows what the *frontend* emitted, which is a different claim.

Misconceptions

The claim, and what is actually true.

The IR is generated once and then handed to the backend.

It is rewritten dozens of times. A production pass pipeline runs well over a hundred passes over the same IR, each one reading and rewriting it in place — see [[pass-pipelines]].

Virtual registers become machine registers one-for-one.

There is no such correspondence. Register allocation maps an unbounded set onto a fixed small one, and any value that loses goes to a stack slot — [[spilling]].

If the IR looks slow, the program will be slow.

Unoptimized IR looks slow by construction. The listing above has nine memory operations for an expression that compiles to two instructions after the first promotion pass.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

After the type checker has proved the program means something, the compiler rewrites it as a flat list of very simple instructions — one operation each, every result given a name, control flow drawn as a graph. That list is the IR. Almost every optimization you have heard of is a rewrite of that list, and the reason the list exists is that you cannot ask "is this value ever used" of a tree.

practical

When a program compiles but computes the wrong answer, dump the IR at -O0 first and confirm the frontend lowered what you wrote. Then dump it at the optimization level that misbehaves and diff. In practice the fault is in one of three places: the lowering fixed an order the language did not specify, a pass applied a transformation whose precondition did not hold, or the source has undefined behavior and the optimizer took the licence it was given. The dump tells you which without any guessing.

advanced

The interesting design question is not what instructions the IR has but what it is *allowed to represent*. An IR that can represent an ill-typed program needs every consumer to defend against one. An IR that cannot represent a use before its definition makes a whole class of pass bugs unrepresentable rather than merely detectable. This is why LLVM IR is typed and why its verifier is not optional: the invariants an IR enforces are the invariants no pass has to re-establish, and every invariant dropped becomes a defensive check in a hundred places — [[ir-verification]].

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThe three-address, virtual-register, basic-block shape describes LLVM, GCC GIMPLE, Cranelift, Go SSA and AtlasLang. It does not describe V8 TurboFan, whose sea-of-nodes IR has no basic blocks until scheduling, and it does not describe a tree-based IR such as GCC GENERIC. The properties transfer; the picture does not.

simplifiedAtlasLang has one IR level, one integer type and no pointers, so several questions that dominate real IR design — aliasing, address spaces, overflow flags — do not arise. It is a faithful model of the shape and a deliberately incomplete model of the difficulty.

If you were asked this in an interview

Why does a compiler have an IR at all, rather than generating code from the typed tree?
What can you ask of an IR that you cannot ask of an AST? Give a concrete analysis.
The unoptimized IR for a two-line function has eleven instructions. Is that a problem?

Connections

DSAdirected-graph binary-tree

Computer Architectureregisters instruction-set-architecture

Domains that do not exist yet

Programming Languages & Runtime Internals — The object representation and calling protocol the IR is eventually lowered onto
Several IR decisions — whether a closure is a struct, whether a method call is a table lookup — are only explicable in terms of the runtime that will execute the result, and that runtime is owned there.