Blocks, loops and methods questions ask you to mark leaders and draw basic blocks, trace what a loop transformation changes, and name the optimisation behind a rewritten instruction. Work each answer out before reading the explanation under it; the marks come from catching where your leader list or your operation count went wrong. For the rest of the syllabus, start from the GATE CS Exam Preparation category.
1. Find basic blocks, then place optimisation in the compiler pipeline
Mark leaders before forming Q1's blocks; match each Q2 phase to its output.
Q1. Count basic blocks and the largest block, GATE 2024
Consider the following pseudo-code.
πΏ1: π‘1 = β1
πΏ2: π‘2 = 0
πΏ3: π‘3 = 0
πΏ4: π‘4 = 4 β π‘3
πΏ5: π‘5 = 4 β π‘2
πΏ6: π‘6 = π‘5 β π
πΏ7: π‘7 = π‘4 + π‘6
πΏ8: π‘8 = π[π‘7]
πΏ9: if π‘8 <= πππ₯ goto πΏ11
πΏ10: π‘1 = π‘8
πΏ11: π‘3 = π‘3 + 1
πΏ12: if π‘3 < π goto πΏ4
πΏ13: π‘2 = π‘2 + 1
πΏ14: if π‘2 < π goto πΏ3
πΏ15: πππ₯ = π‘1
Which one of the following options CORRECTLY specifies the number of basicblocks and the number of instructions in the largest basic block, respectively ?
(A) 6 and 6
(B) 6 and 7
(C) 7 and 7
(D) 7 and 6
Answer: (D) 7 and 6. Leaders: L1, L3, L4, L10, L11, L13, L15. Blocks: L1-L2, L3, L4-L9, L10, L11-L12, L13-L14, L15. There are seven. L4-L9 has six instructions, the largest count.
Q2. Match compiler phases to their artefacts, GATE 2024
Consider the following two sets:
Set X:
P. Lexical Analyzer
Q. Syntax Analyzer
R. Intermediate Code Generator
S. Code Optimizer
Set Y:
1. Abstract Syntax Tree
2. Token
3. Parse Tree
4. Constant Folding
Which one of the following options is the CORRECT match from Set X to Set Y?
(A) P β 4; Q β 1; R β 3; S β 2
(B) P β 2; Q β 3; R β 1; S β 4
(C) P β 2; Q β 1; R β 3; S β 4
(D) P β 4; Q β 3; R β 2; S β 1
Answer: (B). Lexical analysis produces tokens, syntax analysis produces a parse tree, and constant folding is an optimiser transformation. The remaining association is the intermediate-code generator with the AST or equivalent intermediate structure it consumes: P-2, Q-3, R-1, S-4.
2. Count what common-subexpression elimination actually removes
Count pre-loop and per-iteration work separately.
Q3. Additions and dereferences after CSE, GATE 2021
Consider 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 variable y points to a struct (allocated on the heap) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and the dereference operations (of the form y ->f1 or y ->f2) in the optimized code, respectively, are:
(A) 403 and 102
(B) 203 and 2
(C) 303 and 102
(D) 303 and 2
Answer: (D) 303 and 2. Compute x + 3 once, then read y->f1 and y->f2 once each. Forming z needs two more additions, so before the loop there are 3 additions and 2 dereferences. The loop runs (200 - 0) / 2 = 100 times. Updates to p, q and i cost 100 Γ 3 = 300 additions. Total: 3 + 300 = 303 additions and 2 dereferences.
3. Identify natural loops, fusion and unrolling
Identify loops through control flow; distinguish jamming from unrolling.
Q4. Concepts used to identify loops, UGC NET 2021
Which of the following concepts can be used to identify loops?
A. Depth first ordering
B. Dominators
C. Reducible graphs
Choose the correct answer from the options given below:
(A) A and B only
(B) A and C only
(C) B and C only
(D) A, B and C
Answer: (D) A, B and C. Depth-first search exposes back edges. The edge n β h defines a natural loop when h dominates n; reducibility supplies the required single-entry structure. In Entry β H β B β H, H dominates B, and B β H is the back edge.
Q5. Merge two independent loop bodies, UGC NET 2016
In _______, the bodies of the two loops are merged together to form a single loop provided that they do not make any references to each other.
(A) Loop unrolling
(B) Strength reduction
(C) Loop concatenation
(D) Loop jamming
Answer: (D) Loop jamming. Also called loop fusion, it merges for i = 0..7: A[i] = i + 1 and for i = 0..7: B[i] = 2*i into one eight-iteration loop. This is valid only because neither body reads the other's writes.
Q6. What loop unrolling removes, UGC NET 2015
Loop unrolling is a code optimization technique:
(A) that avoids tests at every iteration of the loop
(B) that improves performance by decreasing the number of instructions in a basic block
(C) that exchanges inner loops with outer loops
(D) that reorders operations to allow multiple computations to happen in parallel
Answer: (A). With n = 10 unrolled by 4, main bodies handle 0-3 and 4-7; a remainder handles 8-9. The main loop tests once per group. Unrolling increases body size, so option B states the opposite.
4. Separate CSE, loop-invariant motion, strength reduction and dead code
Q7 checks applicability; Q8 isolates one transformation.
Q7. Which optimisation does not apply, GATE 2006
Consider the following C code segment.
for (i = 0, i<n; i++)
{
for (j=0; j<n; j++)
{
if (i%2)
{
x += (4*j + 5*i);
y += (7 + 4*j);
}
}
}
Which one of the following is false?
(A) The code contains loop invariant computation
(B) There is scope of common sub-expression elimination in this code
(C) There is scope of strength reduction in this code
(D) There is scope of dead code elimination in this code
Answer: (D). For the inner j loop, i%2 and 5*i are invariant. 4*j occurs twice, so CSE computes it once per active iteration; strength reduction generates 0, 4, 8, 12, ... without repeated multiplication. With n = 4, active outer values i = 1, 3 make 5*i = 5, 15. Every update feeds x or y, so no statement is dead.
Q8. Recognise operator strength reduction, UGC NET 2016
In compiler optimization, operator strength reduction uses mathematical identities to replace slow math operations with faster operations. Which of the following code replacements is an illustration of operator strength reduction ?
(A) Replace P + P by 2 * P or Replace 3 + 4 by 7.
(B) Replace P * 32 by P < < 5
(C) Replace P * 0 by 0
(D) Replace (P < <4) β P by P * 15
Answer: (B). Since 32 = 2^5, P * 32 can become P << 5 when integer semantics permit. 3 + 4 β 7 is constant folding, and P * 0 β 0 is algebraic simplification. Option D replaces shift and subtract work with multiplication.
5. Know where an optimisation runs: IR and peephole windows
Target-independent passes rewrite IR; peepholes rewrite short windows.
Q9. Why optimise intermediate code, GATE 2008
Some code optimizations are carried out on the intermediate code because
(A) they enhance the portability of the compiler to other target processors
(B) program analysis is more accurate on intermediate code than on machine code
(C) the information from dataflow analysis cannot otherwise be used for optimization
(D) the information from the front end cannot otherwise be used for optimization
Answer: (A). One machine-independent IR pass can simplify x * 8 before separate x86 and ARM backends lower it. The gain is reuse across targets, not proof that analysis is always more accurate on IR or impossible elsewhere.
Q10. Classify peephole optimisation, ISRO 2016
Peephole optimization is form of
(A) Loop optimization
(B) Local optimization
(C) Constant folding
(D) Data flow analysis
Answer: (B) Local optimization. A peephole can remove MOV R1, R1 and ADD R2, 0 from a three-instruction window. It needs no whole control-flow graph, so it is local, not loop or global data-flow optimisation.
6. Follow-on methods: software pipelining and constant propagation
Software pipelining and constant propagation are both judged by their second-order effect: which operations end up overlapping across iterations, and which statements a later pass is then free to delete.
Q11. Compiler-directed out-of-order execution, ISRO 2020
Which of the following is a type of a out-of-order execution, with the reordering done by a compiler
(A) loop unrolling
(B) dead code elimination
(C) strength reduction
(D) software pipelining
Answer: (D) software pipelining. After the prologue for y[i] = 2*x[i], one steady-state body can load x[i+2], multiply x[i+1] by 2, and store y[i]. The compiler overlaps operations from different iterations.
Q12. What constant propagation can unlock, Beltron Programmer 2025
Which of the following statements about constant propagation is correct?
(A) It applies only to loop variables.
(B) It eliminates all unused variables.
(C) It can lead to further optimizations like dead code elimination.
(D) It increases code size.
Answer: (C). In x = 5; if (x > 3) y = 8; else y = 9; return y;, propagation makes the test 5 > 3, which is true. The compiler keeps y = 8, removes the unreachable else branch, and reduces the return to 8. Propagation exposes the opportunity; dead-code elimination performs the removal.
7. Build an error log and choose the next compiler topic
Each row below pairs a specific confusion with the question that exposes it. Mark the ones that caught you and redo those questions cold.
Mistake | Question that exposes it | One-line correction |
|---|---|---|
Forgetting the instruction after a jump is a leader | Q1 | Mark all leader types before forming blocks. |
Counting loop work before calculating 100 iterations | Q3 | Find iterations, then multiply repeated work. |
Confusing loop discovery with loop transformation | Q4-Q6 | Separate CFG analysis from fusion and unrolling. |
Calling every unused-looking expression dead code | Q7 | Check whether it contributes to a live result. |
Confusing local peephole work with global analysis | Q10 | A peephole sees a short instruction window. |
Treating propagation as dead-code elimination | Q12 | Propagation exposes constants; another pass removes code. |
Review Syntax-Directed Translation and Code Optimization, then Parsing in Compiler Design. Redo Q1, Q3, Q7 and Q11. Continue with GATE Guidance by Sanchit Sir for sequence or the GATE Test Series for timed practice.
