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 .
La dependencia de control es una situación en la que una instrucción de un 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 sólo si la ejecución de S2 está protegida condicionalmente por S1 . S2 depende del control de S1 si y sólo si dónde está la frontera de enunciación posterior a la dominancia . El siguiente es un ejemplo de dicha dependencia de control:
S1 si x > 2 ir a L1S2 y := 3 T3 L1: z := y + 1
Aquí, S2 sólo 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 declaració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 ejecución. El siguiente es un ejemplo de dependencia de flujo (RAW: lectura después de escritura):
S1 x := 10S2 y := x + c
Una declaració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 antidependencia (WAR: Write After Read):
S1 x := y + cS2 y := 10
Aquí, S2 establece el valor de ypero S1 lee un valor anterior de y.
Una declaración S2 se genera dependiente de S1 (escrita ) 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 dependencia de salida (WAW: escritura después de escritura):
S1 x := 10S2 x := 20
Aquí, S2 y S1 configuran la variable x.
Una declaración S2 depende de S1 (escrita ) 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 dependencia de entrada (RAR: lectura-después-lectura):
S1 y := x + 3S2 z := x + 5
Aquí, S2 y S1 acceden a la variable x. Esta dependencia no prohíbe reordenar.
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 dependencia de bucles , que amplía el marco de dependencia que se proporciona aquí.
