We perform a bit-vector based dataflow analysis pass to determine which expressions are partially availalble. The following is the formal definition of the analysis:
| Direction | Forward |
| Lattice | {0,1} |
| Top | 0 |
| Bottom | 1 |
| Meet | Union |
| Initialization | Out(B) ={}, for all basic blocks, B |
| Transfer Function | Out(B) = AvLoc(B) U (In(B) - Kill(B)) |
| where AvLoc(B) is a locally available expression |
In addition to computing which expressions are partially available, the algorithm also computes information for detecting the dynamic path. Each expression that is partially available is associated with a predicate that determines whether the expression has been computed earlier or not. For example, if the expression is locally available in a block, then predicate for the expression is the predicate that determines whether this block itself is executed or not. The predicates that determining whether a basic block is executed or not can be statically computed based on the control-dependence graph. At a meet point, the predicate for an expression is the union of the predicates of the paths along which it is available.