Medium ●●

📝 Intermediate Code Generation

Why it matters: Counting temporaries/instructions, forming quads vs triples and finding basic blocks are standard.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 5 done.

Formulas

Temporaries
#temporaries = #operators (binary and unary) in the expression
Leaders
1st instruction ∪ targets of jumps ∪ instructions following jumps
Basic blocks
#blocks = #leaders
DAG nodes
#nodes = #distinct (op, left, right) values + leaves

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Count basic blocks / leaders
Given three-address code with gotos, find the leaders and the number of basic blocks (or edges).
★★★
Count temporaries / TAC instructions
Translate an expression and count instructions or temporaries.
★★★
DAG nodes for a block
Number of nodes or edges in the DAG after reusing common subexpressions.
★★★
Quadruples vs triples
Which representation allows reordering, or table sizes.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

5 real questions from the official GATE CSE papers (2021 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

5 questions · 0 correct of 0 attempted · marks 0 / 9

Year:
GATE 2025 CS2 · Q21MCQ1 mark
Consider the following statements about the use of backpatching in a compiler for intermediate code generation:
(I) Backpatching can be used to generate code for Boolean expressions in one pass.
(II) Backpatching can be used to generate code for flow-of-control statements in one pass. Which ONE of the following options is CORRECT?
GATE 2025 CS1 · Q52NAT2 marks
Refer to the given 3-address code sequence, split into basic blocks. The number of basic blocks is ______.
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 2024 CS1 · Q39MCQ2 marks
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 option CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively?
GATE 2024 CS2 · Q43MCQ2 marks
Consider the expression x[i] = (p + r) * −s[i] + u / w. The list of triples representing it has missing entries (1), (3) and (6): (0) + p r; (1) ?; (2) uminus (1); (3) ?; (4) / u w; (5) + (3) (4); (6) ?; (7) = (6) (5). Which option fills in the missing entries CORRECTLY? (A) (1) =[] s i, (3) * (0) (2), (6) []= x i. (B) (1) []= s i, (3) − (0) (2), (6) =[] x (5). (C) (1) =[] s i, (3) * (0) (2), (6) []= x (5). (D) (1) []= s i, (3) − (0) (2), (6) =[] x i.
GATE 2021 Set 1 · Q50NAT2 marks
Consider the following C code segment:
a = b + c;
e = a + 1;
d = b + c;
f = d + 1;
g = e + f;
In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes in the DAG is ______.

Common traps

A DAG reuse is invalid if an operand was reassigned in between.
The instruction after a conditional jump is a leader even if it is also the fall-through.