GATE CS

Local optimisation and data-flow analysis

Local optimisation improves code inside a basic block (common subexpressions via a DAG, constant folding, copy propagation, dead-code removal, peephole clean-ups), while data-flow analysis computes facts such as live variables, reaching definitions, available expressions and constants across the whole control-flow graph by solving equations to a fixed point. GATE questions ask you to find basic blocks, build the DAG of a block, write gen/kill or use/def sets, iterate IN and OUT to a fixed point, read off what is live, available or constant at a point, and count the registers an interference graph needs.

6 previous-year questions · 6 solved · 6 practice questions

Basic blocks and the control-flow graph

A basic block is a maximal sequence of consecutive three-address instructions with one entry (the first instruction) and one exit (the last): control enters only at the top and leaves only at the bottom, with no jump into or out of the middle. Statements are numbered in the printed order. A control-flow graph (CFG) has one node per basic block and an edge $B_{1} \to B_{2}$ if control can pass from the end of $B_{1}$ to the start of $B_{2}$ . There is one entry block; a block with no successor is an exit block.

Finding leaders (the first instruction of each block)

The first instruction of the program is a leader.
The target of any conditional or unconditional jump is a leader.
The instruction that immediately follows a conditional or unconditional jump is a leader.

Partitioning and building the CFG

Mark every leader by the three rules above.
Each block runs from a leader up to, but not including, the next leader (or the end of the program).
Add an edge from block $B$ to the block starting at the jump target if $B$ ends in a jump.
Add an edge from $B$ to the next block in printed order if $B$ ends in a conditional jump or in an ordinary instruction (not in an unconditional goto).
An unconditional goto contributes only the jump edge; no fall-through edge.
A block that ends in return or halt has no outgoing edge.

WORKED EXAMPLE

Find the basic blocks and the CFG edges of:

1: i = 1
2: s = 0
3: if i > 10 goto 7
4: s = s + i
5: i = i + 1
6: goto 3
7: x = s
8: y = x + 1

Solution

Leader 1 (first instruction).
Leaders 3 and 7 are jump targets (from instruction 6 and from instruction 3).
Leader 4 follows the conditional jump in 3; leader 7 also follows the goto in 6.
Leaders: 1, 3, 4, 7. Blocks: $B_{1} = {1, 2}$ , $B_{2} = {3}$ , $B_{3} = {4, 5, 6}$ , $B_{4} = {7, 8}$ .
Edges: $B_{1} \to B_{2}$ (fall through); $B_{2} \to B_{4}$ (jump taken) and $B_{2} \to B_{3}$ (fall through); $B_{3} \to B_{2}$ (the goto 3; no fall-through because it ends in an unconditional jump).

Answer: 4 blocks; edges B1→B2, B2→B3, B2→B4, B3→B2.

