Loading previous year questions
4 Qs · since 2013 · 8 marks · 0.3 marks/paperStandard yield
In GATE Compiler Design, the Code Optimization topic focuses on evaluating code transformations such as Common Sub-expression Elimination (CSE), Loop-Invariant Code Motion (LICM),… Guide
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 1013z = x + 3 + y->f1 + y->f2;
for (i = 0; i < 200; i = i + 2){
if (z > i) {
p = p + x + 3;
q = q + y->f1;
} else {
p = p + y->f2;
q = q + x + 3;
}
}
Assume that the variable y points to a…a = b + c
c = a + d
d = b + c
e = d - b
a = e + b
The minimum number of nodes and edges present in the DAG representation of the above basic block respectively arec = a + b;
d = c * a;
e = c + a;
x = c * c;
if (x > a) {
y = a * a;
}
else {
d = d * d;
e = e * e;
}…Topic guide
In GATE Compiler Design, the Code Optimization topic focuses on evaluating code transformations such as Common Sub-expression Elimination (CSE), Loop-Invariant Code Motion (LICM), and statement reordering under hardware constraints. Questions test the candidate's ability to analyze variable liveness, register pressure, and the dynamic operation count of optimized code segments.
Dynamic Operation Counting Post-Optimization (CSE and LICM)
occasional · MCQ · 2 marks · 2021
A C code snippet with a loop containing repeated expressions and field dereferences is provided. The candidate must determine the exact count of runtime operations (e.g., additions, dereferences) executed after applying optimizations like Common Sub-expression Elimination and hoisting invariant expressions out of the loop.
Register Allocation and Spilling with Code Motion
occasional · MCQ · 2 marks · 2013
Given an instruction set architecture with a severely constrained number of registers (e.g., 2 registers), candidates must reorder instructions using code motion and liveness information to determine the minimum number of spills to memory required during execution.
Partitioning Three-Address Code into Basic Blocks
common · NAT · 2 marks · 2025
Given a labeled sequence of three-address code instructions containing conditional/unconditional jumps, determine the number of basic blocks by identifying all leader instructions.
DAG Representation and Counting for a Basic Block
common · MCQ · 2 marks · 2014
Given a single basic block with variable reassignments and common subexpression/algebraic identities, construct the minimal DAG representation and count the total number of nodes and edges.
Loop Iteration Count
Used to compute how many times a counted `for` loop body executes when calculating dynamic runtime operations.
Total Dynamic Operations
Used to sum operations executed once outside the loop (after LICM/CSE) with the operations executed per iteration (including the loop increment).
Leader Identification Rules
Used to find all leader instructions which define the start of each basic block in intermediate code.
DAG Total Node Count
Used when computing the minimum number of nodes in a DAG after local common subexpression elimination.
Questions consistently carry 2 marks and assess concrete runtime implications (exact operation counts or exact spill counts) rather than abstract theoretical definitions.
2021, 2013
Shift from low-level register allocation/spill minimization in basic blocks with branches towards higher-level loop-invariant code motion and pointer dereference elimination.
2021, 2013
While earlier exams tested structural DAG properties (nodes/edges count) via standard 4-option MCQs, recent exams test basic block identification using exact integer NAT prompts.
2025, 2014
Medium difficulty throughout: questions require multi-step tracking of variable lifetimes, loop bounds, and branching logic rather than single-formula applications. Hardness increases when pointers/dereferences or tight register limits force careful step-by-step register allocation simulation.