What are common examiner traps in Intermediate Code Generation?

Forgetting to count initial/input variables that appear on the RHS without prior definitions when asked for 'total variables' in SSA form (as opposed to just temporary/defined variables). Missing leader instructions that immediately follow conditional/unconditional jump statements during basic block partitioning. Confusing array read `=[]` and array write `[]=` operators when constructing or interpreting Triples. Applying register allocation rules blindly without checking if an operand is an immediate constant (which does not require a separate register) versus a memory variable. Classifying the Symbol Table as an intermediate code representation rather than an auxiliary data structure.

Intermediate Code Generation

14 Qs · since 2011 · 21 marks · 0.8 marks/paperStandard yield

Take topic test

In GATE CS, Intermediate Code Generation (ICG) is tested through both theoretical/architectural concepts and precise algorithmic computations. Core recurring topics include Static… Guide

Type

GATE CSE 2025 Set 2Q21MCQ1 markMediumConsider 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 expression in one pass. (II) Backpatching can be used to generate code for flow-of-control statements in one pass. Which ONE of the following…
GATE CSE 2024 Set 1Q39MCQ2 marksMediumConsider 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…
GATE CSE 2024 Set 2Q43MCQ2 marksMediumDiagramConsider the following expression: $x[i] = (p + r) * -s[i] + u/w$ . The following sequence shows the list of triples representing the given expression, with entries missing for triples (1), (3), and (6). Which one of the following options fills in the missing entries CORRECTLY?
GATE CSE 2023Q11MCQ1 markEasyConsider the following statements regarding the front-end and back-end of a compiler. $\textbf{S1}$ : The front-end includes phases that are independent of the target hardware. $\textbf{S2}$ : The back-end includes phases that are specific to the target hardware. $\textbf{S3}$ : The back-end includes phases that…
GATE CSE 2021 Set 2Q13MSQ1 markEasyIn the context of compilers, which of the following is/are NOT an intermediate representation of the source program?
GATE CSE 2017 Set 1Q12MCQ1 markEasyConsider the following intermediate program in three address code $p = a - b$ $q = p * c$ $p = u * v$ $q = p + q$ Which one of the following corresponds to a static single assignment form of the above code?
GATE CSE 2017 Set 1Q43NAT2 marksEasyConsider the following grammar: stmt -> if expr then expr else expr; stmt | ò expr -> term relop term | term term -> id | number id -> a | b | c number -> [0-9] where relop is a relational operator (e.g., <, >, ...), ò refers to the empty statement, and if…
GATE CSE 2017 Set 1Q52NAT2 marksMediumConsider the expression $(a - 1) * (((b + c) / 3) + d)$ . Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which (i) only load and store instructions can have memory operands and (ii) arithmetic instructions can…
GATE CSE 2016 Set 1Q19NAT1 markMediumConsider the following code segment. x = u - t; y = x * v; x = y + w; y = t - z; y = x * y; The minimum number of total variables required to convert the above code segment to static single assignment form is _________ .
GATE CSE 2015 Set 1Q55NAT2 marksEasyThe least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r / 3 + s - t * 5 + u * v / w$ is ______________.
GATE CSE 2015 Set 2Q14MCQ1 markMediumIn the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?
GATE CSE 2014 Set 2Q34MCQ2 marksEasyFor a C program accessing X[i][j][k], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits. t0 = i * 1024t1 = j * 32t2 = k * 4t3 = t1 + t0t4 = t3 + t2…
GATE CSE 2014 Set 3Q17MCQ1 markEasyOne of the purposes of using intermediate code in compilers is to
GATE CSE 2011Q36MCQ2 marksMediumDiagramConsider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables $a$ , $b$ , $c$ , $d$ and $e$ are initially stored in memory. The binary operators used in this expression tree can be evaluated by…

Topic guide

What does GATE test in Intermediate Code Generation?

In GATE CS, Intermediate Code Generation (ICG) is tested through both theoretical/architectural concepts and precise algorithmic computations. Core recurring topics include Static Single Assignment (SSA) form variable counting and renaming, basic block partitioning via leader identification, register allocation on expression trees (Sethi-Ullman / Ershov labeling), array address calculation in 3-address code, and IR structures (Triples, AST, CFG, backpatching). The topic maintains an even split between 1-mark conceptual questions and 2-mark procedural NAT/MCQ problems.

Core concepts

Static Single Assignment (SSA) form and variable versioning
Basic Block Leader Identification Rules (First instruction, branch targets, instructions immediately following branches)
Three-Address Code representations: Quadruples, Triples, and Indirect Triples
Sethi-Ullman algorithm and Ershov numbers for optimal register allocation
Row-major multidimensional array address linearization and dereferencing
Backpatching for single-pass boolean expression and control flow translation
Front-end (source-dependent, target-independent) vs Back-end (target-dependent, source-independent) compiler organization
Distinction between IRs (AST, CFG, TAC) and auxiliary data structures (Symbol Table)

Recurring question patterns

