Program dependence graph

A program dependence graph combines control dependence and data dependence in one directed representation. A node usually denotes a statement, expression, or compiler intermediate-representation operation; an edge from node A to node B means that B may depend on A for either execution control or a value.¹

Control dependence is derived from the control-flow graph: a statement is control-dependent on a branch when the branch determines whether that statement executes. Data dependence connects a definition of a variable or memory location to a later use when the definition can reach that use without an intervening definition. Aliasing, pointers, arrays, and procedure calls make this analysis conservative, so a graph may contain edges representing possible rather than certain dependences.

The graph exposes which operations can be reordered, removed, duplicated, or grouped without changing relevant behavior. A compiler can use dependence information for instruction scheduling, loop transformations, vectorization, partial redundancy elimination, and parallelization, while preserving edges that constrain legal transformations.¹

Program slicing follows selected dependence edges to retain statements affecting a chosen value or behavior. A backward slice starts at a criterion and traces influential statements; a forward slice traces possible effects. These operations support debugging, testing, security review, and impact analysis, and they became closely associated with the broader field of program slicing.³ Static slices usually overapproximate behavior because they must account for feasible but unexecuted paths.

Real compilers extend a procedure-local graph with call and return relationships, parameter bindings, globals, exceptions, and memory effects. Interprocedural dependence graphs represent how a definition in one procedure can influence a use in another, enabling whole-program slicing and analyses that cross procedure boundaries.⁴

Many implementations do not maintain one universal graph for every task. They construct graph fragments from an intermediate representation and combine them with call graphs, alias analyses, memory-dependence analyses, and loop information. Static single assignment form simplifies scalar data-flow reasoning by giving each definition a distinct name; its phi functions make control-flow joins explicit and complement, rather than replace, dependence analysis.² The precision and cost of a PDG therefore depend strongly on the underlying language model and analyses.

A dependence edge does not necessarily mean that two statements execute in the same run or that one statement directly computes the other’s result. It can encode a may-dependence arising from uncertain aliasing, path feasibility, indirect calls, or weak memory knowledge. Analysts therefore distinguish flow, anti-, and output dependences in data-flow settings, even when a compact PDG presents them through a common edge vocabulary.

Dependence graphs also have less obvious uses. They can expose implicit information flows through branch conditions, help identify parallel regions, and provide a structural basis for graph-based code understanding. Exceptional control flow, short-circuit Boolean operators, volatile accesses, concurrency, and irreducible control flow each require careful modeling; treating them as ordinary sequential statements can produce unsound transformations. Industrial compilers commonly maintain related dependence structures alongside SSA and loop representations rather than materializing every possible relation in one graph.⁵

Control dependence

A relation in which execution of one statement is governed by the outcome of a control-flow decision.

Data dependence

A relation connecting a definition to a later operation that may read the defined value or memory location.

Program slicing

The extraction of statements relevant to a selected computation, usually by tracing dependence relations.

Static single assignment

An intermediate representation form in which each scalar variable version has one defining assignment, with phi functions at joins.