Dependence analysis

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 ${\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):

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

Antidependence

A statement S2 is antidependent on S1 (written ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.