Skip to content
GATEiit

GATE CSE 2023 Q37: Live variables at the exit of each block of a flow graph

Question

Consider the control flow graph shown.

Control flow graph: ENTRY to B1 (i = m − 1; j = n; a = 10), B1 to B2 (i = i + 1; j = j − 1). B2 goes to B3 (a = 20) and to B4 (i = a + 1); B3 goes to B4. B4 goes to EXIT and back to B2
Tap the figure to enlarge

Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: D (official GATE 2023 final answer key)

Concept used: Backward liveness: in[B]=use[B]∪(out[B]−def[B])\text{in}[B] = \text{use}[B] \cup (\text{out}[B] - \text{def}[B]), out[B]=⋃in[succ]\text{out}[B] = \bigcup \text{in}[\text{succ}].

First step: Start at B4: it uses aa, and its successor B2 uses ii and jj, so find in[B2]\text{in}[B2] first.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key

More Compiler Design PYQs

PracticePractise Compiler Design questions →Full paperAll GATE CSE 2023 questions →