Consider the control flow graph with basic blocks B1 (j=n; a=10), B2 (i=i+1; j=j-1), B3 (i=a+1; a=20

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2023 GATE-CS Compiler Design paper.

Q: How can I prepare for GATE-CS Compiler Design?

To prepare for GATE-CS Compiler Design, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2023 question covers Data Flow Analysis (Constant Propagation, Liveness, CSE) topic.

Q: What is the difficulty level of this question?

This GATE-CS 2023 Compiler Design question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Consider the control flow graph with basic blocks B1 (j=n; a=10), B2 (i=i+1; j=j-1), B3 (i=a+1; a=20), B4 (i=m-1). Which one of the following correctly lists the set of live variables at the exit of each basic block?

Accepted Answer

Correct Answer: (D)Concept -- Live Variable Analysis (from the Dragon Book by Aho et al., Chapter 9; Data Flow Analysis):A variable is live at a point if there is a path from that point to a use of the variable before any redefinition. Live variable analysis is performed backward.Based on the control flow graph in the GATE 2023 paper (with the specific edges and uses in each block), backward dataflow analysis yields:B4 (entry block, i=m-1): At exit of B4, the variables used subsequently are {a, i, j} -- all three are used in subsequent blocks.B1 (j=n; a=10): After B1, the loop uses i, j (for control), and a (in B3). Live variables at exit = {a, i, j}.B2 (i=i+1; j=j-1): Uses i and j (already defined in B2 itself for the loop). At exit, a is used in B3, j may be checked. Live variables = {a, j}.B3 (i=a+1; a=20): a is used (a+1), then a is redefined (a=20). At exit, a (the new value 20) and j are live for subsequent loop iterations. Live variables = {a, j}.Option (D) correctly captures this analysis.

Consider the control flow graph with basic blocks B1 (j=n; a=10), B2 (i=i+1; j=j-1), B3 (i=a+1; a=20), B4 (i=m-1). Which one of the following correctly lists the set of live variables at the exit of each basic block?

Master GATE-CS with Our Test Series

More Questions from Data Flow Analysis (Constant Propagation, Liveness, CSE)

Frequently Asked Questions

Consider the control flow graph with basic blocks B1 (j=n; a=10), B2 (i=i+1; j=j-1), B3 (i=a+1; a=20), B4 (i=m-1). Which one of the following correctly lists the set of live variables at the exit of each basic block?

Master GATE-CS with Our Test Series

More Questions from Data Flow Analysis (Constant Propagation, Liveness, CSE)

Frequently Asked Questions