article

Open access

The program dependence graph and its use in optimization

Editor: Susan L. Graham Authors:

Jeanne Ferrante,

Karl J. Ottenstein,

Joe D. WarrenAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 9, Issue 3

Pages 319 - 349

https://doi.org/10.1145/24039.24041

Published: 01 July 1987 Publication History

PDF eReader

Abstract

In this paper we present an intermediate program representation, called the program dependence graph (PDG), that makes explicit both the data and control dependences for each operation in a program. Data dependences have been used to represent only the relevant data flow relationships of a program. Control dependences are introduced to analogously represent only the essential control flow relationships of a program. Control dependences are derived from the usual control flow graph. Many traditional optimizations operate more efficiently on the PDG. Since dependences in the PDG connect computationally related parts of the program, a single walk of these dependences is sufficient to perform many optimizations. The PDG allows transformations such as vectorization, that previously required special treatment of control dependence, to be performed in a manner that is uniform for both control and data dependences. Program transformations that require interaction of the two dependence types can also be easily handled with our representation. As an example, an incremental approach to modifying data dependences resulting from branch deletion or loop unrolling is introduced. The PDG supports incremental optimization, permitting transformations to be triggered by one another and applied only to affected dependences.

References

[1]

AHO, A. V., SETHI, R., AND ULLMAN, J. D. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986. {An alternative reference is this book's predecessor, AHO, A. V. AND ULLMAN, J.D. Principles of Compiler Design. Addison-Wesley, 1977.}

Crossref

Google Scholar

[2]

ALBERGA, C. N., BROWN, A. L., LEEMAN, G. B., JR., MIKELSONS, M., AND WEGMAN, M. N. A program development tool. IBM J. Res. Dev 28, 1 (Jan. 1984).

Crossref

Google Scholar

[3]

ALLEN, F.E. Control flow analysis. In Proceedings of a Symposium on Compiler Optimization. SIGPLAN Not. 5, 7 (July 1970), 1-19.

Crossref

Google Scholar

[4]

ALLEN, F.E. Interprocedural analysis and the information derived by it. In Lecture Notes in Computer Science Vol. 23, Springer-Verlag, New York, 1974, 291-321.

Crossref

Google Scholar

[5]

ALLEN, F. E., AND COCKE, J. A catalogue of optimizing transformations. In Design and Optimization of Compilers, Randall Rustin, Ed., Prentice-Hall, Englewood Cliffs, NJ, 1972, 1-30.

Google Scholar

[6]

ALLEN, F. E., COCKE, J., AND KENNEDY, K. Reduction of operator strength. In Program Flow Analysis, Theory and Applications, S. Muchnick and N. Jones, Eds., Prentice-Hall, Englewood Cliffs, NJ, 1981, 79-101.

Google Scholar

[7]

ALLEN, J. R. Dependence analysis for subscripted variables and its application to program transformations. Ph.D. dissertation, Dept. of Computer Science, Rice University, Houston, TX, April 1983.

Crossref

Google Scholar

[8]

ALLEN, J. R., KENNEDY, K., PORTERFIELD, C., AND WARREN, J. Conversion of control dependence to data dependence. In Conference Record of the lOth Annual ACM Symposium on Principles o{ Programming Languages (Austin, Texas, Jan. 24-26, 1983), ACM, New York, 177-189.

Crossref

Google Scholar

[9]

ALLEN, J. R., AND KENNEDY, K. PFC: a program to convert FORTRAN to parallel form. Tech. Rep. 82-6, Dept. of Mathematical Sciences, Rice University, March 1982, 63 pages.

Google Scholar

[10]

ALLEN, R., AND KENNEDY, K. Programming environments for supereomputers. In Supercomputers: Algorithms, Architectures, and Scientific Computation, F. A. Matsen and T. Tajima, Eds., University of Texas Press, Austin, TX, 1986, 19-38.

Crossref

Google Scholar

[11]

BANERJEE, U. Data dependence in ordinary programs. Report 76-837, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, Nov. 1976.

Google Scholar

[12]

BURKE, M. An interval analysis approach toward interprocedural data flow analysis. IBM Research Report RC 10640, T. J. Watson Research Center, Yorktown Heights, NY, July 1984.

Google Scholar

[13]

BURKE, M., AND CYTRON, R. Interprocedural dependence analysis and parallelization. In Proceedings of the ACM SIGPLAN '86 Symposium on Compiler Construction (Paid Alto, CA, June 25-27, 1986). ACM SIGPLAN Not. 21, 7 (July 1986), 162-175.

Crossref

Google Scholar

[14]

COOPER, K., AND KENNEDY, K. Efficient computation of flow insensitive summary information. In Proceedings of the ACM SIGPLAN '84 Symposium on Compiler Construction (Montreal, June 17-22, 1984). ACM SIGPLAN Not. 19, 6 (June 1984), 247-258.

Crossref

Google Scholar

[15]

COOPER, K. Analyzing aliases of reference formal parameters. In Conference Record o/the 12th ACM Symposium on Principles of Programming Languages (New Orleans, LA, Jan. 14-16, 1985), ACM, New York, 281-290.

Crossref

Google Scholar

[16]

CYTRON, R., LOWRY, A., AND ZADECK, K. Code motion of control structures in high-level languages. In Conference Record 13th Annual ACM Symposium on Principles of Programming Languages (St. Petersburg, FL, Jan. 13-15, 1986), ACM, New York, 70-85.

Crossref

Google Scholar

[17]

DAVID, A. L., AND KELLER, R.M. Data flow program graphs. IEEE Comput. 15, 2 (Feb. 1982), 26-41.

Google Scholar

[18]

DENNIS, J.B. First version of a data flow procedure language, revised Comp. Struc. Group Memo 93 (MAC Tech. Memo 61) MIT LCS (May 1975) 21 pages.

Google Scholar

[19]

DENNIS, J.B. Data flow supercomputers. IEEE Comput. 13, 11 (Nov. 1980), 48-56.

Google Scholar

[20]

ELLCEY, S.J. The program dependence graph: interprocedural information representation and general space requirements. Master's thesis, Dept. of Computer Science, Michigan Technological Univ., Houghton, MI, Aug. 1985.

Google Scholar

[21]

FERRANTE, J. The program dependence graph as a basis for node splitting transformations. IBM Research Rep. RC 10542, Yorktown Heights, NY, June 1984.

Google Scholar

[22]

FERRANTE, J., AND MACE, M. On linearizing parallel code. In Conference Record of the 12th Annual ACM Symposium on Principles of Programming Languages (New Orleans, LA, Jan. 14-16, 1985), ACM, New York, 179-190.

Crossref

Google Scholar

[23]

FERRANTE, J., AND Oq~ENSTEIN, K. A program form based on data dependency in predicate regions. In Conference Record o/the lOth Annual ACM Symposium on Principles of Programming Languages (Austin, TX, Jan. 24-26, 1983), ACM, New York, 217-231.

Crossref

Google Scholar

[24]

FERRANTE, J., OTTENSTEIN, K., AND WARREN, g. D. The program dependence graph and its use in optimization. Lecture Notes in Computer Science Vol. 167, Springer-Verlag, 1984, 125-132.

Crossref

Google Scholar

[25]

GRAHAM, S., AND WEGMAN, M. A fast and usually linear algorithm for global flow analysis. J. ACM 23, 1 (Jan. 1976), 172-202.

Crossref

Google Scholar

[26]

HECHT, M.S. Flow Analysis of Computer Programs. Elsevier-North Holland, New York, 1977.

Crossref

Google Scholar

[27]

KAS'JANOV, V.N. Distinguishing hammocks in a directed graph. Soviet Math. Doklady 16, 5 (1975), 448--450.

Google Scholar

[28]

KENNEDY, K. Automatic translation of FORTRAN programs to vector form. Report 476- 029-4, Dept. of Mathematical Sciences, Rice Univ., Houston, TX, June 1980.

Google Scholar

[29]

KUCK, D.J. The Structure of Computers and Computations. Wiley, New York, 1978.

Crossref

Google Scholar

[30]

KUCK, D. J., KUHN, R. H., LEASURE, B., AND WOLFE, M. The structure of an advanced vectorizer for pipelined processors. In Proceedings IEEE 4th International COMPSAC (Chicago, IL, Oct. 1980), IEEE, New York, 709-715.

Google Scholar

[31]

KUCK, D. J., KUHN, R. H., PADUA, D. A., LEASURE, B., AND WOLFE, M. Dependence graphs and compiler optlmizations. In 8th Annual ACM Symposium on Principles of Programming Languages (Williamsburg, VA, Jan. 26-28, 1981), ACM, New York, 207-218.

Crossref

Google Scholar

[32]

KUHN, R.H. Optimization and interconnection complexity for parallel processors, single-stage networks and decision trees. Ph.D. dissertation, Rep. 80-1009, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, Feb. 1980.

Crossref

Google Scholar

[33]

LENGAUER, T., AND TARJAN, R.E. A fast algorithm for finding dominators in a fiowgraph. ACM Trans. Program. Lang. Syst. 1, 1 (July 1979), 121-141.

Crossref

Google Scholar

[34]

MCGRAW, J., SKEDZIELEWSKI, S., ALLAN, S., GRIT, D., OLDEHOEFT, R., GLAUERT, J., DOBES, I., AND HOHENSEE, P. SISAL: streams and iteration in a single-assignment language. Language reference manual version 1.1. Report M-146, Lawrence Livermore National Laboratory, July 20, 1983.

Google Scholar

[35]

MIKELSONS, M. Prettyprinting in an interactive environment. In Proceedings of the ACM SIGPLAN/SIGOA Symposium on Text Manipulation (Portland, OR, June 1981), ACM, New York, 108-116.

Crossref

Google Scholar

[36]

OTTENSTEIN, K.J. Data-flow graphs as an intermediate program form. Ph.D. dissertation, Computer Sciences Dept., Purdue University, Lafayette, IN, Aug. 1978.

Crossref

Google Scholar

[37]

OTTENSTEIN, K.J. An intermediate program form based on a cyclic data-dependence graph. CS-TR 81-1, Dept. of Computer Science, Michigan Technological Univ., Houghton, MI, Oct. 1981; July 1982, errata.

Google Scholar

[38]

OTTENSTEIN, K. J., AND OTTENSTEIN, L. M. The program dependence graph in a software development environment. In Proceedings of the ACM SIGPLAN/SIGSOFT Symposium on Practical Programming Development Environments (Pittsburgh, PA, April 23-25, 1984), ACM SIGPLAN Not. 19, 5 (May 1984), 177-184, and Softw. Eng. Notes 9, 3.

Crossref

Google Scholar

[39]

OTTENSTEIN, K.J. A simplified view of reduction in strength. CS-TR 85-4c, Michigan Technological Univ., Houghton, MI, Aug. 1986.

Google Scholar

[40]

PADUA, D.A. Multiprocessors: discussion of some theoretical and practical problems. Ph.D. dissertation, Computer Sciences Dept., Univ. of Illinois, Urbana-Champaign, Sept. 1979.

Crossref

Google Scholar

[41]

PADUA, D. A., KUCK, D. J., AND LAWRIE, D. High-speed multiprocessors and their compilers. IEEE Trans. Comput. 29, 9 (Sept. 1980), 763-776.

Google Scholar

[42]

REIF, J. H., AND LEWgS, H.R. Symbolic evaluation and the global value graph. In Conference Record of the 4th Annual ACM Symposium on Principles of Programming Languages (Los Angeles, CA, Jan. 17-19, 1977), ACM, New York, 104-118.

Crossref

Google Scholar

[43]

RYDER, B.G. Incremental data flow analysis. In Conference Record lOth Annual ACM Symposium on Principles of Programming Languages (Austin, TX, Jan. 1983), ACM, New York, 167-176.

Crossref

Google Scholar

[44]

SARKAR, V., AND HENNESSY, J. Compile-time partitioning and scheduling of parallel programs. In Proceedings of the ACM SIGPLAN Compiler Construction Conference (Palo Alto, CA, June 25-27, 1986), ACM SIGPLAN Not. 21, 7 (July 1986).

Crossref

Google Scholar

[45]

SARKAR, V., AND HENNESSY, J. Partitioning parallel programs for macro-datafiow. In Proceedings of the ACM Conference on LISP and Functional Programming (Cambridge, UK, Aug. 4-6, 1986), ACM, New York, 202-211.

Crossref

Google Scholar

[46]

SKEDZIELEWSKI, S., AND GLAUERT, J. IFI: an intermediate form for applicative langauges, draft 4. Lawrence Livermore National Laboratory, Livermore, CA, June 26, 1983.

Google Scholar

[47]

TISCHLER, R., SCHAUFLER, R., AND PAYNE, C. Static analysis of programs as an aid to debugging. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on High-Level Debugging (Pacific Grove, CA, March 20-23, 1983), ACM Softw. Eng. Notes 8, 4 (Aug. 1983) and in ACM SIGPLAN Not. 18, 8 (Aug. 1983), 155-158.

Crossref

Google Scholar

[48]

TOWLE, R.A. Control and data dependence for program transformations. Ph.D. dissertation, Univ. of Illinois, Urbana-Champaign, Feb. 1976.

Crossref

Google Scholar

[49]

TRELEAVEN, P. C., HOPKINS, R. P., AND RAUTENBACH, P.W. Combining data flow and control flow computing. Comput. J. 25, 2 (1982), 208-217.

Google Scholar

[50]

WARREN, J. A hierarchical basis for reordering transformations. In Conference Record of the 11th Annual ACM Symposium on Principles of Programming Languages (Salt Lake City, UT, Jan. 1984), ACM, New York, 272-282.

Crossref

Google Scholar

[51]

WATERS, R.C. The programmer's apprentice: knowledge based program editing. IEEE Trans. Softw. Eng. SE-8, I (Jan. 1982), 1-12.

Google Scholar

[52]

WATERS, R.C. Automatic analysis of the logical structure of programs. AI-Lab TR-492, MIT, Cambridge, MA., Dec. 1978. Available as NTIS AD-A0$4 818.

Crossref

Google Scholar

[53]

WEGMAN, M. Summarizing graphs by regular expressions. In Conference Record of the lOth Annual ACM Symposium on Principles of Programming Languages (Austin, TX, Jan. 24-26, 1983), ACM, New York, 203-212.

Crossref

Google Scholar

[54]

WEISER, M. Program slicing. In Proceedings of the 5th International Conference on Software Engineering (San Diego, CA, March 9-12, 1981), IEEE Computer Society Press, New York, 439-449.

Crossref

Google Scholar

[55]

WEgSER, M. Programmers use slices when debugging. Commun. ACM 25, 7 (July 1982), 446-452.

Crossref

Google Scholar

[56]

WOLFE, M.J. Optimizing supercompilers for supercomputers. Ph.D. dissertation. Tech. Rep. UIUCDCS-R-82-1105, Univ. of Illinois, Urbana-Champaign, Oct. 1982.

Crossref

Google Scholar

Cited By

View all

Lee SBinkley DFeldt RGold NYoo S(2025)Causal program dependence analysisScience of Computer Programming10.1016/j.scico.2024.103208240(103208)Online publication date: Feb-2025
https://doi.org/10.1016/j.scico.2024.103208
Gerling L(2025)Syntax-preserving program slicing for C-based software product linesJournal of Systems and Software10.1016/j.jss.2024.112255219(112255)Online publication date: Jan-2025
https://doi.org/10.1016/j.jss.2024.112255
Ding ZLi SChen CHe C(2025)Program Dependence Net and on-demand slicing for property verification of concurrent system and softwareJournal of Systems and Software10.1016/j.jss.2024.112221219(112221)Online publication date: Jan-2025
https://doi.org/10.1016/j.jss.2024.112221
Show More Cited By

Index Terms

The program dependence graph and its use in optimization
1. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Ordinary differential equations
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

On the control dependence in the program dependence graph
CSC '88: Proceedings of the 1988 ACM sixteenth annual conference on Computer science

The program dependence graph, PDG, is used to represent the data and control dependencies between the statements of some program. The data dependencies between the statements are fully understood and they correspond to the definition-use chain. On the ...
Fast condensation of the program dependence graph
PLDI '13

Aggressive compiler optimizations are formulated around the Program Dependence Graph (PDG). Many techniques, including loop fission and parallelization are concerned primarily with dependence cycles in the PDG. The Directed Acyclic Graph of Strongly ...
Fast condensation of the program dependence graph
PLDI '13: Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation

Aggressive compiler optimizations are formulated around the Program Dependence Graph (PDG). Many techniques, including loop fission and parallelization are concerned primarily with dependence cycles in the PDG. The Directed Acyclic Graph of Strongly ...

Reviews

Reviewer: John R. Levine

The program dependence graph (PDG) is a program representation that combines control flow and data flow information into a single structure. The authors cite previous work on control dependence graphs, which represent control flow without data flow, and on data dependence graphs, which show data flow without control flow. The PDG combines data flow and control flow information into a single structure that is useful for a variety of program transformations and optimizations. Nodes in the PDG represent statements, expressions, and predicates, and edges represent data values passed from one expression to another and control conditions that influence the order of execution. The authors start by showing how to construct a PDG from the control and data flow information in the original program. They then describe some variants of the PDG that may be more convenient for different source languages or various applications. The next section shows some applications of the PDG. The authors show how it can be used to find parts of a program that can be made parallel, to do code motion and loop fusion optimizations, and to find the parts of a program that can affect a given variable, which is useful in debugging. Finally, they discuss incremental optimization, which involves updating the PDG as an optimization is made, rather than having to examine the whole program again. For example, if an optimization removes some dead code, the data dependencies for that dead code can be removed directly. They claim that this procedure is much faster than the conventional equivalent. The PDG certainly appears to be a powerful mechanism that unifies a broad class of program analyses and transformations. My primary concern is that it also appears to be too complicated to construct and very large; the authors' estimate is 50 percent larger than the equivalent triples although it seems to me that their estimate is conservative. Nonetheless, they sketch out some impressive results, and we will probably be seeing many more PDG applications in the near future.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 9, Issue 3

July 1987

166 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/24039

Editor:
Susan L. Graham

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1987

Published in TOPLAS Volume 9, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2,197
Total Citations
View Citations
12,422
Total Downloads

Downloads (Last 12 months)1,329
Downloads (Last 6 weeks)186

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lee SBinkley DFeldt RGold NYoo S(2025)Causal program dependence analysisScience of Computer Programming10.1016/j.scico.2024.103208240(103208)Online publication date: Feb-2025
https://doi.org/10.1016/j.scico.2024.103208
Gerling L(2025)Syntax-preserving program slicing for C-based software product linesJournal of Systems and Software10.1016/j.jss.2024.112255219(112255)Online publication date: Jan-2025
https://doi.org/10.1016/j.jss.2024.112255
Ding ZLi SChen CHe C(2025)Program Dependence Net and on-demand slicing for property verification of concurrent system and softwareJournal of Systems and Software10.1016/j.jss.2024.112221219(112221)Online publication date: Jan-2025
https://doi.org/10.1016/j.jss.2024.112221
Wu YChen YPeng XHu BWang XFu BZhao W(2025)CloneRipples: predicting change propagation between code clone instances by graph-based deep learningEmpirical Software Engineering10.1007/s10664-024-10567-030:1Online publication date: 1-Feb-2025
https://dl.acm.org/doi/10.1007/s10664-024-10567-0
Kim KShin JPark JKim J(2024)Performance evaluations of AI‐based obfuscated and encrypted malicious script detection with feature optimizationETRI Journal10.4218/etrij.2024-0255Online publication date: 8-Dec-2024
https://doi.org/10.4218/etrij.2024-0255
Bennouk KAit Aali NEl Bouzekri El Idrissi YSebai BFaroukhi AMahouachi D(2024)A Comprehensive Review and Assessment of Cybersecurity Vulnerability Detection MethodologiesJournal of Cybersecurity and Privacy10.3390/jcp40400404:4(853-908)Online publication date: 7-Oct-2024
https://doi.org/10.3390/jcp4040040
Shi YYin YYu MChu L(2024)CogCol: Code Graph-Based Contrastive Learning Model for Code SummarizationElectronics10.3390/electronics1310181613:10(1816)Online publication date: 8-May-2024
https://doi.org/10.3390/electronics13101816
Paiva JLeal JFigueira Á(2024)Comparing semantic graph representations of source code: The case of automatic feedback on programming assignmentsComputer Science and Information Systems10.2298/CSIS230615004P21:1(117-142)Online publication date: 2024
https://doi.org/10.2298/CSIS230615004P
Lin RFu YYi WYang JCao JDong ZXie FLi H(2024)Vulnerabilities and Security Patches Detection in OSS: A SurveyACM Computing Surveys10.1145/369478257:1(1-37)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3694782
Pan JWu HLeesatapornwongsa TNath SHuang PWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)Efficient Reproduction of Fault-Induced Failures in Distributed Systems with Feedback-Driven Fault InjectionProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695979(46-62)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695979
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

On the control dependence in the program dependence graph

Fast condensation of the program dependence graph

Fast condensation of the program dependence graph

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations