Project ForgeConsider the control flow graph shown: ENTRY→B1{i=m-1;j=n;a=10}→B2{i=i+1;j=j-1}, B2→B3{a=20}, B2→B4{i=a+1}, B3→B4, B4→EXIT, B4→B2 (loop back). Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?
- AB1: {}, B2: {a}, B3: {a}, B4: {a}
- BB1: {i,j}, B2: {a}, B3: {a}, B4: {i}
- CB1: {a,i,j}, B2: {a,i,j}, B3: {a,i}, B4: {a}
- B1: {a,i,j}, B2: {a,j}, B3: {a,j}, B4: {a,i,j}
Explanation
USE/DEF: B1 DEF={i,j,a}; B2 USE={i,j} DEF={i,j}; B3 DEF={a}; B4 USE={a} DEF={i}. B4 has TWO successors (EXIT and B2, via the loop-back edge), requiring fixed-point iteration since OUT[B4] depends on IN[B2] which depends on OUT[B2] which depends on IN[B4]/IN[B3] which depend on OUT[B4]. Iterating to convergence: OUT[B4]=IN[B2]={a,i,j}; IN[B4]=USE∪(OUT−DEF)={a}∪({a,i,j}−{i})={a,j}; OUT[B3]=IN[B4]={a,j}; IN[B3]={}∪({a,j}−{a})={j}; OUT[B2]=IN[B3]∪IN[B4]={j}∪{a,j}={a,j}; IN[B2]={i,j}∪({a,j}−{i,j})={i,j,a} (stable, matching the initial assumption). OUT[B1]=IN[B2]={a,i,j}. Final OUT sets: B1:{a,i,j}, B2:{a,j}, B3:{a,j}, B4:{a,i,j}.
Source: GATE CS 2023 (2023)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.