IRtypical

Three-Address Code

`x = a + b * c` becomes `t1 = b * c; t2 = a + t1; x = t2`. The rewrite looks like busywork until you notice that `t1` is a *name* — and that every analysis in the middle-end is a statement about names.

The question

Why does the compiler invent temporary names for values I never named, and what would break without them?

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

What the program is here

A sequence of instructions of the form result = operand op operand — at most three addresses, hence the name — where every operand is a constant, a variable or a previously defined temporary. It exists to answer two questions the expression tree cannot: in what order do the operations happen, and what do I call the value that came out of that one. An analysis that cannot name a value cannot say anything about it.

What this phase may assume or do

Flattening an expression tree into a sequence is legal only if the chosen order is one the language permits. For an operator whose operand evaluation order is specified, the sequence must match it. For an operator where the order is unspecified, any order is legal — and any program that can tell the difference was already relying on unspecified behavior. Short-circuit operators are the exception that is always got wrong: they may not be flattened into a sequence at all, because the right operand must not be evaluated unless the left fails to determine the result.

Key points

Three-address code has one operation per instruction and operands that are already computed, which forces an explicit evaluation order.
Naming intermediates is the substantive part: an analysis can only make statements about things that have names.
CSE, dead-code elimination, liveness, constant propagation and register allocation are all defined over instruction sequences and names — none of them are expressible over a tree.
Short-circuit operators must be lowered as control flow, never as a binary instruction, or a guard stops guarding.
"Three addresses" describes the shape, not a limit; calls and phi nodes exceed it in every real IR.

One operation per instruction

Take x = a + b * c. The tree says: an assignment whose right side is an addition whose right operand is a multiplication. It says nothing about order — the tree is a statement of dependency, and dependency does not imply sequence. Three-address code makes the sequence explicit by refusing to nest: every instruction has one operator and its operands are already-computed things.

So the multiplication has to happen first, and its result has to go somewhere. That somewhere is t1. Then the addition, whose result is t2. Then the store into x. Three instructions where the source had one statement, and two names that the programmer never wrote.

Those two names are the entire point of the exercise. Before the rewrite, "the result of b * c" is a phrase about a subtree — you can point at it in a diagram but you cannot put it in a set, use it as a map key, or say that it is live across a call. After the rewrite it is t1, and every one of those becomes possible.

The canonical example, and AtlasLang doing the same thing for real

Source and the textbook form

x = a + b * c;

  t1 = b * c
  t2 = a + t1
  x  = t2

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

▸%3 = load @a
▸%4 = load @b
▸%5 = load @c
▸%6 = int %4 * %5
▸%7 = int %3 + %6
▸ret %7

Read it as%6 is t1 and %7 is t2. The extra load instructions are there because AtlasLang lowers a local variable as a memory slot, and they disappear on the first promotion pass. What does not disappear is the naming: after this rewrite, "the product of b and c" has an identity that a pass can compare, store and reason about.

What the names make possible

Common-subexpression elimination is a statement about names: if two instructions compute the same operator over the same operand names, and nothing redefines those names in between, the second one is redundant. Try phrasing that over an expression tree and you find yourself defining structural equality over subtrees and then hunting for interfering assignments in the surrounding statements — which is to say, you find yourself reinventing three-address code badly.

Dead-code elimination is a statement about names: if nothing reads %6 and computing it cannot trap or have an effect, delete it. Liveness is a statement about names. Constant propagation is a statement about names. Register allocation is *entirely* a statement about names — a register is exactly a name with a physical location, and [[live-ranges]] are intervals over the instruction sequence that only exist because there is a sequence.

This is why the flattening is not a formatting choice. Every classical middle-end analysis is defined over instructions and names, and the reason is that a tree offers neither.

The same question, asked of a tree and of three-address codetypical

Question	Over an expression tree	Over three-address code
Is this value computed twice?	Structural comparison of subtrees, plus a search for interfering assignments	Two instructions with equal operator and operand names
Is this value ever used?	Not expressible — a subtree has no identity to look for uses of	Nothing reads the destination name
What is live across this call?	Not expressible — there is no "across"	Names defined before the call instruction and read after it
In what order does this happen?	Not expressible — the tree states dependency, not sequence	Instruction order, explicitly

The operator that must not be flattened

specShort-circuit evaluation of && and || is required by the C, C++, Java, JavaScript, Rust and Go specifications, so the branch lowering is mandatory there, not an optimization. It is not universal: Ada distinguishes and from and then, and Fortran explicitly permits the compiler to evaluate both operands of .AND. in either order or to skip one. Check the language before assuming the guard protects anything.

Flattening assumes that computing an operand is always safe to do. For && and || that assumption is false, and this is the single most common way to get lowering wrong.

