Demand driven through graph reachability [Horwitz, Reps, Sagiv, FSE’95]

Transform super graph into exploded super graph using data flow functions

Node: a data flow fact d at node n

Edge: a dependence between data flow facts at different supergraph nodes

Demand driven algorithm:

Traverses exploded super graph in reverse order from demand until query can be answered or start of program

Previous slide

Next slide

Back to first slide

View graphic version