Contents    Page-10    Prev    Next    Page+10    Index   

Solving Data Flow Equations

If the expressions that are available on entry to a block are known, the values for available on exit can be computed.

For each block b whose predecessors have had their values computed,

availentry(b) = ∏x ∈ Γ^-1 b availexit(x)
availexit(b) = availentry(b) · not( kill(b) ) + comp(b)

No expressions are available on entry to the first block of a program.

The equations can be solved iteratively, using the ordering of the dominator relation, until the values reach a fixpoint. If the inputs to a block change, the values on exit from the block are recomputed, until no more changes occur.