Lowering
Lowering is the verb the whole middle of a compiler runs on: replace a construct with a simpler one that has the same defined behavior, and repeat until nothing is left but jumps, arithmetic and memory. A `for` loop, a closure, a `match` and an `await` are all the same kind of problem.
What does "lowering" actually mean, and how does a high-level feature like match or async become ordinary jumps?
The program at some level of the IR ladder, being rewritten into the level below. During a lowering the program is briefly a mixture — some constructs already replaced, some not — which is why a lowering pass is written as a total function over one node kind rather than as a walk that can be interrupted. What it exists to answer: what is the simplest set of constructs that can express this program, given that every construct the IR keeps is a construct every backend must implement.
A lowering is legal when the replacement has the same defined observable behavior as the original for every input, including the inputs that trap, diverge or have side effects. Two clauses catch most mistakes: the replacement must evaluate each subexpression exactly as often as the original (short-circuit operators and lazily-evaluated arguments are where this fails), and it must preserve the original's behaviour on abrupt exit — an early return, an exception or a panic in the middle of the construct must leave the same state and run the same cleanup.
Key points
- Lowering replaces a construct with simpler constructs that have the same defined behavior, and repeats until only jumps, arithmetic, memory and calls remain.
- Every construct that survives to the backend is one every target must implement and every pass must handle, which is the pressure that drives lowering.
- Desugaring is lowering performed early, at the syntax level, with source-level output; pattern-match compilation is the same verb applied much lower.
- A lowering must preserve behavior on abrupt exit and must evaluate each subexpression exactly as often as the original.
- Lowering discards information, so lowering early can foreclose optimizations — and analyses like natural-loop detection exist to reconstruct what a lowering threw away.
Fewer constructs, more instructions
Every language feature has to be implemented somewhere. It can be implemented in the backend — a real instruction, a real runtime call — or it can be implemented by rewriting it into features that already exist. The second option is lowering, and compilers reach for it relentlessly, because every construct that survives to the backend is a construct that every target must support and every pass must handle.
So a for loop is lowered into a condition block, a body block and a back edge. A switch is lowered into a chain of comparisons, a jump table, or a binary search, depending on how dense the cases are. A closure is lowered into a struct of captured values plus a function that takes it as an extra argument. A match with nested patterns is lowered into a decision tree of tests. An async fn is lowered into a state machine with a resume point per suspension.
Notice what all five have in common: the input has a construct with its own semantics, and the output has only jumps, arithmetic, memory and calls. That is what "lower" means — closer to the machine, further from the author.
| Construct | Lowered into | The part that is easy to get wrong |
|---|---|---|
for x in xs | Iterator creation, a loop with a condition and a back edge | When the iterator is dropped, and what happens on an early break |
a && b | A branch, a block for b, and a join | Evaluating b unconditionally, which is a wrong answer, not a slow one |
| A closure | A struct of captured values plus a function taking it as a hidden argument | Whether a capture is by value or by reference, and how long the struct outlives the frame |
match with nested patterns | A decision tree of discriminant tests and field loads | Testing the same discriminant more times than necessary, and getting arm order wrong |
await | A state machine with a resume point and a saved local frame | Which locals must be kept alive across the suspension, and what happens to them on cancellation |
Desugaring is lowering that happens early
The two words are often used interchangeably, and the difference worth keeping is *when* and *how far*. [[desugaring]] is a lowering performed on or near the syntax tree, replacing one source construct with another source construct: a += b becomes a = a + b, if let becomes a match, a string interpolation becomes a concatenation. The output is still a program in the same language, and it could in principle be printed back out.
[[pattern-matching-compilation]] is the same verb applied much lower and much harder. A match with nested patterns, guards and bindings does not become another source construct — it becomes a decision tree over discriminant tests, and the interesting engineering is minimising how many times each discriminant is examined. There is no source program that the output corresponds to.
Both are instances of the same operation, and the reason to keep the distinction is diagnostic quality. A desugaring performed early means every later error message is about the desugared form, which is why a += b producing an error that mentions a = a + b is a familiar and mildly infuriating experience. The compilers that avoid it keep the sugar in the tree and lower late, paying for it with a richer representation for every intermediate pass to handle.
A lowering with its precondition, in AtlasLang
break, no continue and no exceptions, so its while lowering needs no exit-edge bookkeeping. In a real compiler that is most of the work: break is an edge to the exit block from an arbitrary depth, continue is an edge to the condition block, and an early return or a panic inside the body must run every pending destructor on the way out. Those edges are why loop lowering in rustc or Clang is hundreds of lines rather than twenty.AtlasLang has one interesting lowering: while. The construct disappears entirely, replaced by three blocks and an edge that points backwards. Everything the loop meant is now expressed by the shape of the graph.
The precondition is easy to state and easy to violate. The condition must be evaluated *before every iteration including the first*, which is why the entry block jumps to the condition block rather than to the body. Lower it the other way — jump straight into the body and test at the bottom — and you have written a do/while, which executes the body once even when the condition was false from the start. That is not a performance difference; it is a program that does something the author did not write.
while, as AtlasLang actually does itwhile (n < 3) {
s = s + n;
n = n + 1;
}b0: ; entry jump b1 b1: ; while.cond %0 = load @n %1 = bool %0 < 3 branch %1 ? b2 : b3 b2: ; while.body ... jump b1 ; the back edge b3: ; while.exit
Legal when the condition block is reached before the body on entry, the body's last edge returns to the condition block rather than to the body, and the condition is re-evaluated on every arrival at b1. Under those three conditions the graph executes the body exactly when the source loop would, including zero times.
Entering at b2 instead of b1 turns the loop into a do/while and executes the body once for a condition that was false to begin with — while (n < 3) with n = 10 would run the body. Jumping the back edge to b2 instead of b1 never re-tests the condition and produces an infinite loop. Both compile, both type-check, and both are wrong for every program that used the construct.
Lowering happens repeatedly, not once
A compiler does not lower once. It lowers from the tree to a high-level IR, from there to a mid-level IR, from there to machine IR, and inside each of those there are further lowerings that replace one instruction with several. LLVM has an entire family of passes whose job is expanding an IR construct the backend does not support into ones it does, and they run late, after most optimization.
The reason for the repetition is that each lowering is a decision, and a decision made early cannot be revisited. Lower a switch into a jump table before you know how many cases survive constant propagation and you may have built a table with three live entries. Lower it after and you can choose comparisons instead. [[phase-ordering]] is the general form of this problem, and it has no clean solution — it is why pass pipelines are tuned rather than derived.
The other reason is that lowering *destroys information*, and information is worth keeping as long as it is still useful. A for loop that is still a for loop can be recognised by a loop-idiom pass; once it is three blocks and a back edge, the pass has to reconstruct the loop from the graph, which is [[natural-loops]] — a whole analysis that exists to undo something a lowering did.
How it works
The steps, in the order the compiler takes them.
- Pick the construct to eliminate and state exactly what its semantics are, including its behavior on abrupt exit and on each subexpression's evaluation count.
- Write the replacement using only constructs the target representation already has.
- Establish the precondition under which the two agree, and identify at least one program where a plausible-looking alternative replacement would disagree.
- Rewrite each occurrence, threading source locations onto the generated instructions so diagnostics and debug information survive.
- Recompute any derived structure the rewrite invalidated — predecessor and successor lists, dominance, loop information — rather than patching it incrementally.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- The replacement evaluates a subexpression more or fewer times than the original, and a program with side effects prints twice or not at all — with no error from any phase.
- The loop is entered at the body instead of the condition, and a loop that should not have run at all runs once. The symptom is an off-by-one in a result computed far from the loop.
- The lowering forgets an abrupt-exit path, and a destructor or
finallyblock is skipped on thebreakpath only — so a resource leak appears in exactly one control-flow case and passes every test that does not take it. - Source locations are not threaded onto the generated instructions, and every error and every debugger line for the whole construct points at its first line — the classic "the entire loop is line 12" symptom.
When it helps
- Implementing a new language feature. Most features can be lowered onto existing ones, which means no backend change, no new instruction and no new case in a hundred passes.
- Understanding a performance surprise. Many are explained by seeing what a construct lowered into — an innocuous-looking iterator chain that lowered into a closure capture and an indirect call, for example.
- Porting a language to a new target. The more the language lowers onto a small core, the less of it is target-specific work.
When it hurts
- Diagnostics. Every lowering is a chance for an error message to be about the generated form rather than the written one, and the fix is either to lower later or to thread provenance carefully through the rewrite.
- Optimization quality when the lowering happens too early. Once a construct is gone, any pass that recognised it is a pass that no longer fires, and reconstructing it from the lowered form is strictly harder than never destroying it.
What it costs
Every one of these is paid by something.
- Lowering early buys simpler downstream passes and pays in diagnostic quality and in optimization opportunities that depended on recognising the original construct.
- Lowering late buys precise error messages and better idiom recognition, and pays by making every intermediate pass handle a larger construct set.
- Lowering onto existing constructs buys backend simplicity and pays in instruction count — a
matchthat becomes twelve tests is twelve instructions where a dedicated construct might have been one. - Adding a dedicated IR instruction instead of lowering buys code quality for that feature and pays a permanent tax: every pass, every backend and every verifier now has one more case forever.
What else you could do
What a different compiler or language does instead, and when that is better.
- Implement the feature in the runtime instead of the compiler. Exceptions can be lowered into explicit checks and branches, or handed to a runtime unwinder with side tables — the second keeps the fast path free of any cost and moves the complexity out of the compiler entirely; see
[[stack-unwinding]]. - Implement it in the backend as a real instruction. Worth it when the target has direct support and the lowered form would be badly worse — vector operations are the usual example.
- Lower in the frontend as pure syntax rewriting, which is what a macro system lets users do. Cheap and flexible, and the diagnostics are typically the worst of any option.
- Do not lower at all: keep the construct through to an interpreter that knows about it. A tree-walking interpreter for a language with
matchcan simply implementmatch— see[[tree-walk-interpreter]].
See it for yourself
The flag, dump or tool that shows you this directly.
rustc --emit=mirshows Rust afterfor,if let,?andmatchhave all been lowered, which is the fastest way to see what a high-level construct actually costs.clang -S -emit-llvm -O0 -o -shows C++ range-for loops, destructors and exception edges after lowering — thelandingpadandinvokeinstructions are the exception lowering made visible.go tool compile -S file.goshows Go afterdefer,rangeand interface calls have been lowered, including the calls to runtime helpers the lowering inserted.- Compiler Explorer at
-O0for any language: the difference between the source and the listing is exactly the lowerings, before any optimization has had a chance to confuse the picture.
Plausible wrong readings
Stated the way a confident engineer states them.
- "Lowering is just code generation." Code generation is the last lowering. There are many before it, and most of them produce IR rather than instructions.
- "Lowering makes the program smaller." It nearly always makes it larger. One construct becomes several instructions; that is the trade being made.
- "If it lowers to the same thing, it performs the same." Only if the lowering happens before the passes that matter. The same source construct lowered at two different points in the pipeline can produce very different code —
[[phase-ordering]]. - "Desugaring and lowering are different operations." They are the same operation at different levels. The useful distinction is when it happens and what it costs diagnostics, not what it is called.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
Lowering means replacing a language construct with simpler pieces that behave the same way. A while loop becomes a test, a body and a jump backwards. A closure becomes a struct and a function. Compilers do this over and over until nothing is left but jumps, arithmetic, memory and calls — because that small set is all a machine actually has.
practical
When a high-level construct behaves surprisingly, read its lowered form before theorising. rustc --emit=mir, clang -S -emit-llvm -O0 and go tool compile -S all show what the construct actually became, including runtime calls the lowering inserted that the source never mentions. Most "why is this slow" questions about language features are answered in that listing, and most of the remainder are answered by the same listing at -O2.
advanced
The hard part of lowering is not the happy path, it is the exit paths. Every construct that can be left abruptly — by break, by an early return, by an exception, by a panic, by a cancellation — multiplies the edges the lowering must produce, and each edge must run exactly the right cleanup in exactly the right order. This is why drop elaboration in rustc is a MIR pass in its own right, why C++ exception lowering produces the invoke/landingpad structure rather than plain calls, and why "it works unless you break out of it" is such a recognisable class of compiler bug.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
for at HIR-to-MIR, and Go lowers range in the compiler backend with runtime help. The verb is universal; every specific claim about where a given construct disappears is per-compiler.switch becomes a jump table or a comparison chain.If you were asked this in an interview
- Take
for (x of xs) { ... }and lower it. What did you have to decide that the source did not say? - A lowering of
a && bevaluates both operands. Give me a program that detects this. - Why do compilers lower
switchdifferently depending on the case values?
Connections
- Programming Languages & Runtime Internals — The runtime support a lowering assumes exists — allocators, unwinders, schedulersClosure conversion assumes an allocator, exception lowering assumes an unwinder, and async lowering assumes an executor. The compiler emits the calls; that domain owns what answers them.