LI.6.1 Local optimization · GATE 2027 Compiler Design

ACompressed recap

🧾

Inside one basic block the optimizer folds constants, applies algebraic identities, reduces strength, propagates copies, removes common subexpressions (two equal computations with unchanged operands) and deletes dead assignments. The block DAG does most of these at once: build it, then emit only the nodes needed by variables used after the block. A peephole pass then cleans up the target code.

BMerged rule card

6.1 Local optimization: constant folding, algebraic simplification, strength reduction, copy propagation, dead-code elimination, local CSE with the block DAG, peephole optimization

Constant folding: compute constant expressions at compile time.
Algebraic simplification: x+0, x1, x0, x−0, x/1.
Strength reduction: x2 → x+x or x1; x² → xx.
Copy propagation: after x = y, use y.
Dead code: assignments to variables not used later (no side effects).
Local CSE: block DAG shares (op, operands) nodes; emit code only for needed values.
Peephole: redundant load/store, unreachable code, jump-to-jump, idioms.

CInterleaved GATE-style questions

Q1NAT2 marksDAG optimization

Block: k = 2; m = k + 3; n = m * x; p = n; q = p + 0; only q is needed after it. How many instructions remain?

Numerical answer: ________

Q2MCQ1 markTerms

Computing 3 * 7 at compile time is:

(A) strength reduction
(B) constant folding
(C) copy propagation
(D) peephole

Q3MCQ1 markCSE

In a = b + c; b = b − 1; d = b + c, is b + c a common subexpression?

(A) yes
(B) no, because b changed in between
(C) yes, if c is constant
(D) only in SSA form

Q4MCQ2 marksDead code

In the block x = a + b; y = x * 2; x = c − 1, with only x needed after the block, which assignments are dead?

(A) none
(B) y = x * 2 only
(C) x = a + b and y = x * 2
(D) x = c − 1

Q5MSQ1 markIdentities

Which identities are applied by algebraic simplification?

(A) x + 0 = x
(B) x * 1 = x
(C) x * 0 = 0
(D) x + 1 = x

Q6MCQ1 markPeephole

goto L1 where L1 holds goto L2 can be changed to:

(A) goto L1
(B) goto L2
(C) nothing
(D) a call

Q7NAT1 markCount

How many instructions remain for t1 = 4 * i; t2 = a + t1; t3 = 4 * i; t4 = b + t3; x = t2 + t4 after local CSE (only x needed)?

Numerical answer: ________

Q8MCQ1 markStrength

Which is not a valid strength reduction for unsigned integers?

(A) x * 8 → x << 3
(B) x / 4 → x >> 2
(C) x * x → x²
(D) x * 2 → x + x