GATE CSE Local Optimisation PYQs
In GATE Compiler Design, the Code Optimization topic focuses on evaluating code transformations such as Common Sub-expression Elimination (CSE), Loop-Invariant… Read the guide
- Questions
- 4
- Asked
- since 2013
- Total marks
- 8
- Marks / paper
- 0.3
4 GATE CSE Local Optimisation PYQs with solutions, from Compiler Design. Browse all GATE CSE PYQs.
Questions
Every official paper that asked this topic, newest first.
- GATE CSE 2025 Set 1 · Q52Refer 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 1013NAT2 marksEasySolve - GATE CSE 2021 Set 2 · Q30Consider the following ANSI C code segment:
z = 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 variableypoints to a…MCQ2 marksMediumSolve - GATE CSE 2014 Set 3 · Q34Consider the basic block given below.
a = b + c c = a + d d = b + c e = d - b a = e + bThe minimum number of nodes and edges present in the DAG representation of the above basic block respectively areMCQ2 marksMediumSolve - GATE CSE 2013 · Q48Common Data for Questions 48 and 49:
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume that all variables are dead after this code segment.
c = a + b; d = c * a; e = c + a; x = c * c; if (x > a) { y = a * a; } else { d = d * d; e = e * e; }…MCQ2 marksMediumSolve
What GATE tests in Local Optimisation
Concepts, patterns, formulas and traps distilled from past papers.
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.
Core concepts
- Common Sub-expression Elimination (CSE)
- Loop-Invariant Code Motion (LICM)
- Liveness Analysis and Dead Variable Elimination
- Register Pressure and Register Allocation Spilling
- Heap Pointer Dereference Optimization
- Branch-aware Statement Sinking/Reordering
- Identification of leaders in three-address code sequences
- Basic block partitioning and boundaries
- Directed Acyclic Graph (DAG) construction for basic blocks
- Local common subexpression elimination
- Algebraic identities and simplification within basic blocks
Recurring question patterns
Dynamic Operation Counting Post-Optimization (CSE and LICM)
OccasionalMCQ2 marks2021A 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
OccasionalMCQ2 marks2013Given 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
CommonNAT2 marks2025Given 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
CommonMCQ2 marks2014Given 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.
Formulas GATE uses
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.
Examiner traps in Local Optimisation
- Forgetting to include the loop increment operation (e.g., `i = i + 2`) in the total addition count.
- Assuming repeated sub-expressions inside conditional branches execute every time without recognizing they can be pre-computed before the loop if invariant.
- Counting operations statically from source text rather than dynamically over all loop iterations.
- Failing to sink dead or branch-exclusive computations into the respective branch body (e.g., `else` block), resulting in an overestimation of required register spills.
- Forgetting the instruction immediately following a conditional or unconditional branch as a leader
- Failing to recognize algebraic simplifications or reordered commutative operands (e + b vs b + e) that map directly to existing DAG nodes
- Over-counting nodes by allocating a new leaf node on variable reassignment rather than attaching new labels to existing nodes
- Treating single-instruction lines between leaders as not being distinct basic blocks
How questions are asked
- Dynamic arithmetic and memory access counting post-CSE/LICM
- Minimum register spills evaluation under restricted architecture
- Count the total number of basic blocks in a given three-address code sequence
- Determine the minimum number of nodes and edges in the DAG of a basic block
Paper trends
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
Difficulty notes
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.