Questions: Dataflow Analysis

Question 1

Live variable analysis asks: at each program point, which variables might be used before being overwritten on some path from that point? Why is this a backward analysis rather than a forward one?

• A. Because it only applies to loops, which must be traversed in reverse
• B. Because the information needed at a point depends on what happens later (at uses), not earlier (at definitions)
• C. Because CFG edges are reversed in all standard analyses
• D. Because backward analyses are faster to compute than forward ones

Answer: (B)

A variable is live at point p if there is a path from p to some use of the variable with no intervening definition. That information flows from uses backward toward definitions — you learn that x is live at an earlier point because you see it used at a later point. Reaching definitions, by contrast, asks whether a definition made earlier 'reaches' a later point, which flows forward.

Question 2

In a reaching definitions analysis, a definition of variable x at point d 'reaches' point p if there is a path from d to p along which x is not redefined.

• T. True
• F. False

Answer: True

This is the standard definition. A definition is 'killed' when the same variable is assigned again on the path. Reaching definitions is a forward analysis: you propagate the set of definitions that reach the entry of each basic block forward through the CFG, generating new definitions and killing old ones at each assignment.

Question 3

Why is fixpoint iteration in dataflow analysis guaranteed to terminate, and what property of the transfer functions ensures this?

Model answer: The dataflow values live in a finite lattice, and the transfer functions are monotone — each iteration can only move values in one direction (toward greater or lesser information). Since the lattice has finite height, values cannot keep changing forever; they must stabilize.

At each iteration, the dataflow sets at each block can only grow (for may-analyses like reaching definitions) or shrink (for must-analyses). Because program variables and definitions are finite, the sets are bounded. Monotonicity means no iteration can reverse a prior change, so the sequence of iterates is monotonically increasing (or decreasing) and bounded — by the finite chain condition, it must reach a fixpoint.