Dependency analysis

Dependence analysis or the dependency analysis provides the compiler determines the dependence between instructions. From this it is determined when it is safe to change or parallelize the execution sequence of programs . Generally an instruction depends S2 of S1 off when S1 before S2 must be performed. There are two classes of dependencies: control flow dependence ( control dependence ) and data dependency ( data dependence ).

Control flow dependency

Control flow dependency exists in the case that a program instruction is executed if the evaluation of the previous instruction allows this. An instruction S2 is control flow-dependent of S1 ( ), if and only if the execution of S2 is conditionally protected by S1 . The following example shows such a dependency: ${\displaystyle S1\ \delta ^{c}\ S2}$

S1       if x > 2 goto L1
S2       y := 3
S3   L1: z := y + 1

S1 to S3 are line labels. L1 is a jump label . Here, S2 is only executed if the evaluation at S1 results in 'False'.

Data dependency

Data dependency arises when two instructions read or write to the same resources.

Real data dependence (flow dependence)

An instruction S2 is flow dependent ( ) from S1 , if and only if S1 changes a resource that is read by S2 and S1 is executed before S2 . The following is an example of flow dependence (RAW: Read After Write): ${\displaystyle S1\ \delta ^{f}\ S2}$

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

Antidependence

An instruction S2 is antidependent ( ) from S1 if and only if S2 changes a resource that is read by S1 and S1 is executed before S2 . The following is an example of antidependence (WAR: Write After Read): ${\displaystyle S1\ \delta ^{a}\ S2}$

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

Here S2 writes a value to y, but S1 reads a previous value from y.

Output dependence

An instruction S2 is output dependent ( ) from S1 , if and only if S1 and S2 change the same resource and S1 is executed before S2 . The following is an example of output dependence (WAW: Write After Write): ${\displaystyle S1\ \delta ^{o}\ S2}$

S1       x := 10
S2       x := 20

Both S1 and S2 write the variable x.

Input "dependence"

An instruction S2 is input dependent ( ) from S1 , if and only if S1 and S2 read the same resource and S1 is executed before S2 . The following is an example of input dependence: ${\displaystyle S1\ \delta ^{i}\ S2}$

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

Here S1 and S2 read the variable x. This is not a dependency in the sense of the others that a change in the instruction order is prevented. However, some compilers can use this definition to find optimizations.

Loop dependence

The problem of computing dependencies within loops is significant and not trivial. It is followed in the loop parallelization ( loop dependence analysis ).

literature

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