Dependence analysis

From Wikipedia, the free encyclopedia

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 or not it is safe to reorder or parallelize statements.

1 Control dependencies
2 Data dependencies
3 Loop dependencies
4 See also
5 Further reading

[edit] Control dependencies

A situation in which a program’s 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 S2's execution is conditionally guarded by S1. 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.

[edit] Data dependencies

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

[edit] Flow 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:

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

[edit] 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:

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

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

[edit] 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:

S1       x := 10
S2       x := 20

Here, S2 and S1 both set the variable x.

[edit] Input "dependence"

A statement S2 is input "dependent" on S1 (written $S1\ \delta^i\ S2$ ) if and only if S1 and S2 i> precedes S2 in execution. The following is an example of an input dependence:

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

Here, S2 and S1 both access the variable x. This is not a dependence in the same line as the others, as it does not prohibit reordering instructions. Some compiler optimizations still find this definition useful, however.

[edit] 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.

[edit] See also

automatic parallelization

[edit] Further reading

Cooper, Keith D.; & Torczon, Linda. (2005). Engineering a Compiler. Morgan Kaufmann. ISBN 1-55860-698-X.
Kennedy, Ken; & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0.
Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 1-55860-320-4.