Data flow analysis of applicative programs using minimal function graphs

ABSTRACT

Data or program flow analysis is concerned with the static analysis of programs, to obtain as much information as possible about their possible run time behavior without actually having to run the programs. Due to the unsolvability of the halting problem (and nearly any other question concerning program behavior), such analyses are necessarily only approximate whenever the analysis algorithm is guaranteed to terminate. Further, exact analysis may be impossible due to the lack of knowledge of input data values, so the analysis can at best yield information about sets of possible computations.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
• 3: (Clarke, Richardson 81) Clarke, L. A. and D. J. Richardson. "Symbolic Program Evaluation Methods for Program Analysis", <i>in Program Flow Analysis. Theory and Applications.</i> Englewood Cliffs, NJ. Prentice-Hall, 1981
• 4: 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]
• 5: Patrick Cousot , Radhia Cousot, Automatic synthesis of optimal invariant assertions: Mathematical foundations, ACM SIGPLAN Notices, v.12 n.8, p.1-12, August 1977
• 6: (Cousot, Cousot 77c) Cousot, Patrick and Radhia Cousot, "Static Determination of Dynamic Properties of Recursive Procedures," <i>IFIP Working Conference on Programming Concepts,</i> St. Andrews, N. B., Canada (August 1977), ed. E. J. Neuhold. New York: North-Holland, pp. 237--277.
• 7: (Donzeau-Gouge 81) Donzeau-Gouge, Veronique, "Denotational Definitions of Properties of Program Computations", <i>in Program Flow Analysis; Theory and Applications,</i> Englewood Cliffs, NJ, Prentice-Hall, 1981
• 8: Lloyd D. Fosdick , Leon J. Osterweil, Data Flow Analysis in Software Reliability, ACM Computing Surveys (CSUR), v.8 n.3, p.305-330, Sept. 1976 [doi>10.1145/356674.356676]
• 9: Michael J. C. Gordon, The Denotational Description of Programming Languages: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1979
• 10: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 11: (Hewitt, Smith) Hewitt, C. and B. Smith, "Towards a Programming Apprentice", <i>Proc. of IEEE TransSoftware Eng.,</i> SE-1, no. 1 (March 1975), 26--45
• 12: (Jazayeri 75) Jazayeri, Mehdi, "Live Variable Analysis, Attribute Grammars, and Program Optimization", tech. report, Univ. N. Carolina, Chapel Hill, NC, 1975
• 13: Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
• 14: Neil D. Jones , Peter Sestoft , Harald Sondergaard, An experiment in partial evaluation: the generation of a compiler generator, Proc. of the first international conference on Rewriting techniques and applications, p.124-140, December 1985, Dijon, France
• 15: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 16: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• 17: Alan Mycroft, The Theory and Practice of Transforming Call-by-need into Call-by-value, Proceedings of the Fourth 'Colloque International sur la Programmation' on International Symposium on Programming, p.269-281, April 22-24, 1980
• 18: Mycroft 81) Mycroft, Alan, <i>Abstract Interpretation and Optimising Transformations for Applicative Programs</i>, Ph. D. Thesis, University of Edinburgh, Scotland, 1981.
• 19: Alan Mycroft , Flemming Nielson, Strong Abstract Interpretation Using Power Domains (Extended Abstract), Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.536-547, July 18-22, 1983
• 20: (Nielson 82) Nielson, Flemming, "A Denotational Framework for Flow Analysis", <i>Acta Informatica, Springer-Verlag</i>, Vol. 18, pp. 265--287, 1982.
• 21: (Nielson 84) Nielson, Flemming, <i>Abstract Interpretation Using Domain Theory</i>, thesis CST-31-84, University of Edinburgh, Scotland, 1984.
• 22: Micha Sharir, Data Flow Analysis of Applicative Programs, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.98-113, July 13-17, 1981
• 23: Michel Sintzoff, Calculating properties of programs by valuations on specific models, Proceedings of ACM conference on Proving assertions about programs, p.203-207, January 06-07, 1972, Las Cruces, New Mexico, United States
• 24: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977