intermediateIR
Why do compilers have an intermediate representation at all, instead of going from AST to machine code?
Whether the candidate can name what the AST is bad at, rather than repeating the M-frontends-times-N-backends argument. That argument is correct and everyone has it; the discriminator is the analysis argument underneath.
What a strong answer covers
- The reuse argument is real: with an IR you write M frontends and N backends instead of M times N compilers, which is the whole basis of LLVM as infrastructure and the reason a new language can get a competent optimizer and twelve targets by lowering to an existing IR.
- The deeper reason is that the AST is the wrong shape for analysis. It is a tree, so evaluation order is implicit; it has one node kind per language construct, so every pass must handle every construct; and expressions nest, so intermediate values have no names to reason about. An IR fixes all three: order is explicit because it is a sequence, the instruction set is small and uniform so a pass handles ten cases instead of two hundred, and every intermediate value is named so a data-flow analysis has something to talk about.
- There is usually more than one IR, at different levels. A high-level IR still knows about language constructs — Rust's MIR still knows about borrows, Swift's SIL still knows about ownership — because some checks are only expressible there. A mid-level IR is language-independent and is where the classical optimizations live. A low-level machine IR knows about registers and addressing modes. Lowering is the step between each pair, and each step trades expressiveness for closeness to the machine.
- The costs: every IR is a serialization, a verifier, a printer and a set of invariants to maintain, and each lowering is a place where information is lost — which is why debug info has to be threaded through all of them, and why it so often is not.
✓ Green flags
- Gives the analysis argument, not only the M×N argument.
- Names explicit ordering and named intermediates as concrete benefits.
- Knows real compilers have several IRs and can name one language-specific one.
- Mentions verification and invariants as the maintenance cost.
- Says what each lowering loses.
✗ Red flags
- "The IR is portable assembly." It is not: LLVM IR has target-dependent details, and treating it as portable is how people ship bitcode that only works on one triple.
- "You could optimize the AST directly." You can do some of it, and every pass then has to know every language construct — which is why AST-level optimization is limited to peephole-ish rewrites.
- "The IR is the bytecode." A VM bytecode is designed to be executed; an IR is designed to be analysed, and the design pressures differ.
- "More IRs means a slower compiler." Multiple IRs usually make it faster, because each pass runs on a representation where its analysis is cheap.
Follow-up
Rust checks borrows on MIR rather than on LLVM IR. Why can that check not be done at the lower level?
Implementation challenge
What to ask them to write or trace on a whiteboard.
Lower if (a > b) { x = a * 2; } else { x = b + 1; } into three-address code with explicit labels and branches, and mark each temporary.