Análisis de dependencia

En la teoría de compiladores , el análisis de dependencias produce restricciones de orden de ejecución entre instrucciones o sentencias. En términos generales, una sentencia 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 dependencia determina si es seguro reordenar o paralelizar declaraciones.

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

Una declaració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 posdominación de la declaración . El siguiente es un ejemplo de tal dependencia del control: ${\displaystyle S1\ \delta ^{c}\ S2}$${\displaystyle S1\en PDF(S2)}$${\displaystyle PDF(S)}$${\estilo de visualización 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.

Una dependencia de datos surge de dos declaraciones que acceden o modifican el mismo recurso.

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 una dependencia del flujo (RAW: Read After Write): ${\displaystyle S1\ \delta ^{f}\ S2}$

S1x := 10
S2 y := x + c

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 la ejecución. El siguiente es un ejemplo de una antidependencia (WAR: Write After Read): ${\displaystyle S1\ \delta ^{a}\ S2}$

S1x:= y+c
S2 y := 10

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

Una instrucción S2 depende de la salida de S1 (se escribe ) 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 una dependencia de salida (WAW: Write After Write): ${\displaystyle S1\ \delta ^{o}\ S2}$

S1x := 10
S2x := 20

Aquí, tanto S2 como S1 establecen la variable x.

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 una dependencia de entrada (RAR: Read-After-Read): ${\displaystyle S1\ \delta ^{i}\ S2}$

S1 y := x + 3
S2z := x + 5

Aquí, tanto S2 como S1 acceden a la variable x. Esta dependencia no prohíbe la reordenación.

El problema de calcular dependencias dentro de bucles, que es un problema significativo y no trivial, se aborda mediante el análisis de dependencia de bucles , que extiende el marco de dependencia dado aquí.

• Análisis de programas (informática)
• Paralelización automática
• Vectorización automática
• Análisis de dependencia de bucles
• Marcos que sustentan el modelo poliédrico
• Peligro (arquitectura informática)
• Segmentación de programas
• Eliminación de código muerto

• 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 dependencias . 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.