advancedCFG
What does it mean for one basic block to dominate another, and what does a compiler do with that?
Whether the candidate can state a graph property precisely and then name a transformation whose legality depends on it. Reciting the definition is common; connecting it to a specific pass is not.
What a strong answer covers
- Block A dominates block B if every path from the entry to B passes through A. It is a property of the control-flow graph and the entry block, nothing else. Immediate dominator is the closest such A, and the immediate-dominator relation forms the dominator tree.
- What it buys is the phrase "on every path that reaches here". Common subexpression elimination may reuse an earlier computation only if the earlier one dominates the later — otherwise there is a path that reaches the use without having computed it. Loop-invariant code motion hoists into a preheader that dominates the loop body for the same reason. A value defined in A can be referenced in B without a phi exactly when A dominates B, which is the invariant SSA construction is maintaining.
- Natural loops are defined through dominance too: a back edge is an edge from a block to one of its dominators, and the loop is the set of blocks that can reach the source of that back edge without passing through the header. That definition is what makes "is this a loop" answerable in a graph full of gotos.
- The dominance frontier is the piece that turns this into SSA. The frontier of A is the set of blocks that A does not strictly dominate but that have a predecessor A does dominate — precisely the merge points where a definition in A meets a definition from elsewhere. Insert phi nodes at the iterated dominance frontier of every definition and you have SSA.
✓ Green flags
- States the definition in terms of all paths from entry, not "comes before".
- Names a pass whose legality condition is dominance and explains why.
- Defines back edges and natural loops through dominance.
- Knows the dominance frontier is what phi placement is computed from.
- Mentions post-dominance as the dual and something it is used for, such as control dependence.
✗ Red flags
- "A dominates B if A comes before B in the source." Source order and graph order diverge the moment there is a branch or a goto.
- "Dominance is about loops." Loops are one use; it is a general property of the CFG that most middle-end passes depend on.
- "Every block dominates its successors." Only if the successor has no other predecessor — which is exactly the case where phis are unnecessary.
- "You compute it once at the start." Every transformation that changes the CFG invalidates it, and forgetting to recompute it is a real and nasty class of compiler bug.
Follow-up
A pass splits a block in two and forgets to update the dominator tree. What kind of miscompilation would you expect, and when would it show up?
Implementation challenge
What to ask them to write or trace on a whiteboard.
Draw a CFG with a diamond and a loop. Write the immediate dominator of every block, draw the dominator tree, and mark the dominance frontier of the block that assigns inside the loop.