Análisis de dependencia

En la teoría de compiladores , el análisis de dependencias produce restricciones de orden de ejecución entre instrucciones. En términos generales, una instrucción S2 depende de S1 si S1 debe ejecutarse antes que S2 . En términos generales, existen dos clases de dependencias: dependencias de control y dependencias de datos .

El análisis de dependencias determina si es seguro reordenar o paralelizar las instrucciones.

Controlar dependencias

La dependencia de control es una situación en la que una instrucción de un programa se ejecuta si la instrucción anterior se evalúa de manera que permita su ejecución.

Una instrucción S2 depende del control de S1 (escrita ) si y solo si la ejecución de S2 está protegida condicionalmente por S1 . S2 depende del control de S1 si y solo si donde es la frontera de post-dominancia de la instrucción . El siguiente es un ejemplo de dicha dependencia de control: $S1\ \delta ^{c}\ S2$ $S1\in PDF(S2)$ $PDF(S)$ $S$

S1 si x > 2 ir a L1 S2 y := 3 S3 L1: z := y + 1

Aquí, S2 solo se ejecuta si el predicado en S1 es falso.

dependencias de datos

La dependencia de datos surge de dos instrucciones que acceden o modifican el mismo recurso.

Dependencia de flujo (verdadero)

Una instrucción S2 depende del flujo de S1 (escrita ) si y solo si S1 modifica un recurso que S2 lee y S1 precede a S2 en la ejecución. El siguiente es un ejemplo de dependencia de flujo (RAW: Read After Write): $S1\ \delta ^{f}\ S2$

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

Antidependencia

Una instrucción S2 es antidependiente de S1 (escrita ) si y solo si S2 modifica un recurso que S1 lee y S1 precede a S2 en su ejecución. El siguiente es un ejemplo de una antidependencia (WAR: Write After Read): $S1\ \delta ^{a}\ S2$

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

Aquí, S2 establece el valor de ypero S1 lee un valor previo de y.

Dependencia de la salida

Una instrucción S2 depende de la salida de S1 (escrita ) si y solo si S1 y S2 modifican el mismo recurso y S1 precede a S2 en la ejecución. El siguiente es un ejemplo de dependencia de salida (WAW: Escritura después de escritura): $S1\ \delta ^{o}\ S2$

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 de S1 (escrita ) 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\ \delta ^{i}\ S2$

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.