On the adequacy of program dependence graphs for representing programs

ABSTRACT

Program dependence graphs were introduced by Kuck as an intermediate program representation well suited for performing optimizations, vectorization, and parallelization. There are also additional applications for them as an internal program representation in program development environments. In this paper we examine the issue of whether a program dependence graph is an adequate structure for representing a program's execution behavior. (This question has apparently never been addressed before in the literature). We answer the question in the affirmative by showing that if the program dependence graphs of two programs are isomorphic then the programs are strongly equivalent.

REFERENCES

• Aho86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Allen82: Allen, J.R. and K. Kennedy, "PFC: A program to convert Fortran to parallel form," Rep. MASC-TR82-6, Dept. of Math. Sciences, Rice Univ., Houston, Tex. (Mar. 1982).
• Allen83: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• Bannerjee79: Utpal Banerjee, Speedup of ordinary programs, 1979
• Ferrante87: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• Horwitz87: Horwitz, S., J. Prins, and T. Reps, "Integrating non-interfering versions of programs," Report 690, Department of Computer Sciences, University of Wisconsin--Madison (Mar. 1987).
• Horwitz88: S. Horwitz , J. Prins , T. Reps, Integrating non-intering versions of programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-145, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73572]
• Kuck72: Kuck, D.J., Y. Muraoka, and S.C. Chen, "On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up," IEEE Transactions on Computers C-21, pp. 1293-1310 (Dec. 1972).
• Kuck78: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• Kuck81: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• Ottenstein84: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
• Towle76: Towle, R., "Control and data dependence for program transformations," TR 76-788, Dept. of Computer Science, Univ. of B.linois, Urbana-Champaign, IL (Mar. 1976).
• Wolfe82: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computability theory

General Terms:
Design, Languages, Theory