Data-Flow Dependence Analysis
1. Purpose
Data-flow analysis tracks how values flow across the CFG: what definitions reach a point, what is live, what is available — to prove an optimization safe. Dependence analysis adds read/write ordering (RAW/WAR/WAW) for reordering/parallelism.
2. Classic Analyses (exam table)
| Analysis | Question | Direction |
|---|---|---|
| Reaching definitions | which writes may reach here? | forward |
| Live variables | whose value used later? | backward |
| Available expressions | already computed (no redefinition)? | forward |
| Very busy / U-D chains | used on all paths? def-use links? | backward / both |
Equations: OUT[B] = GEN[B] ∪ (IN[B] − KILL[B]) iterated to fixpoint.
3. Dependences
RAW (flow): write → read (true) — must preserve order
WAR (anti): read → write — rename fixes
WAW (output): write → write — second kills first
Loop a[i]=a[i-1]+1 has loop-carried RAW (distance 1) → cannot parallelize directly.
4. Use in Opt
- Common-subexpr needs available; dead-code needs live; constant prop needs reaching const defs.
5. Exam Points
- Define 4 data-flow analyses + equations — 7 marks, very frequent.
- RAW/WAR/WAW with example — 5 marks, frequent.
- Loop-carried dependence + distance — 3-5 marks, frequent.