Block $d$ dominates block $n$ if every path from the entry to $n$ passes through $d$ ; every block dominates itself, and the entry dominates every block. An edge $n \to d$ in which $d$ dominates $n$ is a back edge. Its natural loop is $d$ (the loop's header) together with every block that can reach $n$ without passing through $d$ . The header dominates every block of the loop, and control can enter the loop only through the header. In the example above, every path from $B_{1}$ to $B_{3}$ passes through $B_{2}$ , so $B_{2}$ dominates $B_{3}$ ; hence $B_{3} \to B_{2}$ is a back edge and its natural loop is ${B_{2}, B_{3}}$ with header $B_{2}$ .

Local optimisation inside a basic block

Local optimisation looks at one block at a time. Within a block there are no branches, so every fact can be tracked by a single top-to-bottom (or bottom-to-top) scan. Only the values that are live when the block ends must be preserved.

Local transformations

Transformation	What it does	Condition
Constant folding	Evaluate an operation on constants at compile time: `x = 2 * 8` becomes `x = 16`	All operands are known constants
Constant propagation (local)	Replace a use of `x` by the constant assigned to it earlier in the block	`x` has not been reassigned in between
Copy propagation	After `x = y`, replace later uses of `x` by `y`	Neither `x` nor `y` is reassigned in between
Common subexpression elimination (CSE)	Reuse the value of an expression already computed instead of computing it again	No operand was redefined between the two computations
Dead-code elimination	Delete an assignment whose target is never used afterwards	Target is not live after the statement, and the statement has no side effect
Algebraic simplification	`x + 0`, `x * 1`, `x - 0` become `x`; `x * 0` becomes `0`	Identity holds for the type
Strength reduction	Replace a costly operation by a cheaper one: `x * 2` becomes `x + x` or a left shift; `x ** 2` becomes `x * x`	Result is identical
Peephole optimisation	Examine a short window of instructions: delete a store straight back to the location just loaded (`R0 = a` then `a = R0`), remove unreachable code, replace a jump to a jump by a single jump	No deleted instruction carries a label (is a jump target)

Building the DAG of a block (for CSE and dead code)

Process the statements in order. For a statement x = y op z, find the node currently holding y and the node holding z; if a variable has none yet, create a leaf for its initial value.
If a node labelled op with exactly those two children already exists, reuse it; otherwise create it. This reuse is the common-subexpression elimination.
Attach the label x to that node, and remove x from any other node it was attached to.
For x = y, attach x to the node of y (no new node).
A later reference to a variable always uses the node it is attached to now, so a redefined operand produces a new node, not a reuse.
Unless told otherwise, + and * are commutative, so a + b and b + a give the same node.
At the end, delete any root node (a node no other node uses) that carries no live-out label, and repeat until none is left; this is dead-code elimination. A node with no live label is still computed (into a temporary) if a kept node uses it. For a node with several live labels, compute it once and copy it to the others.

DAG walk-through of: a = b + c; b = a - d; c = b + c; d = a - d (all four variables live at exit)

Statement	Action on the DAG	Result
a = b + c	Leaves $b_{0}$ , $c_{0}$ ; new node $N_{1} = + (b_{0}, c_{0})$	$N_{1}$ labelled a
b = a - d	Leaf $d_{0}$ ; new node $N_{2} = - (N_{1}, d_{0})$	$N_{2}$ labelled b
c = b + c	b is now $N_{2}$ , c is still $c_{0}$ : $+ (N_{2}, c_{0})$ is new, so it is not the same as $N_{1}$	$N_{3}$ labelled c
d = a - d	a is $N_{1}$ , d is still $d_{0}$ : $- (N_{1}, d_{0})$ already exists as $N_{2}$	$N_{2}$ now labelled b, d

Reading the DAG back gives the optimised block: a = b + c, b = a - d, c = b + c, d = b. There are 3 operator nodes instead of 4 operations, because d = a - d recomputes the value already held in b; the third + cannot be shared with the first since b changed.

EXAM TIP

When a question asks for the number of nodes in a DAG, check whether it counts the leaves (initial values of variables, and constants) as well as the operator nodes. The walk-through above has 3 leaves ( $b_{0}$ , $c_{0}$ , $d_{0}$ ) and 3 operator nodes, so 6 nodes in all.

EXAM TIP

Do not eliminate x + y the second time if x or y was assigned in between, even if the printed expression looks identical. A DAG handles this automatically; by hand, check every assignment between the two occurrences.

Global data-flow analysis: the framework

Global analysis computes, for every block $B$ , a set $IN [B]$ (facts true at the start of $B$ ) and $OUT [B]$ (facts true at its end) by solving a system of equations over the CFG. Each block has a transfer function built from per-block sets. A forward analysis computes IN from the predecessors' OUT; a backward analysis computes OUT from the successors' IN. A may analysis (a fact holds on some path) joins with union and starts from the empty set; a must analysis (a fact holds on all paths) joins with intersection and starts from the universal set. Conventions: unless stated, the CFG has a single entry block and the sets at the program boundary are empty; in a statement x = y op z the operands are read before x is written, so x = x + 1 reads x before assigning it.

Per-block sets. Liveness: $use [B]$ = variables read in $B$ before any assignment to them in $B$ ; $def [B]$ = variables assigned in $B$ (a variable both read first and assigned is in both sets, which gives the same IN as listing it only in use). Reaching definitions: $gen [B]$ = the definitions in $B$ that survive to the end of $B$ (the last definition of each variable assigned in $B$ ); $kill [B]$ = all other definitions, anywhere in the program, of the variables assigned in $B$ . Available expressions: $e_gen [B]$ = expressions evaluated in $B$ none of whose operands is assigned later in $B$ , counting the statement's own target (x = x + y does not generate x + y); $e_kill [B]$ = every expression of the program that has an operand assigned in $B$ (the union with $e_gen$ puts back any expression recomputed after the assignment).

LIVE VARIABLES (BACKWARD, UNION)

IN [B] = use [B] \cup (OUT [B] - def [B]), OUT [B] = S \in succ (B) ⋃ IN [S]

A variable is live at a point if its current value may be read later before being overwritten. Initialise IN[B] = ∅ for all B; OUT of an exit block is ∅ unless the question names live-out variables.

REACHING DEFINITIONS (FORWARD, UNION)

OUT [B] = gen [B] \cup (IN [B] - kill [B]), IN [B] = P \in pred (B) ⋃ OUT [P]

A definition reaches a point if some path from it to that point does not redefine the variable. Initialise OUT[B] = ∅; IN[entry] = ∅.

AVAILABLE EXPRESSIONS (FORWARD, INTERSECTION)

OUT [B] = e_gen [B] \cup (IN [B] - e_kill [B]), IN [B] = P \in pred (B) ⋂ OUT [P]

An expression is available at a point if on every path to it the expression has been computed and its operands not changed since. IN[entry] = ∅; initialise OUT[B] to the set U of all expressions for every other block.

The three bit-vector analyses side by side

Analysis	Direction	Join (meet)	Initial value	Boundary	Used for
Live variables	Backward	Union	IN[B] = ∅	OUT[exit] = ∅	Dead-code elimination, register allocation
Reaching definitions	Forward	Union	OUT[B] = ∅	IN[entry] = ∅	Constant/copy propagation, loop-invariant checks
Available expressions	Forward	Intersection	OUT[B] = U (all expressions)	IN[entry] = ∅	Global common subexpression elimination

Iterative algorithm to a fixed point

Compute the per-block sets (use/def, gen/kill or e_gen/e_kill).
Set every IN or OUT to its initial value (empty for may analyses, U for must analyses, except at the boundary).
Sweep over the blocks, recomputing the sets with the equations. Backward problems need fewest passes visiting blocks in postorder (successors before predecessors where possible); forward problems in reverse postorder. The order changes only the number of passes, not the final sets.
Repeat until a whole sweep changes nothing. This terminates because every set only grows (may) or only shrinks (must) and is bounded.
To read a fact at a point inside a block, start from IN[B] (forward) or OUT[B] (backward) and apply the block's instructions one at a time.

EXAM TIP

Check the join before iterating. Liveness and reaching definitions take a union over successors or predecessors; available expressions take an intersection. Starting available expressions from the empty set instead of U gives sets that are too small: an expression that is available all round a loop is lost at the loop header, because the header's IN intersects with the back-edge OUT while that is still empty.

Constant propagation as a data-flow problem

Global constant propagation tracks, for every variable at every point, one of three values: undefined (no assignment has reached it yet, written $⊤$ ), a constant $c$ , or NAC (not a constant, written $⊥$ ). The analysis is forward, and at a join point the incoming values of each variable are combined by the meet in the table below. Transfer rule for $x = y op z$ : if $y$ or $z$ is NAC, $x$ becomes NAC; if both are constants, $x$ becomes the computed constant; otherwise (an operand undefined and none NAC) $x$ stays undefined. A copy $x = y$ gives $x$ the value of $y$ ; a value read from input or returned by a call is NAC. Convention used here: every variable is undefined at the entry and in every block before the first pass; a question may instead treat the program's inputs as NAC at the entry.

Meet of two incoming values for one variable at a join point

Value on path 1	Value on path 2	Result at the join
undefined	$c$	$c$
$c$	$c$ (same constant)	$c$
$c_{1}$	$c_{2}$ with $c_{1} \neq = c_{2}$	NAC
NAC	anything	NAC
undefined	undefined	undefined

Example: two paths join, then z = x + y and w = x + 1 execute

Variable	On path 1	On path 2	At the join
x	2	2	2
y	3	4	NAC
z = x + y			NAC (y is NAC)
w = x + 1			3 (x is the constant 2)

EXAM TIP

Unlike liveness or reaching definitions, constant propagation is not a bit-vector problem, and it is not distributive. If $x = 2, y = 3$ on one path and $x = 3, y = 2$ on the other, then $x + y = 5$ on both paths, yet the per-variable meet makes $x$ and $y$ NAC and so reports $x + y$ as NAC. Apply the meet table at each join and then the transfer rule, unless the question says otherwise.

Worked example: liveness to a fixed point

WORKED EXAMPLE

CFG with entry $B_{1}$ , edges $B_{1} \to B_{2}$ , $B_{2} \to B_{2}$ , $B_{2} \to B_{3}$ :

B1: a = 1
    b = 2
B2: c = a + b
    d = c * 2
    if d < 50 goto B2   (otherwise fall into B3)
B3: e = d + b
    return e

Nothing is live after the return. Find the live variables at the exit of $B_{2}$ and at the entry of $B_{1}$ .

Solution

use/def: $B_{1}$ : use = ∅, def = {a, b}. $B_{2}$ : c = a + b reads a, b; d = c * 2 reads c (already defined in the block); the test reads d (defined in the block). So use = {a, b}, def = {c, d}. $B_{3}$ : e = d + b reads d, b; return e reads e (defined in the block). So use = {b, d}, def = {e}.
Pass 1, reverse order. $B_{3}$ : OUT = ∅, IN = {b, d}. $B_{2}$ : OUT = IN[B2] ∪ IN[B3] = ∅ ∪ {b, d} = {b, d}; IN = {a, b} ∪ ({b, d} − {c, d}) = {a, b}. $B_{1}$ : OUT = IN[B2] = {a, b}; IN = ∅ ∪ ({a, b} − {a, b}) = ∅.
Pass 2. $B_{3}$ unchanged. $B_{2}$ : OUT = {a, b} ∪ {b, d} = {a, b, d}; IN = {a, b} ∪ ({a, b, d} − {c, d}) = {a, b}. $B_{1}$ : OUT = {a, b}, IN = ∅. OUT[B2] has changed, so another pass is needed.
Pass 3 changes nothing, so the fixed point is reached: OUT[B2] = {a, b, d}, IN[B2] = {a, b}, IN[B1] = ∅.

Answer: Live at the exit of B2: {a, b, d}. Live at the entry of B1: none.

EXAM TIP

Variable a is live at the exit of $B_{2}$ only because the loop edge $B_{2} \to B_{2}$ reads it again at the top of $B_{2}$ . When a block is its own successor, its IN set feeds its OUT set, which is why one pass is not enough.

Loops: invariant code motion and induction variables

A statement $x = y op z$ in a loop is loop-invariant if each operand is a constant, or has all its reaching definitions outside the loop, or has exactly one reaching definition and that definition is a statement inside the loop already marked invariant. Mark statements repeatedly until nothing new is marked. An invariant statement can be moved to a pre-header, a new block placed just before the loop header through which every entry into the loop passes.

Conditions for moving an invariant statement x = y op z to the pre-header

The statement's block dominates every exit of the loop at which $x$ is live out (if $x$ is live at no exit, this holds trivially).
$x$ is assigned only once in the loop.
No use of $x$ in the loop is reached by any definition of $x$ other than this statement.

An induction variable changes by a constant amount each iteration. A basic induction variable $i$ has only assignments of the form $i = i + c$ or $i = i - c$ in the loop, with $c$ a loop constant. A derived induction variable $j$ is assigned once in the loop as a linear function of a basic one, $j = c_{1} \cdot i + c_{2}$ . Strength reduction removes the multiplication: for $j = 4 \cdot i$ with the update $i = i + c$ , place $j = 4 \cdot i$ in the pre-header, insert $j = j + 4 c$ immediately after each update of $i$ , and delete the multiplication from the loop, since $j$ now always equals $4 \cdot i$ . After this, $i$ can be eliminated if its only remaining uses are its own update and the loop test; the test is rewritten in terms of $j$ (for example $i < n$ becomes $j < 4 n$ , with $4 n$ computed in the pre-header).

Register allocation by graph colouring

The interference graph has one node per variable (or live range) and an edge between two nodes if they are live at the same time. Convention: two variables interfere if one is live immediately after an instruction that defines the other. A value that dies at an instruction can therefore share a register with the value that instruction defines: in x = y + z with y not live afterwards, $x$ and $y$ do not interfere. Interfering variables need different registers, so allocating with $k$ registers means colouring the graph with $k$ colours.

Colouring with k registers (simplify and select)

Pick a node with fewer than $k$ neighbours and remove it from the graph, pushing it on a stack. Such a node can always be coloured after the rest.
Repeat until the graph is empty. If every remaining node has $k$ or more neighbours, choose one to spill (keep in memory), remove it and continue.
Pop the nodes in reverse order, giving each a colour not used by its already-coloured neighbours.
The fewest registers that need no spill is the chromatic number of the graph, which is at least the size of the largest clique. The simplify heuristic is not exact: it can spill on a graph that does have a $k$ -colouring.

For a single basic block with no branches, when each variable's live range is one interval (for example, each variable is assigned at most once in the block, or each live range is treated as its own node), the interference graph is an interval graph, so the fewest registers needed equals the largest number of variables live at any one point. Count the variables live on entry to the block and just after each instruction, taking into account the sharing rule above.

EXAM TIP

A triangle (three mutually interfering variables) already forces 3 registers, but 3 colours are not enough for every graph with no 4-clique. Check the graph with an actual colouring before stating the answer if the question does not say it is a block.

PREVIOUS-YEAR QUESTIONS

6 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2024 Set 1 · GATE CSE 2023

GATE 2026 CS1 Q.42

GATE 2026 · CS1Q.42 · 2 marks · MCQ

Consider the control flow graph shown in the figure.

Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5?

Note: All the variables are integers.

GATE 2026 CS1 question 42: Control flow graph. — Figure from the GATE 2026 CS1 paper. It is part of the question.

(A)
B4: { b + i }; B5: { c + m }
(B)
B4: { g * k }; B5: { c + m }
(C)
B4: { g * k, b + i }; B5: { }
(D)
B4: { g * k }; B5: { }

Answer and solution

GATE 2026 CS1 Q.42: answer and solution

GATE 2026 CS2 Q.45

GATE 2026 · CS2Q.45 · 2 marks · MCQ

Consider the control flow graph given below.

Which one of the following options is the set of live variables at the exit point of each basic block?

GATE 2026 CS2 question 45: Control flow graph. — Figure from the GATE 2026 CS2 paper. It is part of the question.

(A)
B1:{a, b, c, e, f}, B2:{d, e}, B3:{b, c, e, f}, B4:∅
(B)
B1:∅, B2:{d, e}, B3:{a, c, f}, B4:∅
(C)
B1:{a, b, c, e, f}, B2:{d, e}, B3:{c, e, f}, B4:∅
(D)
B1:∅, B2:{d, e, f}, B3:{a, b, c, e, f}, B4:∅

Answer and solution

GATE 2026 CS2 Q.45: answer and solution

GATE 2025 CS1 Q.13

GATE 2025 · CS1Q.13 · 1 mark · MCQ

Which ONE of the following techniques used in compiler code optimization uses live variable analysis?

(A)
Run-time function call management
(B)
Register assignment to variables
(C)
Strength reduction
(D)
Constant folding

Answer and solution

GATE 2025 CS1 Q.13: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.13: answer and solution

GATE 2025 CS1 Q.52

GATE 2025 · CS1Q.52 · 2 marks · NAT

Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is ________. (Answer in integer)

1001: i = 1
1002: j = 1
1003: t1 = 10*i
1004: t2 = t1+j
1005: t3 = 8*t2
1006: t4 = t3-88
1007: a[t4] = 0.0
1008: j = j+1
1009: if j <= 10 goto 1003
1010: i = i+1
1011: if i <= 10 goto 1002
1012: i = 1
1013: t5 = i-1
1014: t6 = 88*t5
1015: a[t6] = 1.0
1016: i = i+1
1017: if i <= 10 goto 1013

GATE 2025 CS1 question 52: A 17-line three-address code listing, numbered 1001 to 1017, given in the stem as a fenced block exactly as printed. — Figure from the GATE 2025 CS1 paper. It is part of the question.

Answer and solution

GATE 2025 CS1 Q.52: answer and solution

GATE 2024 CS1 Q.39

GATE 2024 · CS1Q.39 · 2 marks · MCQ

Consider the following pseudo-code.

L1:  t1 = -1
L2:  t2 = 0
L3:  t3 = 0
L4:  t4 = 4 * t3
L5:  t5 = 4 * t2
L6:  t6 = t5 * M
L7:  t7 = t4 + t6
L8:  t8 = a[t7]
L9:  if t8 <= max goto L11
L10: t1 = t8
L11: t3 = t3 + 1
L12: if t3 < M goto L4
L13: t2 = t2 + 1
L14: if t2 < N goto L3
L15: max = t1

Which one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively ?

(A)
6 and 6
(B)
6 and 7
(C)
7 and 7
(D)
7 and 6

Answer and solution

GATE 2024 CS1 Q.39: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.39: answer and solution

GATE 2023 CS Q.37

GATE 2023 · CSQ.37 · 2 marks · MCQ

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?

GATE 2023 CS question 37: Control flow graph with four basic blocks. — Figure from the GATE 2023 CS paper. It is part of the question.

(A)
B1: {}, B2: {a}, B3: {a}, B4: {a}
(B)
B1: {i, j}, B2: {a}, B3: {a}, B4: {i}
(C)
B1: {a, i, j}, B2: {a, i, j}, B3: {a, i}, B4: {a}
(D)
B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}