a != 0 && 10 / a > 1 is a perfectly ordinary defensive expression: the left operand exists precisely to prevent the right one from dividing by zero. Lower it as a binary instruction over two already-computed operands and the division happens unconditionally. The program now faults on exactly the input the author wrote the guard for. Nothing in the type checker objects, because the expression is well typed.

So short-circuit operators are lowered as *control flow*, not arithmetic — a branch, a block that computes the right operand, and a join where the result comes back together. In AtlasLang that produces a temporary slot written on both paths and read at the join, which is precisely the situation that later requires a phi node. The smallest program that forces [[phi-functions]] to exist is a short-circuit &&.

Lowering &&

Before

x = (a != 0) && (10 / a > 1)

After

b0:  %2 = bool %0 != 0
     store @sc, %2
     branch %2 ? b3 : b4
b3:  %4 = int 10 / %0
     %5 = bool %4 > 1
     store @sc, %5
     jump b4
b4:  %6 = load @sc

Legal only when

Legal for any language in which && is specified to evaluate its right operand only when the left evaluates to true. The branch reproduces exactly that rule, and the temporary slot carries the result of whichever path ran. Both paths write the slot before the join reads it, so the value at b4 is defined on every path.

Illegal when

Lowering the same expression as a single binary instruction over two evaluated operands — %2 = bool %0 != 0; %5 = ...; %6 = %2 and %5 — is wrong for any short-circuiting language. On a == 0 the division executes and the program faults on the input the guard was written to protect against. It is equally wrong when the right operand merely has a side effect: flag && log("checked") would log unconditionally.

Why "three"

The name is historical arithmetic: result = operand op operand mentions three addresses. It is a description of the shape rather than a hard limit, and real IRs violate it constantly — a call names a destination, a callee and any number of arguments; a phi node names a destination and one operand per predecessor.

What survives from the name is the property that matters: each instruction performs at most one operation, and every operand is something already computed rather than something to compute. That property is what makes the sequence walkable one instruction at a time, and it is why an interpreter over three-address code is a short program while an interpreter over an expression tree is a recursive one.

The next constraint to add is that each name is assigned exactly once. That is not part of three-address code, it is a further restriction on top of it, and it is [[static-single-assignment]].

How it works

The steps, in the order the compiler takes them.

Traverse the expression tree in the language's specified evaluation order, children before parents.
For each leaf, emit an instruction that materialises the value into a fresh name — a constant, a load, or an incoming parameter.
For each internal node, emit one instruction applying its operator to the names its children produced, into a fresh name.
Return the name of the node's result to the parent, which uses it as an operand.
Detect short-circuit and conditional operators before this walk and lower them into branches and blocks instead, since they are control flow wearing the syntax of an operator.

How it breaks

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

A short-circuit operator is lowered as arithmetic, and a program that guarded against division by zero divides by zero anyway — on precisely the input the guard existed for, with no diagnostic anywhere.
Operands are evaluated in an order the language specifies differently, and a call whose arguments have side effects produces output in the wrong sequence. The program is correct under one compiler and wrong under another.
A temporary is reused for two values whose lifetimes overlap, and a value is silently overwritten. The wrong answer appears several instructions later with nothing linking it to the cause.
The lowering emits a temporary for a value that also has an observable identity — a volatile read, for example — and a later pass removes the "redundant" second read, changing what the hardware sees.

When it helps

Reading any IR dump. Once the pattern is familiar, an unoptimized listing reads as a linearised version of the source expression and the correspondence is mechanical.
Writing an interpreter or a bytecode compiler. Three-address code steps one instruction at a time, which makes both a loop rather than a recursion.
Debugging evaluation-order bugs. The IR dump states the order the compiler chose, which is faster and more reliable than reasoning about what the standard permits.

When it hurts

When you need to recognise a source-level pattern. Once flattened, a * b + c and a hand-written fused multiply-add look identical, and the frontend idiom that motivated a transformation may no longer be visible — which is part of why [[ir-levels]] exists.
For very large expressions, the temporary count is proportional to the operation count, and an unoptimized function can have thousands of live names before any promotion pass runs. That is compile-time memory that a tree-based IR would not spend.

What it costs

Every one of these is paid by something.

Naming every intermediate buys the ability to analyse and pays in instruction count and compile-time memory — an unoptimized function has one name per operation, and most of them exist for microseconds.
Fixing an evaluation order buys determinism and pays with the loss of a freedom the language may have granted, which can foreclose a reordering a later pass would have wanted.
One operation per instruction buys simple pass code and pays in listing length: the eleven-instruction dump for a two-line function is what readable-to-a-pass looks like, not what fast looks like.

What else you could do

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

