En la teoría del compilador , el análisis de dependencia produce restricciones de orden de ejecución entre declaraciones / instrucciones. En términos generales, una declaración S2 depende de S1 si S1 debe ejecutarse antes que S2 . En términos generales, hay dos clases de dependencias: dependencias de control y dependencias de datos .
El análisis de dependencia determina si es seguro reordenar o paralelizar declaraciones.
Control de dependencias
La dependencia de control es una situación en la que se ejecuta una instrucción de programa si la instrucción anterior se evalúa de una manera que permite su ejecución.
Una declaración S2 es dependiente de control de S1 (escrito) si y solo si la ejecución de S2 está protegida condicionalmente por S1 . El siguiente es un ejemplo de tal dependencia de control:
S1 si x> 2 pasa a L1S2 y: = 3 S3 L1: z: = y + 1
Aquí, S2 solo se ejecuta si el predicado en S1 es falso.
Consulte las dependencias de datos para obtener más detalles.
Dependencias de datos
Una dependencia de datos surge de dos declaraciones que acceden o modifican el mismo recurso.
Dependencia del flujo (verdadero)
Una declaración S2 es el flujo depende de S1 (escrito) si y solo si S1 modifica un recurso que S2 lee y S1 precede a S2 en ejecución. El siguiente es un ejemplo de dependencia de flujo (RAW: lectura después de escritura):
S1 x: = 10S2 y: = x + c
Antidependencia
Un enunciado S2 es antidependiente de S1 (escrito) si y solo si S2 modifica un recurso que S1 lee y S1 precede a S2 en ejecución. El siguiente es un ejemplo de una antidependencia (WAR: Write After Read):
S1 x: = y + cS2 y: = 10
Aquí, S2 establece el valor de y
pero S1 lee un valor anterior de y
.
Dependencia de la producción
Una declaración S2 se emite dependiendo de S1 (escrito) si y solo si S1 y S2 modifican el mismo recurso y S1 precede a S2 en ejecución. El siguiente es un ejemplo de una dependencia de salida (WAW: Write After Write):
S1 x: = 10S2 x: = 20
Aquí, S2 y S1 establecen la variable x
.
Dependencia de entrada
Una declaración S2 es dependiente de la entrada en S1 (escrito) si y solo si S1 y S2 leen el mismo recurso y S1 precede a S2 en ejecución. El siguiente es un ejemplo de una dependencia de entrada (RAR: Read-After-Read):
S1 y: = x + 3S2 z: = x + 5
Aquí, tanto S2 como S1 acceden a la variable x
. Esta dependencia no prohíbe el reordenamiento.
Dependencias de bucle
El problema de calcular las dependencias dentro de los bucles, que es un problema importante y no trivial, se aborda mediante el análisis de la dependencia de los bucles , que amplía el marco de dependencia proporcionado aquí.
Ver también
Otras lecturas
- Cooper, Keith D .; Torczon, Linda. (2005). Ingeniería de un compilador . Morgan Kaufmann. ISBN 1-55860-698-X.
- Kennedy, Ken; Allen, Randy. (2001). Optimización de compiladores para arquitecturas modernas: un enfoque basado en la dependencia . Morgan Kaufmann. ISBN 1-55860-286-0.
- Muchnick, Steven S. (1997). Diseño e implementación de compiladores avanzados . Morgan Kaufmann. ISBN 1-55860-320-4.