Incremental data flow analysis

ABSTRACT

In this paper we present ACINCF and ACINCB, incremental update algorithms for forward and backward data flow problems, which are based on a linear equations model of Allen/Cocke interval analysis [Allen 77, Ryder 82a]. We have studied their performance on a robust structured programming language L. Given a set of localized program changes in a program in L, we can identify a priori the nodes in its flow graph whose corresponding data flow equations will be affected by the changes. We can characterize these affected nodes by their corresponding program structures and their relation to the original change sites.

REFERENCES

• 1: C. N. Alberga , A. L. Brown , G. B. Leeman, Jr. , M. Mikelsons , M. N. Wegman, A program development tool, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.92-104, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567543]
• 2: {Allen 71} Allen, F. E. A Basis for Program Optimization In Proceedings of 1971 IFIP Congress, pages 385-390. Institute of Electrical and Electronics Engineers. Inc., North Holland Publishing Company, Amsterdam. Holland, 1971.
• 3: {Allen 73} Allen, F. E. and Schwartz, J. T. Determining the Data Relationships in a Collection of Procedures. 1973.
• 4: {Allen 74} Allen, F. E. Interprocedural Data Flow Analysis. In Proceedings of 1974 IFIP Congress, pages 398-402. Institute of Electrical and Electronics Engineers, Inc., North Holland Publishing Company. Amsterdam, Holland, 1974.
• 5: F. E. Allen , J. Cocke, A program data flow analysis procedure, Communications of the ACM, v.19 n.3, p.137, March 1976 [doi>10.1145/360018.360025]
• 6: {Allen 79} Allen, F. E. private communication.
• 7: {Babich 78a} Babich, W. A. and Jazayeri, M. The Method of Attributes for Data Flow Analysis, Part I: Exhaustive Analysis. Acta Informatica 10:245-264, 1978.
• 8: {Babich 78b} Babich, W. A. and Jazayeri, M. The Method of Attributes for Data Flow Analysis, Part II: Demand Analysis. Acta Informatica 10:265-272, 1978.
• 9: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 10: {Elshoff 76} Elshoff, J. A Numerical Profile of Commercial PL/I Programs. Software Practice and Experience 6(4):505-525, 1976.
• 11: {Farrow 75} Farrow, R., Kennedy, K. and Zucconi, L. Graph Grammars and Global Program Data Flow Analysis. In Proceedings of Seventeenth Annual IEEE Symposium on the Foundations of Computer Science, pages 42-56. Institute of Electrical and Electronics Engineers, Inc., November, 1975.
• 12: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 13: {Kennedy 74} Kennedy, K. Schaeffer's Node Splitting Algorithm. SETL Newsletter # 125, February 6, 1974, Courant Institute of Mathematical Sciences, New York University.
• 14: Ken Kennedy , Linda Zucconi, Applications of a graph grammar for program control flow analysis, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.72-85, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512958]
• 15: D. F. Kibler , J. M. Neighbors , T. A. Standish, Program manipulation via an efficient production system, ACM SIGPLAN Notices, v.12 n.8, p.163-173, August 1977
• 16: {Knuth 71} Knuth, D. E. An Empirical Study of FORTRAN Programs. Software Practice and Experience 1:105-133, 1971.
• 17: David B. Loveman, Program Improvement by Source-to-Source Transformation, Journal of the ACM (JACM), v.24 n.1, p.121-145, Jan. 1977 [doi>10.1145/321992.322000]
• 18: Bob Paige , J. T. Schwartz, Expression continuity and the formal differentiation of algorithms, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.58-71, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512957]
• 19: {Paull 82} Paull, M. C. Design of Algorithms. in preparation, 1982.
• 20: John F. Reiser, SAIL, Stanford University, Stanford, CA, 1976
• 21: Thomas Reps, Optimal-time incremental semantic analysis for syntax-directed editors, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.169-176, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582172]
• 22: {Robinson 76} Robinson, S. K. and Torsun, I. S. An Empirical Analysis of FORTRAN Programs. Computer Journal 19(1):56-62, 1976
• 23: Barry K. Rosen, High-level data flow analysis, Communications of the ACM, v.20 n.10, p.712-724, Oct. 1977 [doi>10.1145/359842.359849]
• 24: {Ryder 74} Ryder, B G. The PFORT Verifier. Software Practice and Experience 4:359-377, 1974
• 25: {Ryder 79} Ryder, B. G. Constructing the Call Graph of a Program. IEEE Transactions on Software Engineering SE-5(3):216-225, May, 1979.
• 26: Barbara Gershon Ryder, Incremental data flow analysis based on a unified model of elimination algorithms, 1982
• 27: {Ryder 82b} Ryder, B. G. and Paull, M. C. A Unified Model of Elimination Algorithms. 1982 in preparation.
• 28: {Ryder 82c} Ryder, B. G. and Paull, M. C. A Comparison of incremental Data Flow Analysis Algorithms 1982. in preparation.
• 29: {Sharir 79} Sharir, M. Interprocedural Analysis of Global Variable Usage. 1979.
• 30: {Tarjan 74} Tarjan, R. E. Testing Flow Graph Reducibility, Journal of Computer and System Sciences 9.355-365, 1974.
• 31: Robert E Tarjan, Fast algorithms for solving path problems, Stanford University, Stanford, CA, 1979
• 32: {Ullman 73} Ullman, J D. Fast Algorithms for the Elimination of Common Subexpressions Acta Informatica 2(3):191-213, 1973.