Answer and solution

GATE 2023 CS Q.37: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 12 marks · NAT

A basic block is:

t1 = a + b
t2 = b + a
t3 = t1 * t2
t4 = t3 - t1
t5 = t2 * t1

Assume + and * are commutative. In the DAG built for this block, how many operator (interior) nodes are there?

Answer and solution

Answer: $3$

t1 = a + b creates node $+ (a, b)$ labelled t1.
t2 = b + a is the same node by commutativity; t2 is added to it.
t3 = t1 * t2 creates $* (N_{+}, N_{+})$ labelled t3.
t4 = t3 - t1 creates $- (N_{*}, N_{+})$ labelled t4.
t5 = t2 * t1 is $* (N_{+}, N_{+})$ , the existing node; t5 is added to it.
Operator nodes: +, *, -, so 3.

PRACTICE 22 marks · NAT

The interference graph of five variables a, b, c, d, e has exactly these edges: a-b, a-c, b-c, b-d, c-d, d-e. What is the minimum number of registers needed so that interfering variables get different registers?

Answer and solution

Answer: $3$

a, b, c are mutually adjacent (a triangle), so at least 3 colours are needed.
Colour a = 1, b = 2, c = 3.
d is adjacent to b (2) and c (3) but not to a, so d = 1.
e is adjacent only to d (1), so e = 2.
A proper colouring with 3 colours exists, so the minimum is 3.

