language: en

Demand Interprocedural Dataflow Analysis

Susan Horwitz, Thomas Reps, and Mooly Sagiv
University of Wisconsin

Abstract 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: g It provides precise (meet-over-all-interprocedurally-valid-paths) solutions to a large class of problems. g It has a polynomial worst-case cost for both a single demand and a sequence of all possible demands. g 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. g 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 superior to the current best exhaustive algorithm.

CR Categories and Subject Descriptors: D.2.2 [Software Engineering]: Tools and Techniques; D.3.4 [Programming Languages]: Processors compilers, optimization; E.1 [Data Structures] graphs; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems computations on discrete structures; G.2.2 [Discrete Mathematics]: Graph Theory graph algorithms General Terms: Algorithms, Experimentation, Theory Additional Key Words and Phrases: demand dataflow analysis, distributive dataflow framework, graph reachability, interprocedural dataflow analysis, interprocedurally realizable path, interprocedurally valid path, meet-over-all-valid-paths solution

[On leave from IBM Scientific Center, Haifa, Israel.]

[This work was supported in part by a David and Lucile Packard Fellowship for Science and Engineering, by the National Science Foundation under grants CCR-8958530 and CCR-9100424, by the Defense Advanced Research Projects Agency under ARPA Order No. 8856 (monitored by the Office of Naval Research under contract N00014-92-J-1937), by the Air Force Office of Scientific Research under grant AFOSR-91-0308, and by a grant from Xerox Corporate Research. Part of this work was done while the authors were visiting the University of Copenhagen. A preliminary version of this paper appeared in]

[SIGSOFT 95: Proceedings of the Third ACM SIGSOFT Symposium on Foundations of Software Engineering (Washington DC, October 10-13, 1995) [15]]

[Authors' address:]

Computer Sciences Department; Univ. of Wisconsin;
1210 West Dayton Street; Madison, WI 53706; USA.
Electronic mail: {horwitz, reps, sagiv}@cs.wisc.edu.