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. 1.Aho, A.V., Hopcroft, J.E., and Ullman, J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA (1974).]]
2. 2.Aho, A.V., Ganapathi, M., and Tjiang, S.W.K., "Code generation using tree matching and dynamic programming," A CM Trans. Program. Lang. Syst. 11(4) pp. 491-516 (October 1989).]]
3. 3.Baker, B., "An algorithm for structuring flowgraphs," J. A CM 24(1) pp. 98-120 (January 1977).]]
4. 4.Cai, J, and Paige, R., "Program derivation by fixed point computation," Science of Computer Programming 11 pp. 197-261 (1988/89).]]
5. 5.Callahan, D., Cooper, K.D., Kennedy, K., and Torczon, L., "Interprocedural constant propagation," Proceedings of the SIGPLAN 86 Symposium on Compiler Construction, (Palo Alto, CA, June 25-27, 1986), ACM SIGPLAN Notices 21(7) pp. 152-i61 (July 1986).]]
6. 6.Callahan, D., "The program summary graph and flow-sensitive interprocedural data flow analysis," Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices 23(7)pp. 47-56 (July 1988).]]
7. 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. 8.Cooper, K.D. and Kennedy, K., "Fast interprocedural alias analysis," pp. 49-59 in Conference Record of the Sixteenth ACM Symposium on Principles of Programming Languages, (Austin, TX, Jan. I1-i3, 1989), ACM, New York, NY (1989).]]
9. 9.Cousot, P. and Cousot, R., "Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints," pp. 238-252 in Conference Record of the Fourth A CM Symposium on Principles of Programming Languages, (Los Angeles, CA, January 17-19, 1977), ACM, New York, NY (1977).]]
10. 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. 11.Duesterwald, E., Gupta, R., and Soffa, M.L., "Demand-driven computation of interprocedural data flow," in Conference Record of the Twenty-Second A CM Symposium on Principles of Programming Languages, (San Francisco, CA, Jan. 23-25, 1995), ACM, New York, NY (1995). (To appear.)]]
12. 12.Fischer, C.N. and LeBlanc, R.J., Crafting a Compiler, Benjamin/Cummings Publishing Company, Inc., Menlo Park, CA (1988).]]
13. 13.Giegerich, R., Moncke, U., and Wilhelm, R., "Invariance of approximative semantics with respect to program transformation," pp. 1-10 in Informatik-Fachberichte 50, Springer-Verlag, New York, NY (1981).]]
14. 14.Grove, D. and Torczon, L., "Interprocedural constant propagation: A study of jump function implementation," pp. 90-99 in Proceedings of the A CM SIGPLAN 93 Conference on Programming Language Design and Implementation, (Albuquerque, NM, June 23-25, 1993), ACM, New York, NY (1993).]]
15. 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. 16.Horwitz, S., Reps, T., and Binkley, D., "Interprocedural slicing using dependence graphs," ACM Trans. Program. Lang. Syst. 12(1)pp. 26-60 (January 1990).]]
17. 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. 18.Jones, N.D. and Mycroft, A., "Data flow analysis of applicative programs using minimal function graphs," pp. 296-306 in Conference Record of the Thirteenth A CM Symposium on Principles of Programming Languages, (St. Petersburg, FL, Jan. 13-15, 1986), ACM, New York, NY (1986).]]
19. 19.Kernighan, B.W., "Ratfor- A preprocessor for a rational Fortran," Software- Practice & Experience 5(4) pp. 395-406 (1975).]]
20. 20.Kildall, G., "A unified approach to global program optimization," pp. 194-206 in Conference Record of the First ACM Symposium on Principles of Programming Languages, ACM, New York, NY (1973).]]
21. 21.Knoop, J. and Steffen, B., "The interprocedural coincidence theorem," pp. 125-140 in Proceedings of the Fourth International Conference on Compiler Construction, (Paderborn, FRG, October 5- 7, 1992), Lecture Notes in Computer Science, Vol. 641, ed. U. Kastens and P. Pfahler, Springer-Vedag, New York, NY (1992).]]
22. 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. 23.Kou, L.T., "On live-dead analysis for global data flow problems," Journal of the ACM 24(3) pp. 473-483 (July 1977).]]
24. 24.Landi, W. and Ryder, B.G., "Pointer-induced aliasing: A problem classification," pp. 93-103 in Conference Record of the Eighteenth ACM Symposium on Principles of Programming Languages, (Orlando, FL, January 1991), ACM, New York, NY (1991).]]
25. 25.Nielson, F. and Nielson, H.R., "Finiteness conditions for fixed point iteration," in Conference Record of the 1992 A CM Symposium on Lisp and Functional Programming, (San Francisco, CA, June 22-24 1992), ACM, New York, NY (1992).]]
26. 26.Nielson, H.R. and Nielson, F., "Bounded fixed point iteration," pp. 71-82 in Conference Record of the Nineteenth ACM Symposium on Principles of Programming Languages, (Albuquerque, NM, January 1992), ACM, New York, NY (1992).]]
27. 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. 28.Reps, T., Horwitz, S., Sagiv, M., and Rosay, G., "Speeding up slicing," SIGSOFT 94: Proceedings of the Second ACM SIGSOFT Symposium on the Foundations of Software Engineering, (New Orleans, LA, December 7-9, 1994), ACM SIGSOFT Software Engineering Notes 19(December 1994). (To appear.)]]
29. 29.Reps, T., "Solving demand versions of interprocedural analysis problems," pp. 389-403 in Proceedings of the Fifth International Conference on Compiler Construction, (Edinburgh, Scotland, April 7-9, 1994), Lecture Notes in Computer Science, Vol. 786, ed. P. Fritzson,Springer-Verlag, New York, NY (1994).]]
30. 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. 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. 32.Zadeck, F.K., "Incremental data flow analysis in a structured program editor," Proceedings of the SIGPLAN 84 Symposium on Compiler Construction, (Montreal, Can., June 20-22, 1984), ACM SIGPLAN Notices 19(6)pp. 132-143 (june 1984).]]

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Paths and connectivity problems

• Software and its engineering

  • Software creation and management

    • Software development techniques

      • Flowcharts

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language types

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes

  • Randomness, geometry and discrete structures