Lesson 4: Data Flow


The Data Flow Framework

Here's the pseudocode for solving a forward data flow problem with a worklist algorithm:

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

For the backward version, flip predecessors & successors, and flip in and out.

Instantiating Data Flow