Elimination algorithms for data flow analysis

ABSTRACT

A unified model of a family of data flow algorithms, called elimination methods, is presented. The algorithms, which gather information about the definition and use of data in a program or a set of programs, are characterized by the manner in which they solve the systems of equations that describe data flow problems of interest. The unified model provides implementation-independent descriptions of the algorithms to facilitate comparisons among them and illustrate the sources of improvement in worst case complexity bounds. This tutorial provides a study in algorithm design, as well as a new view of these algorithms and their interrelationships.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: ALLEN, F. E. 1971. A basis for program optimization. In Proceedings of the 1971 IFIP Congress. IEEE, North Holland Publ., Amsterdam, pp. 385-390.
• 3: ALLEN, F. E. 1974. Interprocedural data flow analysis. In Proceedings of 1974 IFIP Congress. IEEE, North Holland Publ., Amsterdam, 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: BACKUS, J. W., BEEMER, R. J., BEST, S., GOLDBERG, R., HAIBT, L. M., HERRICK, H. L., NELSON, R. A., SAYRE, D., SHERIDAN, P. B., STERN, H., ZILLER, I., HUGHES, R. A., AND Nu~r, R. 1957. The FORTRAN automatic coding systern. In Proceedings of the Western Joint Computer Conference (Los Angeles, Calif.), pp. 188-198. Also in Programming Systems and Languages, S. Rosen, Ed. McGraw-Hill, New York, 1967, pp. 29-47.
• 6: 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]
• 7: 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]
• 8: BURKE, M. 1984. An interval analysis approach toward interprocedural data flow analysis. Computer Science Tech. Rep. RC 10640, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, July.
• 9: John Cocke, Global common subexpression elimination, Proceedings of a symposium on Compiler optimization, p.20-24, July 27-28, 1970, Urbana-Champaign, Illinois
• 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: FARROW, R., KENNEDY, K., AND ZUCCONI, L. 1975. Graph grammars and global program data flow analysis. In Proceedings of the 17th Annual IEEE Symposium on the Foundations of Computer Science (Nov.). IEEE, New York, pp. 42-56.
• 12: FONG, A. C., AND ULLMAN, J. D. 1977. Finding the depth of a flow graph. Comput. Syst. Sci. 15, 300- 309.
• 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: HECHT, M. S., AND ULLMAN, J. D. 1977. A simple algorithm for global data flow analysis problems. SIAM J. Comput. 4, 4 (Dec.), 519-532.
• 16: HOPCROrT, J. E., AND ULLMAN, J. D. 1972. An n log n algorithm for reduction of flow graphs. In Proceedings of the 6th Annual Princeton Conference on Information Sciences and Systems (Princeton, N.J., Mar.), M. E. Van Valkenberg and M. Edelberg, Eds. Dept of Electrical Engineering, Princeton Univ., Princeton, N.J., pp. 119-122.
• 17: ISAACSON, E., AND KELLER, H. B. 1966. Analysis of Numerical Methods. Wiley, New York.
• 18: KENNEDY, K. 1971. A global flow analysis algorithm. Int. J. Comput. Math. Sect. A 3, (Dec.), 5-15.
• 19: KENNEDY, K. 1979. A survey of data flow analysis techniques. In Program Flow Analysis: Theory and Applications, S. Muchnick and N. jones Eds., Prentice-Hall, Englewood Cliffs, N.J., pp. 5-54.
• 20: 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]
• 21: 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]
• 22: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 23: KNUTH, D. E. 1971. An empirical study of FOR- TRAN programs. So{tw. Pract. Exper. i, 105-133.
• 24: PAULL, M. C. 1987. Introduction to Algorithm Design Principles. Wiley-Interscience, New York, in press.
• 25: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 26: ROBINSON, S. K., AND TORSUN, I. S. 1976. An empirical analysis of FORTRAN programs. Comput. J. 19, 1, 56-62.
• 27: RYDER, B. G. 1974. The PFORT verifier. Softw. Pract. Exper. 4, 359-377.
• 28: RYDER, B. G. 1979. Constructing the call graph of a program. IEEE Trans. So{tw. Eng. SE-5, 3 (May), 216-225.
• 29: Barbara G. Ryder, Incremental data flow analysis, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.167-176, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567084]
• 30: Barbara Gershon Ryder, Incremental data flow analysis based on a unified model of elimination algorithms, 1982
• 31: RYDER, B. G. 1985. Incremental algorithms for software systems. Tech. Rep. DCS-TR-158, Dept. of Computer Science, Rutgers Univ., New Brunswick, N.J., July.
• 32: 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
• 33: RYDER, B. G., AND PAULL, M. C. 1983. Incremental data flow analysis algorithms. Tech. Rep. DCS- TR-131, Dept. of Computer Science, Rutgers Univ., New Brunswick, N.J. Being reviewed for publication.
• 34: SCHWARTZ, J. T., AND SHARIR, M. 1978. Tarjan's fast interval finding algorithm. SETL Newsletter No. 204, Mar. 3, 1978, Courant Institute of Mathematical Sciences, New York Univ., New York.
• 35: SCHWARTZ, J. T., AND SHARIR, M. 1979. A design for optimizations of the bitvectoring class. Tech. Rep. 17, Dept. of Computer Science, Courant Institute of Mathematical Sciences, New York Univ., New York, Sept.
• 36: SHARIR, M. 1977. On interprocedural flow analysis. SETL Newsletters No. 187, Apr. 1977, No. 187a, May 1977, Courant institute of Mathematical Sciences, New York Univ., New York.
• 37: TARJAN, R. E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 2, 146- 159.
• 38: TARJAN, R. E. 1974. Testing flow graph reducibility. J. Comput. Syst. Sci. 9, 355-365.
• 39: Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
• 40: 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]
• 41: Robert Endre Tarjan, A Unified Approach to Path Problems, Journal of the ACM (JACM), v.28 n.3, p.577-593, July 1981 [doi>10.1145/322261.322272]
• 42: ULLMAN, J. D. 1973. Fast algorithms for the elimination of common subexpressions. Acta Inform. 2, 3, 191-213.
• 43: Mark N. Wegman, General and efficient methods for global code improvement, 1981
• 44: Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.132-143, June 17-22, 1984, Montreal, Canada

INDEX TERMS

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

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

General Terms:
Algorithms, Languages