Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Program dependence graph

Representation of graph notation

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated December 30, 2024
Image credit is listed at the end of this article.

A Program Dependence Graph (PDG) is a directed graph of a program's control and data dependencies. Nodes represent program statements and edges represent dependencies between these statements.

PDGs are used in optimization, debugging, and understanding program behavior. One example of this is their utilization by compilers during dependence analysis, enabling the optimizing compiler to make transformations to allow for parallelism.

Watch videos about Program dependence graphExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Program dependence graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Dependency graph

In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order that respects the given dependencies from the dependency graph.

Control-flow graph

In computer science, a control-flow graph is a representation, using graph notation, of all paths that might be traversed through a function during its execution, or control flow. The control-flow graph was conceived by Frances E. Allen, who noted that Reese T. Prosser used boolean connectivity matrices for flow analysis before.

Data-flow analysis

Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. It forms the foundation for a wide variety of compiler optimizations and program verification techniques.