Subtopic 7 of 7
9.7Data-flow framework at a glance
Each analysis picks a direction (forward/backward), a meet (∪ or ∩), and gen/kill sets per block, then iterates to a fixed point. Initialisation: ∅ for ∪-analyses, universal set for ∩-analyses.
| Analysis | Direction | Meet | Initial value | Used for |
|---|---|---|---|---|
| Reaching definitions | Forward | ∪ (may) | ∅ | constant propagation, loop invariants |
| Live variables | Backward | ∪ (may) | ∅ | dead code, register allocation |
| Available expressions | Forward | ∩ (must) | universal set (entry: ∅) | common subexpression elimination |
| Very busy expressions | Backward | ∩ (must) | universal set | code hoisting |
"May" analyses start at ∅ and grow; "must" analyses start at the universal set and shrink.
Previous year questions: Code Optimisation & Data-Flow (3)
PYQs are grouped by topic, so this is the full set for Code Optimisation & Data-Flow; try the ones that match this subtopic. Open all 3 on the topic page.