Controlar la dependencia

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 manera que permita su ejecución.

Una instrucción B tiene una dependencia de control de una instrucción precedente A si el resultado de A determina si B debe ejecutarse o no. En el siguiente ejemplo, la instrucción${\displaystyle S_{2}}$tiene una dependencia de control de la instrucción${\displaystyle S_{1}}$. Sin embargo,${\displaystyle S_{3}}$no depende de${\displaystyle S_{1}}$porque${\displaystyle S_{3}}$siempre se ejecuta independientemente del resultado de${\displaystyle S_{1}}$.

S1. si (a == b) S2. a = a + b S3. b = a + b

Intuitivamente, existe una dependencia de control entre dos enunciados A y B si

• B podría ejecutarse después de A.
• El resultado de la ejecución de A determinará si B se ejecutará o no.

Un ejemplo típico es que existen dependencias de control entre la parte condicional de una instrucción if y las instrucciones en sus cuerpos verdadero/falso.

Una definición formal de dependencia de control puede presentarse de la siguiente manera:

Una declaración${\displaystyle S_{2}}$Se dice que el control depende de otra declaración.${\displaystyle S_{1}}$si y solo si

• existe un camino${\displaystyle P}$de${\displaystyle S_{1}}$a${\displaystyle S_{2}}$de tal manera que cada declaración${\displaystyle S_{i}}$≠${\displaystyle S_{1}}$dentro${\displaystyle P}$será seguido por${\displaystyle S_{2}}$en cada posible ruta hacia el final del programa y
• ${\displaystyle S_{1}}$no necesariamente será seguido por${\displaystyle S_{2}}$, es decir, existe una ruta de ejecución desde${\displaystyle S_{1}}$hasta el final del programa que no pasa${\displaystyle S_{2}}$.

Expresadas con la ayuda de la (post)dominancia, las dos condiciones son equivalentes a

• ${\displaystyle S_{2}}$La post-domina todo${\displaystyle S_{i}}$
• ${\displaystyle S_{2}}$no postdomina${\displaystyle S_{1}}$

Las dependencias de control son esencialmente la frontera de dominancia en el grafo inverso del grafo de flujo de control (GFC). ^{[ 1 ]} Por lo tanto, una forma de construirlas sería construir la frontera de post-dominancia del GFC y luego invertirla para obtener un grafo de dependencia de control.

A continuación se presenta un pseudocódigo para construir la frontera de post-dominancia:

Para cada X en un recorrido ascendente del árbol postdominador, haga lo siguiente : PostDominanceFrontier(X) ← ∅ para cada Y ∈ Predecesores(X) hacer : si Postdominador inmediato(Y) ≠ X: entonces PostfronteraDominancia(X) ← PostfronteraDominancia(X) ∪ {Y} hecho para cada Z ∈ Hijos(X) hacer : para cada Y ∈ PostfronteraDominancia(Z) hacer : si Postdominador inmediato(Y) ≠ X: entonces PostfronteraDominancia(X) ← PostfronteraDominancia(X) ∪ {Y} hecho hecho hecho hecho

Aquí, Children(X) es el conjunto de nodos en la CFG que son inmediatamente postdominados por X , y Predecessors(X) es el conjunto de nodos en la CFG que preceden directamente a X en la CFG. Cabe destacar que el nodo X se procesará solo después de que todos sus Hijos hayan sido procesados. Una vez calculado el mapa de frontera de postdominancia, al invertirlo se obtendrá un mapa de los nodos en la CFG a los nodos que tienen una dependencia de control sobre ellos.

• Análisis de dependencia
• dependencia de datos
• Análisis de dependencia de bucle § Dependencia de control