We can say that a variable ‘v’ is live(at a statement ‘n’) if there exists a path in CFG from this statement to another statement ‘m’ such that ‘v’ is used in ‘m’ and for each n <= k < m and v is not defined in any statement k. simply, a variable is live(at a statement/point) if there exists a path in CFG where it is used before its modifying.
This question can be solved by definition and by using the algorithm.
Here, they’ve asked live variables at exit point of each basic block.
For B1 : there are 2 paths at exit of B1;
- B2, B3, B4 : In this path ‘i’, ‘j’ are live as they both are used before modifying. ‘a’ is not live as it is modified(defined) in B3 before being used in B4.
- B2, B4 : In this path ‘i’, ‘j’ & ‘a’ all three are live as all these are used before being modified (defined).
Thus, set of live variables at exit of B1 is {${a,i,j}$}.
For B2 : again there are 2 paths at exit of B2;
- B3, B4 : In this path, only ‘j’ is live because ‘a’ & ‘i’ both are dead as they have been defined before usage in B3 & B4 respectively and ‘j’ is being used before modifiying in B2 (we can reach B2 from B4 as there is loop).
- B4 : after B2, there’s a direct path to B4. Here, ‘a’ & ‘j’ are live because they are being used before definition in B4 & B2 respectively and ‘i’ is dead because it is being defined before use in B4.
Thus, set of live variables at exit of B2 is {${a,j}$}.
For B3 : In path B4 B2 B4 or B4 B2 B3, ‘a’ & ‘j’ are live and ‘i’ is dead because ‘i’ is defined before use in B4.
Thus, set of live variables at exit of B3 is {${a,j}$}.
For B4 : liveness analyisis is same as for B1 because paths at exit of B4 (B2 B3 B4 & B2 B4) are same for B1
except for EXIT (which doesn’t change the ans).
Thus, set of live variables at exit of B4 is {${a,i,j}$}.
