Precise interprocedural dataflow analysis via graph reachability

ABSTRACT

The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts must be a finite set, and that the dataflow functions must distribute over the confluence operator (either union or intersection). This class of probable problems includes—but is not limited to—the classical separable problems (also known as “gen/kill” or “bit-vector” problems)—e.g., reaching definitions, available expressions, and live variables. In addition, the class of problems that our techniques handle includes many non-separable problems, including truly-live variables, copy constant propagation, and possibly-uninitialized variables.Results are reported from a preliminary experimental study of C programs (for the problem of finding possibly-uninitialized variables).

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Alfred V. Aho , Mahadevan Ganapathi , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989 [doi>10.1145/69558.75700]
• 3: Brenda S. Baker, An Algorithm for Structuring Flowgraphs, Journal of the ACM (JACM), v.24 n.1, p.98-120, Jan. 1977 [doi>10.1145/321992.321999]
• 4: J. Cai , R. Paige, Program derivation by fixed point computation, Science of Computer Programming, v.11 n.3, p.197-261, April 1989 [doi>10.1016/0167-6423(88)90033-0]
• 5: David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, ACM SIGPLAN Notices, v.21 n.7, p.152-161, July 1986
• 6: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, ACM SIGPLAN Notices, v.23 n.7, p.47-56, July 1988
• 7: Cooper, K.D, and Kennedy, K., "Interprocedural side-effect analysis in linear time," Proceedings of the A CM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices 23(7)pp. 57-66 (July 1988).
• 8: K. D. Cooper , K. Kennedy, Fast interprocedual alias analysis, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-59, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75282]
• 9: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 10: Cousot, P. and Cousot, R., "Static determination of dynamic properties of recursive procedures," pp. 237-277 in Formal Descriptions of Programming Concepts, (IFIP WG 2.2, St. Andrews, Canada, August 1977), ed. E.J. Neuhold,North-Holland, New York, NY (1978).
• 11: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Demand-driven computation of interprocedural data flow, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.37-48, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199461]
• 12: Charles N. Fischer , Richard J. LeBlanc, Jr., Crafting a compiler, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1988
• 13: Robert Giegerich , Ulrich Möncke , Reinhard Wilhelm, Invariance of Approximate Semantics with Respect to Program Transformations, GI - 11. Jahrestagung in Verbindung mit Third Conference of the European Co-operation in Informatics (ECI), p.1-10, October 20-23, 1981
• 14: Dan Grove , Linda Torczon, Interprocedural constant propagation: a study of jump function implementation, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.90-99, June 21-25, 1993, Albuquerque, New Mexico, United States
• 15: Holley, L.H. and Rosen, B.K., "Qualified data flow problems," IEEE Transactions on Software Engineering SE-7(1)pp. 60-78 (January 1981).
• 16: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 17: Horwitz, S., Reps, T., and Sagiv, M., "Demand interprocedural dataflow analysis," Unpublished Report, Computer Sciences Department, University of Wisconsin, Madison, WI 0. (In preparation.)
• 18: Neil D. Jones , Alan Mycroft, Data flow analysis of applicative programs using minimal function graphs, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.296-306, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512672]
• 19: Kernighan, B.W., "Ratfor- A preprocessor for a rational Fortran," Software- Practice & Experience 5(4) pp. 395-406 (1975).
• 20: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 21: Jens Knoop , Bernhard Steffen, The Interprocedural Coincidence Theorem, Proceedings of the 4th International Conference on Compiler Construction, p.125-140, October 05-07, 1992
• 22: Knoop, J. and Steffen, B., "Efficient and optimal bit-vector data flow analyses: A uniform interprocedural framework," Bericht Nr. 9309, Institut fuer Informatik und Praktische Mathematik, Christian- Albrechts-Universitaet zu Kiel, KieI, Germany (April 1993).
• 23: Lawrence T. Kou, On Live-Dead Analysis for Global Data Flow Problems, Journal of the ACM (JACM), v.24 n.3, p.473-483, July 1977 [doi>10.1145/322017.322027]
• 24: William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99599]
• 25: Flemming Nielson , Hanne Riis Nielson, Finiteness conditions for fixed point iteration, Proceedings of the 1992 ACM conference on LISP and functional programming, p.96-108, June 22-24, 1992, San Francisco, California, United States
• 26: Hanne Riis Nielson , Flemming Nielson, Bounded fixed point iteration, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-82, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143182]
• 27: Reps, T., Sagiv, M., and Horwitz, S., "Interprocedural dataflow analysis via graph reachability," TR 94-14, Datalogisk Institut, University of Copenhagen, Copenhagen, Denmark (April 1994). (Available through World Wide Web at ftp://ftp.diku.dk/diku/semantics/papers/D-215.ps.Z.)
• 28: Thomas Reps , Susan Horwitz , Mooly Sagiv , Genevieve Rosay, Speeding up slicing, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.11-20, December 06-09, 1994, New Orleans, Louisiana, United States
• 29: Thomas W. Reps, Solving Demand Versions of Interprocedural Analysis Problems, Proceedings of the 5th International Conference on Compiler Construction, p.389-403, April 07-09, 1994
• 30: Sagiv, M., Reps, T., and Horwitz, S., "Precise interprocedural dataflow analysis with applications to constant propagation," Unpublished Report, Comp. Sci. Dept., Univ. of Wisconsin, Madison, WI (Oct. 1994). (Submitted for conference publication.)
• 31: Sharir, M. and Pnueli, A., "Two approaches to interprocedural data flow analysis," pp. 189-233 in Program Flow Analysis: Theory and Applications, ed. S.S. Muchnick and N.D. Jones,Prentice-Hall, Englewood Cliffs, NJ (1981).
• 32: Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.132-143, June 17-22, 1984, Montreal, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Experimentation, Languages, Theory