Subtopic 4 of 7
9.4Live-variable analysis
A variable is live at a point if its current value may be used later. Backward, ∪ (may). Used for dead-code elimination and register allocation.
Flow graph: B1→B2, B2→B3, B2→B4, B3→B2 (loop)
Live variables (backward, ∪ may)
OUT[B] = ∪ IN[S] over successors S
IN[B] = use[B] ∪ (OUT[B] − def[B])
| Block | use | def |
|---|---|---|
| B1 | {} | {i,s} |
| B2 | {i,n} | {} |
| B3 | {s,i} | {s,i} |
| B4 | {s} | {r} |
B1: i=0; s=0 B2: if i<n B3: s=s+i; i=i+1 B4: r=s*2 (gen = use, kill = def)
| Block | IN | OUT |
|---|---|---|
| B1 | {} | {} |
| B2 | {} | {} |
| B3 | {} | {} |
| B4 | {} | {} |
- Initialise
- Pass 1: something changed, iterate again
- Pass 2: something changed, iterate again
- Pass 3: no change: fixpoint reached
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.