IRimplementation

Levels of IR: High, Mid and Low

Rust has HIR, THIR, MIR and then LLVM IR. That is not indecision. Each level answers a question the level below it can no longer phrase, and each lowering discards something on purpose — which is precisely why the earlier level had to exist.

The question

Why do real compilers have three or four IRs instead of one, and how do I know which one a pass should run on?

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

What the program is here

A ladder of representations of the same program, ordered by distance from the source. High-level IR still knows about the language constructs the author wrote; mid-level IR knows about values, control flow and types but not syntax; low-level IR knows about the target. Each rung exists to answer questions that are natural at that distance and impossible at any other.

What this phase may assume or do

A lowering from one level to the next must preserve the program's defined observable behavior, and it is permitted to discard any information the levels below it will never consult. That second clause is the load-bearing one: discarding is legal only if nothing downstream needs it, and the standard way to discover that you were wrong is a diagnostic or a debugger that can no longer say something useful.

Key points

High-level IR keeps the author's vocabulary; mid-level IR keeps values and control flow; low-level IR admits the target.
Each lowering discards information on purpose, and the discarded information is the reason the higher level had to exist.
A pass belongs at the highest level that can still express its question — too high and it cannot be asked, too low and the answer is gone.
Rust moved borrow checking from the tree to MIR because the analysis needed a control-flow graph; the level was added for the analysis, not the other way round.
Every level you skip is diagnostic quality you cannot recover later; every level you add is another printer, verifier and test suite.

Three distances, three questions

A high-level IR is close enough to the source that the constructs the author wrote are still visible. Rust's HIR still has for loops, if let, method calls and macro-expansion results; it is what lints, type checking and most diagnostics run against, because those are all things you want to phrase in the author's vocabulary. Ask "did this match cover every case" and only a representation that still has a match in it can answer.

A mid-level IR has given that up. Rust's MIR has basic blocks, locals and a small set of statements; the for loop is gone, replaced by an explicit iterator protocol lowering plus a loop in the control-flow graph. What it gained is a graph you can run dataflow over — which is exactly what borrow checking needs, and exactly why borrow checking moved from the AST to MIR.

A low-level IR has admitted the target. Machine IR still uses virtual registers but the instructions are real ones, calling conventions have been applied, and stack slots exist. Ask "how many registers does this function need" and only this level can answer, because the answer depends on the machine.

What each level can answer, and what it had to discard to get thereimplementation

Level	Example	Answers naturally	Discarded on the way in
High-levelimplementation	Rust HIR, Swift AST/SIL-raw, Java's early trees	Is this `match` exhaustive; is this lint triggered; what should this error message say	Nothing yet — this is the source with names resolved
Mid-levelimplementation	Rust MIR, LLVM IR, Go SSA, GCC GIMPLE	Which values are live; where is this borrow last used; is this expression redundant	Syntactic sugar, source-level loop forms, most of the language's vocabulary
Low-leveltarget	LLVM Machine IR, GCC RTL	Which instruction encodes this; how many registers are needed; what does the frame look like	Portability, and any structure the target does not have an instruction for

Rust, all four rungs

implementationThis is rustc as of the 2020s and the level names are rustc's own. GCC uses GENERIC, GIMPLE and RTL for roughly the same three distances; Swift uses SIL in raw and canonical forms before LLVM IR; V8 goes bytecode to sea-of-nodes with no equivalent of a high-level IR at all. The three-distance idea transfers; the number of rungs and every name does not.

Rust is the clearest published example because each level has a documented reason. The AST is what the parser produces and what macros operate on. HIR is the AST after name resolution and macro expansion, with the syntax regularised — this is where type checking happens. THIR is HIR with types fully applied, which is where exhaustiveness checking and pattern-match lowering run. MIR is the control-flow graph, which is where borrow checking, const evaluation and Rust-specific optimization run. Only then does it become LLVM IR.

The reason MIR exists at all is instructive: borrow checking used to run on the tree, and it was both imprecise and hard to explain. Moving it to a CFG made "this borrow ends here" a dataflow fact rather than a syntactic approximation, which is what made non-lexical lifetimes possible. The IR level was added because an analysis needed a representation that did not exist yet.

That is the general rule for deciding which level a pass belongs on: the pass belongs at the highest level that can still express its question. Run it too high and the question is not answerable; run it too low and the information is gone. Exhaustiveness checking cannot run on MIR because the match is gone. Liveness cannot run on HIR because there is no control-flow graph.

One Rust function, four representationsimplementation

