Data-flow framework

ACompressed recap

🧾

A data-flow problem is defined by its direction (forward or backward), its meet (∪ for may, ∩ for must), per-block gen and kill sets giving OUT = gen ∪ (IN − kill), and a boundary value. The iterative algorithm repeats until a fixed point. Reaching definitions is forward with ∪; gen keeps the last definition of each variable in the block; kill holds all other definitions of those variables.

BMerged rule card

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

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

CInterleaved GATE-style questions

Q1NAT2 marksReaching

In the Dragon-book example, how many definitions are in OUT[B2]?

Numerical answer: ________

Q2MCQ1 markgen

Block B: d1 x = 1; d2 y = x; d3 x = 3. gen[B] is:

• (A) { d1, d2, d3 }
• (B) { d2, d3 }
• (C) { d1 }
• (D) { d3 }

Q3MCQ1 markMeet

A data-flow problem asking whether a fact holds on every path uses the meet:

• (A) union
• (B) intersection
• (C) difference
• (D) none

Q4MCQ1 markInitialisation

For a must (∩) forward problem, the OUT sets of blocks other than ENTRY start as:

• (A) ∅
• (B) the universal set of facts
• (C) gen[B]
• (D) kill[B]

Q5NAT2 marksReaching

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

Numerical answer: ________

Q6MSQ2 marksFacts

Which are true?

• (A) Backward problems compute OUT from successors.
• (B) Reaching definitions can detect possibly uninitialised variables.
• (C) kill[B] contains only definitions inside B.
• (D) The fixed point does not depend on the order of visiting blocks.

Q7NAT1 markRounds

For the Dragon-book reaching-definitions example visited in order B1–B4, after how many rounds (including the confirming round) does the algorithm stop?

Numerical answer: ________

Q8MCQ2 marksUse

If exactly one definition of x reaches a use, and it is x = 5, the optimizer may:

• (A) delete the use
• (B) replace the use of x by 5
• (C) move the definition into a loop
• (D) nothing