Incremental data-flow analysis algorithms

ABSTRACT

An incremental update algorithm modifies the solution of a problem that has been changed, rather than re-solving the entire problem. ACINCF and ACINCB are incremental update algorithms for forward and backward data-flow analysis, respectively, based on our equations model of Allen-Cocke interval analysis. In addition, we have studied their performance on a “nontoy” structured programming language L. Given a set of localized program changes in a program written in L, we identify a priori the nodes in its flow graph whose corresponding data-flow equations may be affected by the changes. We characterize these possibly affected nodes by their corresponding program structures and their relation to the original change sites, and do so without actually performing the incremental updates. Our results can be refined to characterize the reduced equations possibly affected if structured loop exit mechanisms are used, either singly or together, thereby relating richness of programming language usage to the ease of incremental updating.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: 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]
• 3: ALLEN, F. E. Interprocedural data flow analysis. In Proceedings of 1974 ZFZP Congress. IEEE Press, New York, 1974, pp. 398-402.
• 4: 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]
• 5: BABICH, W. A., AND JAZAYERI, M. The method of attributes for data flow analysis, Part II: Demand analysis. Acta Znf. 10 (1978), 265-272.
• 6: BABICH, W. A., AND JAZAYERI, M. The method of attributes for data flow analysis, Part I: Exhaustive analysis. Actu Znf. 10 (1978), 245-264.
• 7: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• 8: BURKE, M. An interval analysis approach toward interprocedural data flow analysis. Comput. Sci. Tech. Rep. RC 10640, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., July 1984.
• 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: Keith D. Cooper , Ken Kennedy, Efficient computation of flow insensitive interprocedural summary information, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.247-258, June 17-22, 1984, Montreal, Canada
• 11: ELSHOFF, J. A numerical profile of commercial PL/I programs. Softw. Pratt. &per. 6,4 (1976), 505-525.
• 12: ELSHOFF, J. The influence of structured programming on PL/I program profiles. IEEE Trans. Softw. Eng. SE-3,5 (Sept. 1977), 364-368.
• 13: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 14: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 15: ISAACSON, E., AND KELLER, H. B. Anulysis of Numerical Methods. Wiley, New York, 1966.
• 16: Gregory F. Johnson , C. N. Fischer, A meta-language and system for nonlocal incremental attribute evaluation in language-based editors, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.141-151, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318627]
• 17: JOHNSON, S. C. LINT, A C program checker. In UNIX System Programmer's Manual Vol. 2. Holt, Rinehart and Winston, New York, 1979, pp. 278-290.
• 18: D. F. Kibler , J. M. Neighbors , T. A. Standish, Program manipulation via an efficient production system, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.163-173, August 15-17, 1977
• 19: KNUTH, D. E. An empirical study of FORTRAN programs. Softw. Pruct. Exper. I (1971), 105-133.
• 20: 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]
• 21: Larry Melvin Masinter, Global program analysis in an interactive environment, 1980
• 22: OSTERWEIL, L. J., AND FOSDICK, L. D. DAVE-A validation, error detection, and documentation system for FORTRAN programs. Softw. Pratt. Exper. 6 (Sept. 1976), 473-486.
• 23: PAIGE, R. Formal Differentiation-A Program Synthesis Technique. UMI Research Press, Ann Arbor, Mich., 1981.
• 24: Marvin C. Paull, Algorithm design: a recursion transformation framework, Wiley-Interscience, New York, NY, 1988
• 25: REISER, J., ED. SAIL. Memo AIM-289, Artificial Intelligence Laboratory, Stanford Univ., Stanford, Calif., Aug. 1976.
• 26: 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]
• 27: Thomas W. Reps , Carla Marceau , Tim Teitelbaum, Remote attribute updating for language-based editors, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-13, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512645]
• 28: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 29: ROBINSON, S. K., AND TORSUN, I. S. An empirical analysis of FORTRAN programs. Comput. J. 19, 1 (1976), 56-62.
• 30: 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]
• 31: Barry K. Rosen, Linear cost is sometimes quadratic, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.117-124, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567545]
• 32: RYDER, B. G. The PFORT verifier. Softw. Pratt. Exper. 4 (1974), 359-377.
• 33: RYDER, B. G. Constructing the call graph of a program. IEEE Trcms. Softw. Eng. SE-5, 3 (May 1979), 216-225.
• 34: Barbara Gershon Ryder, Incremental data flow analysis based on a unified model of elimination algorithms, 1982
• 35: RYDER, B. G. An application of static program analysis to software maintenance. In Proceedings of the 12th Hawaii Znternatianal Conference on System Sciences, Vol. II: Software (Kona, Hawaii, Jan. 1987). University of Hawaii and University of S.W. Louisiana, in cooperation with the ACM and the IEEE Technical Committee on Computational Medicine. pp. 82-91. (Also available in abridged version as Tech. Rep. CAIP-TR-009, Center for Computer Aids for Industrial Productivity, Rutgers Univ., New Brunswick, N.J., July 1986.)
• 36: RYDER, B. G., AND CARROLL, M. D. A new structure for performing interval-based incremental data flow analysis. Tech. Rep. CAIP-TR-008, Center for Computer Aids for Industrial Productivity, Rutgers Univ., New Brunswick, N.J., May 1986.
• 37: RYDER, B. G., AND CARROLL, M. D. Interval-based incremental data flow analysis. Tech. Rep. CAIP-TR-007, Center for Computer Aids for Industrial Productivity, Rutgers Univ., New Brunswick, N.J., May 1986.
• 38: Martin Carroll , Barbara G Ryder, An incremental algorithm for software analysis, Proceedings of the second ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.171-179, December 09-11, 1986, Palo Alto, California, United States
• 39: RYDER, B. G., AND CARROLL, M. D. An incremental analysis algorithm for software systems. Tech. Rep. CAIP-TR-035, Center for Computer Aids for Industrial Productivity, Rutgers Univ., New Brunswick, N.J., May 1987.
• 40: Barbara G. Ryder , Marvin C. Paull, Elimination algorithms for data flow analysis, ACM Computing Surveys (CSUR), v.18 n.3, p.277-316, Sept. 1986 [doi>10.1145/27632.27649]
• 41: SCHWARTZ, J. T. Interprocedural optimizations. SETL Newsl. 134, Courant Institute of Mathematical Sciences, New York Univ., New York, July 1, 1974.
• 42: SCHWARTZ, J. T., AND SHARIR, M. A design for optimizations of the bitvectoring class. Comput. Sci. Tech. Rep. 17, Courant Institute of Mathematical Sciences, New York Univ., New York, Sept. 1979.
• 43: SHARIR, M., AND PNUELI, A. Two approaches to interprocedural data flow analysis. In Program Flaw Analysis: Theory and Applications, S. Muchnick and N. Jones, Eds. Prentice-Hall, Englewood Cliffs, N.J. 1981, pp. 189-234.
• 44: SHIMASAKI, M., FUKAYA, S., IKEDA, K., AND KIYONO, T. An analysis of PASCAL programs in compiler writing. Softw. Pratt. Erper. 10,2 (Feb. 1980), 149-158.
• 45: TARJAN, R. E. Testing flow graph reducibility. J. Comput. Syst. Sci. 9 (1974), 355-365.
• 46: Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
• 47: ULLMAN, J. D. Fast algorithms for the elimination of common subexpressions. Acta Znf. 2, 3 (1973), 191-213.
• 48: Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, 1984
• 49: Polle T. Zellweger, An interactive high-level debugger for control-flow optimized programs (Summary), Proceedings of the ACM SIGSOFT/SIGPLAN software engineering symposium on High-level debugging, p.159-171, January 1983 [doi>10.1145/800007.808029]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Languages