In compiler theory , dependency analysis generates restrictions on the order of execution of instructions. Roughly speaking, an instruction S2 depends on S1 if S1 must be executed before S2 . An extensive classification divides dependencies into two types, control dependencies and data dependencies .
Dependency analysis determines whether or not it is safe to reorder or parallelize statements.
An S2 instruction is control dependent on S1 (expressed as) if and only if the execution of S2 is conditioned by S1 . The following code is an example of a control dependency:
S1 if x > 2 goto L1 S2 y := 3 S3 L1: z := y + 1
Here, S2 is only executed if the condition of S1 is false.
A data dependency arises between two instructions that intend to access or modify the same resource.
Flow dependency or true
An S2 instruction has true or flow dependence on S1 (expressed as) if and only if S1 modifies a resource that S2 reads and S1 precedes S2 in the order of execution. The following example shows a true dependency:
S1 x: = 10 S2 y: = x + c
An S2 instruction is antidependent of S1 (expressed as) if and only if S2 modifies a resource that S1 reads and S1 precedes S2 in the order of execution. The following example shows an antidependency:
S1 x: = y + c S2 y: = 10
Here, S2 modifies the value of
ybut S1 reads a previous value from said variable.
An S2 instruction has an output dependency on S1 (expressed as) if and only if S1 and S2 modify the same resource and S1 precedes S2 in the order of execution. The following example shows an output dependency:
S1 x := 10 S2 x := 20
Here, both S2 and S1 modify the value of the variable
An S2 instruction has an input "dependency" on S1 (expressed as) if and only if S1 and S2 read the same resource and S1 precedes S2 in the order of execution:
S1 y := x + 3 S2 z := x + 5
Here, S2 and S1 access the variable
x. This is not a dependency in the same line as the previous ones, since it does not prohibit the reordering of instructions.
The problem of dependencies in loops, something significant and not trivial, is addressed by the analysis of loop dependencies.
- 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.