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.
Contents
- Control dependencies
- Data dependencies
- FlowTrue dependence
- Antidependence
- Output dependence
- Input dependence
- Loop dependencies
- References
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
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
Antidependence
A statement S2 is antidependent on S1 (written
Here, S2 sets the value of y
but S1 reads a prior value of y
. The term 'antidependece' widely used in literature is a misnomer because 'anti' means opposite. The correct term should be 'ante' means before. Hence the correct word should be antedependence.
Output dependence
A statement S2 is output dependent on S1 (written
Here, S2 and S1 both set the variable x
.
Input dependence
A statement S2 is input dependent on S1 (written
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.