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 dependencies

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 $S1\ \delta^c\ S2$) if and only if ''S2s execution is conditionally guarded by ''S1''. ''S2'' is ''control dependent'' on ''S1'' if and only if $S1 \in PDF(S2)$ where $PDF(S)$ is the post dominance frontier of statement $S$. The following is an example of such a control dependence:

S1 if x > 2 goto L1
S2 y := 3
S3 L1: z := y + 1

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

Data dependencies

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

Flow(True) dependence

A statement ''S2'' is flow dependent on ''S1'' (written $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):

S1 x := 10
S2 y := x + c

Antidependence

A statement ''S2'' is antidependent on ''S1'' (written $S1\ \delta^a\ S2$) if and only if ''S2'' modifies a resource that ''S1'' reads and ''S1'' precedes ''S2'' in execution. The following is an example of an antidependence (WAR: Write After Read):

S1 x := y + c
S2 y := 10

Here, ''S2'' sets the value of y but ''S1'' reads a prior value of y.

Output dependence

A statement ''S2'' is output dependent on ''S1'' (written $S1\ \delta^o\ S2$) if and only if ''S1'' and ''S2'' modify the same resource and ''S1'' precedes ''S2'' in execution. The following is an example of an output dependence (WAW: Write After Write):

S1 x := 10
S2 x := 20

Here, ''S2'' and ''S1'' both set the variable x.

Input dependence

A statement ''S2'' is input dependent on ''S1'' (written $S1\ \delta^i\ S2$) if and only if ''S1'' and ''S2'' read the same resource and ''S1'' precedes ''S2'' in execution. The following is an example of an input dependence (RAR: Read-After-Read):

S1 y := x + 3
S2 z := x + 5

Here, ''S2'' and ''S1'' both access the variable x. This dependence does not prohibit reordering.

Loop dependencies

The problem of computing dependencies within loops, which is a significant and nontrivial problem, is tackled by loop dependence analysis, which extends the dependence framework given here.

See also

* Program analysis (computer science)
* Automatic parallelization
* Automatic vectorization
* Loop dependence analysis
* Frameworks supporting the polyhedral model
* Hazard (computer architecture)
* Program slicing
* Dead code elimination

Further reading

*
*
*

{{Program analysis
Static program analysis