Algorithm 3.3 Reaching-Definitions

Input: CFG ( $kill_B$ and $gen_B$ computed for each basic block $B$ )

Output: $IN[B]$ and $OUT[B]$ for each basic block $B$

1: $OUT[ENTRY] = \empty$

2:for each basic block $B\in V(CFG) - \{ENTRY\}$ do

3: $OUT[B] = \empty$

4:end for

5:repeat

6:for each basic block $B\in V(CFG) - \{ENTRY\}$ do

7: $IN[B] = \bigcup\limits_{P\in pre(B)} OUT[P]$

8: $OUT[B] = gen_B\cup (IN[B] - kill_B)$

9:end for

10:until no changes to any $OUT[B]$ of basic block $B\in V(CFG) - \{ENTRY\}$ occur