CS Atlas GATE 2027
Compiler Design course
0 / 90 complete

Compiler Design/Phase 6 · Optimization

Checkpoint CP6 · Item 82 of 90

Optimization

Read at your own pace. Try the questions before opening the answers.

On this page

⏱️

15 questions · 21 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT.

Q1NAT2 marksLocal

Block: x = 4; y = x * 2; z = y + 0; t = b * 1; u = t + z; w = u, only u needed. Instructions after optimization?

Numerical answer: ________

Q2MCQ1 markTerms

Replacing x = y; z = x + 1 by z = y + 1 (and dropping x if unused) is:

  • (A) constant folding
  • (B) copy propagation (+ dead-code elimination)
  • (C) strength reduction
  • (D) code motion

Q3MCQ2 marksLocal CSE

In the block a = b + c; b = a − d; c = b + c; d = a − d, which statement reuses an earlier value?

  • (A) c = b + c
  • (B) d = a − d
  • (C) b = a − d
  • (D) none

Q4MCQ1 markFramework

In a forward problem, IN[B] is computed from:

  • (A) successors
  • (B) predecessors
  • (C) B itself only
  • (D) the exit

Q5NAT2 marksReaching

In the Dragon-book reaching-definitions example (Lesson 6.2), how many definitions reach the start of B4?

Numerical answer: ________

Q6MCQ1 markReaching

For reaching definitions, kill[B] contains:

  • (A) definitions in B
  • (B) all other definitions of variables defined in B
  • (C) variables used in B
  • (D) nothing

Q7MCQ1 markConstant propagation

5 meet 6 is:

  • (A) 5
  • (B) 6
  • (C) NAC
  • (D) UNDEF

Q8NAT2 marksConstant propagation

In the graph of Lesson 6.3 (B1: x = 2, y = 3; B2: z = x + y; B3: z = 5, y = 4; B4: w = z * 2), what is w?

Numerical answer: ________

Q9MCQ1 markDistributivity

Constant propagation is:

  • (A) distributive
  • (B) not distributive
  • (C) a backward problem
  • (D) a union problem

Q10MCQ1 markLiveness

For liveness, IN[B] =

  • (A) def ∪ (OUT − use)
  • (B) use ∪ (OUT − def)
  • (C) use ∩ OUT
  • (D) OUT − use

Q11NAT2 marksRegisters

For p = a + b; q = p * c; r = q − a; s = r + p; t = s * q (only t needed after), the maximum number of live variables at a point is:

Numerical answer: ________

Q12MSQ2 marksDirections

Match correctly: which pairs are right?

  • (A) reaching definitions: forward, ∪
  • (B) liveness: backward, ∪
  • (C) available expressions: forward, ∩
  • (D) constant propagation: backward

Q13NAT1 markAvailable

In the GATE example of Lesson 6.5 (c = 7 in B3), how many expressions are available at the start of B4?

Numerical answer: ________

Q14MCQ1 markLoops

Replacing t = 4 * i (i += 1) by t = t + 4 is:

  • (A) code motion
  • (B) strength reduction on an induction variable
  • (C) copy propagation
  • (D) peephole optimization

Q15MCQ1 markUses

Which analysis tells whether an assignment is dead across blocks?

  • (A) reaching definitions
  • (B) liveness
  • (C) available expressions
  • (D) constant propagation

Answer Vault

Try the questions first. Open when you are ready to check.

Q1 Answer: 12 marks

u = b + 8: 1.

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

Q2 Answer: (B)1 mark

Use y where x was a copy of it.

  • (A) is wrong: No constants.
  • (C) is wrong: No cheaper operator.
  • (D) is wrong: No loop.

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

Q3 Answer: (B)2 marks

a − d with unchanged a and d₀ equals b’s value: d = b.

  • (A) is wrong: b changed.
  • (C) is wrong: First computation.
  • (D) is wrong: One does.

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

Q4 Answer: (B)1 mark

Information flows along edges.

  • (A) is wrong: Backward problems.
  • (C) is wrong: No.
  • (D) is wrong: No.

Re-read: Lesson 6.2 — The data-flow analysis framework: gen/kill sets, in/out equations, forward vs backward, meet operator, iterating to a fixed point

Q5 Answer: 42 marks

IN[B4] = { d3, d4, d5, d6 }: 4.

Re-read: Lesson 6.2 — The data-flow analysis framework: gen/kill sets, in/out equations, forward vs backward, meet operator, iterating to a fixed point

Q6 Answer: (B)1 mark

Those are overwritten by B.

  • (A) is wrong: Those are gen.
  • (C) is wrong: Uses are irrelevant.
  • (D) is wrong: No.

Re-read: Lesson 6.2 — The data-flow analysis framework: gen/kill sets, in/out equations, forward vs backward, meet operator, iterating to a fixed point

Q7 Answer: (C)1 mark

Different constants.

  • (A) is wrong: No.
  • (B) is wrong: No.
  • (D) is wrong: No.

Re-read: Lesson 6.3 — Constant propagation

Q8 Answer: 102 marks

z = 5 on both paths: w = 10.

Re-read: Lesson 6.3 — Constant propagation

Q9 Answer: (B)1 mark

Meeting first can lose correlated constants.

  • (A) is wrong: No.
  • (C) is wrong: Forward.
  • (D) is wrong: Uses its own lattice meet.

Re-read: Lesson 6.3 — Constant propagation

Q10 Answer: (B)1 mark

Read here, or needed later and not overwritten here.

  • (A) is wrong: Swapped.
  • (C) is wrong: No.
  • (D) is wrong: No.

Re-read: Lesson 6.4 — Liveness analysis: live variables at each point; what liveness is used for

Q11 Answer: 32 marks

3.

Re-read: Lesson 6.4 — Liveness analysis: live variables at each point; what liveness is used for

Q12 Answer: (A) (B) (C)2 marks

Constant propagation is forward.

Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressions

Q13 Answer: 11 mark

Only a * b: 1.

Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressions

Q14 Answer: (B)1 mark

Multiplication becomes addition.

  • (A) is wrong: Nothing moves out.
  • (C) is wrong: No copy.
  • (D) is wrong: Not a window pattern.

Re-read: Lesson 6.6 — Loop optimizations: code motion, induction variables (brief, low weight)

Q15 Answer: (B)1 mark

Dead = target not live after it.

  • (A) is wrong: Answers where values come from.
  • (C) is wrong: About expressions.
  • (D) is wrong: About constant values.

Re-read: Lesson 6.4 — Liveness analysis: live variables at each point; what liveness is used for

Wrong on Q → re-read

QuestionTopicRe-read
Q1LocalLesson 6.1
Q2TermsLesson 6.1
Q3Local CSELesson 6.1
Q4FrameworkLesson 6.2
Q5ReachingLesson 6.2
Q6ReachingLesson 6.2
Q7Constant propagationLesson 6.3
Q8Constant propagationLesson 6.3
Q9DistributivityLesson 6.3
Q10LivenessLesson 6.4
Q11RegistersLesson 6.4
Q12DirectionsLesson 6.5
Q13AvailableLesson 6.5
Q14LoopsLesson 6.6
Q15UsesLesson 6.4
ONE MORE CONNECTION MADE

Ready for the next idea?

Mark this item complete when you’ve finished reading and working through it.