advancedData Flow
Liveness, reaching definitions, available expressions and constant propagation are four different analyses. What do they have in common?
Whether the candidate sees the framework or four unrelated algorithms. The discriminator is whether they can place a new analysis into the framework on the spot by naming its direction and meet operator.
What a strong answer covers
- They are all instances of one framework. You choose a lattice of facts, a transfer function that says how one instruction changes the facts, a direction, and a meet operator for combining facts where control flow merges. Then you iterate to a fixed point: initialize, apply transfer functions, propagate along edges, repeat until nothing changes. Termination is guaranteed when the lattice has finite height and the transfer functions are monotone.
- The four differ only in those choices. Liveness is backward, facts are sets of variables, and the meet is union — a variable is live if it is live on any successor path. Reaching definitions is forward, sets of definitions, union. Available expressions is forward, sets of expressions, intersection — an expression is available only if it is available on every path. Constant propagation is forward over a three-level lattice per variable, and its meet says that two different constants merge to "not a constant".
- Union versus intersection is the same distinction as "may" versus "must" analysis, and it decides the direction of conservatism. A may-analysis that is wrong says something might happen when it cannot, and you lose an optimization. A must-analysis that is wrong says something always happens when it does not, and you miscompile. That is why the safe default differs per analysis.
- The framework also tells you the limits. It is per-procedure unless you make it interprocedural, it is path-insensitive because merging discards which path you took, and it is only as good as its model of memory — which is where alias analysis re-enters and why almost every real analysis is conservative around loads and stores.
✓ Green flags
- Names all four components: lattice, transfer function, direction, meet.
- Places at least two analyses correctly on direction and meet.
- Explains may versus must in terms of which way an error is safe.
- Knows why the iteration terminates and what would break termination.
- Names path-insensitivity as an inherent precision limit, not a bug.
✗ Red flags
- "They all walk the CFG, so they are similar." True and useless — the shared thing is the fixed-point structure, not the traversal.
- "You just iterate until it stops changing" with no account of why it must stop.
- "Liveness is forward — you go through the program in order." It is backward: whether a value is needed depends on what comes after.
- "Constant propagation is just constant folding done repeatedly." Folding is a rewrite; propagation is the analysis that tells folding a value is a constant on every path.
Follow-up
I want to know, at each point, which variables might hold a value derived from user input. Give me the four components.
Implementation challenge
What to ask them to write or trace on a whiteboard.
Run liveness by hand on a four-block CFG with a loop. Show the in and out sets after each iteration and say how many iterations it took to reach the fixed point.