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.
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
The following is an example of such a control dependence: Here, S2 only runs if the predicate in S1 is false.
A data dependence arises from two statements which access or modify the same resource.
) 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): 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 input dependence (RAR: Read-After-Read): Here, S2 and S1 both access the variable x.