A flexible approach to interprocedural data flow analysis and programs with recursive data structures

ABSTRACT

A new approach to data flow analysis of procedural programs and programs with recursive data structures is described. The method depends on simulation of the interpreter for the subject programming language using a retrieval function to approximate a program's data structures.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	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]
	3	Patrick Cousot , Radhia Cousot, Automatic synthesis of optimal invariant assertions: Mathematical foundations, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.1-12, August 15-17, 1977
	4	Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
	5	Eng75 Engelfriet, Joost, Tree Automata and Tree Grammars. DAIMI Report FN-10, Dept. of Computer Science, University of Aarhus, Aarhus, Denmark, April 1975.
	6	Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
	7	JoM81 Jones, Neil D. & Steven S. Muchnick, Flow Analysis and Optimization of LISP-Like Structures, in Steven S. Muchnick & Neil D. Jones (eds.), Program Flow Analysis: Theory and Applications, Prentice-Hall, Englewood Cliffs, New Jersey, 1981, pp. 102 -- 131.
	8	Jon80 Jones, Neil D., Flow Analysis of Lambda Expressions, Technical Report DAIMI IR-23, Computer Science Department, University of Aarhus, Aarhus, Denmark, October 1980.
	9	Ken76 Kennedy, Ken, A Comparison of Two Algorithms for Global Data Flow Analysis, SIAM J. Comput., vol. 5, no. 1, 1976, pp. 158 -- 180.
	10	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]
	11	McC63 McCarthy, John, Towards a Mathematical Science of Computation, Information Processing 1962, North-Holland, Amsterdam, 1963, pp. 220 -- 226.
	12	Nie80 Nielson, Flemming, Semantic Foundations of Data Flow Analysis, Technical Report DAIMI PB-131, Computer Science Department, Aarhus University, Aarhus, Denmark, February 1981.
	13	John H. Reif, Data flow analysis of communicating processes, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.257-268, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567777]
	14	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
	15	ShP81 Sharir, Micha & Amir Pnueli, Two Approaches to Interprocedural Data Flow Analysis, in Steven S. Muchnick & Neil D. Jones (eds.), Program Flow Analysis: Theory and Applications, Prentice-Hall, Englewood Cliffs, New Jersey, 1981, pp. 189 -- 234.
	16	Tha73 Thatcher, James W., Tree Automata: An Informal Survey, in Alfred V. Aho (ed.), Currents in the Theory of Computing, Prentice-Hall, Englewood Cliffs, New Jersey, 1973, pp. 143 -- 172.