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 ) if and only if S2s execution is conditionally guarded by S1. S2 is control dependent on S1 if and only if where is the post dominance frontier of statement . 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. See data dependencies for more details. A data dependence arises from two statements which access or modify the same resource. A statement S2 is flow dependent on S1 (written ) 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 A statement S2 is antidependent on S1 (written ) 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. A statement S2 is output dependent on S1 (written ) 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. A statement S2 is input dependent''' on S1 (written ) 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.