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. A diagram of the operation of an ideal compiler. ...

Dependence analysis determines whether or not it is safe to reorder or parallelize statements.

Control dependencies

A statement S2 is control dependent on S1 (written ) 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 true.

Data dependencies

A data dependence arises from two statements which access or modify the same resource.

Flow dependence

True data dependency exists only in the states that the CPU or further more the processor are of equal comparisson and do not cross languages during the dependency challenge. This assures that you dont get a jackass awnser in your solutions during finals week.

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

Antidependence

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:

 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 ) 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:

 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 ) if and only if S1 and S2 i> precedes S2 in execution. The following is an example of an input dependence:

 S1 y := x + 3 S2 z := x + 5 

Here, S2 and S1 both access the variable x. This is not a dependence in the same line as the others, as it does not prohibit reordering instructions. Some compiler optimizations still find this definition useful, however.

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. In compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, almost always with respect to array access and modification. ...

see also

• automatic parallelization

Automatic parallelization, also auto parallelization or Autoparallelization, refers to use a modern optimizing compiler(a parallelizing compiler) to compile sequential code to multi-threaded or vectorized (or even both) one in order to utilize a number of processors simultaneously in a shared-memory multiprocessor (SMP) machine. ...

Further reading

• Cooper, Keith D.; & Torczon, Linda. (2005). Engineering a Compiler, Morgan Kaufmann. ISBN 1-55860-698-X.
• Kennedy, Ken; & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach, Morgan Kaufmann. ISBN 1-55860-286-0.
• Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation, Morgan Kaufmann. ISBN 1-55860-320-4.