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 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 formula_1) 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.
See data dependencies for more details.
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 formula_2) 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 formula_3) 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 codice_1 but "S1" reads a prior value of codice_1.
Output dependence.
A statement "S2" is output dependent on "S1" (written formula_4) 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 codice_3.
Input dependence.
A statement "S2" is input dependent on "S1" (written formula_5) 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 codice_3. 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.