Análisis de dependencia - Dependence analysis

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 el control dependiente de S1 (por escrito ) si y sólo si S2' s ejecución es condicional vigilada por S1 . El siguiente es un ejemplo de tal dependencia de control: ${\ Displaystyle S1 \ \ delta ^ {c} \ S2}$

S1       if x > 2 goto L1
S2       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 sólo si S1 modifica un recurso que S2 lee y S1 precede a S2 en la ejecución. El siguiente es un ejemplo de dependencia del flujo (RAW: lectura después de escritura): ${\ Displaystyle 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 ejecución. El siguiente es un ejemplo de una antidependencia (WAR: Write After Read): ${\ Displaystyle S1 \ \ delta ^ {a} \ S2}$

S1       x := y + c
S2       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 es de salida dependiente de S1 (escrito ) si y sólo si S1 y S2 modifican el mismo recurso y S1 precede a S2 en la ejecución. El siguiente es un ejemplo de una dependencia de salida (WAW: Write After Write): ${\ Displaystyle S1 \ \ delta ^ {o} \ S2}$

S1       x := 10
S2       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 sólo si S1 y S2 leen el mismo recurso y S1 precede a S2 en la ejecución. El siguiente es un ejemplo de una dependencia de entrada (RAR: Read-After-Read): ${\ Displaystyle 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 prohíbe reordenar.

Dependencias de bucle

El problema de calcular las dependencias dentro de los bucles, que es un problema significativo y no trivial, se aborda mediante el análisis de la dependencia de los bucles , que amplía el marco de dependencia que se proporciona aquí.

Ver también

• Análisis de programas (informática)
• Paralelización automática
• Vectorización automática
• Análisis de dependencia de bucle
• Estructuras que soportan el modelo poliédrico
• Peligro (arquitectura de computadora)
• Programa de corte
• Eliminación de código muerto

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 .