ASTbuild time
The parse result: tokens grouped into syntax, macros unexpanded.
Structure.
Nothing yet.
HIRbuild time
Macro-expanded, name-resolved, syntactically regularised tree.
Which declaration every path refers to; a stable shape for type checking and lints.
Macro call sites as written, and some syntactic variation that was pure sugar.
THIRbuild time
HIR with every type known and applied.
Full type information, which is what pattern-match compilation and exhaustiveness need.
Nothing structural; this is an annotation step.
MIRbuild time
A control-flow graph of basic blocks over locals, with explicit drops.
A graph for dataflow: borrow checking, const evaluation, drop elaboration.
Source-level control-flow forms. A for loop, a while let and a manual loop are now the same shape.
LLVM IRbuild time
The shared, target-independent instruction set.
Access to LLVM's optimizer and every LLVM target.
Everything Rust-specific — lifetimes, &mut non-aliasing unless explicitly encoded as an attribute, the type system.

Read it asRead the loses column as a list of reasons the previous rung was necessary. Every entry is something a pass above needed and no pass below will ever ask for. When that judgement is wrong, the symptom is a diagnostic that cannot be phrased or a debugger that cannot answer — see [[information-loss]].

Where AtlasLang sits, and what that costs it

AtlasLang has one IR level. The typed tree lowers directly to three-address instructions in basic blocks, and that same IR is what the optimizer, the SSA converter and the bytecode compiler all consume. For a teaching language with one integer type and no pointers, one level is honest — there is no analysis in the system that needs a rung that is not there.

The cost shows up exactly where the theory predicts. AtlasLang cannot report "this while loop never executes" in terms of the while the author wrote, because by the time any analysis runs, the while is three blocks and a back edge with a label attached as a courtesy. The labels in the CFG — while.cond, if.join, and.rhs — exist *only* so the interactives can show you where a block came from. They are a deliberate, minimal substitute for a high-level IR, and they are decoration: nothing in the compiler reads them.

That is the miniature version of the real tradeoff. Every level you do not build is diagnostic quality you cannot get back later, and every level you do build is another representation with a printer, a verifier and a test suite.

One while loop, after the only lowering AtlasLang has

Source

let n = 0;
let s = 0;
while (n < 3) {
  s = s + n;
  n = n + 1;
}
print(s);

AtlasLang IR — verbatim engine output

▸b0: ; entry
▸  store @n, 0
▸  store @s, 0
▸  jump b1
▸b1: ; while.cond preds=b0,b2
▸  %0 = load @n
▸  %1 = bool %0 < 3
▸  branch %1 ? b2 : b3
▸b2: ; while.body preds=b1
▸  %2 = load @s
▸  %3 = load @n
▸  %4 = int %2 + %3
▸  store @s, %4
▸  %5 = load @n
▸  %6 = int %5 + 1
▸  store @n, %6
▸  jump b1
▸b3: ; while.exit preds=b1
▸  %7 = load @s
▸  print %7
▸  ret

Read it asThe while is gone. What remains is a block that tests, a block that works, a block that continues, and a jump b1 at the end of b2 that makes the graph cyclic. The ; while.cond comments are labels the lowering attached for the interactives; no pass consults them. A compiler that wanted to say "your loop condition is always false, did you mean <=?" needed to say it before this point.

How it works

The steps, in the order the compiler takes them.

Lower the source to a high-level IR by resolving names and expanding macros, keeping every construct the author wrote.
Run every analysis whose question is phrased in source vocabulary — lints, exhaustiveness, most diagnostics — at that level.
Lower to a mid-level IR by replacing source constructs with explicit control flow and values, producing a CFG.
Run every analysis that is about values over time — liveness, borrow checking, constant propagation — at that level.
Lower to a target-specific IR by selecting instructions and applying the calling convention, then allocate registers.
Thread source locations through every lowering explicitly, since none of them are preserved automatically.

How it breaks

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

A diagnostic can only be phrased in terms the compiler no longer has, and the error message says "expected value, found unit at line 40" when the author's mistake was a missing match arm twenty lines earlier.
A pass is written at the wrong level and quietly does less than intended — an optimization that was supposed to recognise a source idiom fires on none of it, because the idiom stopped being recognisable one lowering earlier.
The debugger reports a variable as optimized out, because a lowering dropped the metadata that connected it to its storage and nothing downstream could reconstruct it.
Two lowerings disagree about a corner case, and the program behaves differently depending on whether a pass fired — the class of bug that only reproduces at one optimization level.

When it helps

Deciding where to implement a new analysis or lint. The level question is usually the whole design decision, and getting it wrong wastes the implementation entirely.
Explaining why a compiler produces a bad error message. Almost always the answer is that the check runs at a level where the author's construct no longer exists.
Understanding why a language keeps its own IR above a shared one — Swift SIL and Rust MIR are both answers to "LLVM IR cannot express what we need to check".

When it hurts

Small compilers and DSLs. Multiple levels are a real maintenance cost and a single-level design is the right answer for most implementations that will never have a second target.
When the levels are not actually different. Two IRs that answer the same questions are two test suites and one benefit, and the second one tends to be added because it felt tidy rather than because an analysis needed it.

What it costs

Every one of these is paid by something.

