advancedSSA
Why is SSA useful?
Whether the candidate can connect a representation choice to the cost of the analyses built on it. The discriminator is whether they can name an analysis that becomes trivial and say what it used to cost.
What a strong answer covers
- In SSA every value is assigned exactly once, and every use names exactly one definition. That single property turns a large family of questions from analyses into lookups. "Which definition reaches this use?" is answered by the name itself, so reaching definitions is free. Constant propagation becomes: is this value defined by a literal? Copy propagation becomes: is this value a copy of another one? Both were data-flow problems and are now single-step tests.
- The reason it works is that the hard case — a value with different definitions on different paths — is made explicit instead of implicit. A phi node at a merge point says "this value is %a if we came from block 1 and %b if we came from block 2", which is not an instruction so much as a written-down fact about the control-flow graph.
- It also makes the use-def graph explicit, which is what dead code elimination, value numbering and most of the modern middle-end are written against. And it shrinks live ranges: distinct assignments to the same source variable become distinct values that can occupy different registers, which is why register allocation is usually done on SSA or just after leaving it.
- It is not free. Phi nodes have no machine encoding, so you must leave SSA before code generation, and that lowering inserts copies — and inserts them wrongly if a critical edge has not been split. Construction needs dominance frontiers. And memory is not in SSA in most compilers: loads and stores stay as they are until an alias analysis promotes them.
✓ Green flags
- States the invariant in one sentence — one definition per value — and immediately says what it buys.
- Names a specific analysis that gets simpler and what it cost before.
- Explains phi as a fact about predecessors, not as a runtime instruction.
- Knows you have to leave SSA, and that leaving it costs copies.
- Notes that memory usually is not in SSA, and that this is where alias analysis re-enters.
✗ Red flags
- "SSA makes the code faster." SSA is a representation. It makes analyses cheaper and more precise; the speed comes from the optimizations those analyses enable.
- "Phi nodes are executed at runtime, they pick a value based on a condition." Nothing evaluates a phi. It is resolved into copies on the incoming edges when SSA is left.
- "You can just number the variables x1, x2, x3 as you go." That works on straight-line code and fails at the first merge — which is exactly the case phi nodes exist for.
- "SSA removes the need for data-flow analysis." It removes the need for some of it. Liveness, availability across memory, and anything interprocedural are all still analyses.
Follow-up
Where do the phi nodes go, and how does the compiler decide? Then: what is a critical edge, and what goes wrong if you place the copies without splitting one?
Implementation challenge
What to ask them to write or trace on a whiteboard.
Take a diamond — an if/else where both arms assign x — and convert it to SSA by hand. Then convert it back out of SSA, writing the copies explicitly, and say which block each copy belongs in.