The data flow framework:
- Figure out the thing you want to know at the entry and exit of a block
- Write an equation for every block relating the entry to the exit
- Add equalities according to the edges in the CFG
- Solve the system of equations
Data flow analysis can be used to solve the reaching definition problem.
Worklist Algorithm
Given a CFG, an initial value init
, and functions merge
and transfer
in[entry] = init
out[*] = init
worklist = all blocks
while worklist is not empty:
b = pick any block from worklist
in[b] = merge(out[p], for every predecessor p of b)
out[b] = transfer(b, in[b])
if out[b] changed:
worklist += successors of b
That’s the “forward” version. For the “backward” verion, reverse predecessors and successors, and reverse in
and out
.
Requirements for Data Flow Analyses
Monotonicity: The values have to go only “in one direction”
- If the values are sets, for example, you can either only add things or only remove things. But not both.
- Worklist algorithm will only terminate under this requirement