I just started reading about data flow analysis in compilers and I am trying to understand the concept of live-out variables. For this I read the algorithm to compute live-out variables in each bloc of a control flow graph. In the example link, I don't understand how they computed $LiveOutI_1$ for the $B_3$ block. Indeed $succ(B_3)=\{B_4\}$, $LiveOutI_0(B_4)=\emptyset$, $VarKill(B_4)=\emptyset$, $UEVar(B_4)=\{s\}$ so using the formula $$LiveOutI_1(B_3)=UEVar(B_4) \cup (LiveOutI_0(B_4) \cap \overline{VarKill(B_4)} ) = \{s\}\cup(\emptyset\cap\overline{\emptyset}) = \{s\}.$$ So why is the result $LiveOutI_1(B_3)=\{s,i\}$?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You are missing the fact that in the Control-Flow Graph, B1 is also a successor of B3 (notice the arrow from B3 to B1).
From B1, we will have:
$UEVar(B_1) \cup (LiveOutI_0(B_1) \cap \overline{VarKill(B_1)}) = i \cup (\emptyset \cap \overline{VarKill(B_1)}) = \{i\}$
And from B3, we have $\{s\}$ (as you computed correctly).
Together, we get $\{s, i\}$ as expected.
Hope this helps!
-- SG