PRACTICE 31 mark · NAT

CFG with entry $B_{1}$ and edges $B_{1} \to B_{2}$ , $B_{1} \to B_{3}$ , $B_{2} \to B_{4}$ , $B_{3} \to B_{4}$ :

B1: a = 3
    b = 5
    read p
    if p > 0 goto B3   (otherwise fall into B2)
B2: c = a + b
    b = 2
    goto B4
B3: t = 2 * a
    c = t + 2
    b = a - 1
B4: d = c * b

Using global constant propagation with the meet of undefined, constant and NAC values at the entry of $B_{4}$ , what constant value is found for d?

Answer and solution

Answer: $16$

After $B_{1}$ : a = 3, b = 5, p = NAC (read from input), c, d, t undefined.
Through $B_{2}$ : c = 3 + 5 = 8, then b = 2. OUT[B2]: a = 3, b = 2, c = 8, t undefined.
Through $B_{3}$ : t = 6, c = 6 + 2 = 8, b = 3 − 1 = 2. OUT[B3]: a = 3, b = 2, c = 8, t = 6.
Meet at the entry of $B_{4}$ : a = 3; b = 2 (same constant on both paths); c = 8 (same constant); t = undefined ∧ 6 = 6.
d = c * b = 8 × 2 = 16, both operands constants, so d is the constant 16.

