What does flattening expressions into three-address instructions with temporaries expose that an expression tree leaves implicit?
answer
- one operator per instruction
- nested expressions get compiler-made names
- order stops being a traversal choice
- each name has one defining instruction
- jumps and labels replace nesting
basics
~20 sThree-address code gives every intermediate value a name and every operation its own instruction in a fixed order. Evaluation order and the producer of each value become explicit data rather than facts implied by a tree walk.
solid answer
~50 sIn three-address code each instruction carries at most one operator and roughly three operand slots — `dst = src1 op src2` — so a nested expression is flattened with compiler-generated temporaries. `d = (a + b) * (a - c)` becomes `t1 = a + b`, `t2 = a - c`, `t3 = t1 * t2`, `d = t3`: three operator instructions, one per operator node, plus a copy. Two things that a tree only implies are now written down. **Evaluation order** is the instruction order, rather than something a traversal decides. And **every intermediate value has a name**, so each temporary has one instruction that defines it and a set of instructions that use it. That turns questions a tree answers by re-walking — where does this value come from, is it still needed, do two places compute the same thing — into lookups over a flat list, which is why later rewrites are easier at this level than on the tree.
code
pseudocode · 16 linesfunction flatten(node):
if node is a leaf:
return node.name // a variable or constant
left = flatten(node.left) // a name
right = flatten(node.right) // a name
t = new_temp() // fresh, never reused
emit(t, "=", left, node.op, right)
return t // the name of this subtree's value
// flatten(parse of "(a + b) * (a - c)") emits:
// t1 = a + b
// t2 = a - c
// t3 = t1 * t2
// and returns t3go deeper
Recall that before machine code the compiler rewrites expressions into a flat list of very simple steps, each computing one thing into a name the compiler invented.
Be able to flatten a two-operator expression on the spot, count the temporaries you introduced, and explain that the list makes evaluation order and each value's producer explicit.
Show that you know the trade: the flat form buys explicit order and def-use relationships but destroys higher-level shape, which is why a real compiler keeps more than one level rather than flattening at once.
Treat the level as an interface. How much structure the flat form preserves decides which rewrites are ever possible in your compiler, and that choice is far harder to reverse than any individual pass.
## What the form is **Three-address code** is a linear intermediate representation. Each instruction has **at most one operator** and at most three operand positions: a destination and up to two sources. The name comes from those three addresses. Typical instruction kinds are: - a binary operation, `t3 = t1 * t2` - a unary operation, `t4 = -t3` - a copy, `d = t3` - an unconditional jump, `goto L` - a conditional jump, `if t1 > t2 goto L` - a label marking a jump target Anything that does not fit — a nested expression, a chained comparison — is broken up, and each broken-out piece gets a **temporary**: a compiler-generated name that did not exist in the source. ## The flattening, step by step For `d = (a + b) * (a - c)`: ``` t1 = a + b t2 = a - c t3 = t1 * t2 d = t3 ``` Count them: the expression has three operator nodes, so the flattening introduces exactly **three temporaries**, plus one copy into the destination. (A front end that is slightly smarter writes `d = t1 * t2` and skips the copy; a straightforward recursive emitter produces the copy and leaves it to be cleaned up later.) The emitter itself is a post-order walk: flatten the left child to a name, flatten the right child to a name, allocate a fresh temporary, emit one instruction, and return the temporary as the name of the whole subtree. ## What becomes explicit | Fact | On the tree | In three-address code | |---|---|---| | Evaluation order | Implied by how you traverse | The instruction order, written down | | Intermediate values | Anonymous — a subtree's result | Each has a name you can refer to | | Where a value came from | Found by re-walking the subtree | The one instruction that assigns that name | | Control flow | Implied by nested constructs | Explicit labels and jumps | | "Same computation twice" | Structural comparison of subtrees | Two instructions with the same operator and operand names | The last two rows matter more than they look. **Explicit control flow** is what lets the instruction stream be cut into **basic blocks**: maximal runs with one entry at the top and no jump out until the end. Blocks and the edges between them are a graph, and a graph is something you can compute over. A tree of nested loops and conditionals does not give you that directly. **Named intermediates** are what make *definition* and *use* into first-class relationships. For any temporary you can point at the instruction that defines it and list the instructions that read it. A rewrite that wants to replace an instruction, delete one whose result nobody reads, or notice that two instructions compute the same thing is now working with names and a list, not with subtree identity. ## Why the lower level makes rewrites easier This is the question behind the question. A rewrite is easy when the thing it must reason about is **written down** rather than **implied**. On a tree, "this value is computed before that one" is a property of the traversal you happen to run; in the flat form it is a property of the program text. On a tree, "this value is used twice" requires recognising that two subtrees are structurally equal; in the flat form it is two uses of one name. The trade runs the other way too, and a good answer says so. Flattening **loses** shape: once a counted loop has become tests and jumps, a rewrite that needed to see "this is an iteration over a window" can no longer see it. That is why compilers commonly keep more than one level rather than flattening everything immediately. ## Practical notes - Temporaries are typically unbounded in number at this stage; the mapping onto a finite set of machine registers happens further down. - The number of temporaries a naive emitter produces is one per operator node, which is why the form looks verbose next to the source. - The form is deliberately close to a simple machine but not tied to one: three operand slots and explicit jumps describe most targets without committing to any. ## What interviewers listen for The strong answer flattens a small expression correctly on the spot, counts the temporaries, and then names what the flat form exposes — order and provenance — rather than just asserting "it is closer to machine code". The weak answer treats the flat form as merely verbose, with no account of what the verbosity buys.
- Why does the flat form need explicit labels and jumps rather than nested constructs?Because explicit jumps let the instruction stream be split into basic blocks — runs with a single entry and an exit at the end — and the blocks plus their edges form a graph. Analyses are defined over that graph. Nested constructs imply the same edges but do not hand them to you.
- What is lost by flattening, and how do compilers cope with the loss?High-level shape. Once an iteration construct has become a test and two jumps, no pass can recognise it as an iteration without reconstructing that fact. Compilers cope by keeping a higher-level representation alongside or above the flat one, and doing shape-dependent work while the shape still exists.
- Are the temporaries the same thing as machine registers?No. At this level they are an unbounded supply of names, one per operator node in the worst case. Mapping them onto a finite register file, and spilling the ones that do not fit, is a separate job done much further down the pipeline.
It is the difference between handing in a long calculation as one line and writing every intermediate step on its own numbered line. The second is longer, but a reviewer can point at exactly the step that is wrong and at every later step that used it.
saying these in an interview costs you the question
- Thinks three-address code means exactly three operands, always
- Says the flat form is only verbose with no benefit
- Believes temporaries are machine registers at this stage
- Claims flattening loses nothing that later passes want
- Expects nested expressions to survive inside one instruction