Análisis de dependencias

En teoría de compiladores, el análisis de dependencias genera restricciones en el orden de ejecución de las instrucciones. Grosso modo, se dice una instrucción S2 depende de S1 si S1 debe ser ejecutada antes que S2. Una clasificación extensa divide las dependencias en dos tipos, dependencias de control y dependencias de datos.

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

Dependencias de control

Una instrucción S2 depende en cuanto a control de S1 (expresado como $S1\ \delta ^{c}\ S2$ ) si y solo si la ejecución de S2 viene condicionada por S1. El siguiente código es un ejemplo de dependencia de control:

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

Aquí, S2 solamente es ejecutada si la condición de S1 es falsa.

Dependencias de datos

Una dependencia de datos surge entre dos instrucciones que pretenden acceder o modificar un mismo recurso.

Dependencia de flujo o verdadera

Una instrucción S2 posee dependencia verdadera o de flujo respecto de S1 (expresado como $S1\ \delta ^{f}\ S2$ ) si y solo si S1 modifica un recurso que S2 lee y S1 precede a S2 en el orden de ejecución. El siguiente ejemplo muestra una dependencia verdadera:

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

Antidependencia

Una instrucción S2 es antidependiente de S1 (expresado como $S1\ \delta ^{a}\ S2$ ) si y solo si S2 modifica un recurso que S1 lee y S1 precede a S2 en el orden de ejecución. El siguiente ejemplo muestra una antidependencia:

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

Aquí, S2 modifica el valor de y pero S1 lee un valor anterior de dicha variable.

Dependencia de salida

Una instrucción S2 presenta una dependencia de salida respecto de S1 (expresado como $S1\ \delta ^{o}\ S2$ ) si y solo si S1 y S2 modifican el mismo recurso y S1 precede a S2 en el orden de ejecución. El siguiente ejemplo muestra una dependencia de salida:

S1       x := 10
S2       x := 20

Aquí, Tanto S2 como S1 modifican el valor de la variable x.

"Dependencia" de entrada

Una instrucción S2 presenta una "dependencia" de entrada respecto de S1 (expresado como $S1\ \delta ^{i}\ S2$ ) si y solo si S1 y S2 leen el mismo recurso y S1 precede a S2 en el orden de ejecución:

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

Aquí, S2 y S1 acceden a la variable x. Esta no es una dependencia en la misma línea que las anteriores, ya que no prohíbe la reordenación de instrucciones.

Dependencias de bucles

El problema de las dependencias en bucles, algo significativo y nada trivial, es tratado por el análisis de dependencias de bucles.

Lecturas recomendadas

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.

Datos: Q5700696