PRACTICE 41 mark · MCQ

How many basic blocks does the following three-address code have?

1: x = 0
2: y = 1
3: if x > 5 goto 7
4: x = x + y
5: y = y + 1
6: goto 3
7: z = x
8: if z > 2 goto 10
9: z = 0
10: return z

(A)
4
(B)
5
(C)
6
(D)
7

Answer and solution

Answer: (C)

Leader 1 is the first instruction.
Jump targets: 7 (from 3), 3 (from 6), 10 (from 8) are leaders.
Instructions following jumps: 4 (after 3), 7 (after 6), 9 (after 8) are leaders.
Leaders: {1, 3, 4, 7, 9, 10}, which is 6.
Blocks: {1,2}, {3}, {4,5,6}, {7,8}, {9}, {10}.

PRACTICE 52 marks · MSQ

CFG with entry $B_{1}$ and edges $B_{1} \to B_{2}$ , $B_{2} \to B_{2}$ , $B_{2} \to B_{3}$ :

B1: x = 1
    y = 2
    z = 3
B2: w = x + y
    x = w
    if x < 9 goto B2   (otherwise fall into B3)
B3: p = x + z
    return p

Nothing is live after the return. Which variables are live at the exit of $B_{2}$ ?

(A)
x
(B)
y
(C)
z
(D)
w

