The program dependence graph and its use in optimization
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot the international journal of robotics research and application · doi:10.1108/ir.1999.04926fae.001 · Cited by 39,228 · see citing works
Compilers: Principles, Techniques, and Tools
Aho, A. V., Sethi, R., & Ullman, J. D. (1986) · Cited by 8,152 · see citing works
Weiser, M. (1984) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1984.5010248 · Cited by 3,216 · see citing works
Aho, A. V., & Ullman, J. D. (1977) · International Linear Collider · Cited by 1,003 · see citing works
Optimizing supercompilers for supercomputers
Wolfe, M. (2020) · ACM International Conference on Supercomputing (ICS) · doi:10.1145/3392717.3400034 · Cited by 839 · see citing works
Programmers use slices when debugging
Weiser, M. (1982) · Communications of the ACM · doi:10.1145/358557.358577 · Cited by 763 · see citing works
Allen, F. E. (1970) · ACM SIGPLAN Notices · doi:10.1145/390013.808479 · Cited by 743 · see citing works
Automatic translation of FORTRAN programs to vector form
Allen, R., & Kennedy, K. (1987) · ACM Transactions on Programming Languages and Systems · doi:10.1145/29873.29875 · Cited by 735 · see citing works
Flow Analysis of Computer Programs
Hecht, M. S. (1977) · Cited by 724 · see citing works
Dependence graphs and compiler optimizations
Kuck, D. J., Kuhn, R. H., Padua, D., Leasure, B., & Wolfe, M. (1981) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/567532.567555 · Cited by 658 · see citing works
A fast algorithm for finding dominators in a flowgraph
Lengauer, T., & Tarjan, R. E. (1979) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357062.357071 · Cited by 648 · see citing works
The program dependence graph in a software development environment
Ottenstein, K. J., & Ottenstein, L. M. (1984) · ACM SIGPLAN Notices · doi:10.1145/390011.808263 · Cited by 643 · see citing works
Self-citationConversion of control dependence to data dependence
Allen, J. R., Kennedy, K., Porterfield, C., et al. (1983) · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · doi:10.1145/567067.567085 · Cited by 609 · see citing works
Dennis (1980) · Computer · doi:10.1109/mc.1980.1653418 · Cited by 584 · see citing works
The Structure of Computers and Computations
Kuck, D. L. (1978) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 500 · see citing works
Davis, & Keller (1982) · Computer · doi:10.1109/mc.1982.1653939 · Cited by 289 · see citing works
High-Speed Multiprocessors and Compilation Techniques
Padua, Kuck, & Lawrie (1980) · IEEE Transactions on Computers · doi:10.1109/tc.1980.1675676 · Cited by 270 · see citing works
Interprocedural dependence analysis and parallelization
Burke, M., & Cytron, R. K. (2004) · ACM SIGPLAN Notices · doi:10.1145/989393.989411 · Cited by 219 · see citing works
An asynchronous programming language and computing machine
Arvind, A., Gostelow, K. P., & Plouffe, W. (1978) · eScholarship (California Digital Library) · Cited by 207 · see citing works
PFC: A Program to Convert Fortran to Parallel Form
Allen, J. R., & Kennedy, K. (1982) · Rice Research Repository (Rice University) · Cited by 195 · see citing works
A Fast and Usually Linear Algorithm for Global Flow Analysis
Graham, S. L., & Wegman, M. N. (1976) · Journal of the ACM · doi:10.1145/321921.321939 · Cited by 187 · see citing works
Dependence analysis for subscripted variables and its application to program transformations
Allen, J. R. (1983) · Rice Research Repository (Rice University) · Cited by 168 · see citing works
Proceedings of the 6th international conference on Software engineering
Ohno, Y., Basili, V. R., Enomoto, H., et al. (1982) · Cited by 157 · see citing works
The program dependence graph and its use in optimization
Ferrante, J., Ottenstein, K. J., & Warren, J. D. (1984) · Lecture notes in computer science · doi:10.1007/3-540-12925-1_33 · Cited by 147 · see citing works
Self-citationCompile-time partitioning and scheduling of parallel programs
Sarkar, V., & Hennessy, J. L. (1986) · doi:10.1145/12276.13313 · Cited by 139 · see citing works
Interprocedural dependence analysis and parallelization
Burke, M., & Cytron, R. K. (1986) · doi:10.1145/12276.13328 · Cited by 138 · see citing works
The Programmer's Apprentice: Knowledge Based Program Editing
Waters, R. C. (1982) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1982.234769 · Cited by 117 · see citing works
Partitioning parallel programs for macro-dataflow
Sarkar, V., & Hennessy, J. L. (1986) · doi:10.1145/319838.319863 · Cited by 107 · see citing works
Efficient computation of flow insensitive interprocedural summary information
Cooper, K. D., & Kennedy, K. (1984) · doi:10.1145/502874.502898 · Cited by 106 · see citing works
Symbolic evaluation and the global value graph
Reif, J. H., & Lewis, H. R. (1977) · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · doi:10.1145/512950.512961 · Cited by 90 · see citing works
Analyzing aliases of reference formal parameters
Cooper, K. D. (1985) · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · doi:10.1145/318593.318658 · Cited by 86 · see citing works
Multiprocessors: discussion of some theoretical and practical problems
Haiek, D. A. P. (1980) · Cited by 77 · see citing works
Control and data dependence for program transformations.
Towle, R. A. (1976) · Cited by 74 · see citing works
Interprocedural dependence analysis and parallelization
Burke, M., & Cytron, R. K. (1986) · ACM SIGPLAN Notices · doi:10.1145/13310.13328 · Cited by 69 · see citing works
Incremental data flow analysis
Ryder, B. G. (1983) · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · doi:10.1145/567067.567084 · Cited by 66 · see citing works
Kuhn, R. H. (1980) · Cited by 53 · see citing works
Code motion of control structures in high-level languages
Cytron, R. K., Lowry, A., & Zadeck, F. K. (1986) · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · doi:10.1145/512644.512651 · Cited by 53 · see citing works
Combining data flow and control flow computing
Treleaven, P. C. (1982) · The Computer Journal · doi:10.1093/comjnl/25.2.207 · Cited by 52 · see citing works
A hierarchical basis for reordering transformations
Warren, J. D. (1984) · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · doi:10.1145/800017.800539 · Cited by 45 · see citing works
Self-citationMcGraw, J. R., Skedzielewski, S., Allan, S. J., et al. (1983) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · Cited by 44 · see citing works
Automatic Analysis of the Logical Structure of Programs
Waters, R. C. (1978) · Defense Technical Information Center (DTIC) · Cited by 43 · see citing works
Compile-time partitioning and scheduling of parallel programs
Sarkar, V., & Hennessy, J. L. (1986) · ACM SIGPLAN Notices · doi:10.1145/13310.13313 · Cited by 42 · see citing works
Ferrante, J., & Mace, M. E. (1985) · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · doi:10.1145/318593.318636 · Cited by 41 · see citing works
Self-citationData-flow graphs as an intermediate program form.
Ottenstein, K. J. (1978) · Purdue e-Pubs (Purdue University System) · Cited by 34 · see citing works
Self-citationA program form based on data dependency in predicate regions
Ferrante, J., & Ottenstein, K. J. (1983) · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · doi:10.1145/567067.567089 · Cited by 29 · see citing works
Self-citationPrettyprinting in an interactive programming environment
Mikelsons, M. (1981) · doi:10.1145/800209.806461 · Cited by 29 · see citing works
Proceedings of the 1986 ACM conference on LISP and functional programming
Scherlis, W. L., Association for Computing Machinery-Digital Library, ACM Special Interest Group on Programming Languages, et al. (1986) · Cited by 21 · see citing works
Supercomputers: Algorithms, Architectures, and Scientific Computation
Matsen, F. A., IV, Tajima, T., & Haydock, R. (1988) · Computers in Physics · doi:10.1063/1.4822755 · Cited by 18 · see citing works
Static analysis of programs as an aid to debugging
Tischler, R., Schaufler, R., & Payne, C. (1983) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/1006140.1006182 · Cited by 17 · see citing works
Interprocedural analysis and the information derived by it
Allen, F. E. (1975) · Lecture notes in computer science · doi:10.1007/3-540-07131-8_31 · Cited by 14 · see citing works
Alberga, C. N., Brown, A. L., Leeman, G. B., et al. (1984) · IBM Journal of Research and Development · doi:10.1147/rd.281.0060 · Cited by 14 · see citing works
HIGH-SPEED MULTIPROCESSORS AND THEIR COMPILERS.
Kuck, D. J., & Padua, D. (1979) · Cited by 11 · see citing works
Summarizing graphs by regular expressions
Wegman, M. N. (1983) · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · doi:10.1145/567067.567088 · Cited by 10 · see citing works
Computing Education for the Developing Asian Countries
Jordan (1980) · Computer · doi:10.1109/mc.1980.1653658 · Cited by 8 · see citing works
A File Index for Document Storage and Retrieval Utilizing Descriptor Fragments
Allen, F. W. (1982) · The Computer Journal · doi:10.1093/comjnl/25.1.2 · Cited by 5 · see citing works
Static analysis of programs as an aid to debugging
Tischler, R., Schaufler, R., & Payne, C. (1983) · doi:10.1145/1006147.1006182 · Cited by 3 · see citing works
Flagged first, then by citations
Research works printed but not linked: 3
- [21]21. 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.
- [28]28. KAS'JANOV, V. N. Distinguishing hammocks in a directed graph. Soviet Math. DokZady 16, 5 (1975), 448-450.
- [31]31. 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.
Cited by
Sorted by citations
DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones
Jiang, L., Misherghi, G., Su, Z., & Glondu, S. (2007) · 29th International Conference on Software Engineering (ICSE'07) · doi:10.1109/icse.2007.30 · Cited by 1,039 · see citing works
GPLAG: detection of software plagiarism by program dependence graph analysis
Liu, C., Chen, C., Han, J., & Yu, P. S. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150522 · Cited by 422 · see citing works
Academic Source Code Plagiarism Detection by Measuring Program Behavioral Similarity
Cheers, H., Lin, Y., & Smith, S. P. (2021) · IEEE Access · doi:10.1109/access.2021.3069367 · Cited by 59 · see citing works
“Semantic approaches typically analyse a program through program dependence graphs [25].”
BackgroundDetecting Automatic Software Plagiarism via Token Sequence Normalization
Sağlam, T., Brödel, M., Schmid, L., & Hahner, S. (2024) · Proceedings of the IEEE/ACM 46th International Conference on Software Engineering · doi:10.1145/3597503.3639192 · Cited by 9 · see citing works
- Authors
- Ferrante, J., Ottenstein, K. J., & Warren, J. D.
- Affiliations
- IBM T. J. Watson Research Center, Yorktown Heights, NY
- Michigan Technological University (US)
- Rice University (US)
- Venue
- ACM Transactions on Programming Languages and Systems
- Published
- 1987-07
- Volume
- 9
- Issue
- 3
- Pages
- 319-349
- ISSN
- 0164-0925 (ISSN-L)
- 1558-4593
- OpenAlex
- W2144344516
- Semantic Scholar
- 38641821f40fe883c5ce51a5133d538099093f9a
- Cited by
- 2,755
- References
- 56
- Citations by year
- 2026: 61 · 2025: 72 · 2024: 87 · 2023: 83 · 2022: 87 · 2021: 83 · 2020: 61 · 2019: 74 · 2018: 83 · 2017: 69 · 2016: 97 · 2015: 88 · 2014: 112 · 2013: 124 · 2012: 97
- FWCI
- 40.05
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM Transactions on Programming Languages and Systems (publishedVersion)
- Digital Commons - Michigan Tech (Michigan Technological University) (submittedVersion)
- Funders
- National Science Foundation (8404909, 8404463, 8203487, 8511439)
- International Business Machines Corporation
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Physical Sciences › Computer Science › Hardware and Architecture › Embedded Systems Design Techniques
- Keywords
- program dependence graph, data dependencies, control dependence, program optimization, vectorization, control flow graph, incremental optimization, loop unrolling, program transformation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
