Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (pdgs) to express the essential control and data dependencies among atomic program operations. In this paper, we provide a semantic justification for this practice by deriving two different forms of program dependence graph — the output pdg and the def-order pdg—and their semantic definitions from non-strict generalizations of the denotational semantics of the programming language. In the process, we demonstrate that both the output pdg and the def-order pdg (with minor technical modifications) are conventional data-flow programs. In addition, we show that the semantics of the def-order pdg dominates the semantics of the output pdg and that both of these semantics dominate—rather than preserve—the semantics of sequential execution.

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: Jeanne Ferrante , Karl J. Ottenstein, A program form based on data dependency in predicate regions, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.217-236, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567089]
• 3: 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]
• 4: S. Horwitz , J. Prins , T. Reps, On the adequacy of program dependence graphs for representing programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-157, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73573]
• 5: 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]
• 6: Ulrik Jørring , William L. Scherlis, Compilers and staging transformations, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.86-96, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512652]
• 7: 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]
• 8: OTTENSTEIN, K. J. An intermediate program form based on a cyclic data-dependence graph. Technical Report No 81-1, Department of Computer Science, Michigan Tech. University, 1981.
• 9: David A. Schmidt, Denotational semantics: a methodology for language development, William C. Brown Publishers, Dubuque, IA, 1986
• 10: R. Parsons-Selke, A rewriting semantics for program dependence graphs, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-24, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75279]
• 11: Mitchell Wand, Loops in combinator-based compilers, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.190-196, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567086]
• 12: Mitchell Wand, Semantics-directed machine architecture, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.234-241, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582179]
• 13: Mitchell Wand, Deriving Target Code as a Representation of Continuation Semantics, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.496-517, July 1982 [doi>10.1145/357172.357179]
• 14: Joe Warren, A hierarchical basis for reordering transformations, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.272-282, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800539]
• 15: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics
      D.3.4 Processors
          Subjects: Compilers
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

General Terms:
Algorithms, Design, Languages, Theory