Dependence analysis
Encyclopedia
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 or not it is safe to reorder or parallelize statements.
A statement S2 is control dependent on S1 (written
) if and only if S2s 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.
) 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
) 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
) 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
) 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
, which extends the dependence framework given here.
Data dependency
A data dependency in computer science is a situation in which a program statement refers to the data of a preceding statement. In compiler theory, the technique used to discover data dependencies among statements is called dependence analysis.There are three types of dependencies: data, name, and...
.
Dependence analysis determines whether or not it is safe to reorder or parallelize statements.
Control dependencies
Control dependence is a situation in which a program’s 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. 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.
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) 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) 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.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 (WAW: Write After Write):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 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. 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 analysisLoop dependence analysis
In compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, with respect to array access and modification, induction, reduction and private variables, simplification of loop-independent code and management of conditional branches...
, which extends the dependence framework given here.
See also
- Program analysis (computer science)Program analysis (computer science)In computer science, program analysis is the process of automatically analysing the behavior of computer programs. Two main approaches in program analysis are static program analysis and dynamic program analysis...
- Automatic parallelizationAutomatic parallelizationAutomatic parallelization, also auto parallelization, autoparallelization, or parallelization, the last one of which implies automation when used in context, refers to converting sequential code into multi-threaded or vectorized code in order to utilize multiple processors simultaneously in a...
- Vectorization (parallel computing)
- Loop dependence analysisLoop dependence analysisIn compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, with respect to array access and modification, induction, reduction and private variables, simplification of loop-independent code and management of conditional branches...
- Frameworks supporting the polyhedral modelFrameworks supporting the polyhedral modelUse of the polyhedral model within a compiler requires software to represent the objects of this framework and perform operations upon them ....