More levels buy diagnostics and language-specific optimization, and cost a printer, a parser, a verifier and a full test suite per level — plus the lowering between them, which is where the interesting bugs live.
Lowering early buys simpler downstream passes and pays in diagnostic quality: everything the lowering discarded is something no later phase can mention.
Lowering late buys precise error messages and pays in complexity, because every pass that runs before the lowering must handle the full richness of the source language.
Keeping a private IR above a shared one buys language-specific analysis and pays with a second optimizer to maintain, which is why Swift and Rust both employ people to do exactly that.

What else you could do

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

One level, as AtlasLang and many small compilers do. Simpler, and diagnostics are limited to whatever the frontend said before lowering.
Two levels with a hard split: a language IR for checking and a shared IR for code generation. This is the Swift and Rust answer, and it is the common shape for a language with guarantees LLVM cannot express.
A single IR with enough attributes to serve all levels. LLVM has drifted toward this with metadata and attributes, and the cost is that every pass must decide what to do with metadata it does not understand.
Sea-of-nodes, which collapses the distinction differently: control and data live in one graph and scheduling decides the order last — see [[ir-design-tradeoffs]].

See it for yourself

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

rustc -Z unpretty=hir src/main.rs on a nightly toolchain prints HIR; rustc --emit=mir writes MIR. Reading the same function in both is the fastest way to see what a lowering costs.
gcc -fdump-tree-all -fdump-rtl-all writes every GCC intermediate form to numbered files; the sequence of filenames is itself a map of the pass pipeline.
swiftc -emit-sil file.swift prints Swift SIL, the high-level IR where Swift-specific optimization happens before LLVM IR is generated.
Compare clang -S -emit-llvm output against clang -Xclang -ast-dump output for one function to see the high-to-mid gap in a language that has no explicit middle rung.

Plausible wrong readings

Stated the way a confident engineer states them.

"More IRs means a slower compiler." It means more compile-time work per function and often *better* diagnostics and faster generated code. Whether it is a net loss depends entirely on which you are paying for.
"HIR, MIR and LLVM IR are just names for the same thing at different times." They are different data structures with different node sets. A pass written against one does not compile against another.
"The lowest level is the most accurate." It is the most target-specific. It is also the level at which the question "what did the programmer write" has no answer at all.
"You should optimize as early as possible." You should optimize at the level where the transformation is expressible and its precondition is checkable. Doing it early on a rich representation often means handling many more cases for the same result.

Misconceptions

The claim, and what is actually true.

MIR is just LLVM IR with Rust names.

MIR has drops, borrows, unwinding edges and Rust-specific terminators that LLVM IR has no way to represent. It exists because borrow checking cannot be run on LLVM IR at all.

A high-level IR is one that is easier to read.

It is one that is closer to the source *vocabulary*. HIR is not more readable than MIR; it just still contains the constructs the author typed, which is what lints and exhaustiveness checks need.

Go deeper

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

overview

Compilers usually have several intermediate representations, not one. The higher ones still contain the constructs you wrote — loops, matches, method calls — and are where error messages and lints come from. The lower ones have replaced all of that with blocks, values and jumps, and are where optimization happens. Each step down throws something away deliberately, which is why the step above it had to exist.

practical

When you are adding a check to a compiler, the first question is which level it runs on, and the test is simple: can the question be phrased in that representation, and is the information it needs still present? Exhaustiveness needs the match, so it runs high. Liveness needs a control-flow graph, so it runs mid. Register pressure needs the target, so it runs low. Getting this wrong is not a performance mistake — it makes the pass impossible to write correctly, usually after it is half written.

advanced

The subtle cost of a ladder is that every rung multiplies the surface for miscompilation, because a lowering is a translation and translations can be wrong. rustc mitigates this with MIR-level interpretation — the const evaluator runs MIR directly, so the same representation is both compiled and executed and a disagreement is detectable. That trick generalises: whenever a level can be *executed* as well as lowered, differential testing between the two is possible, and it is one of the very few practical defences against a wrong lowering — [[translation-validation]].

How much this depends on

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

implementationLevel names are project-specific and not comparable across compilers. rustc's MIR and GCC's GIMPLE occupy a similar distance from the source but have different node sets, different type systems and different invariants. Do not reason about one from documentation about the other.

typicalMainstream ahead-of-time compilers generally have three or four levels. JIT compilers frequently have fewer on the fast tier and more on the optimizing tier, because tier-one exists to start executing quickly and cannot afford the lowering — see [[tiered-compilation]].

If you were asked this in an interview

Rust has HIR, THIR, MIR and LLVM IR. Give me a reason each one exists.
You are asked to add a lint that fires on empty match arms. Which representation do you run it on, and why not the one below?
Why did moving borrow checking to MIR improve it?

Connections

DSAn-ary-tree directed-graph

Domains that do not exist yet

Programming Languages & Runtime Internals — The runtime representation a low-level IR is ultimately lowering onto
Drop elaboration in Rust MIR and ARC insertion in Swift SIL are both compiler-side halves of a runtime memory-management story that is owned there.