Monoids for Rapid Data Flow Analysis

Ambitious optimizing compilers have alertness and selectivity properties that lead to a serious discrepancy between the total cost of data flow analysis and the partial cost covered by the usual kind of theoretical estimate. This discrepancy motivates a new high-level analysis method for data flow problems expressible in terms of a semilattice L and monoid M of isotope maps from L to L, under algebraic constraints somewhat weaker than those imposed by Graham and Wegman in solving data flow problems on reducible graphs. The cost of the new method is roughly similar to that of the method of Graham and Wegman when estimates are made in the usual way, while the cost of updating in alert and selective compilers tends to be lower. The new method copes with arbitrary escapes and jumps, can find sharper information than fixpoint methods when M is not distributive, and can be tuned to trade time for sharpness of information.