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 $S1\ \delta ^{c}\ S2$ ) if and only if S2's execution is conditionally guarded by S1. S2 is control dependent on S1 if and only if $S1\in PDF(S2)$ where $PDF(S)$ is the post dominance frontier of statement $S$ . 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 $S1\ \delta ^{f}\ S2$ ) 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 $S1\ \delta ^{a}\ S2$ ) 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 $S1\ \delta ^{o}\ S2$ ) 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

Aquí, tanto S2 como S1 establecen la variable x.

Dependencia de la entrada

Una instrucción S2 depende de la entrada S1 (escrita) $S1\ \delta ^{i}\ S2$ ) si y solo si S1 y S2 leen el mismo recurso y S1 precede a S2 en la ejecución. El siguiente es un ejemplo de dependencia de entrada (RAR: Read-After-Read):

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

Aquí, tanto S2 como S1 acceden a la variable x. Esta dependencia no impide la reordenación.

dependencias de bucle

El problema del cálculo de dependencias dentro de los bucles, que es un problema significativo y no trivial, se aborda mediante el análisis de dependencias de bucles , que amplía el marco de dependencias presentado aquí.

Véase también

Lecturas adicionales

Cooper, Keith D.; Torczon, Linda. (2005). Ingeniería de un compilador . 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). Diseño e implementación avanzados de compiladores . Morgan Kaufmann. ISBN 1-55860-320-4.