Abstract Demand Interprocedural Dataflow Analysis

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 algorithm has four 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 best known exhaustive algorithm for the same class of problems. � Experimental results show that in many situations (e.g., when only a small number of demands are made, or when most demands are answered yes) the demand algorithm is faster than the current best exhaustive algorithm