Constant propagation

ACompressed recap

🧾

Constant propagation tracks, per variable, UNDEF, a constant, or NAC. At joins, equal constants survive and different ones become NAC; UNDEF imposes nothing. The transfer function folds when operands are constants. It is forward, iterates to a fixed point, makes loop counters NAC, and is not distributive (safe but imprecise).

BMerged rule card

6.3 Constant propagation

• Lattice per variable: UNDEF (⊤) > constants > NAC (⊥).
• Meet: UNDEF ∧ v = v; c ∧ c = c; c₁ ∧ c₂ = NAC (c₁ ≠ c₂); NAC ∧ v = NAC.
• Transfer x = y op z: both constant → fold; any NAC → NAC; else UNDEF.
• Forward; iterate from UNDEF to a fixed point.
• Not distributive: safe but can miss constants.

CInterleaved GATE-style questions

Q1MCQ1 markMeet

3 meet NAC is:

• (A) 3
• (B) NAC
• (C) UNDEF
• (D) 0

Q2NAT2 marksLoop

B1: i = 0, k = 5; B2 (self-loop): j = k * 2, i = i + 1; B3: m = j + k. What is m at the end of B3?

Numerical answer: ________

Q3MCQ1 markLoop

In the same graph, i at the start of B2 is:

• (A) 0
• (B) 1
• (C) NAC
• (D) UNDEF

Q4MCQ2 marksPrecision

Paths x = 2, y = 3 and x = 3, y = 2 join before z = x + y. Constant propagation gives z =

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

Q5MCQ1 markDirection

Constant propagation is:

• (A) backward
• (B) forward
• (C) bidirectional
• (D) local only

Q6MSQ2 marksTransfer

For the statement x = y * z, which are correct?

• (A) y = 2, z = 3 → x = 6
• (B) y = 2, z = NAC → x = NAC
• (C) y = UNDEF, z = 3 → x = UNDEF
• (D) y = NAC, z = NAC → x = 0

Q7NAT1 markValue

Path 1 sets z = 5; path 2 sets z = 5; after the join w = z * 2. Value of w?

Numerical answer: ________

Q8MCQ1 markUse

After constant propagation shows that a branch condition is always false, the optimizer may:

• (A) remove the branch and the unreachable code
• (B) add a loop
• (C) rename variables
• (D) nothing