**Demand Interprocedural Dataflow Analysis**

*Susan Horwitz, Thomas Reps, and Mooly Sagiv*

University of Wisconsin

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.

(Click here to access the paper: PostScript, PDF.)