Tree IR — GCC GENERIC, and most AST interpreters — keeps the nesting and never invents temporaries. Better for source-level pattern matching and diagnostics, worse for any analysis about values over time.
Stack-based IR, as in JVM bytecode and WebAssembly, leaves intermediates on an operand stack instead of naming them. More compact to encode and awkward to optimize directly, which is why JITs for both convert to a register or SSA form first — [[stack-vs-register-vm]].
Continuation-passing style names every intermediate *and* every control-flow point, which makes control flow and data flow uniform. It is the standard IR for functional-language compilers and considerably less familiar to read.
Sea-of-nodes drops the sequence entirely and keeps only dependencies, deciding order at scheduling time — the maximally opposite choice, discussed in [[ir-design-tradeoffs]].

See it for yourself

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

clang -S -emit-llvm -O0 -o - file.c shows the unoptimized three-address form with every temporary the frontend created; each %N is one.
python -m dis shows the stack-machine alternative for contrast — the same expression with no temporaries at all, because the operand stack does that job.
gcc -fdump-tree-gimple writes GIMPLE, which is GCC's three-address form and is explicitly documented as such.
Our IR explorer at /compilers/pipeline shows the AtlasLang IR panel: type an expression and watch the temporaries appear one per operator.

Plausible wrong readings

Stated the way a confident engineer states them.

"The temporaries are wasteful — the compiler is generating bad code." They are how the compiler generates good code. Every one of them is deleted or assigned a register before anything is emitted.
"Three-address code means at most three operands." It means at most three addresses in the classical arithmetic form. Calls and phi nodes have more, in every real IR.
"Three-address code is SSA." It is not. SSA additionally requires that each name is assigned exactly once, which three-address code does not — x = x + 1 is perfectly legal three-address code.
"The evaluation order in the dump is the order the CPU will use." It is the order the compiler committed to. Later passes may reorder anything unobservable, and the hardware reorders again beneath that.

Misconceptions

The claim, and what is actually true.

The compiler could skip the temporaries and generate the same code.

It could generate the same code for this expression. It could not run CSE, dead-code elimination, liveness or register allocation, because all four are defined over named values.

Each temporary becomes a stack slot or a register.

Most become nothing at all. They are deleted by promotion, folding and copy propagation long before the register allocator sees the function.

t1 = b * c means the multiplication definitely happens.

It means the compiler committed to a place for it in the sequence. If t1 turns out to be unused and multiplication cannot trap in this language, the instruction is removed — [[dead-code-elimination]].

Go deeper

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

overview

The compiler rewrites every expression so that each instruction does exactly one thing: x = a + b * c becomes a multiplication into a temporary, then an addition into another, then a store. The temporaries look like clutter, and they are the whole point — a value with a name is a value the compiler can make statements about.

practical

When you read an unoptimized IR dump, expect roughly one instruction per operator plus a load per variable read and a store per variable write. If the count is much higher, look for a short-circuit operator or a call that got expanded. If a value you expect to see once appears twice, that is a common subexpression the optimizer has not run on yet — and the dump at -O1 will usually show it collapsed.

advanced

The evaluation-order commitment made here is quietly one of the more consequential decisions in the frontend. C and C++ leave the order of function arguments unspecified, so a frontend may choose freely — and two compilers choosing differently is a genuine portability hazard that no diagnostic catches. Java and C# specify strict left-to-right, which removes the hazard and removes a reordering freedom the optimizer would otherwise have had. Neither choice is free: one buys portability of behavior, the other buys latitude for the backend, and the language committee pays for whichever it picks.

How much this depends on

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

typicalLLVM IR, GCC GIMPLE, Go SSA, Cranelift CLIF and AtlasLang IR are all three-address forms. JVM bytecode, CPython bytecode and WebAssembly are stack forms with no temporaries; V8 TurboFan is a graph with no instruction order until scheduling. The shape is dominant, not universal.

simplifiedAtlasLang names temporaries %0, %1 in a single global counter per function, and its listings show an untyped-looking %6 = int %4 * %5 where LLVM would show %6 = mul nsw i32 %4, %5. The missing piece is the overflow flag, and it is not cosmetic: it is what tells the optimizer whether it may assume the multiplication does not wrap.

If you were asked this in an interview

Rewrite x = a + b * c - d / e as three-address code, and tell me how many temporaries you needed and why.
Why can && not be lowered as a binary instruction?
What can a pass do with t1 that it could not do with the subtree b * c?

Connections

DSAbinary-tree dfs

Computer Architectureregisters

Domains that do not exist yet

Testing & Reliability Engineering — Property-based testing of a translation against a reference evaluator
The right way to convince yourself a lowering preserves meaning is to evaluate the tree and the instruction sequence on random inputs and compare — a general technique owned there, applied to compilers as [[differential-testing]].