Discussion
Consider the control flow graph shown.
Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?
Answer: D
The live sets at block exits are B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}.
A variable is live at a point if some path from there uses it before redefining it. Work backwards from the uses, assuming nothing is live at EXIT:
- B2 uses i and j (i = i + 1, j = j - 1) before defining them, so both are live on entry to B2.
- B4 uses a, then redefines i. Its successors are B2 and EXIT, so live-out of B4 = live-in of B2.
- B3 defines a and uses nothing; B2 flows to B3 and B4.
Solving: live-in(B4) = {a} plus (live-out(B4) minus {i}) = {a, j}; live-in(B3) = {a, j} minus {a} = {j}; live-out(B2) = {j} plus {a, j} = {a, j}; live-in(B2) = {i, j} plus ({a, j} minus {i, j}) = {a, i, j}, which is live-out of both B1 and B4. B3's exit set is live-in(B4) = {a, j}.
The first two options drop i and j at B1's exit although B2 reads them at once. The third keeps i live after B2, but i is redefined in B4 before any use on that path.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development