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

0 · Recall Warm-up

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

• In local optimization, why is a + b after a = a − 1 not a common subexpression with an earlier a + b? from Lesson 6.1
• Under call by value-result, when are values copied back? from Lesson 5.4
• How do you find the edges of a flow graph? from Lesson 4.4

1 · The Story

📖

Which figure reaches here?

Across chapters, Ishaan wants to know: when chapter 4 reads “the price”, which earlier sentences that set the price could be responsible? The draft has detours and loops, so it could be any of several.

He keeps a sheet with two columns per chapter: what can arrive at its start, and what can leave its end. A chapter passes on everything that arrives, except settings it overwrites, plus the settings it makes itself. What arrives at a chapter is everything that can leave any chapter leading into it.

He fills the sheet with nothing, then goes round all chapters again and again, updating each from its neighbours. The sheet keeps growing, a little each round, until a full round changes nothing. Then it is right.

2 · Predict First

🤔

In the flow graph of Example 1, can the definition d1 (i = m − 1 in B1) reach the start of B2, even though B2 is in a loop? Write your guess down. The answer is in the vault.

3 · Core Concept

What data-flow analysis computes

Data-flow analysis computes, for every program point, a set of facts that hold on all or on some paths reaching that point (or leaving it). The facts are summarised per basic block as IN[B] (at its start) and OUT[B] (at its end).

Transfer functions with gen and kill

The effect of a block is a transfer function. For many problems it has the form

OUT[B] = gen[B] ∪ (IN[B] − kill[B])        (forward)

gen[B]: facts created in B; kill[B]: facts destroyed in B.

Combining paths: the meet operator

Where several paths join, their facts are combined with a meet operator: union (∪) when a fact must hold on some path (“may” problems), intersection (∩) when it must hold on all paths (“must” problems).

Forward:  IN[B] = meet over predecessors P of OUT[P]
Backward: OUT[B] = meet over successors S of IN[S];  IN[B] = f_B(OUT[B])

Iterating to a fixed point

Initialise every OUT (forward) to the empty set for ∪ problems, or to the universal set for ∩ problems (the boundary, ENTRY or EXIT, gets its own fixed value). Recompute all blocks repeatedly until no set changes: a fixed point. Because sets only grow (∪) or only shrink (∩) and are finite, this terminates. Visiting blocks in the direction of the flow (forward problems in program order) reduces the number of rounds.

First instance: reaching definitions

A definition d of x (an assignment to x) reaches point p if there is a path from d to p on which x is not redefined. Forward, meet = ∪.

• gen[B]: definitions in B that reach B’s end (the last definition of each variable in B);
• kill[B]: all other definitions in the program of variables defined in B.

Use: if exactly one definition of x reaches a use and it is x = constant, the use can be replaced by the constant; if none reaches, x may be uninitialised.

Story → compiler term

4 · Visual

Reaching definitions (Dragon-book example, recomputed). d1–d3 are in B1, d4–d5 in B2, d6 in B3, d7 in B4.

Round-robin iteration in block order: stable after 3 rounds (the last round confirms nothing changes).

5 · Worked Examples

Example 1 Easy

Compute gen and kill for each block of the flow graph above.

Solution

B1 defines i, j, a: gen = { d1, d2, d3 }, kill = every other definition of i, j, a: { d4, d5, d6, d7 }. B2: gen = { d4, d5 }, kill = { d1, d2, d7 }. B3: gen = { d6 }, kill = { d3 }. B4: gen = { d7 }, kill = { d1, d4 }. Ishaan’s “settings made” and “settings overwritten”.

Example 2 Medium

Iterate to the fixed point and give IN[B2] and OUT[B2].

Solution

Round 1 (in order B1–B4, using values already updated this round): OUT[B1] = { d1, d2, d3 }; IN[B2] = OUT[B1] ∪ OUT[B4] = { d1, d2, d3 } so OUT[B2] = { d3, d4, d5 }; then B3, B4. Round 2 picks up the loop edge B4 → B2. Final: IN[B2] = { d1, d2, d3, d5, d6, d7 }, OUT[B2] = { d3, d4, d5, d6 }.

Example 3 GATE

Which definitions reach the start of B3 in: B1: d1 x = 1, d2 y = 2; B2: d3 x = x + 1 (B2 loops to itself); B3: y = x * 2; edges B1→B2, B2→B2, B2→B3?

Solution

IN[B2] = OUT[B1] ∪ OUT[B2] = { d1, d2, d3 } (d1 arrives from B1; d3 comes round the loop). OUT[B2] = { d3 } ∪ (IN − { d1 }) = { d2, d3 }. IN[B3] = { d2, d3 }: d1 cannot reach B3, because every path to B3 passes d3.

6 · Shortcuts

⚡

Recipe for any gen/kill problem: (1) direction; (2) meet ∪ or ∩; (3) gen, kill per block; (4) initialise; (5) iterate in flow order until stable. Valid when: every data-flow question.

⚡

Reaching definitions kill = all other definitions of the variables defined in the block (anywhere in the program). Valid when: computing kill sets.

7 · GATE Traps

⚠️

• gen[B] keeps only the last definition of each variable in B.
• kill[B] includes definitions in other blocks, including ones that never reach B.
• Reaching definitions is a may problem: meet = ∪, initial OUT = ∅.
• The number of rounds depends on the visiting order; the fixed point does not.
• IN is computed from predecessors (forward); backward problems use successors.

8 · Memory Hook

🧠

OUT = gen ∪ (IN − kill); IN = meet of the neighbours; repeat until quiet.

9 · Connect the Dots

Reaching definitions answer “which assignment can this value come from?”. The next lesson uses the same framework with a different kind of fact: is this variable known to hold one particular constant here?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markDirection

Reaching definitions is a:

• (A) backward, intersection problem
• (B) forward, union problem
• (C) forward, intersection problem
• (D) backward, union problem

Q2MCQ1 markTransfer

For a forward gen/kill problem, OUT[B] equals:

• (A) IN[B] ∪ kill[B]
• (B) gen[B] ∪ (IN[B] − kill[B])
• (C) gen[B] ∩ IN[B]
• (D) kill[B] − gen[B]

Q3NAT2 marksReaching

In the Dragon-book example above, how many definitions reach the start of B2?

Numerical answer: ________

Q4MSQ1 markFixed point

Which are true about the iterative algorithm?

• (A) It stops when a full pass changes no set.
• (B) For union problems, sets start empty and only grow.
• (C) Visiting order affects the final answer.
• (D) It always terminates for finite sets of facts.

Q5NAT1 markKill

In that example, how many definitions are in kill[B1]?

Numerical answer: ________

11 · Rule Card

• Facts per block: IN[B], OUT[B].
• Forward: IN[B] = meet over preds of OUT[P]; OUT[B] = gen[B] ∪ (IN[B] − kill[B]).
• Backward: OUT[B] = meet over succs of IN[S]; IN[B] = f_B(OUT[B]).
• Meet: ∪ for may problems (start ∅); ∩ for must problems (start with the universe).
• Iterate until no change: fixed point.
• Reaching definitions: forward, ∪; gen = last definitions in B; kill = other definitions of the same variables.

12 · Concept Ledger

data-flow analysisprogram pointIN[B] / OUT[B]transfer functiongen[B] / kill[B]meet operator (∪, ∩)forward / backward problemfixed pointreaching definitionsmay / must problem

13 · Answer Vault