Answer and solution

Answer: (A), (B), (C)

$B_{3}$ : use = {x, z}, def = {p}; IN[B3] = {x, z}.
$B_{2}$ : w = x + y reads x, y; x = w reads w (defined in the block); the test reads x (defined in the block). use = {x, y}, def = {w, x}.
OUT[B2] = IN[B2] ∪ IN[B3]; IN[B2] = {x, y} ∪ (OUT[B2] − {w, x}).
Pass 1: IN[B2] = ∅ at the start, so OUT[B2] = {x, z}; IN[B2] = {x, y} ∪ {z} = {x, y, z}.
Pass 2: OUT[B2] = {x, y, z} ∪ {x, z} = {x, y, z}; IN[B2] = {x, y} ∪ ({x, y, z} − {w, x}) = {x, y, z}. No further change.
OUT[B2] = {x, y, z}. y is live because the loop edge makes $B_{2}$ read y again; w is not live because it is assigned before being read in every iteration.

PRACTICE 61 mark · MCQ

Blocks: $B_{1}$ computes t = a + b and goes to both $B_{2}$ and $B_{3}$ . $B_{2}$ executes a = 1. $B_{3}$ executes x = a + b. Both go to $B_{4}$ , which executes y = a + b. Which statement about the expression a + b at the entry of $B_{4}$ is correct?

(A)
It is available, so y = a + b can be replaced by y = t.
(B)
It is not available, because the path through $B_{2}$ assigns to a after it was computed in $B_{1}$ .
(C)
It is available, because $B_{1}$ computes it on every path.
(D)
It is available, because $B_{3}$ computes it.

Answer and solution

Answer: (B)

OUT[B1] = {a+b}.
$B_{2}$ : e_gen = ∅ (it does not evaluate a+b); e_kill contains a+b because it assigns a. OUT[B2] = ∅ ∪ ({a+b} − {a+b}) = ∅.
$B_{3}$ : e_gen = {a+b}; OUT[B3] = {a+b}.
IN[B4] = OUT[B2] ∩ OUT[B3] = ∅ ∩ {a+b} = ∅.
So a+b is not available at B4; option B is correct.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Local optimisation, Data flow analyses: constant propagation, liveness analysis, common sub expression elimination

Preparing in Kolkata? IAE Academy's course for GATE CSE.