Subtopic 6 of 7
9.6Available expressions
Expression x op y is available at p if on every path it is computed and its operands are not redefined afterwards. Forward, ∩ (must). Used for CSE.
Flow graph: B1→B2, B2→B3, B2→B4, B3→B2 (loop)
Available expressions (forward, ∩ must)
IN[B] = ∩ OUT[P] over predecessors P (entry IN = ∅)
OUT[B] = gen[B] ∪ (IN[B] − kill[B])
| Block | gen | kill |
|---|---|---|
| B1 | {x3} | {x1,x2} |
| B2 | {x1} | {} |
| B3 | {} | {x1,x2} |
| B4 | {} | {} |
x1: i+1 x2: s+i x3: n-1 (others start as the full set)
| Block | IN | OUT |
|---|---|---|
| B1 | {} | {x1,x2,x3} |
| B2 | {x1,x2,x3} | {x1,x2,x3} |
| B3 | {x1,x2,x3} | {x1,x2,x3} |
| B4 | {x1,x2,x3} | {x1,x2,x3} |
- Initialise
- Pass 1: something changed, iterate again
- Pass 2: 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.