← 🚀 Code Optimisation & Data-Flow
Subtopic 5 of 7

9.5Reaching definitions

A definition d reaches p if some path from d to p does not redefine the variable. Forward, ∪ (may). Used for constant propagation and loop-invariant detection.

Flow graph: B1→B2, B2→B3, B2→B4, B3→B2 (loop) Reaching definitions (forward, ∪ may) IN[B] = ∪ OUT[P] over predecessors P OUT[B] = gen[B] ∪ (IN[B] − kill[B])
Blockgenkill
B1{d1,d2}{d3,d4}
B2{}{}
B3{d3,d4}{d1,d2}
B4{d5}{}

d1: i=0 d2: s=0 d3: s=s+i d4: i=i+1 d5: r=s*2

BlockINOUT
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.