An exhaustive dataflow analysis algorithm associates with each point in a program a set of "dataflow facts" that are guaranteed to hold whenever that point is reached during program execution. By contrast, a demand dataflow analysis algorithm determines whether a single given dataflow fact holds at a single given point.

This paper presents a new demand algorithm for interprocedural dataflow analysis. The new algorithm has three important properties:

• It provides precise (meet over all interprocedurally valid paths) solutions to a large class of problems.
• It has a polynomial worst-case cost for both a single demand and a sequence of all possible demands.
• The worst-case total cost of the sequence of all possible demands is no worse than the worst-case cost of a single run of the current best exhaustive algorithm.