Control flow models depict program flow, while data flow models highlight information transmission via variables. Initially developed for compiler optimization, data flow models find use in software engineering tasks like testing and error detection. Their efficient algorithms have broad applicability beyond compiler construction.

Definition-Use Pairs

Data Flow Models associates the point in a program where a value is produced (”definition”) with the points at which the value may be accessed (”use”). These associations captures the flow of information through a program, from input to output.

• Definitions: statements that change the value of one or more variables
• Uses: statements whose execution extracts a value from a variable.

Euclid’s Algoriothm

Each definition-use pair associates a definition of a variable with a use of the same variable. A single definition can be paired with more than one use, and viceversa.

If there is another assignment to the same value on the path, we say that the first definition is killed by the second.

A definition-clear path is a path from definition to use on which the definition is not killed by another definition of the same variable.

Definition-use pairs record a kind of program dependence, sometimes called diect data dependence. → represented in the form of a graph

Data dependence graph of GCD method. Each directed edge represents a direct data dependence

The control-dependence graph shows direct control dependencies, that is, where execution of one statement control wether another is executed.

Program dependence representations typically include both data dependence and control dependence information in a single graph with the two kinds of information appearing as different kinds of edges among the same set of nodes.

A node will typically have many dominators, but except for the root, there is a unique immediat dominator, which is closest to N of any path from the root and which is in turn duminated by all the other dominators of N. → the immediate dominator relation forms a tree.

Dominators that are calculated in the reverse of the control flow graph, are called post-dominators, while dominators in the normal direction of execution are called pre-dominators.

When these conditions are true, we say node $N$ is control-dependent on node $C$:

1. $C$ has at least two successors in the CFG
2. $C$ is nt post-dominated by $N$ (→ N is not already inevitable when C is reached)
3. There is a successor of $C$ in the CFG that is post-dominated by $N$