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.

GATE CSE Intermediate Code Generation PYQs

Standard yield15.6% of Compiler Design

In GATE CS, Intermediate Code Generation (ICG) is tested through both theoretical/architectural concepts and precise algorithmic computations. Core recurring to… Read the guide

Take topic test

Questions: 14
Asked: since 2011
Total marks: 21
Marks / paper: 0.8

14 GATE CSE Intermediate Code Generation PYQs with solutions, from Compiler Design. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Intermediate Code Generation

Concepts, patterns, formulas and traps distilled from past papers.

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
Commonmixed1.5 marks2017, 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
Occasionalmixed2 marks2017, 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
Occasionalmixed2 marks2024, 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
OccasionalMCQ2 marks2024, 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
CommonMCQ1 marks2025, 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.