- Análisis de dependencias
-
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.
Contenido
Dependencias de control
Una instrucción S2 depende en cuanto a control de S1 (expresado como ) 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 ) 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 ) 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 ) 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 ) 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.
Categoría: Compiladores
Wikimedia foundation. 2010.