Does a PDG contain both data and control relationships?

Yes. Combining those forms of dependence is its defining purpose, although representation details vary.

Is a PDG always acyclic?

No. Loops and recurring dependencies can produce cycles, so it should not be treated as a simple one-way task list.

Can a PDG help with program slicing?

Yes. Following relevant dependencies can identify program portions that may affect a selected value or observation.

AI Glossary / Data engineering and architecture / Advanced

Program dependence graph

Definition

A program dependence graph, or PDG, is a directed representation of the data and control dependencies between elements of a program. It makes explicit which computations rely on values produced elsewhere and which operations execute because of particular control decisions.

What it means

Program text lists operations in an order, but that order does not by itself explain every relationship needed to preserve behavior. One assignment may use another assignment's value, while another operation may occur only when a condition is true.

A PDG represents those relationships as graph edges. Nodes can correspond to statements, instructions or larger program elements, depending on the representation. The graph is useful for analysis because related computations can be followed through dependencies rather than merely through adjacent lines of text.

This differs from a control-flow graph, which describes possible transfers of execution between program locations. A PDG asks about dependence. The two representations are related, but they answer different questions.

How it works

Data-dependence analysis identifies relationships such as a value being defined at one operation and used at another. Memory accesses can require additional analysis because different pointers may refer to the same location.

Control-dependence analysis identifies operations whose execution depends on a branch outcome. These relationships are derived from the program's control structure; they are not simply edges between every pair of successive statements.

The resulting graph supports activities such as identifying computations relevant to a result, examining transformations and analyzing opportunities for reordering. A compiler must preserve the required semantics, including relevant dependencies and other language constraints.

A graph also has an analysis boundary. A representation of one function or instruction range may omit relationships outside that scope. Unknown calls, aliasing and other complexities can lead an analysis to conservatively include possible dependencies. An edge therefore need not prove that a particular influence occurred in every execution.

Three practical examples

A compiler uses dependence information when deciding whether computations can be reordered without changing the required result.
A debugging tool follows dependencies backward from an incorrect output to identify statements that may have contributed to it.
A code-analysis system examines whether an input can influence a sensitive output through values or conditional execution.

Think of it this way

Think of a project chart showing both prerequisites and decision gates. Some work needs the result of another task; other work happens only if a review chooses a particular branch.

The analogy captures two kinds of relationship. Program semantics are more exacting than an informal project plan: shared memory, exceptions and language rules can affect what transformations are valid. A simple-looking graph is not automatically a complete proof that tasks can run independently.

Worked example

Separating data and control dependence

Consider this invented program fragment: first set x to input + 1; then test whether x is greater than 10; if the test is true, set y to 2 × x and print y.

The input influences x through a data dependence. The computation of x supplies data to the test and to the multiplication. The multiplication supplies the value printed. The branch outcome controls whether the multiplication and print operation execute.

For input 4, x becomes 5 and nothing is printed. For input 10, x becomes 11, y becomes 22 and 22 is printed. Moving the print operation outside the condition without preserving its control relationship changes the behavior.

This small trace illustrates dependency types, not a full formal graph construction algorithm. A real representation may include entry nodes, intermediate instructions and additional edges required by its chosen analysis.

Illustrative case study

A fictional development team asks an AI assistant to parallelize a data-processing routine. The assistant notices that two output calculations use different variable names and proposes running them independently.

A dependence review reveals that both variables can refer to the same underlying buffer, and one operation also occurs only after a validation branch. The team revises the proposal and checks the actual aliasing and control conditions before making any transformation.

The lesson is that textual separation is not semantic independence. A useful program analysis must represent the relevant memory and control relationships, and the validity of its conclusion depends on the assumptions used to build the graph.

Common misconceptions and mistakes

A PDG is just a flowchart with a new name. It represents dependencies rather than only possible next execution steps.
No visible edge always proves independence. The graph may omit relationships outside its scope or depend on assumptions that need checking.
Every dependency edge describes an influence observed in one run. Static analyses can represent possible relationships across many executions.

Business use

Program dependence graphs support tools that improve code understanding, optimization and impact analysis. Their business value usually appears through more dependable engineering decisions rather than through direct end-user features.

When evaluating a tool, ask what its nodes and edges mean, which language features it handles and where its analysis stops. A graph that ignores external calls or uncertain memory relationships can be informative without supporting every transformation claim.

For AI-assisted maintenance, a PDG can provide structured evidence about potentially related code. It does not replace checking requirements or validating changed behavior. A proposed simplification should be assessed against the relevant dependencies, observable side effects and representative executions, especially when the assistant infers independence from names or proximity alone.

Check your understanding

Why is moving print y outside the branch in the worked example not justified merely because y depends on x?

Answer: Data dependence is only part of the behavior. The print operation is also controlled by the condition, and removing that control relationship can make output occur when the original program printed nothing.

Related terms

Intermediate representation
Control-flow graph
data dependence
control dependence
static analysis
program slicing
alias analysis
compiler optimisation

Learn next

Read control flow and definition - use relationships. Annotate a small conditional program with value dependencies and branch-controlled operations, then examine which relationships a proposed reordering must preserve.

Sources

Ferrante, Ottenstein and Warren, The Program Dependence Graph and Its Use in Optimization: https://bears.ece.ucsb.edu/class/ece253/papers/ferrante87.pdf. Primary paper introducing the representation and its optimisation role.

LLVM documentation, Dependence Graphs: https://www.llvm.org/docs/DependenceGraphs/index.html. Primary explanation of data and program dependence graphs and analysis scope.

Korel, The program dependence graph in static program testing: https://www.sciencedirect.com/science/article/pii/0020019087901025. Primary research abstract on testing applications. The arithmetic trace and development-team case are original illustrations.

Previous: Profiling Next: Programming by example