Demand driven approaches
Demand for a specific subset: set of queries
query: q=(y,n): Are set of data flow facts y part of the exhaustive solution at program point n?
Worst case complexity: no worse than for exhaustive, even when sequence of all possible demands needed
Two approaches: (both interprocedural)
- Propagation modeled as a partial reversal of original exhaustive data flow analysis [Duesterwald, Gupta, Soffa, POPL’95, TOPLS’97]
- Propagation modeled as a graph reachability problem [Horwitz, Reps, Sagiv, FSE’95]