Constant propagation

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Give the transfer function of a forward gen/kill problem. from Lesson 6.2
• Which allocation strategy is impossible for a language with recursion? from Lesson 5.5
• In SSA form, what does a φ-function do? from Lesson 4.3

1 · The Story

📖

Certain figures

Ishaan wants to replace “the price” by “50” wherever that is certain. For each chapter and each figure he writes one of three marks: not yet seen (no route has set it so far), a definite number, or varies.

Where routes join, he combines marks: not-yet-seen with 50 gives 50; 50 with 50 gives 50; 50 with 60 gives varies; anything with varies gives varies.

One case surprises him. On one route x = 2 and y = 3; on the other x = 3 and y = 2. The total x + y is 5 on both routes, but his sheet only stores x and y separately, which both vary. So it says the total varies too. The method is safe, but not perfect.

2 · Predict First

🤔

B1: x = 2, y = 3; B2: z = x + y; B3: z = 5, y = 4; B2 and B3 both go to B4: w = z * 2. Is w a constant in B4? Write your guess down. The answer is in the vault.

3 · Core Concept

The lattice of values

For each variable, the analysis keeps one value from a three-level lattice:

• UNDEF (⊤): no definition seen yet on any path;
• a constant c;
• NAC (⊥, not a constant): different values are possible.

Meet

Combining values at a join (applied per variable):

Transfer function

For x = y op z inside a block: if y and z are both constants, x = y op z (folded); if either is NAC, x = NAC; otherwise (some UNDEF) x = UNDEF. A copy x = y copies y’s value; x = constant gives that constant. Other variables pass through unchanged. The problem is forward; IN[B] is the meet of the predecessors’ OUT.

Iteration and loops

Start with every variable UNDEF and iterate to a fixed point. In a loop, a variable such as i = i + 1 changes value each time round, so after the meet at the loop header it becomes NAC. Values only move down the lattice (UNDEF → constant → NAC), so the iteration terminates.

Not distributive

Unlike reaching definitions, constant propagation is not distributive: meeting before applying a block can lose precision compared with applying it on each path separately. (The x = 2, y = 3 vs x = 3, y = 2 example.) The answer is still safe: a variable is reported constant only when it truly is.

Using the result

Replace uses of a variable that is a constant at that point by the constant, fold the resulting expressions, and remove branches whose conditions become constant.

Story → compiler term

4 · Visual

Constant propagation, computed. At B4, z = 5 on both incoming paths (constant), y = 3 or 4 (NAC); so w = 10 and v is NAC.

5 · Worked Examples

Example 1 Easy

Compute the values at the end of B4 in the flow graph above.

Solution

IN[B4] = OUT[B2] meet OUT[B3]: x = 2 meet 2 = 2; y = 3 meet 4 = NAC; z = 5 meet 5 = 5. Then w = z * 2 = 10 and v = y + x = NAC. Ishaan’s sheet: certain on every route, or “varies”.

Example 2 Medium

B1: i = 0, k = 5; B2 (loop, back to itself): j = k * 2, i = i + 1; B3 (after the loop): m = j + k. Which variables are constants at the end of B3?

Solution

At the B2 header, i meets 0 (from B1) and 1, 2, … (from B2): NAC. k stays 5, so j = 10 every time. At B3: m = 10 + 5 = 15; i is NAC. Constants at B3: j = 10, k = 5, m = 15.

Example 3 GATE

Two paths join: one sets x = 2, y = 3, the other x = 3, y = 2; then z = x + y. What does constant propagation conclude about z, and is that the true value?

Solution

x and y are NAC after the meet, so z is NAC. In reality z = 5 on both paths. Constant propagation is not distributive: it meets before computing, losing the correlation between x and y. Safe, not exact.

6 · Shortcuts

⚡

Per variable, per join: equal constants survive; different constants or any NAC give NAC; UNDEF is ignored. Valid when: meeting at a join.

⚡

Loop counters are NAC at the loop header; anything computed only from values that never change in the loop stays constant. Valid when: loops in constant-propagation questions.

7 · GATE Traps

⚠️

• UNDEF meet c = c (not NAC): an undefined value on one path does not spoil a constant on another.
• c₁ meet c₂ with c₁ ≠ c₂ is NAC.
• Constant propagation is not distributive; it can miss constants that hold on every path.
• A variable incremented in a loop is NAC at the header, even if it starts constant.
• Constant propagation is forward.

8 · Memory Hook

🧠

Undefined steps aside; equal constants agree; anything else is NAC.

9 · Connect the Dots

Constant propagation looks forward: what values arrive here? The next analysis looks backward: is this variable’s current value still needed later? That answer drives dead-code elimination and the use of the few machine registers.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markMeet

In constant propagation, 7 meet 7 gives:

• (A) UNDEF
• (B) 7
• (C) NAC
• (D) 14

Q2MCQ1 markMeet

UNDEF meet 4 gives:

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

Q3NAT2 marksPropagation

B1: a = 4, b = a * 3; B2: c = b − 2; B3: c = 10; B2 and B3 both go to B4: d = c + a. What is the constant value of d at the end of B4?

Numerical answer: ________

Q4MCQ2 marksPropagation

Same graph but B3 sets c = 11. Then at the end of B4, d is:

• (A) 14
• (B) 15
• (C) NAC
• (D) UNDEF

Q5MSQ1 markFacts

Which are true about constant propagation?

• (A) It is a forward problem.
• (B) It is distributive.
• (C) Values only move downward in the lattice.
• (D) A loop counter is NAC at the loop header.

11 · Rule Card

• 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.

12 · Concept Ledger

constant propagationlatticeUNDEF (⊤)NAC (⊥, not a constant)distributive framework

13 · Answer Vault