Static Single Assignment (SSA) Variable Counting and Translation
common · mixed · 1.5 marks · 2017, 2016, 2015
Given an arithmetic expression or a sequence of straight-line three-address code statements, candidates must compute the minimum number of temporary variables or total variables (including distinct unassigned input variables) required in SSA form, or select the correctly renamed SSA sequence.
Optimal Register Evaluation on Expression Trees / Load-Store Arch
occasional · mixed · 2 marks · 2017, 2011
Given an expression tree or complex arithmetic expression, determine the minimum number of registers needed to evaluate the expression without spilling on a load-store architecture (often utilizing Ershov/Sethi-Ullman numbers, accounting for immediate vs. memory operands).
Basic Block and Control Flow Analysis
occasional · mixed · 2 marks · 2024, 2017
Given a sequence of three-address code with conditional and unconditional jumps, identify the number of basic blocks, leaders, instructions in the largest basic block, or compute total control-flow paths through branching structures.
Array Address Calculation and Intermediate Code Decompilation
occasional · MCQ · 2 marks · 2024, 2014
Match or deduce array dimensions and element byte sizes from generated row-major intermediate offset calculations, or fill missing entries in IR data structures like Triples/Quadruples for array accesses.
Compiler Phase Boundaries and IR Conceptual Characteristics
common · MCQ · 1 marks · 2025, 2023, 2021, 2015
Evaluate statements regarding machine-independence vs. target-dependence in front-end/back-end, distinguish IRs (AST, CFG, TAC) from compiler data structures (Symbol table), and properties of backpatching in single-pass code generation.

Formulas GATE uses

Ershov / Sethi-Ullman Register Numbering

R(\text{node}) = \begin{cases} \max(R(\text{left}), R(\text{right})) & \text{if } R(\text{left}) \neq R(\text{right}) \\ R(\text{left}) + 1 & \text{if } R(\text{left}) = R(\text{right}) \end{cases}

Determining the minimum number of registers required to evaluate a binary expression tree without memory spills on a load-store machine.

Row-Major 3D Array Offset Calculation

\text{Offset}(X[i][j][k]) = \big((i \times D_2 + j) \times D_3 + k\big) \times S = i \cdot (D_2 \cdot D_3 \cdot S) + j \cdot (D_3 \cdot S) + k \cdot S

Deducing array dimensions ( $D_2, D_3$ ) and element size ( $S$ ) from generated 3-address code instructions for array indexing.

Total SSA Variables Count

\text{Total SSA Variables} = |\text{Unique Unassigned Input Variables}| + |\text{Assignment Statements}|

Calculating total variables in an SSA-converted straight-line basic block where each assignment produces a fresh variable version.

Combinatorial Control Flow Paths

\text{Total Paths} = \prod_{i=1}^{n} (\text{paths in branch}_i) = 2^n \quad \text{for } n \text{ sequential 2-way conditionals}

Computing execution paths through chained or nested conditional structures.

Examiner traps in Intermediate Code Generation

Forgetting to count initial/input variables that appear on the RHS without prior definitions when asked for 'total variables' in SSA form (as opposed to just temporary/defined variables).
Missing leader instructions that immediately follow conditional/unconditional jump statements during basic block partitioning.
Confusing array read `=[]` and array write `[]=` operators when constructing or interpreting Triples.
Applying register allocation rules blindly without checking if an operand is an immediate constant (which does not require a separate register) versus a memory variable.
Classifying the Symbol Table as an intermediate code representation rather than an auxiliary data structure.

How questions are asked

Compute minimum SSA variables required for a given arithmetic expression or code block (NAT)
Identify leaders and count basic blocks / size of the largest block from 3-address code (MCQ/NAT)
Determine minimum registers required using expression tree evaluation (MCQ/NAT)
Deconstruct 3-address code array offset arithmetic to infer array declaration dimensions (MCQ)
Fill in missing table entries in a Triples/Quadruples representation table (MCQ)
Multi-statement verification on compiler front-end/back-end roles, IR definitions, and backpatching (MCQ/MSQ)

Paper trends

Shift from basic register allocation and architecture-oriented questions to structured IR manipulations (SSA form variable counts, basic blocks, Triples).
2024, 2017, 2016, 2015, 2011
Recent resurgence of 1-mark MSQ and conceptual MCQs targeting precise phase boundaries, IR definitions, and backpatching mechanisms.
2025, 2023, 2021
Fine-grained procedural questions on 3-address code representations, such as triple syntax conventions for array reads (`=[]`) vs array writes (`[]=`), appeared in recent iterations.
2024

Difficulty notes

Easy questions are purely conceptual checks on front-end/back-end partitioning, identifying intermediate representations (AST, CFG, TAC vs symbol table), or basic single-pass backpatching statements. Medium questions require multi-step procedural application: identifying leaders in 10-15 line 3-address code blocks, calculating SSA variable versions across re-assignments, parsing multi-dimensional array offset arithmetic, or applying Sethi-Ullman register allocation.