Dependence analysis

In compiler theory, dependence analysis produces execution-order constraints between statements/instructions. Broadly speaking, a statement S2 depends on S1 if S1 must be executed before S2. Broadly, there are two classes of dependencies--control dependencies and data dependencies.

Dependence analysis determines whether it is safe to reorder or parallelize statements.

Control dependency is a situation in which a program instruction executes if the previous instruction evaluates in a way that allows its execution.

A statement S2 is control dependent on S1 (written ${\displaystyle S1\ \delta ^{c}\ S2}$) if and only if S2's execution is conditionally guarded by S1. The following is an example of such a control dependence:

Here, S2 only runs if the predicate in S1 is false.

A data dependence arises from two statements which access or modify the same resource.

A statement S2 is flow dependent on S1 (written ${\displaystyle S1\ \delta ^{f}\ S2}$) if and only if S1 modifies a resource that S2 reads and S1 precedes S2 in execution. The following is an example of a flow dependence (RAW: Read After Write):

...
Wikipedia